Эффективный алгоритм для решения лабиринта сбора монет - PullRequest
0 голосов
/ 29 ноября 2018

Какой наилучший алгоритм использовать для решения лабиринта, который в идеале представляет собой график, при этом собирая наибольшее количество монет за фиксированное число шагов?

У каждого ребра есть расстояние, а у каждого узла -определенное количество монет (0 - n монет)

В качестве входных данных дается общее фиксированное количество шагов, и гарантируется, что существует решение, которое решает лабиринт после этих шагов.

Спасибо

1 Ответ

0 голосов
/ 29 ноября 2018

Извините, вы не найдете эффективное решение для этой проблемы, оно NP-hard , что означает, что если вам нужно точное решение, оно будет иметь экспоненциальную сложность.Это можно показать, уменьшив проблему Рюкзак .

Предположим, у вас есть экземпляр Рюкзака с n элементами, установленными w_0 ... w_n весов и набор v_0 ..._ v_n значений и емкости W , мы можем построить график, где каждая вершина соответствует значению плюс 2 дополнительных вершины s и e для начала и конца.Создайте ребро из s для каждой вершины v_i с весом w_i / 2 , а также ребро из v_i в вершину e с соответствующим весом w_i / 2 .Теперь найдите путь от s до e , ограниченный длиной W .Этот путь не будет посещать вершину v_i более одного раза, поскольку после сбора монеты нет причин возвращаться в этот узел.Кроме того, чтобы посетить любой v_i и добраться до e , он потратит ровно w_i шагов, будь то переход от s или возвращение из e.Решение гарантирует, что предел шагов не будет превышен, а комбинация значений максимальна.Поэтому, просто выбирая все посещенные вершины v_i , мы получаем решение для оптимизационной версии рюкзака с NP-сложностью.

Теперь это не так уж и плохо.У проблемы есть решение, оно просто неэффективно.Для небольшого лабиринта он все еще может работать с использованием грубой силы, то есть начинать с вершины и пытаться идти в любом направлении рекурсивно.Если превышено максимальное количество шагов - отменить.Если доехали до места назначения - верните путь.Затем из всех возвращенных путей выберите тот, который дает максимальное количество монет.

Кроме того, если вам не нужно точное решение - вы можете попытаться дать приблизительное решение.Например, вы можете использовать алгоритм Dijkstra для создания дерева кратчайших путей.Так что теперь у вас есть кратчайший путь от источника до каждой вершины.Выберите путь от источника к месту назначения и попробуйте улучшить его итеративно.В каждой итерации выбирайте вершину на пути, просматривайте всех ее соседей и наблюдайте, как она проходит через этого соседа, дает вам лучшее значение, оставаясь при этом с ограничением шагов.Это не обязательно даст вам оптимальное решение, но, скорее всего, приведет к хорошим решениям.

И тогда вы можете попробовать другие способы оптимизации, такие как «выбрать монетку и запустить».Посмотрите на свой путь и попытайтесь улучшить его, перейдя от некоторой вершины к соседу и немедленно вернувшись.Это может быть полезно, если у вашего лабиринта тупик, так что, естественно, вы не пойдете туда, чтобы добраться до места назначения, но у вас достаточно шагов, чтобы пойти туда, собрать несколько монет и вернуться.

Надеюсь, это поможет.

...