경로 찾는 알고리즘 어려움

Question

문제 :

우리가 적은 회전에 최적화 된 A * 알고리즘을 수정합니다. 가능한 경우 알고리즘은 을 (x, 1) 또는 (x-1, y)가 선호하는 (a, b)에서 ANY TILE ADJACENT TO (x, y)까지의 경로로 찾습니다.

내 시도 용액 :

1. 실행에서 원래 A * 알고리즘 (a, b)에 대한 (X, Y).
2. (x-1, ) 또는 (x + 1,)을 통과하는 경로의 마지막 좌표를 찾습니다.
3. 해당 좌표계에서 *에서 y까지 직선으로 접근 할 수있는 수직선이있는 경우 해당 선을 따라가는 경로를 수정하십시오.

비주얼 데모 :

......S   .....S 
.  X   . X 
.   =>  .  
.     . 
E    E. 

그러나 내 솔루션은 어떤 경우에 작동 것이라고 모르겠어요 (X 액세스 할 수없는 경우 S에서 경로 전자합니다) 예 :

......S   .....S 
.  X   . X 
.X  ???  X.  
.     . 
E    E.. 

누구나이 문제에 대한 해결책을 생각할 수 있습니까?

참고 : A * 알고리즘은 방향 변경 횟수를 고려하여 결과 경로의 회전 횟수를 줄이는 것을 제외하고는 일반적입니다.

Answer 1

A *는 따라서 실제로 모든 꼭지점 [단일 소스로부터]으로 최단 경로를 찾는 내지 [admissible heuristic 기능] 설계 실제로 Dijkstra's algorithm의 정보를 버전이다.

당신은 목표 정점 [A * 깔끔하게 여러 대상을 처리 할 수있는 바와 같이 (x,y)에 인접한 모든 타일을 정의 할 수 있습니다, 당신은 또한 어떤 대상 노드에 허용 값을 제공하기 위해 휴리스틱 기능을 수정해야합니다. 이것은 h'(tile) = max { h(tile) - 1 , 0}을 간단히 수정하여 수행 할 수 있습니다. 그러나 어떤 경우에는 더 나은 방법이 필요할 수 있습니다. 당신이 목표 타일의 확장 후 대상 타일 [경로를 찾을 때까지로,

1. 실행 A * 을 :

   위를 설정 한 후, 우리는 원래 A *에 다음 수정을 유도 할 수있다 전술 한 바와]. 경로 길이를 d으로합시다.

2. 열린 노드에 대해 f(tile) 값이 d보다 엄격하게 커질 때까지 현재 상태로 A*을 계속 실행하십시오. 길이가 d 인 경로를 통해 소스에서 접근 할 수있는 모든 타일을 찾을 수 있도록 보장 된 이며 특히 - 길이가 d 인 출처에서부터 경로가있는 모든 대상 타일을 찾을 수 있습니다. [허용 가능한 휴리스틱 함수로 가정].
3. 모든 타일에서 "선호하는 타일"을 선택하고 경로를 반환 할 수 있습니다. 타일이 발견되지 않으면 임의의 타겟 타일 인 의 경로를 반환합니다.

도움이 되었기를 바랍니다.

Answer 2

휴리스틱 기능을 수정하여 (x+1,y) 및 (x-1,y) 지점을 약간 부스트하십시오. 그런 다음 패스를 마친 후 2 단계를 거치면 넥타이가 2 점으로 나뉩니다.