나는이 곳 어디에서도 아무것도 찾을 수 없다는 것에 상당히 놀랐다. 상당히 잘 알려진 문제인 것처럼 보인다 :암시 적 그래프에서 최단 경로를 찾는 연결 검사의 수 최소화하기
Euclidean 최단 경로 문제를 2 차원으로 생각해보십시오. 장애물 다각형 P과 두 지점 및 B의 집합을 감안할 때, 우리는 P을의 (내부) 어떤 페이지 교차하지 에서B에 최단 경로를 찾으려면 .
이 문제에 대한 가시성 그래프, 노드가 P의 정점 인 그래프를 만들 수 있으며, 두 직선 사이의 직선이 요소를 교차하지 않으면 두 노드가 연결되는 그래프 P입니다. 그러한 에지에 대한 에지 가중치는 단순히이 두 점 사이의 유클리드 거리입니다. 이를 해결하기 위해 그래프에서 a에서 b까지의 최단 경로를 결정할 수 있습니다. A *를 예로 들어 봅시다.
그러나 이것은 좋은 접근 방법이 아닙니다. 가시성 그래프를 미리 작성하려면 두 개의 다각형에있는 두 개의 꼭지점이 연결되어 있는지 확인해야합니다. 두 개의 다각형 사이의 거리를 결정하는 것보다 더 복잡한 검사가 필요합니다. 따라서 "두 개의 노드가 실제로 연결되어 있는지 확인하기 전에 할 수있는 모든 것을 수행합니다"라는 A * 수정 된 버전을 사용하여 실제로 문제를 빠르게 처리 할 수 있습니다.
여전히 A *와 다른 모든 최단 경로 문제는 항상 인접한 정점을 값싼 방식으로 통과 할 수있는 명시 적으로 지정된 그래프로 시작됩니다. 그래서 내 질문은 두 개의 노드가 연결되어 있는지 확인하는 것을 최소화하는 "암시 적 그래프"에서 두 노드 a와 b 사이의 최단 경로를 찾기위한 좋은 (최적?) 알고리즘이 있습니까?
편집 :
이 V
이 세트 a
, V
의 b
요소하자 :
가 무슨 뜻인지 명확히하기 위해, 이것은 내가 무엇을 찾고의 예입니다. w: V x V -> D
이 계량 함수 (일부 선형 순서 집합 D
) 인 경우 V
의 두 요소가 연결된 것으로 간주되는 경우 c: V x V -> {true, false}
이 true를 반환한다고 가정합니다. 다음 알고리즘은 a
에서 b
까지의 최단 경로를 찾을 수 있으며 V
인 [x_i | i < n]
, x_0 = a
, x_{n-1} = b
및 c(x_i, x_{i+1}) = true
인 모든 i < n - 1
에 대한 목록을 반환합니다.
Let (V, E) be the complete graph with vertex set V.
do
Compute shortest path from a to b in (V, E) and put it in P = [p_0, ..., p_{n-1}]
if P = empty (there is no shortest path), return NoShortestPath
Let all_good = true
for i = 0 ... n - 2 do
if c(p_i, p_{i+1}) == false, remove edge (p_i, p_{i+1}) from E, set all_good = false and exit for loop
while all_good = false
루프에서 최단 경로를 계산할 때 적절한 추론이있는 경우 A *를 사용할 수 있습니다. 분명히이 알고리즘은 a
에서 b
까지 최단 경로를 생성합니다.
또한이 알고리즘은 가능한 한 드물게 c
을 호출 할 때 최적이라고 가정합니다. 발견 된 최단 경로의 경우, 함수 w
이 허용하는 모든 더 짧은 경로를 배제 했어야합니다.
하지만 더 좋은 방법이 있을까요?
편집 2 :
그래서 나는 상대적으로 잘 작동 해결책을 발견 난 할 노력하고있어 : A *를 사용하여 노드를 편안하게, 대신 이웃을 통과하고에 추가 할 때/우선 순위 대기열에서 그것들을 업데이트하면서, 가상의 f와 g 값과 가상의 부모와 함께 모든 꼭지점을 우선 순위 큐에 넣습니다. 그런 다음 우선 순위 큐에서 다음 요소를 선택할 때 노드에 부모 노드가 실제로 연결되어 있는지 확인합니다. 그렇다면 노드는 정상적으로 진행되고 그렇지 않으면 폐기됩니다.
이렇게하면 연결 확인 횟수가 크게 줄어들고 성능이 향상됩니다. 그러나 여전히 더 우아한 방법, 특히 "가상의 새로운 경로"가 길이 1만큼 연장되지 않는 방법 (부모는 항상 가상이 아닌 실제입니다)이 있다고 확신합니다.
대략 두 노드가 실제로 연결되어 있는지 확인하기 전에 할 수있는 일은 모두 수행합니다. 사실, 조금 더 나아가 노드 u를 풀었을 때 이미 닫힌 집합에있는 모든 v를 먼저 확인하거나 열린 집합에 있고 새로운 g가 향상되지 않으면 u와 v는 실제로 인접 해 있습니다. 그러나 A *는 시작 노드를 여유롭게 할 때와 같이 연결 확인 (또는 'next')을 불필요하게 자주 호출합니다. 그 일을하지 않는 알고리즘이 내가 찾고있는 알고리즘입니다. – Xoph