0
그래프에서 두 점 사이의 최단 경로를 찾고 한 검사 점을 방문해야합니다. 또한 각 꼭지점을 한 번만 방문 할 수 있습니다. 네트워크 흐름과 관련이 있다고 생각하지만 구현 방법을 모릅니다.세 점 사이의 최단 경로
A
답변
0
용량이있는 다목적 최소 비용 흐름 문제로 완전히 모델링 할 수 있습니다. 꼭지점을 두 번 사용하지 않고 C를 통해 A에서 B로 이동하려고합니다. A에서 C (상품 1)와 B에서 C (상품 2) 사이의 흐름으로 모델링 할 수 있습니다. 노드가 두 번 사용되는 것을 피하려면 모델의 모든 노드에서 다음 트릭을 수행해야합니다.
p 개의 수신 및 t 개의 송신 에지가있는 노드 X가있는 경우 새 노드 Y를 만들고 모래밭. p 수신 링크는 모두 X에 도착하고, q 송신 에지는 모두 Y에서 출발합니다. X에서 Y까지 단 하나의 링크 (L) 만 추가합니다. L 링크의 용량을 1로 설정하면 각 노드가 사용됩니다 일단.
그러면 (M) ILP로 기록하고 해결할 수 있습니다. ILP는 올바른 솔루션을 제공합니다. 응용 프로그램에 따라 과도 할 수도 있습니다. 빠른 경험적 발견을 원한다면 2 개의 A * 검색을 사용하고 중복되지 않기를 바랍니다.
관련 문제
- 1. 이진 행렬의 두 점 사이의 최단 경로
- 2. 알고리즘 : 모든 점 사이의 최단 경로
- 3. 좌표계의 두 점 사이의 최단 경로
- 4. 여러 점 사이의 최단 거리
- 5. AI 검색 문제 : 장애물이있는 평면에서 2 점 사이의 최단 경로
- 6. 하스켈을 사용하여 그리드의 두 점 사이의 최단 경로 찾기
- 7. 세 벡터 점 사이의 각도
- 8. n GPS 점 사이의 최단 거리 계산
- 9. 특정 노드와 점 사이의 최단 거리
- 10. 두 점 사이의 최단 거리를 가져옵니다
- 11. 장애물이있는 점 A에서 점 B까지의 Java 2D 배열 최단 경로
- 12. 구면의 Geodesics (최단 거리 경로) 사이의 교차점
- 13. 두 노드 사이의 최단 경로 찾기 (정점)
- 14. 두 도형 사이의 최단 경로 찾는 법?
- 15. 게임 경로 찾기 : 가중치가 적용된 두 점 사이의 최단 경로 찾기
- 16. 안드로이드에서 세 점 사이의 각도 계산
- 17. 세 점 사이의 최대 거리를 계산하십시오.
- 18. 최단 경로 찾기
- 19. k 번째 최단 경로 찾기?
- 20. C 프로그래밍 언어, 최단 경로
- 21. 최단 경로 에지 웨이트
- 22. R, 최단 경로 결정
- 23. 그래프의 최단 경로 수
- 24. Trie의 최단 경로
- 25. Neo4jrb로 최단 경로 찾기
- 26. 지도의 최단 경로
- 27. Networkx - 최단 경로 길이
- 28. 사용자 지정지도 최단 경로
- 29. Dag의 최단 경로
- 30. 최단 경로 알고리즘 업데이트
A * 알고리즘을 확인하십시오. –
죄송합니다. http://en.wikipedia.org/wiki/A*_search_algorithm 링크 만 더 제공 할 수 있습니다. 여기에서 구현 예를 찾을 수 있습니다. –
고맙습니다.하지만 체크 포인트에 대해서는 아무 것도 없습니다. 시작과 검사 점 사이의 최단 경로를 찾으면 끝까지 내 길을 막을 수도 있습니다. – Kamgar