Извините, вы не найдете эффективное решение для этой проблемы, оно 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 для создания дерева кратчайших путей.Так что теперь у вас есть кратчайший путь от источника до каждой вершины.Выберите путь от источника к месту назначения и попробуйте улучшить его итеративно.В каждой итерации выбирайте вершину на пути, просматривайте всех ее соседей и наблюдайте, как она проходит через этого соседа, дает вам лучшее значение, оставаясь при этом с ограничением шагов.Это не обязательно даст вам оптимальное решение, но, скорее всего, приведет к хорошим решениям.
И тогда вы можете попробовать другие способы оптимизации, такие как «выбрать монетку и запустить».Посмотрите на свой путь и попытайтесь улучшить его, перейдя от некоторой вершины к соседу и немедленно вернувшись.Это может быть полезно, если у вашего лабиринта тупик, так что, естественно, вы не пойдете туда, чтобы добраться до места назначения, но у вас достаточно шагов, чтобы пойти туда, собрать несколько монет и вернуться.
Надеюсь, это поможет.