Для игры, в которой существует K количество координат с каждой координатой, имеющей счет, существует команда из N игроков. Цель каждого игрока - набрать как можно больше очков, минимизируя пройденное расстояние.
После того, как какой-либо игрок в команде посетил координату, он призовет ноль очков при повторном посещении.
Существует два варианта этой игры, в которых каждый игрок должен разработать правильный маршрут:
- Режим 1 (цикл), где каждый игрок должен будет вернуться к начальной точке. (0,0)
- Режим 2 (Путь), где каждый игрок начнет с (0,0) , но может закончить маршрут в любой точке
Маршрут решения - только , рассчитанный на основе общего пройденного расстояния.
Например: учитывая маршрут одного игрока [A,B,C,D] (где AD - координаты), маршрут будет оцениваться так:
- Mode 1 Score = Total euclidean distance from (0,0)->A->B->C->D->(0,0)
- Mode 2 Score = Total euclidean distance from (0,0)->A->B->C->D
В конечном счете, цель команды - минимизируйте общее расстояние, пройденное всеми N игроками, при этом гарантируя, что все игроки наберут коллектива не менее P очков.
Я предполагаю, что это может быть связано с проблемой коммивояжера. Однако, в отличие от TSP, где все узлы должны быть посещены один раз, игра требует, чтобы игроки минимизировали пройденное расстояние до тех пор, пока Score > = P .
Какой может быть хороший алгоритм для аппроксимации оптимального набора маршрутов для N игроков?