@alex_ak1

Как решить задачу комивояжера с магией?

Есть карта (квадратная сетка) с препятствиями и точками, которые надо посетить. Герой ходит на 1 клетку, но имеет в кармане магический свиток (N штук), который перенесет его не на соседнюю клетку, а на расстояние до 8 клеток сквозь препятствия.
Как посчитать минимальный по расстоянию маршрут в таком виде?
Если нет этих свитков, то все просто - считаем расстояние от героя до каждого предмета (волной). Потом от каждого предмета до всех остальных предметов, строим таблицу расстояний и в рекурсии перебираем, ища минимум.
Но свитки все портят, я никак не могу придумать, как это лучше сделать (вернее вообще как сделать).
Из мыслей - проводить волновым алгоритмом с учетом возможных телепортаций, и для каждого расстояния строить не 1 число, а от 0 до N чисел (от не дошли, до дошли за такое время,используя k телепортаций). Получается не двумерная, а трехмерная таблица, в которой уже в рекурсии ищем минимум времени. Но по моему я как-то не то придумываю.
Помогите придумать алгоритм :)
Спасибо
  • Вопрос задан
  • 155 просмотров
Пригласить эксперта
Ответы на вопрос 2
@CBET_TbMbI
Не совсем понятен принцип свитков. Каждый свиток одноразовый даже если использован на на всю силу? Буду исходить из этого.
Думал бы я примерно так (полный перебор):
1. Рассматривать только имеющиеся в инвентаре свитки. Нет смысла перебирать все возможные варианты.
2. Определить возможное сокращение каждого пути с каждым из свитков. Получится несколько цифр (по количеству типов свитков) для каждого из путей. Это сама по себе не простая задача, т.к. для каждого пути и каждого свитка придётся перебирать варианты, выбирая оптимум для пары путь-свиток.
3 (опционально). Если в следующих пунктах будут проблемы с быстротой счёта, то нужно отобрать только те сокращённые пути, которые максимально отличаются от исходных по длине.
4. Составить все возможные графы из комбинаций путей/сокращённых путей. Их может быть очень много. Сократить тут особо не вижу как - как не крути, нужен перебор всех вариантов (можно с учётом пункта 3 для упрощения, но это риск пропустить оптимум, особенно если есть много слабых свитков). Тут надо не забывать, что свитков ограниченное количество - не имеет смысла рассматривать графы с таким количеством сокращённых путей, на которые не хватит свитков. Кстати, если типов свитков будет меньше, то будет проще.
5. Для каждого из полученных графов решить свою задачу коммивояжёра и выбрать лучший вариант из них.
Примечание: этот вариант не рассматривает использование нескольких свитков на одном пути. Если это надо, то придётся включить во все пункты дополнительное усложнение.

Можно придумать краткий перебор, но он может пропустить оптимум. Зато расчётов намного меньше.
Заочно начать назначать свитки, начиная с самого мощного.
1 (как и в полном переборе). Определить возможное сокращение каждого пути с каждым из свитков. Получится несколько цифр для каждого из путей.
2. Самый мощный заочно отдаётся пути, в котором возможно максимальное сокращение пути.
3. Второй свиток так же отдаётся самому большому сокращению (включая уже сокращённый).
4. И так далее пока все свитки или пути не кончатся.
5. В итоге останется только один граф из путей и сокращённых путей, которые будет или оптимальным или не очень далёким от него. Для него и решаем задачу коммивояжёра.
Примечание: из плюсов то, что в него автоматом встраивается вариант с несколькими свитками за 1 путь.

П.С. Надо ещё понять, насколько нужно оптимальное решение.
Если оно для ИИ-противников, то не будет ли с такими безошибочными ИИ слишком сложно играть?
А для игрока и вовсе интересней ставить задачи, в которых он на основе своего личного скила может оптимизировать пути. Идеальный автопилот может только убить интерес к игре. Разве что такой автопилот будет редким бонусом.
Ответ написан
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Если свитков и точек интереса немного, то можно решать обходом в ширину на расширенном графе.

Вершина в новом графе характеризуется четверкой чисел: (m, x, y, k) - m - маска уже посещенных интересных точек, x, y - координаты клетки, k - сколько свитков осталось. Ребра в графе хранить не надо, а стоит их рассчитывать на лету. Всегда можно пойти в 4 соседние стороны. При этом x, y, пересчитываются, k не меняется. Маска m получает новый бит, если конечная точка - одна из интересных (через битовое or. Если бит уже был установлен, он не меняется). Если k>0 - то можно телепортироваться. Перебирайте все x', y' в пределах 8 клеток от изначальной. Маска m получает новый бит, если конечная точка интересная. k уменьшается на 1.

Вот по этим четверкам с заданными ребрами запускайте обход в ширину из точки (0, x_start, y_start, N). Как только доходите до точки с маской включающей все интересные точки - вы нашли кратчайший путь.

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

Это будет за O(W^2*H^2*N*2^M), если W,H - размеры поля, N - количество свиков, M - количество интересных точек.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы