java - 数据结构的图要求经过指定一些边，求最优解？

Question

数据结构的图要求经过指定一些边，求最优解？
能帮忙指点一下应该怎么去网上找资料吗，比如和哪个问题类似，应该用什么算法？这个问题是这样的,货运公司必须经过某一些城市,题目给出各个城市之间的花费,让用A*算法求最优解.

这是输入:
花费 360 Sydney 到 Wagga         
花费 200 Sydney 到 Bathurst      
花费 200 Dubbo 到 Grafton        
花费 240 Dubbo 到 Bathurst       
花费 480 Grafton 到 Wagga        
花费 440 Grafton 到 Bathurst     
花费 400 Wagga 到 Bathurst       

要求必须经过:
Grafton 到 Wagga
Dubbo 到 Grafton
Sydney 到 Wagga
Sydney 到 Bathurst

结果是:
Sydney 到 Bathurst
Bathurst 到 Dubbo
Dubbo 到 Grafton
Grafton 到 Wagga
Wagga 到 Sydney
Sydney 到 Wagga
总花费 1840

Answer 1

이것은 개인적으로 아직은 그래프 이론의 일부라고 생각하지만, SPFA, Dijkstra 알고리즘 등 기존의 최단 경로 관련 알고리즘으로는 풀 수 없는 문제입니다. Zeng Jin은 친구가 나에게 화웨이에 대한 경쟁 질문이 어떤 것인지 물어본 것 같습니다. 이 질문에는 A* 알고리즘을 사용하는 것이 확실히 가능합니다. 핵심은 이 휴리스틱 기능을 어떻게 설계하느냐입니다.
관련 지식을 검색할 수 있습니다
1. 지정된 중간 노드 집합을 통한 최단 경로 알고리즘
2. 휴리스틱 검색 알고리즘 A*

Answer 2

이 질문에는 다항식 답이 없다고 생각합니다. (뺨 때리기에 오신 것을 환영합니다)
점 수 n, 간선 수 m, 통과해야 하는 간선 수 k, n무차별 방식인 O(n^3)을 고려하여 임의의 두 지점 사이의 최단 경로를 전처리합니다(물론 n시간 힙 최적화 다익스트라도 가능하지만 이는 병목 현상이 아닙니다). O(k!)를 열거합니다. k개의 항목이 통과되었습니다. 가장자리를 배열하고 답을 계산하면 총 복잡성은 O(k!*k)이며 이는 분명히 허용할 수 없는 수준입니다.
모든 순열을 열거하여 최적의 솔루션을 얻을 필요는 없습니다. 더 나은 솔루션을 얻기 위해 시뮬레이션된 어닐링과 같은 무작위 알고리즘을 사용할 수 있으며 대부분의 경우 최적의 솔루션을 얻을 수 있습니다. .
이 질문이 NPC인지 NPH인지 증명해 보고 싶습니다.
원래 문제의 m개 모서리를 [i]부터 [i]까지 기록합니다.
k개 점으로 새 그래프를 만들고 k개 중 i번째 및 j번째 간선을 지정합니다. to[i]가 [j]에서 도달할 수 있으면 새 그래프에서 i에서 j까지 연결합니다. dis[to[i]][from[j]]의 가장자리. 따라서 원래 문제는 다항식 시간의 새로운 문제로 축소됩니다. 경로 길이를 최소화하기 위해 k 점 그래프의 모든 점을 통과하는 반복 가능한 경로를 찾습니다. 이 새로운 문제는 NPC나 NPH와 매우 비슷해 보입니다. (웃긴)
하지만 새로운 문제를 원래의 문제로 되돌리는 방법을 찾지 못했습니다. 현재 아이디어는 새 문제의 각 지점 i에 대해 원래 문제의 i에 대해 연결하는 것입니다. 문제 ;j, 원래 문제의 (i

Answer 3

알고리즘은 이해하지 못하지만 이러한 유형의 CSP 문제를 해결하기 위한 일반적인 프레임워크는 알고 있습니다. Optaplanner를 살펴보세요