Достаточно эффективный алгоритм обхода графа

Question

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

Вам предоставляется сеть узлов, связанных путями. Каждый путь имеет расстояние и ноль или более элементов вдоль пути, которые могут быть собраны только один раз каждые пять минут. Сбор этих элементов увеличивает ваш счет.

Цель состоит в том, чтобы спланировать следующие пять минут обхода пути с учетом путей, которые были пройдены уже за последние пять минут, чтобы максимизировать увеличение оценки.

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

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

Есть ли известный алгоритм, который решает эту проблему более эффективно, чем метод грубой силы? Даже если он только находит приблизительное решение, а не оптимальное.

РЕДАКТИРОВАТЬ

Спасибо @SaiBot, вот мое окончательное решение, на случай, если кто-нибудь когда-нибудь задаст себе такой же вопрос:

Я назначил каждому пути, идущему от узла A к узлу B, уникальный идентификатор. Путь от B до A имел свой собственный идентификатор. Вне функции поиска в DFS, но доступной для нее, я хеш-код держал под идентификатором, и значение состояло как из пройденного расстояния до перехода по этому пути, так и из размера вознаграждения, полученного до сих пор. Чтобы свести к минимуму дополнительную работу, я позаботился о том, чтобы на каждом узле исходящие пути сортировались от кратчайшего до самого длинного. Затем, когда алгоритму DFS было предложено оценить путь, который он оценил ранее, первое, что он проверяет, - это кэшированный результат. Если кешированный результат прибыл с:

( reward <= previous_reward && distance >= previous_distance )
|| reward / distance <= previous_score

Тогда есть основания полагать, что повторение этого пути не принесет никакой пользы, поэтому он немедленно возвращается со счетом 0, чтобы немедленно отстранить его от рассмотрения. В противном случае он записывает новое входящее вознаграждение, расстояние и счет в кэш и работает нормально.

Кроме того, я сделал еще одну вещь. Я рассуждал, что мне нужно определенное количество новизны на пути, то есть я не хотел, чтобы он просто нашел один крошечный маленький путь, который получил бы максимальное вознаграждение, я хотел, чтобы он исследовал карту. Поэтому я добавил фильтр к исходящим узлам, говоря, что если узел был посещен за последние X минут, уберите его из рассмотрения. Это имело побочный эффект, позволяя алгоритму направлять себя в угол, поэтому я добавил запасной вариант, при котором, если бы не было доступных опций, он сортировал бы исходящие пути по последним посещенным, самым старым первым и попытался в этом. порядок.

Результат был приличным, но я собираюсь провести еще несколько экспериментов, чтобы увидеть, смогу ли я получить еще лучшие результаты.

Answer 1

Ваша проблема тесно связана с вычислением парето-оптимального пути в многокритериальных сетях, например, как описано в этой статье.

Если у вас есть только один критерий (например, расстояние), связанный с каждым ребром, то Dijkstra позволяет вам быстро найти все возможные пути (оптимизируя расстояние). Это возможно, поскольку вы можете "отбросить" путь, который прибывает в узел, если другой путь, достигающий этого узла, уже имеет меньшее расстояние.

Проблема возникает, когда у вас есть два или более критерия (например, расстояние и вознаграждение), связанных с каждым ребром. Теперь, если два пути (начиная с вашего начального узла) ведут к одному и тому же узлу, а path_1 имеет меньшее расстояние, чем path_2, но path_2 имеет более высокое вознаграждение, чем path_1, вы также не можете отказаться от него. Однако, если оба критерия пути хуже, чем в другом пути, вы можете отказаться от него.

Один из возможных алгоритмов для полного поиска описан в статье выше.

редактировать

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