Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 13
То есть каждый из параллельных потоков решает ограниченное число случайных задач, выбирает оптимальное из решений, а после выбирается оптимальный из результатов всех потоков? Как-то это слишком случайно.
Если уж не удается метод ветвей и границ параллелить (алгоритмы распараллеливания искали?), может быть попробовать полностью просчитывать дерево решений? Пусть каждый поток рассчитывает свою ветку. Полный перебор фактически будет, зато он действительно полный и параллельный заодно.
Если уж не удается метод ветвей и границ параллелить (алгоритмы распараллеливания искали?), может быть попробовать полностью просчитывать дерево решений? Пусть каждый поток рассчитывает свою ветку. Полный перебор фактически будет, зато он действительно полный и параллельный заодно.
Да, я прекрасно понимаю, что работоспособность алгоритма на самом-то деле держится чуть ли не на «честном слове», но, опять же, как показывают результаты, он умудряется выдавать даже разумные результаты, а не совсем абы что. Собственно говоря, он в полной мере соответствует понятию «эвристический алгоритм».
Недостаток метода ветвей и границ в том, что он даже в последовательной реализации довольно мерзкий и сложный. Как его паралелить — тоже вопрос. Но в конечном итоге все упирается в то, что реализовывать эту штуку надо было с использованием технологий, с которыми я ранее не работал, и если Windows Azure — это по сути тот же C#, то остальные три уже представляли собой неслабый challenge, а потому хотелось использовать что-то максимально простое в реализации. Для начала была идея использовать алгоритм муравьиной колонии, но потом пришла в голову эта идея, я ее и реализовал. У меня всегда была слабость к решениям пусть не оптимальным, но зато самостоятельно придуманным.
Алгоритм, разумеется, не претендует на какие-либо лавры и прочая, но чтобы сдать задачу преподавателю его хватило. Эту статью же я написал как некий ответ на пост «Введение в оптимизацию. Имитация отжига», так как там и в самой посте, и в комментариях к нему велись обсуждения вопроса «а если менять два города местами — что будет?». Решил, что раз уж у меня есть именно такая реализация и даже некое исследование к ней, то будет неплохо ее запостить на всеобщее обозрение.
Недостаток метода ветвей и границ в том, что он даже в последовательной реализации довольно мерзкий и сложный. Как его паралелить — тоже вопрос. Но в конечном итоге все упирается в то, что реализовывать эту штуку надо было с использованием технологий, с которыми я ранее не работал, и если Windows Azure — это по сути тот же C#, то остальные три уже представляли собой неслабый challenge, а потому хотелось использовать что-то максимально простое в реализации. Для начала была идея использовать алгоритм муравьиной колонии, но потом пришла в голову эта идея, я ее и реализовал. У меня всегда была слабость к решениям пусть не оптимальным, но зато самостоятельно придуманным.
Алгоритм, разумеется, не претендует на какие-либо лавры и прочая, но чтобы сдать задачу преподавателю его хватило. Эту статью же я написал как некий ответ на пост «Введение в оптимизацию. Имитация отжига», так как там и в самой посте, и в комментариях к нему велись обсуждения вопроса «а если менять два города местами — что будет?». Решил, что раз уж у меня есть именно такая реализация и даже некое исследование к ней, то будет неплохо ее запостить на всеобщее обозрение.
Скажите, а в каком вузе вам поставили такие интересные требования к задаче?
У вас отличный преподаватель! *Ошибся веткой…
Я как то решал эту задачу для мобил. Есть много имплементаций метода ветвей и границ, вот тут например есть пдф-ки, которые я тогда нарыл. В итоге я решил задачу методом Литтла, вот ссылка на его оригинальную рабору. Если вы погуглите, то найдете много чего интерсного, например вот этот репозиторий. В своем решении я использовал реализацию 1972 года, которую нарыл в архиве. Клевость именно этой реализации была в том, что там не использовалось ни единого обьекта, все было сделано на массивах. Работало ну очень резво даже в эмуляторе.
В Вашей реализации нет собственно «отжига».
Есть «велосипед» в некоторых источниках, называющийся методом монотонного спуска (ММС).
Привет ЛЭТИ! (я там аспиранствовал)
Есть «велосипед» в некоторых источниках, называющийся методом монотонного спуска (ММС).
Привет ЛЭТИ! (я там аспиранствовал)
Не соглашусь с Вами. Да, в моем алгоритме нет «отжига» как такового (хотя «легким движением руки» его можно соответствующим образом в оный превратить: добавить температуру и переход из одного состояния в другое осуществлять также на вероятностной основе), но тем не менее этот алгоритм гораздо ближе к отжигу, чем к ММС (по крайней мере по той причине, что ММС — это детерминированный алгоритм). Поправьте если я неправ.
Ага. Теперь название понятнее.
Т.е. Вы изобретали, но еще не изобрели.
Когда изобретете — обязательно напишИте.
Буду ждать.
Да, статья Вас вдохновившая, мне тоже понравилась.
Не до вершин написания поста, но до «поиграть».
Ваша статья, зато, «сподвигла» меня продолжить дискуссию про оптимизацию.
За что Вам отдельное спасибо!
Ну успехов Вам.
Т.е. Вы изобретали, но еще не изобрели.
Когда изобретете — обязательно напишИте.
Буду ждать.
Да, статья Вас вдохновившая, мне тоже понравилась.
Не до вершин написания поста, но до «поиграть».
Ваша статья, зато, «сподвигла» меня продолжить дискуссию про оптимизацию.
За что Вам отдельное спасибо!
Ну успехов Вам.
Если я все правильно понял — то ваша задача найти наикротчайший путь из точки А в точку Б.
Алгоритм Дейкстры вам совсем не знаком?
«Достоинства метода» — уж простите, не вижу ни одного достоинства вашей придумки.
Поправте если не верно трактовал вашу первоначальную задачую.
Алгоритм Дейкстры вам совсем не знаком?
«Достоинства метода» — уж простите, не вижу ни одного достоинства вашей придумки.
Поправте если не верно трактовал вашу первоначальную задачую.
Да, Вы неверно поняли задачу. Алгоритм Дейкстры находит длину кратчайшего пути из пункта А в пункт Б, при этом этот путь может быть самим ребром, соединяющим эти вершины, а путь коммивояжера должен проходить через каждую вершину графа, притом ровно по одному разу, а после этого возвращаться в начальную вершину. Алгоритм Дейкстры, к тому же, находит только расстояния между вершинами (есть, вроде, вариации алгоритма Дейкстры, которые как-то еще и путь находят, но с такими я и правда не знаком), а в моей задаче важен именно путь (последовательность вершин), по которому должен пройти коммивояжер.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Как я изобретал метод имитации отжига