Как использовать алгоритм Примса в 3d пространстве

Question

Мне было интересно, как я мог бы использовать алгоритм Прима в 3d пространстве. Чтобы перевести его в контекст: я хочу рассчитать все возможные и самые короткие/наиболее эффективные способы/проложить кабель в стене с учетом некоторых непригодных мест/ограничений в трехмерном пространстве.

Любые идеи о том, как можно смоделировать (как алгоритмически, так и технически)? Я знаю общие алгоритмы shortst path и min/max spanning tree, но изучал/использовал их всего лишь в 2d пространстве до сих пор.

Answer 1

Вы должны просто преобразовать 3D-стену в график. Скажем, наша стена является простым куб, мы делим его на множество мелких кубиков:

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

Поскольку вы получаете обычный граф, вы можете использовать алгоритм Prim.

Вы можете опустить вершины и края, где препятствия и уменьшить размер кубов, если вы хотите более высокую детализацию.