Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

Как я изобретал способ имитации отжига

Anna | 17.06.2014 | нет комментариев
Добродушного времени, Прогр!

Сподвигло меня на написание этой работы прочтение «Вступление в оптимизацию. Имитация отжига». Так уж сложилось, что как раз незадолго я столкнулся с задачей коммивояжера и для ее решения придумал алгорифм, суть которого, как оказалось, дюже близка к идее алгорифма имитации отжига, описываемого в указанной статье. Больше того, там даже есть «отсылка» к моей идее, а еще схожие обсуждения велись в комментариях, потому я решил, что сообществу будет увлекательно посмотреть на реализацию.

Начну с маленький вводной. Я студент 1-го курса магистратуры на специальности «Программная инженерия», и в этом семестре у нас был курс распределенных систем, в котором мне досталась на реализацию задача коммивояжера. Причем хорошо бы так, но еще и с требованием реализовать ее параллельно и с применением четырех различных спецтехнологий (Windows Azure, библиотека openmpi, язык программирования Go, язык программирования Limbo в OS Inferno). Натолкнись я тогда на настоль высококачественно описанный вариант решения, задач было бы значительно поменьше, но на тот момент я смог найти только способ ветвей и границ. Гнусная штука нужно сказать, потому идея реализовывать его параллельно, да к тому же с применением незнакомых ранее спецтехнологий сразу показалась мне неудачной. В итоге длинных обдумываний данной задачи я пришел к алгорифму, тот, что оказался на изумление простым, правда и не дюже результативным. Тем не менее, я его смог сдать преподавателю, а проведенная «исследовательская» работа над алгорифмом, как оказалось, абсолютно сгодится для данной статьи. Разве что для статьи я приведу программный код на чистом C# и без применения параллельных заморочек.
Детально на вопросах что такое оптимизация и способ отжига я останавливаться не буду, считаю, что в статье «Вступление в оптимизацию. Имитация отжига» оно объяснено легко восхитительно, и каждому желающим разобраться подробнее я советую ее прочесть. Я же перейду сразу к изложению задачи коммивояжера и моему решению.

Обзор задачи

Задача коммивояжёра — одна из самых знаменитых задач комбинаторной оптимизации, заключающаяся в отыскании самого выигрышного маршрута, проходящего через указанные города по одному разу с дальнейшим возвратом в начальный город. В условиях задачи указываются критерий выгодности маршрута (кратчайший, самый дешёвый, комплексный критерий и тому сходственное).
Если формализовать задачу, то речь идет некоем взвешенном графе (простоты обсуждений ради положим его неориентированным, правда в всеобщем случае это может быть не так), в котором требуется обнаружить путь обхода, проходящий через все вершины ровно по одному разу и возвращающийся в исходную точку, при этом малейшего веса (для дальнейших рассуждений буду называть вершины графа городами, а вес ребра — расстоянием между городами).

Такой граф дозволено изобразить в виде симметричной матрицы с нулями на основной диагонали (длина пути из города в него самого равно нулю).

Алгорифм решения

В этой части я опишу оба метода реализации алгорифма (последовательную и параллельную), и приведу программный код для последовательного варианта.

Последовательная реализация
Сотворим произвольный первоначальный путь, содержащий все вершины по одному разу и возвращающийся в исходную позицию. После этого случайным образом будем менять местами два города и сопоставлять длины ветхого и нового путей. Если новейший путь оказался короче, сберегаем его. Если нет, то наращиваем счетчик. Когда счетчик примет предварительно заданное значение, останавливаем алгорифм, конечный обнаруженный таким образом путь будет считаться наилучшим.

Параллельная реализация
Сделаем произвольный исходный путь, содержащий все вершины по одному разу и возвращающийся в исходную позицию и «раздадим» его всякому из параллельно работающих процессов/потоков. Всякий из них, самостоятельно друг от друга, изготавливает описанные операции по поиску оптимального пути и возвращает обнаруженный итог. Главк зависимости P(K) для p = 0,1 («де юре» график должен быть дискретным, но я верю вы мне извините такую вольность):

Дозволено видеть, что теснее при K = 6..7 вероятность P становится равна 0,5. То есть польза от применения нескольких процессов очевидна – дюже стремительное увеличение вероятности.
Обнаружим сейчас вероятность p для одного процесса. Видимо, она обратно пропорциональна размеру Nматрицы и прямо пропорциональна значению F, которого достигает счетчик, когда алгорифм прекращает свою работу. Больше точную оценку, к сожалению, дать фактически немыслимо. Чуть ли не исключительное, что мы можем сказать о графе – это что число различных путей равно (N-1)!

 

Источник: programmingmaster.ru

Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB