Я хочу найти недорогой путь между двумя вершинами на ориентированном графе, где стоимость каждого ребра одинакова. Простота реализации алгоритма и время выполнения очень важны, поэтому я готов пожертвовать оптимальным решением для почти оптимального, если алгоритм проще и быстрее.Алгоритм поиска графа, где ребра могут быть заблокированы препятствиями
Кромку можно заблокировать препятствием. Вероятность блокировки края заранее известна. Блокировки не зависят друг от друга. Обнаружено, что ребро разблокировано или заблокировано, когда вершина на вершине края достигнута.
Моя проблема аналогична канадской проблеме путешественников, но я понимаю, что решения для задач стохастического программирования относительно сложно реализовать, и время, затрачиваемое на поиск оптимальной политики, может быть относительно высоким.
На данный момент я собираюсь преобразовать проблему в детерминированную, чтобы ее можно было решить с помощью алгоритма поиска, такого как A *. Это хороший подход, и если да, то как я могу это сделать?
Какая разница между «заблокированный край» и без края? – angelatlarge
@angelatlarge Вероятность. No edge == заблокированный край со 100% уверенностью – SomeWittyUsername
Я думал о том, что край заблокирован препятствием (которое я теперь добавил к формулировке) и делаю край необратимым, что, по-моему, похоже на то, что нет никакого края. – Amos