Какой выбрать алгоритм для решения задачи?

Question

[Артем]

Есть задача:
Множество городов, обслуживаемых фирмой X, представлено графом, вершины которого соответствуют городам, а ребра – соединяющим их маршрутам, при этом длина ребра определяет расстояние между городами. Каждому городу соответствует целое число – количество контрактов, которые могут быть заключены в этом городе. Определить маршрут, которым должен двигаться коммивояжер так, чтобы заключить максимально возможное число контрактов. Подразумевается, что запаса топлива в машине коммивояжера хватит только на ограниченный маршрут. Решение должно быть визуализировано.
Вопрос: какой алгоритм стоит тут применить?

Answer 1

[Алексей Кулаков]

Так вроде это классическая задача коммивояжера. В википедии описаны алгоритмы решения этой задачи. Проанализируй все и выбери оптимальный.

Comments

[Mrrl]

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

Answer 2

[Mrrl]

Если есть память N*2^N, где N - число городов, то можно воспользоваться динамикой по набору пройденных городов плюс последнему городу, где оказался коммивояжер. Для каждого такого сочетания запоминаем минимальное количество топлива, которое потребовалось, чтобы добраться до этой ситуации и город, из которого приехали в последний город. Потом для всех ситуаций проезжаем из последнего города по всем рёбрам, и попадаем в ситуации, где посещённых городов на 1 больше. Снова для каждой находим оптимальный (по топливу) путь, по которому мы туда попали... и так, пока топливо не кончится. После чего проходимся по всему списку, и смотрим, где больше собрано призов.
До 20-25 городов должно работать разумное время. Дальше придётся искать эвристики.