Коммивояжер - решение алгоритмом муравьёв

В этом видео я реализую алгоритм описаной в Exponenta Pro - Математика в приложениях №4(4)/2003 в статье «Муравьиные алгоритмы» автора С.Д. Штовба.
Реализация на языке C++ с некоторыми изменениями.

[@AndersonSilva-dg4mg]

О круто, новое полезное видео, спасибо Владимир, продолжайте пожалуйста дальше, очень нужно

[@VladimirMozhenkov]

Буду стараться )))

[@javagraf2753]

Володя, давай больше высшей математики пожалуйста !!!

[@MAKSIM24251]

Здравствуйте! А можно исходники кода? Очень нужны

[@jroslovemonro]

Добрый день! Скажите, пожалуйста, будут ли практические занятия на подобия 23 февраля?

[@DenorJanes]

Могли бы вы залить код на гит?

[@user-iq9sp1fr5i]

Будьте добры, расскажите, что находится в Path.cpp, на видео, он лишь на пару секунд показался

[@user-tu5wj6jw4e]

может не в тему, но хотелось бы посмотреть урок по dll хукам (ну например у нас в приложении есть пустая функция, которая возвращает строку, нужно ее перехватить и вернуть текущее время на компьютере)

[@user-uw7tc4ke7p]

Почему нет исходников кода?

[@user-ye8zh3ep7m]

А где пример кода?

[@user-is9lr5lz4w]

Володя, вам не обидно, когда вас называют тем, кого нет, точнее Иисусом. Ну не похож даже, близко. Ну и с нетерпением ждем роликов, всегда ожидается что-то необычное и всегда это приходит.

[@Rayvenor]

Если задачу минимизации обхода нельзя разделить на более простые, то будет ли различно решение двух разных задач - 1. Обход графа с фиксированного старта и 2. Обход того же графа с того же старта с возвращением на старт? Т.е. можно ли задачу с возвращением на старт разбить на две - обход без возвращения и поиск кратчайшего пути с финиша (найденного предыдущим решением) на старт? Можно ли как-то просто оценить граф и понять, что эти задачи решаются разным порядком обхода или для этого графа задача с возвращением разбиваема на две?

[@VladimirMozhenkov]

В самом конце вы задали на самом деле очень интересный вопрос. Это вопрос называется "Проблема остановки". То есть "Можно-ли взять какой-то алгоритм, проанализировать его, и выдать ответ на вопрос 'Выдаст-ли этот алгоритм ответ вообще или нет?'?" Ответ: Вы не можете гарантировать этого. Дело в том, что разбить у вас получится (это просто переменные в коде), но приблизитесь-ли вы при этом к ответу? Теперь про первые вопросы: Фактически это и происходит. Ведь ваш алгоритм нахождения пути обратно к старту может быть алгоритмом муравьёв, и тогда вопрос, а зачем разделять-то... если мы всё равно одно и тоже делаем. К тому-же любой другой алгоритм, который вы придумаете, должен будет унаследовать вектор Табу от предыдущего и активно им пользоваться (иначе вы посетите некоторые города дважды, а некоторые не посетите вообще), а большинство других алгоритмов просто не рассчитаны на посещение промежуточных точек.

[@Rayvenor]

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

[@VladimirMozhenkov]

Вы не сможете использовать алгоритм нахождения пути "как чёрный ящик". Он вас поведёт по уже посещённым узлам или не посетит те, которые надо было посетить.

[@Rayvenor]

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

[@Rayvenor]

Посмотрел ваши ролики по другим алгоритмам и у меня сложилось впечатление, что в моём случае используется алгоритм Флойда. При том, что заранее он не прогонялся по всем узлам, а отрабатывает с нуля при каждом обращении.

[@phat80]

Володя, просто интересно. Как твоя жена или девушка относится к бороде? Не мешает ли она вообще в общении с противоположным полом? И по какой причине вообще отращиваешь? Стиль или лень?

[@Eugene.Gubanov]

Привет, Володя! Писал тебе на почту по поводу заказа видео - не отвечаешь. :(

[@user-ue7ey9wh1j]

Я не математик, но очень интересно. Подскажите ваш метод получается из последних слов не доказуем? Рас вы говорите что можно только надеяться, что решение будет хорошим? Но не быстрым? 😄

[@crowleyrskraine6300]

Задача коммивояжера вообще быстро не решается, когда N это очень большое целое число.

[@user-ue7ey9wh1j]

@@crowleyrskraine6300 это примерно тоже самое что и количество вариантов перетасовки карт. Число в степени равным количеству переменных. 😄😄😄

[@PAKRULIN]

Алгоритм муравев был первым который я увидел на этом канале.

[@denjikminion6307]

Поиск в ширину или в глубину называется то,что ты описываешь

[@VladimirMozhenkov]

Нет. Это *совершенно* другие вещи. Вы не можете даже попытаться решить задачу коммивояжера обходом. Это NP задача, она в том-же классе что и шахматы к примеру. Попробуйте найти решение шахматной комбинации обходом, вам жизни всей вселенной не хватит.

[@crowleyrskraine6300]

Как называется компилятор из видео?

[@ashotvantsyan9028]

g++, с IDE сложно, но что то линкуксовое.

[@crowleyrskraine6300]

@@ashotvantsyan9028 Джини IDE называется. Спасибо

[@zokirshukurov3944]

sochizga klass

[@Eugene.Gubanov]

Редко видео стали выходить. :(

[@ivanpavlenko64]

Евгений Губанов можно же заказывать

[@Eugene.Gubanov]

Знаю. Сам заказывал много раз. Но пока новых идей нет. Вся надежда на автора канала. :)

[@user-ff3rp9ch5w]

Переводят в структуры их поселения ! Марина Первомайская!и по банкам !

[@user-vo4yc6th4m]

почему я здесь?

[@VladimirMozhenkov]

потому что место где вы находитесь называется "здесь", все остальные места называются "там". если вы пойдёте "туда", то "там" станет "здесь", а "здесь" превратится в "там". так что вы всегда будете именно "здесь". я рад, что мог вам помочь разобраться в этом лингвистическом вопросе.

[@heisenborg_programming]

C каждым видео у вас лицо темнее и темнее))

[@default6508]

На яваскрипте слабо?)

[@roma.bantikov]

не интересно, Валера.