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

Question

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

大家讲道理 · Answer

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

大家讲道理 · Answer

이 질문에는 다항식 답이 없다고 생각합니다. (뺨 때리기에 오신 것을 환영합니다)
점 수 n, 간선 수 m, 통과해야 하는 간선 수 k, n<=500, m<=5000, k<=라고 가정합니다. 500.
무차별 방식인 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<<1에서 (i<<1)|1 사이에 +inf 간선을 연결하고 새 문제의 각 간선 i->에 대해 연결하는 것입니다. 문제 ;j, 원래 문제의 (i<<1)|1에서 j<<1로 disi 가장자리를 연결하지만 몇 가지 문제가 있는 것 같아서 아직 명확하게 생각하지 못했습니다.

伊谢尔伦 · Answer

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

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

모든 응답(3)나는 대답할 것이다