СИ - 30 лет

Евгений Машеров · 03.04.2024, 12:18

Касательно ЗК (в смысле TSP). Тут знание о постановке задачи коммивояжёра позволяет выбрать правильный ответ, даже не зная о "муравьином алгоритме". А вот если не знать постановки задачи, а только услыхать вопрос - пчёлы могут быть естественнее. Они летают по маршруту цветок-улей, и если знать только "кратчайший путь между несколькими пунктами с возвратом в исходную точку", то отвергнуть пчёл никак. А если знать, что ищется маршрут, проходящий через все пункты, не более одного раза через каждый и возвращающийся на исходную позицию" - то пчёл можно отсечь. При этом алгоритм "муравьиный" условно, первые концепции от наблюдения за термитами, потом лишь перешли к муравьям, и задача коммивояжёра не самая лучшая для метода, это просто красивая и понятная иллюстрация, успехи метода в задаче о сворачивании белков и некоторых других оптимизационных, для TSP есть куда лучшие алгоритмы.

03.04.2024, 12:18	#11
Евгений Машеров Senior Member Регистрация: 06.04.2006 Сообщения: 1,035 Поблагодарил(а): 1,798 Поблагодарили 1,005 раз(а) в 393 сообщениях	Касательно ЗК (в смысле TSP). Тут знание о постановке задачи коммивояжёра позволяет выбрать правильный ответ, даже не зная о "муравьином алгоритме". А вот если не знать постановки задачи, а только услыхать вопрос - пчёлы могут быть естественнее. Они летают по маршруту цветок-улей, и если знать только "кратчайший путь между несколькими пунктами с возвратом в исходную точку", то отвергнуть пчёл никак. А если знать, что ищется маршрут, проходящий через все пункты, не более одного раза через каждый и возвращающийся на исходную позицию" - то пчёл можно отсечь. При этом алгоритм "муравьиный" условно, первые концепции от наблюдения за термитами, потом лишь перешли к муравьям, и задача коммивояжёра не самая лучшая для метода, это просто красивая и понятная иллюстрация, успехи метода в задаче о сворачивании белков и некоторых других оптимизационных, для TSP есть куда лучшие алгоритмы.