Я застрял на графике проблемы. Я работаю с OpenSG и пытаюсь найти пути между двумя точками в здании.Минимизировать Удержание графика Связь
Я построил этот график:
я использую его, чтобы найти кратчайший путь между двумя точками в здании:
Это, как я найти путь:
- Я добавляю начальный/целевой узел на график
- Я добавляю ребра из старт/целевого узла ко всем узлам, которые доступны (это делается с IntersectAction в OSG)
- Я использую A * -алгоритм, чтобы найти кратчайший путь
Я хочу, чтобы минимизировать график в настоящее время. Не имеет значения, если пути между двумя точками получаются немного дольше, я просто хочу оправдать избыточность, которую у меня есть сейчас. Например, все светло-зеленые узлы могут быть удалены. В комнате нет точки, которая не «видит» дверь, поэтому нет необходимости в узлах. Он должен выглядеть примерно так:
Итак, у меня есть алгоритм, который делает более или менее то, что я хочу, но я просто подумал, что это должна быть хорошо известная проблема. Это не минимальная крышка вершины, потому что, например, если в минимальном покрытии верхушки дверной узел не включен, я не найду способ между двумя комнатами.
я сравнивал с различными графах проблем, но я не смог найти реальный матч ...
Его очень поздно (6:20 утра), и я должен идти спать и, может быть, кажется, немного сбивает с толку или, может быть, его действительно очевидно. Спасибо за любой вклад в проблему.