#graph-theory #graph-algorithm #theory #path-finding #traveling-salesman
Вопрос:
Чтобы все было как можно проще, есть ли вариант TSP, в котором я пытаюсь максимизировать выгоду с ограничением на то, сколько я могу путешествовать с требованием, чтобы я вернулся домой? (Я довольно плохо разбираюсь в этих типах алгоритмов, возможно, требуется DP?)
Предположим, я могу рассчитать расстояние между каждым узлом, и каждый посещенный узел будет удален из списка.
Я думаю, что тогда это должно быть направлено (поскольку затраты могут отличаться в зависимости от направления) с соотношением затрат и выгод в качестве весов.
Любые советы будут оценены по достоинству.
Комментарии:
1. Первый совет: EAAITQ (объясните любую аббревиатуру в вопросе)
Ответ №1:
- Запустите стандартный TSP
- Если общее расстояние меньше, чем макс. СДЕЛАНО
- Запустите Dijsktra, чтобы найти расстояние от дома до каждой вершины
- Удалить вершину дальше всего от дома
- петля
Комментарии:
1. не могли бы вы, пожалуйста, дать краткое объяснение того, почему этот процесс будет работать?