Расстояние таксомотора геометрия

Question

Поэтому у меня есть начальное состояние для массива, который является 8puzzle и состояние цели

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

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

Я пытаюсь выяснить, что расстояние между начальным состоянием и целью государством, не вдаваясь по диагонали , Может кто-нибудь мне помочь? (Примечание: я не против превратить этот массив в массив 2d, если это упростит ситуацию, я просто хочу знать, что такое расстояние для всего).

Всюду, что я ищу в Интернете, ожидает состояние цели цели, которое находится только в порядке возрастания. Это не относится к моей проблеме.

Answer 1

Эти массивы представляют собой состояния состояния 8-puzzle. Один из способов реализации решения для такой загадки сводится к поиску кратчайшего пути (см. How do you solve the 15-puzzle with A-Star or Dijkstra's Algorithm? для получения дополнительной информации). И особенно для A* algorithm вам понадобится admissible heuristic, который в этом случае может быть задан суммой Taxicab- or Manhattan distances между положениями плиток в текущем массиве и их положениями в состоянии цели. Эта эвристика используется, потому что она определяет нижнюю границу фактического количества ходов, которое потребуется. Как уже упоминалось в комментарии: фактическое количество ходов должно по крайней мере быть таким же большим, как чисто геометрическое (манхэттенское) расстояние между плитами.

Реализация этого не так сложна. Точная реализация будет зависеть от представления состояния правления. Для этого также можно использовать 2D-массивы. Но использование 1D-массивов имеет приятное преимущество: тривиально найти соответствия между позициями плитки.

Вообще, когда вы нашли определенное значение v в положении (sx,sy) в текущем состоянии, то вы должны поиска для позиции (gx,gy), что это значение имеет в состоянии цели, так что вы можете вычислить расстояние между два.

Но поскольку массивы содержат только цифры от 0 до array.length-1, вы можете вычислить «инверсию» состояния цели и использовать это для прямого поиска позиции (индекса) значения в массиве.

_{Пример и деталь добавлены, согласно запросу в комментарии:}

В качестве примера рассмотрит значение 6 в головоломках, которая появляется в положении (1,2). Теперь вы должны найти позицию, которую 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; 
    } 
}