Comments 17
А не проще было всё это реализовать через NumPy, чем возиться с подключением собственной библиотеки и передачей данных через строки?
Проще конечно же! Но вот быстрее ли, сомнительно. Возможно Вы сможете доказать обратное.
Да и код для библиотеки уже существовал, нужно было только обернуть функцию.
Ну вот Вам снизу написали про готовую функцию на SciPy - можно ее ради интереса сравнить по быстродействию с Вашей dll-кой, чтобы самому не морочиться с повторной реализацией алгоритма на NumPy. SciPy как раз с использованием массивов NumPy сделан. А NumPy в свою очередь использует библиотеки, написанные на Fortran и C. Так что с весьма большой долей вероятности реализация на NumPy будет или сравнима с Вашей или даже быстрее.
P.S. - ни к чему Вас не призываю, просто заметил, что серьезную математику на чистом Питоне программировать - дело не очень продуктивное.
У вас списки, в которых лежат не числа, а объекты похожие на числа. Медленнее такого уже не сочинить. Но этот код довольно просто переписать на numpy и поразиться тому, что пайтон реально быстрый.
На пайтоне так не программируют. Программируют как-то так
scipy.sparse.csgraph.shortest_path — SciPy v1.9.3 Manual
Удивительно, как вы смогли написать статью про решение задачи динамическим программированием и не сказать ни одного правильного слова про, собственно, динамическое программирование. Хоть бы статью на википедии процитировали, что ли.
И вообще вы алгоритм, как будто не поняли.
В процессе работы нам нужно хранить все возможные комбинации построенных маршрутов, а также длину минимального маршрута на данный момент.
Нет. Вообще нет. Алгоритм находит для каждого подмножества вершин кратчайший путь, начинающийся с 0 и заканчивающийся в заданной вершине. Тут 2 параметра — подмножество и последняя вершина. Это те самые подзадачи, упомянутые в википедии. И ответ на каждую такую подзадачу вы сохраняете. Поэтому вам и нужно столько памяти, чтобы все сохранить.
Оптимизация по памяти и времени достигается тем, что не надо рассматривать подзадачи, где последняя вершина 0 и также подмножества, где вершины 0 нет. Поэтому первый шаг и выделяется отдельно, ибо там считается основная задача, где вы начали с 0 и в 0 же вернулись.
Еще стоило написать, что тут рекурсивная реализация с мемоизацией.
Ну и имена переменных, конечно, ужасные. Что за m вообще? Плюс складывать разные по смыслу вещи в m[0], m[1] и m[2] и m[3] — очень усложняет чтение кода. На олимпиадах каких-нибудь это оправдано, но код в статье стоит немного причесать перед выкладыванием.
Спасибо что вы не прошли мимо! Алгоритм как раз я понял хорошо, возможно выразил не совсем академично, но благодаря Вам, всё стало гораздо яснее. А мне ещё расти над собой.
Жаль, что вы не высказались за сам подход.
В смысле — за сам подход? Алгоритм — хороший, сильно быстрее полного перебора или метода ветвей и границ. Имеет свои ограничения и сильно больше 30 вершин не потянет, ну так задача NP-полная, все алгоритмы экспоненциальные и медленные.
Огромный вам плюс в статью, что при всех небольших недочетах описания, реализация правильная.
Мне всегда казалось, что метод ветвей (кстати, не ветвлений) и границ самый простой для понимания способ решения этой задачи. И при его наличии полный перебор можно даже не упоминать, ведь он по сути и есть способ перебора.
Интересно было бы увидеть решение такси-агрегаторов.
Подождите но разве не за разработку алгоритма решения транспортной задачи Леонид Канторович получил Нобеля в 1975 году?
Когда-то я узнал о неплохой и очень быстрой аппроксимации решения задачи коммивояжера. Предлагается построить минимальное остовное дерево графа. Это делается очень быстро, буквально линейно по количеству рёбер.
А затем обходим его вокруг, как бы по периметру. Все ребра при этом будут пройдены дважды. Но можно будет срезать путь, когда следующая по плану не листовая, и мы её уже посещали. Поскольку путь коммивояжера тоже является остовным деревом, то его длина не превосходит сумму длин рёбер дерева минимального, которое в худшем случае мы обойдём дважды.
В итоге результат будет не более чем в два раза хуже оптимального.
Извините косноязычность.
Добрый день! Спасибо большое за статью, очень интересно. Знаете ли вы как расширить задачу примитивного коммивояжера до задачи коммивояжера с множеством коммивояжеров и приоритетом задач?
Задача коммивояжера (TSP) точное решение — метод динамического программирования