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

Question

[alex_ak1]

Есть карта (квадратная сетка) с препятствиями и точками, которые надо посетить. Герой ходит на 1 клетку, но имеет в кармане магический свиток (N штук), который перенесет его не на соседнюю клетку, а на расстояние до 8 клеток сквозь препятствия.
Как посчитать минимальный по расстоянию маршрут в таком виде?
Если нет этих свитков, то все просто - считаем расстояние от героя до каждого предмета (волной). Потом от каждого предмета до всех остальных предметов, строим таблицу расстояний и в рекурсии перебираем, ища минимум.
Но свитки все портят, я никак не могу придумать, как это лучше сделать (вернее вообще как сделать).
Из мыслей - проводить волновым алгоритмом с учетом возможных телепортаций, и для каждого расстояния строить не 1 число, а от 0 до N чисел (от не дошли, до дошли за такое время,используя k телепортаций). Получается не двумерная, а трехмерная таблица, в которой уже в рекурсии ищем минимум времени. Но по моему я как-то не то придумываю.
Помогите придумать алгоритм :)
Спасибо

Comments

[Wataru]

Ограничения бы очень помогли. Насколько большие числа?

[alex_ak1]

Wataru, Ну предположим маленькие. Карта невелика (10-50 клеток), предметов тоже ну пусть 10 и магий тоже около 10. ТО есть полный перебор осуществим за приемлемое время даже при O! сложности

[Adamos]

alex_ak1, ну, то есть в полный перебор включаются дополнительные ребра магически достижимых точек при условии, что магия не была использована до этой точки N раз.
Теория графов на изменчивости пути по ходу движения ломается, насколько я понимаю.

[alex_ak1]

Adamos, Я вижу это так в таком случае - в рекурсии получаем на вход путь и количество оставшихся свитков и пытаемся обойти не i предмет (в 1д цикле), а i предмет и k прыжков (в 2д цикле). Идем до конца (или отбрасываем по разным параметрам ответы) и собственно ищем решение

[Adamos]

alex_ak1, ну да, только рекурсию для полных переборов лучше не делать функционально (многовато вызовов). Развернуть в цикле со счетчиком уровня.

[alex_ak1]

Adamos, ну тут количество уровней ограничено кол_предметов*кол_свитков, а за счет отброса и еще меньше. Как по мне - приемлемо

Answer 1

[CBET_TbMbI]

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

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

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

Comments

[alex_ak1]

Свиток одноразовый и двигает на максимум 8 клеток по обеим осям. Разницы между свитками нет.
Про ии - это курсовик для школы. Не думаю, победа такого ИИ будет... Важна :)))
Не понял, зачем у вас строятся графы. Это же просто табличка ожидается, что если из узла j мы идем в остальные узлы (строки) с помощью k прыжков (столбцы) то доходим за столько то.

[CBET_TbMbI]

alex_ak1, каждый полученный граф является отдельной задачей, в которой надо найти оптимальный путь (по сути это ваша начальная задача без свитков).
Оптимальный путь для графа без свитков может отличаться от оптимального пути графа с применением свитка в одном месте и может отличаться от оптимального пути, где свиток применён в другом месте.

[alex_ak1]

То есть это поиск от ЭТОГО предмета (или старта) до всех остальных?
Я тут вижу так - волновой алгоритм, но карта не плоская, а несколько слоев (несколько свитков) и каждый прыжок поднимает уровень волнового алгоритма. В результате на каждый остальной предмет будет столбец расстояний с использованием от 0 до N свитков

[alex_ak1]

CBET_TbMbI, И из этих столбцов строится слой для итоговой 3д-матрицы, по которой будет ходить рекурсия. Вот.

[CBET_TbMbI]

alex_ak1, волновой алгоритм может найти только один путь. По сути это первый пункт моего списка.
У вас же задача коммивояжёра? Это отдельная задача, где волновым можно решить только часть её - а именно, найти прохождение одного ребра графа.

[alex_ak1]

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

[CBET_TbMbI]

alex_ak1, да, он ищет пути от одной до всех (например, от А до Б и от А до В), но не ищет остальные пути (чтобы найти путь от Б до В его придётся запустить ещё раз), и не отвечает на вопрос в какой последовательности обходить точки, чтобы суммарный путь был минимальной.

[alex_ak1]

CBET_TbMbI, Ну да. Мы ищем одним проходом пути от А до Б, до В, до Г.
Потом вторым проходом от Б до А (ну за компанию), до В и до Г. И так для всех.
Таким образом мы строим матрицу путей от всех до всех (в том числе с использованием свитков). А уже потом по этой матрице ищем самый короткий путь

[CBET_TbMbI]

alex_ak1, вот эту матрицу я и называю графом. Внося в неё свитки матрица/граф меняется. Даже с одним свитком вариантов несколько, в зависимости от того, в каком пути его применить. И чтобы гарантировано найти минимум, надёжнее всего рассмотреть все матрицы/графы. В каждой найти свой минимум, а потом найти минимум среди минимумов

Вопрос сводится к тому, как перебрать их все. Это уже творческий вопрос, допускающий несколько решений. Я дал лишь один из возможных вариантов - последавательно найти сначала все возможные матрицы/графы, а потом уже выбирать из них. На мой субъективный вкус он самый понятный и надёжный, но он почти наверняка не самый оптимальный по скорости счёта.

[alex_ak1]

CBET_TbMbI, У меня матрица получается в 3д. 2д матрица это без свитков. А 3д возникает из-за них как раз.
В общем я примерно понял алгоритм :)
Спасибо за помощь!

Answer 2

[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 - количество интересных точек.

Comments

[alex_ak1]

Сложно как-то. Надо думать, как этот граф работает :)

[Wataru]

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