Нужна идея для алгоритма поиска звезды с несколькими целями

Question

Алгоритм поиска звезды с указанной целью довольно прост.Однако, что если в графе есть несколько целей?Например;Вы можете найти кратчайший путь, который должен включать ранее указанные узлы.Ограничение здесь состоит в том, что ваш путь должен включать в себя узлы A, B и C (или более), а не просто найти путь к узлу A, B или C. И, конечно, граф включает один или несколько узлов типа A, B, C.Таким образом, возникает вопрос, как я могу адаптировать Алгоритм поиска по звездам для нескольких целей ?

редактировать: мы можем посещать более одного узла.

Answer 1

Вы описываете условия на пути, а не условия на цели. A *, как и все алгоритмы поиска, - это поиск пути к цели [может быть в наборе целей, без проблем с этим].

Ваша проблема [для общего случая], по крайней мере, так же сложна, как и проблема Командующий , и, таким образом, эта проблема NP-Hard .

Сокращение простое: учитывая экземпляр TSP - найдите кратчайший путь от некоторого v до v, такой, что путь проходит через все вершины [ограничение]. Вы можете сделать это, просто пометив каждую вершину разным знаком.

Обратите внимание, однако, что алгоритм A* не имеет проблем с поиском кратчайшего пути к вершине в наборе целевых вершин . Помните, что A * основан на алгоритме Дейкстры , который находит кратчайший путь к всем вершинам из одного источника.

Answer 2

Хмм .. Вычислить кратчайшие пути из S-> A, S-> B, S-> C, выбрать кратчайший (скажем, B), вычислить кратчайший путь из B-> C и B-> A, выбратькратчайший (скажем, C), вычислите кратчайший путь C до A. Затем сложите пути вместе.

[Edit] Окей, не все так просто.Я думаю, что вы можете использовать A * для оценки кратчайших путей для всех перестановок между Start, A, B, C (включая S-> каждый узел в наборах целей, каждый узел в A, каждый в B и т. Д.) И выбрать самый короткийкомбинация.

Answer 3

У вас есть набор z всех узлов, целевой узел G и наборы a через y узлов подцелей.Начиная с S, начальный узел, путь ко всем узлам от a до y.Затем из этого пути к узлам с a по y, но если маршрут уже прошел через узел c, например, игнорируйте все узлы c для этой ветви.Отбирайте ветви, которые удаляются от конечной цели, пока вы не прочитаете конечное состояние цели, и не найдете путь, который проходит через все известные состояния подцели.

Надежда, которая имеет смысл.Вскоре я приведу диаграмму, которая может помочь.