В лабе требуется найти решение задачи коммивояжера несколькими способами. Сделал все способы кроме полного перебора. Как его реализовать?
Примечание:
Ты просто гениален! Я думал об этом же. Но как это реализовать даже не представляю!
Примечание:
Напиши что-нибудь в духе краткого описания алгоритма, пожалуйста!
Примечание:
Так, ладно, организовал сам. Все таки сессия близко.
Как это сделал я, способ очень удобный для программирования:
У меня есть 7 городов (занумерованы 1,2...7)
Делаем вектор :1,1,1,1,1,1,1 (длины 7)
Есть матрица m[7][7] (по диагонали можно поставить нули) [стоимость переезда из i-ого города в j-ый]
ставим начальную стоимость пути - у меня максимальное double число
в цикле:
пока не все перебрали, проверяем подходит ли вектор (т.е. все v[i] - различны, первый вектор, очевидно, не подходит). Если не подходим - генерим новый и продолжаем цикл, если подходит высчитываем стоимость пути, и если, вдруг, она стала меньше предыдущей стоимости - запоминаем маршрут и стоимость.
в конце у нас будет маршрут с минимальной стоимостью
Чем плох этот алгоритм: для больших маршрутов будет считаться очень долго (дольше чем "обычный" перебор), так же, скорее всего, будет не корректно работать для задач, когда есть ограничения на перемещения ( у меня предполагается, что можно попасть из каждого города в каждый!)
для 7ми городов вполне подходит и такой метод :)
RPI.su - самая большая русскоязычная база вопросов и ответов. Наш проект был реализован как продолжение популярного сервиса otvety.google.ru, который был закрыт и удален 30 апреля 2015 года. Мы решили воскресить полезный сервис Ответы Гугл, чтобы любой человек смог публично узнать ответ на свой вопрос у интернет сообщества.
Все вопросы, добавленные на сайт ответов Google, мы скопировали и сохранили здесь. Имена старых пользователей также отображены в том виде, в котором они существовали ранее. Только нужно заново пройти регистрацию, чтобы иметь возможность задавать вопросы, или отвечать другим.
Чтобы связаться с нами по любому вопросу О САЙТЕ (реклама, сотрудничество, отзыв о сервисе), пишите на почту [email protected]. Только все общие вопросы размещайте на сайте, на них ответ по почте не предоставляется.