장애물과 공간 제약으로 총 경로 비용 최소화

Question

2D Grid에 배열 된 노드 네트워크가 있습니다. 2 차원 그리드의 물리적 공간을 차지할 연결과 노드 쌍을 연결하고 싶습니다. 이제 연결 자체가 장애물이며 미래의 연결은 연결을 피하는 경로를 취해야합니다.

현재 A* algorithm을 사용 중이며 점차 연결을 구축하고 있습니다. 시작 노드에서 끝 노드까지 최단 경로를 찾지 만 다른 연결을 고려하지 않으므로 모든 쌍을 연결 한 후의 총 경로 비용이 최적이 아닙니다.

해결할 수있는 알고리즘이 있는지 또는 NP 완전 문제입니까? 관련 자료에 대한 어떤 방향으로도 감사 할 것입니다.

Answer 1

minimum genus graph embedding, 노드가 그래프 정점이고 필요한 연결이 가장자리 인 것을 찾으려고하는 것 같습니다. 최소한의 속은 필요로하는 최소 교차 수로 해석 될 수 있습니다. 최소 길이의 연결을 찾는 것이 더 어렵습니다 (또는 그럴까요?)

최소 그래프 속 자체는 NP 완성입니다 (특히 결정 버전 - 그래프가 속의 표면에 포함될 수 있는지 여부 k). 따라서 최소한의 횡단면으로 이러한 경로를 찾는 것이 문제라면 문제는 NP가 될 것입니다.

그러나 평면형 그래프 만 고려하면 선형 적 시간 내에 평면형 포함을 찾을 수 있습니다.