암시 적 그래프에서 최단 경로를 찾는 연결 검사의 수 최소화하기

Question

나는이 곳 어디에서도 아무것도 찾을 수 없다는 것에 상당히 놀랐다. 상당히 잘 알려진 문제인 것처럼 보인다 :

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만큼 연장되지 않는 방법 (부모는 항상 가상이 아닌 실제입니다)이 있다고 확신합니다.

Answer 1

A * 또는 일을 명시 적으로 그래프를하지 않아도 다 익스트라의 알고리즘, 그들은 실제로에만 필요합니다

1. 소스 정점 (s)
2. 함수 next:V->2^V 등이 next(v)={u | there is an edge from v to u }
3. 함수를 isGoal:V->{0,1} 등 그 isGoal(v) = 1 iff v 대상 노드입니다.
4. (U는 V) = 비용은 또한 (A) 내에 물론 V

에 U를 이동하고 * 휴리스틱 기능을 필요로하는가는 승 w:E->R는 h:V->R되도록 h(v) 같은 것을 가중치 함수 비용 근사치.

이 기능을 사용하면 가장 빠른 경로를 찾는 데 필요한 그래프 부분 만 생성 할 수 있습니다.
사실, A * 알고리즘은이 접근법을 사용하는 인공 지능 문제에서 무한 그래프 (또는 기존 저장소에 적합하지 않은 거대한 그래프)에 자주 사용됩니다.

아이디어는 단지 주어진 노드 (일부 주어진 u에 대한 E의 모든 (u,v))에서 A *의 가장자리에 볼이다. 이를 수행하기 위해 전체 가장자리를 E으로 설정할 필요가 없으며 대신 next(u) 함수를 사용할 수 있습니다.