Нужно решить задачу коммивояжора через выпуклые множества. Подскажите что, где посмотреть. Исходнику тоже буду рад, но лучше описание. Собственно, мне нужно эти выпуклые множества связать, а как их построить я знаю.
Здравствуйте, <Аноним>, Вы писали:
А>Нужно решить задачу коммивояжора через выпуклые множества. Подскажите что, где посмотреть. Исходнику тоже буду рад, но лучше описание. Собственно, мне нужно эти выпуклые множества связать, а как их построить я знаю.
Вопрос поверг меня в ступор.
Давайте сначала.
Множество D ( E^n называется выпуклым, если отрезок [x, y] ( D для любых x, y (- D. (E^n — линейное пространство размерности n, если память не изменяет)
Задача коммивояжера формулируется так:
дано: города, некоторые из них соединены дорогами. Для каждой дороги указана ее длина (в другой интерпритации — время, необходимое для ее преодоления). Из любого города можно добраться в любой другой по одной или нескольким дорогам. Требуется найти путь, с помощью которого можно обойти все города, пройдя минимальное расстояние (за минимальное время).
Это типичная задача теории графов, формулируется так: в заданном графе найти гамильтонов цикл минимального веса.
т.к. задача np-полная, то ее часто решают приблизительно. Самый распространенный метод — метод ветвей и границ. Слышал еще, что решают с помощью генетических алгоритмов.
Здравствуйте, xtile, Вы писали:
X>Здравствуйте, <Аноним>, Вы писали:
А>>Нужно решить задачу коммивояжора через выпуклые множества. Подскажите что, где посмотреть. Исходнику тоже буду рад, но лучше описание. Собственно, мне нужно эти выпуклые множества связать, а как их построить я знаю.
Здравствуйте, Аноним, Вы писали:
А>Нужно решить задачу коммивояжора через выпуклые множества. Подскажите что, где посмотреть. Исходнику тоже буду рад, но лучше описание. Собственно, мне нужно эти выпуклые множества связать, а как их построить я знаю.
Задача коммивояжера действительно НП-трудная, но существует множество полиномиально разрешимых случаев. Наиболее простой метод — метод Гилмора-Гомори, в котором надо, чтобы матричка расстояний удовлетворяла определенным условиям.
Этот алгоритм решает сначала задачу о размещениях, а потом соединяет частичные циклы в один большой, который и есть решение. Сложность всео алгоритма О (н лог н) и определяется сложностью сортировки массива из н элементов.
Касательно дискретных выпуклых множеств я не уверен (никогда о таких не слышал). Было бы полезно определение такого множества здесь увидеть. это бы помогло дать совет.
Неясен также вопрос какое решение нужно: оптимальное или приближенное. Если оптимальное, то какие условия на матрице расстояний выполняются (например неравенство треугольника).
Здравствуйте, xtile, Вы писали:
X>Здравствуйте, <Аноним>, Вы писали:
. . . X>т.к. Слышал еще, что решают с помощью генетических алгоритмов.
Насчет генетических алгоритмов не обольщайся. Пока учился (Таганрогский Радиотехнический Бурситет),
нас этим дерьмом пихали.
Генетические алгоритмы это плод воображения батаника переквалифицированного
в программиста. Как-то кому-то взбрело в голову что с помощью них можно решать
NP-полные задачи. Это не так, потому что он основывается на случайном решении
я даже как-то реализовал задачу комивояжера генетическим алгоритмом
могу сказать одно — не фонтан лучше опираться на метод ветвей и границ
Здравствуйте, _BOBAH_, Вы писали:
_BO>Генетические алгоритмы это плод воображения батаника переквалифицированного _BO>в программиста. Как-то кому-то взбрело в голову что с помощью них можно решать _BO>NP-полные задачи. Это не так, потому что он основывается на случайном решении _BO>я даже как-то реализовал задачу комивояжера генетическим алгоритмом _BO>могу сказать одно — не фонтан лучше опираться на метод ветвей и границ
при хорошо подобранных параметрах и нормальном кроссовере генетический алгоритм дает вполне хорошее решение, сам этим маленько занимался.
где-то слышал, что существуют где-то наборы с очень большим количеством городов (300, например) и наилучшее найденное на сегодняшний день решение для них. в какой-то статье приводилось сравнение алгоритмов на таких наборах. только вот где их взять?
Здравствуйте, bipka, Вы писали:
B>при хорошо подобранных параметрах и нормальном кроссовере генетический алгоритм дает вполне хорошее решение, сам этим маленько занимался.
B>где-то слышал, что существуют где-то наборы с очень большим количеством городов (300, например) и наилучшее найденное на сегодняшний день решение для них. в какой-то статье приводилось сравнение алгоритмов на таких наборах. только вот где их взять?
вот именно где их взять — сам много этим занимался, пробовал сам закодировать хромосомы — но что-то не очень это
дело получается, самое интересное что готовые алгоритмы, работающие как надо, на ту же самую задачу комивояжера
не находил — в теории все интересно выглядит, но если бы посмотреть на готовый, РАБОТАЮЩИЙ, вариант алгоритма, тогда
может быть и мое мнение о этих алг-ах смягчится. А пока я при своем мнении остаюсь
Здравствуйте, _BOBAH_, Вы писали:
_BO>вот именно где их взять — сам много этим занимался, пробовал сам закодировать хромосомы — но что-то не очень это
проблему там представляет не хромосомы, а кроссовер.
т.к. при кроссовере надо, с одной стороны, получить валидный маршрут (где каждый город будет один раз и будут все города), а с другой стороны унаследовать от родителей какие-то хорошие качества, т.е. участки маршрута, и при преобразовании получившегося маршрута в допустимый не сильно их испортить _BO>дело получается, самое интересное что готовые алгоритмы, работающие как надо, на ту же самую задачу комивояжера _BO>не находил — в теории все интересно выглядит, но если бы посмотреть на готовый, РАБОТАЮЩИЙ, вариант алгоритма, тогда _BO>может быть и мое мнение о этих алг-ах смягчится.
возникает вопрос, что такое хороший и работающий. работающий — сколько угодно. я на 2м курсе (2 года назад) писал курсовую на эту тему. вполне рабочий вариант получился кое-какие разработки там есть, но я их пока не публиковал и их еще разваивать и развивать. _BO>А пока я при своем мнении остаюсь
вот и возникает вопрос — как проверить, хороший ли алгоритм.
чтобы проверить, надо знать правильное решение
а знать действительно правильное решение на больших размерах не представляется возможным
сравнивать с решением, найденным методом ветвей и границ? конкретно я статистику не набирал, но думаю, будет очень неплохой результат. надо попробовать
особенно, если учитывать время работы алгоритмов — то генетический его уделает
я о том и говорю, что тогда, 2 года назад, читал в какой-то статье, что где-то есть задача городов на 300, для которой известно не лучшее, но наилучшее найденное на сегодняшний день решение. вот получить такой набор и это наилучшее решение и скормить его ген. алгоритму — вот это было бы интересно.
Здравствуйте, Аноним, Вы писали:
А>Нужно решить задачу коммивояжора через выпуклые множества. Подскажите что, где посмотреть. Исходнику тоже буду рад, но лучше описание. Собственно, мне нужно эти выпуклые множества связать, а как их построить я знаю.
Задачу Коммивояжора непосредственно мы программировали в институте по предмету вычислительная математика, но там мы её решали, если правильно помню, методом ветвей и границ. Короче вот вам сайт моего бывшего преподавателя и дипломного руководителя. www.belsky.narod.ru
Вечная ему память! Там вы найдете комплекты лекций по теории графов, а также по вычислительной математике и обработке экспериментальных данных. Могу с увереннностью сказать, что лекции супер. В вычислительной математике есть и задача, алгоритм по выпуклому программированию. Просмотрите лекции, не поленитесь, может что и найдете нужного для вас.
BS>Вечная ему память! Там вы найдете комплекты лекций по теории графов, а также по вычислительной математике и обработке экспериментальных данных. Могу с увереннностью сказать, что лекции супер. В вычислительной математике есть и задача, алгоритм по выпуклому программированию. Просмотрите лекции, не поленитесь, может что и найдете нужного для вас.
может выпуклое множество -- это то что все называют матроидом?
лучше опираться на метод ветвей и границ
кое-какие разработки там есть, но я их пока не публиковал и их еще разваивать и развивать.
