거리 택시 기하학

Question

그래서 나는 8puzzle 및

int[] myPuzzle = {1,3,4, 
        0,2,5, 
        8,6,7} 

int[] goalPuzzle = {2,1,0, 
        3,4,5, 
        8,7,6}; 

내가 초기 상태와 목표 상태 간의 거리가 대각선으로 이동하지 않고 무엇인지 알아 내려고 노력하고 목표 상태 배열의 초기 상태를 . 누구든지 나를 도울 수 있습니까? (참고 :이 배열을 2 차원 배열로 바꾸면 모든 것이 거리가 무엇인지 알고 싶을뿐입니다.

온라인으로 보이는 모든 곳에서 오름차순으로 된 goalPuzzle 상태가 필요합니다. 이것은 내 문제의 경우가 아닙니다.

Answer 1

이 어레이는 8-puzzle의 상태를 나타냅니다. 그러한 퍼즐을 위해 솔버을 구현하는 한 가지 방법은 최단 경로 검색으로 이어집니다 (자세한 내용은 How do you solve the 15-puzzle with A-Star or Dijkstra's Algorithm? 참조). 특히 A* algorithm의 경우 admissible heuristic이 필요합니다.이 경우에는 현재 배열의 타일 위치와 목표 상태의 위치 사이에 의 합으로 표시 할 수 있습니다. 이 추론은 필요한 실제 이동 수에 대한 하한을 정의하기 때문에 사용됩니다. 덧글에 언급 된 바와 같이 : 실제 이동 수 은 적어도 타일 사이의 순수한 기하학적 (맨하탄) 거리만큼 커야합니다.이어야합니다.

이렇게 구현하는 것은 그렇게 어렵지 않습니다. 정확한 구현은 보드 상태의 표현에 달려 있습니다. 하나는 2D 배열을 사용할 수도 있습니다. 그러나 1D 배열을 사용하면 좋은 장점이 있습니다. 타일 위치 간의 일치를 찾는 일은 쉽지 않습니다. 현재 상태에서 위치 (sx,sy)에서 특정 값 v을 찾을 때 사이의 거리를 계산할 수 있도록 일반적으로

는, 당신은, 위치이 값이 목표 상태에 가지고 (gx,gy)에 대한 검색에 있습니다 둘.

그러나 배열에는 0에서 array.length-1까지의 숫자 만 포함되므로 목표 상태의 "역"을 계산하고이를 사용하여 배열에서 값의 위치 (색인)를 직접 조회 할 수 있습니다.

_{예 및 세부 사항은 코멘트 요청에 따라, 추가 :}

예를 들어, 위치 (1,2)에 나타나는 퍼즐,의 값 6을 고려하십시오. 이제 6이 목표 상태에있는 위치를 찾아야합니다. 귀하의 예에서는 (2,2) 또는 색인 8입니다. 목표 상태 배열에서 6 값을 검색하여이 위치를 찾을 수 있습니다. 그러나 각 값에 대해 이렇게하면 O(n*n)이됩니다. 즉 비효율적입니다. invert 메서드는 지정된 목표 상태에 대해 [2,1,0,3,4,5,8,7,6]을 반환합니다. 이 배열의 요소 i은 값i이 원래 배열에 있었던 위치입니다. 예를 들어,이 배열을 인덱스 6 (찾고있는 값)에 액세스하면 8 값을 찾을 수 있습니다. 그리고 8은 정확히 6 값이 목표 배열에 있었던 색인입니다. 목표 배열에서 특정 값의 색인을 찾는 것은 간단한 조회 (예 : , 전체 배열을 통한 검색없이)로 수행 할 수 있습니다.

1D 배열의 색인과 보드 크기에서 거리를 계산하는 데 사용되는 (x,y) 좌표를 계산할 수 있습니다. 목표 퍼즐을 정의 무엇

public class TaxicabPuzzle 
{ 
    public static void main(String[] args) 
    { 
     int[] myPuzzle = { 
      1,3,4, 
      0,2,5, 
      8,6,7 
     }; 

     int[] goalPuzzle = { 
      2,1,0, 
      3,4,5, 
      8,7,6 
     }; 

     int distanceBound = computeDistanceBound(myPuzzle, goalPuzzle, 3); 
     System.out.println("Distance bound: "+distanceBound); 
    } 

    private static int computeDistanceBound(
     int state[], int goal[], int sizeX) 
    { 
     int inverseGoal[] = invert(goal); 
     int distance = 0; 
     for (int i=0; i<state.length; i++) 
     { 
      int goalIndex = inverseGoal[state[i]]; 
      distance += distance(i, goalIndex, sizeX); 
     } 
     return distance; 
    } 

    // For two indices in an array that represents a 2D array in row-major 
    // order, compute the manhattan distance between the positions that are 
    // defined by these indices 
    private static int distance(int index0, int index1, int sizeX) 
    { 
     int x0 = index0 % sizeX; 
     int y0 = index0/sizeX; 
     int x1 = index1 % sizeX; 
     int y1 = index1/sizeX; 
     return Math.abs(x1 - x0) + Math.abs(y1 - y0); 
    } 

    // Given an array containing the values 0...array.length-1, this 
    // method returns an array that contains at index 'i' the index 
    // that 'i' had in the given array 
    private static int[] invert(int array[]) 
    { 
     int result[] = array.clone(); 
     for (int i=0; i<array.length; i++) 
     { 
      result[array[i]] = i; 
     } 
     return result; 
    } 
}