Calcul de Manhattan Distance dans un tableau 2d

Question

J'écris un programme pour résoudre un problème de puzzle nxn 8. J'ai de la difficulté avec la fonction de calcul de Manhattan qui est désactivée par deux du puzzle avec lequel je suis en train de tester mon programme. Cela sera éventuellement étendu pour utiliser l'algorithme de recherche de chemin A *, mais je n'y suis pas encore.

Voici ma fonction (qui est basée sur l'état initial du conseil d'administration et ne tenant pas compte de la quantité de mouvements prises jusqu'à présent):

// sum of Manhattan distances between blocks and goal 
public int Manhattan() // i don't think this is right yet - check with vince/thomas 
{ 
    int distance = 0; 

    // generate goal board 
    int[][] goal = GoalBoard(N); 

    // iterate through the blocks and check to see how far they are from where they should be in the goal array 
    for(int row=0; row<N; row++){ 
     for(int column=0; column<N; column++){ 
      if(blocks[row][column] == 0) 
       continue; 
      else 
       distance += Math.abs(blocks[row][column]) + Math.abs(goal[row][column]); 
     } 
    } 

    distance = (int) Math.sqrt(distance); 

    return distance; // temp 
} 

Ceci est l'exemple que je travaille hors de :

8 1 3  1 2 3  1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 
4  2  4 5 6  ---------------------- ---------------------- 
7 6 5  7 8  1 1 0 0 1 1 0 1 1 2 0 0 2 2 0 3 

initial   goal   Hamming = 5 + 0   Manhattan = 10 + 0 

Mon calcul de Hamming est correct et renvoie 5, mais mon Manhattan renvoie 8 au lieu de 10. Que fais-je tort?

C'est la sortie de mon programme:

Size: 3 
Initial Puzzle: 
8 1 3 
4 0 2 
7 6 5 

Is goal board: false 

Goal Array: 
1 2 3 
4 5 6 
7 8 0 
Hamming: 5 
Manhatten distance: 8 
Inversions: 12 
Solvable: true 

Answer 1

L'erreur réside dans la mise à jour de la distance.

En écrivant distance += Math.abs(blocks[row][column]) + Math.abs(goal[row][column]); vous ajoutez tout le contenu des cellules initial et but. Un seul exclu en initiale et objectif est la cellule avec les mêmes coordonnées que 0 en initiale.

Dans votre exemple, cela donne 2 fois la somme de 0 à 8 moins 5. 2 * 36 -8 = 64. Ensuite, vous prenez le carré qui est 8.

Manhattan - comme décrit par Wiktionary est calculé par la distance dans les lignes plus la distance dans les colonnes.

Votre algorithme doit verrouiller comme (attention, pseudocode avance!)

for (cell : cells) { 
    goalCell = findGoalcell(cell.row, cell.col); 
    distance += abs(cell.row - goalCell.row); 
    distance += abs(cell.col - goalCell.col); 
} 

Et ne prenez pas la racine carrée.