Recherche du chemin le plus court dans un tableau à deux dimensions (Javascript)

Une façon de résoudre votre problème consiste à représenter d'abord votre tableau 2D sous forme de graphique, où chaque lettre est un nœud, et il existe un bord entre deux nœuds si la lettre qu'ils représentent est voisine dans le tableau, et ces lettres sont différent (un A et un B ).
Ensuite, tout ce que vous avez à faire est d'utiliser un algorithme classique de chemin le plus court, tel que celui de Dijkstra, ou A *, pour trouver le chemin le plus court entre deux nœuds de votre graphe. Cela équivaudra à trouver le chemin le plus court entre deux lettres de votre tableau.

Modifier: voici un pseudocode pour répondre à la question que vous avez posée dans le commentaire.

nodes = init_a_2d_array_of_graph_nodes(ARRAY_WIDTH, ARRAY_HEIGHT)
for i from 1 to ARRAY_WIDTH:
    for j from 1 to ARRAY_HEIGHT:
        if i < ARRAY_WIDTH and array[i][j] != array[i+1][j]:
            add_edge(nodes[i][j], nodes[i+1][j])
        if j < ARRAY_HEIGHT and array[i][j] != array[i][j+1]:
            add_edge(nodes[i][j], nodes[i][j+1])

Tout d'abord, vous devez initialiser une structure graphique. Si vous ne savez pas comment faire ça, vérifiez en ligne, il doit y avoir plein de façons de le faire, c'est plutôt simple.

Ensuite, vous devez créer un nœud pour chaque lettre de votre tableau. Il est également pratique de stocker ces nœuds dans un tableau 2D, afin que vous puissiez trouver facilement quelle lettre de votre tableau correspond à quel nœud de votre graphique. Ensuite, pour toutes les lettres voisines, vous vérifiez si ces lettres sont différentes (c'est ce qui est vérifié dans les 2 conditions if ). Si tel est le cas, vous connectez les deux nœuds avec une arête.

Après cela, vous devrez exécuter un algorithme de chemin le plus court sur votre graphique, entre votre nœud source et votre nœud de destination. L'algorithme de Dijkstra est le meilleur moyen de démarrer avec l'algorithme de chemin le plus court, c'est le plus largement utilisé et il est assez rapide dans la plupart des situations que vous rencontrerez.

Enfin, une fois que vous avez votre chemin, vous devez récupérer l'index (ligne et colonne) des nœuds de votre graphe, qui vous donnera le chemin correspondant dans votre tableau de lettres.

N'hésitez pas à commenter à nouveau s'il y a encore quelque chose que vous ne comprenez pas.

Eh bien, vous pouvez utiliser des grilles comme graphiques sans les convertir en une représentation de liste de contiguïté de graphique habituelle.

Ainsi, chaque paire (ligne, colonne) est un nœud,

Vous ne pouvez aller au nœud suivant que si : 2 nœuds sont voisins et ont des valeurs différentes,

Le but de la liste de contiguïté est d'obtenir des nœuds voisins efficaces, mais avec les cellules de la grille, vous pouvez toujours vérifier les 4 directions et traiter les nœuds qui existent. P >

Exemple de code:

let A = [ [ 'A', 'A', 'A', 'B', 'A' ],
        [ 'B', 'B', 'B', 'B', 'B' ],
        [ 'A', 'B', 'A', 'A', 'A' ],
        [ 'A', 'B', 'B', 'B', 'B' ],
        [ 'A', 'A', 'A', 'A', 'A' ] ];
		
let visited = new Set();
let rows = A.length;
let columns = A[0].length;
let distance = Array(rows).fill().map(() => Array(columns).fill(-1));
distance[0][0]=0;
let Q = []; //Queue
Q.push([0,0]);
visited.add([0,0].toString());

let dr = [-1,1,0,0]; 
let dc = [0,0,-1,1]; 

while(Q.length > 0)
{
	let cur = Q.shift();
	let row = cur[0];
	let col = cur[1];
	
	for(let k=0; k<4; k++)
	{
		let newRow = row + dr[k];
		let newCol = col + dc[k];
		
		if(!visited.has([newRow,newCol].toString()) && newRow>=0 && newCol >=0 && newRow < rows && newCol < columns && A[newRow][newCol] !== A[row][col])
		{
			visited.add([newRow,newCol].toString());
			distance[newRow][newCol] = distance[row][col] + 1;
			Q.push([newRow,newCol]);
		}
	}
}

if(distance[rows-1][columns-1] === -1)console.log("Path does not exist");
else console.log(distance[rows-1][columns-1]);

Quelqu'un connaît-il une implémentation de Graph simple qui peut m'aider à résoudre ce problème?

Le Dijkstra algortihm est utilisé pour trouver le chemin le plus court entre deux nœuds. Chaque position dans votre tableau à deux dimensions représente un nœud, les arêtes sont dérivées dynamiquement des nœuds environnants qui remplissent votre règle "d'alternance".

Vous pouvez l'optimiser davantage pour votre cas d'utilisation avec la recherche bidirectionnelle et une métrique d'objectif (A *).

Comme il représente un graphique non orienté non pondéré , vous pouvez simplement utiliser BFS:

const m =
  [ [ 'A', 'A', 'A', 'B', 'A' ],
    [ 'B', 'B', 'B', 'B', 'B' ],
    [ 'A', 'B', 'A', 'A', 'A' ],
    [ 'A', 'B', 'B', 'B', 'B' ],
    [ 'A', 'A', 'A', 'A', 'A' ] ]

let successors = (root, m) => {
  let connectedCells = [
    [root[0] - 1, root[1]],
    [root[0], root[1] - 1],
    [root[0] + 1, root[1]],
    [root[0], root[1] + 1]
  ]

  const validCells = connectedCells.filter(
    (cell) => (
      cell[0] >= 0 && cell[0] < m.length 
      && cell[1] >= 0 && cell[1] < m[0].length)
  )

  const successors = validCells.filter(
    (cell) => (m[cell[0]][cell[1]] !== m[root[0]][root[1]])
  )

  return successors
}

const buildPath = (traversalTree, to) => {
  let path = [to]
  let parent = traversalTree[to]
  while (parent) {
    path.push(parent)
    parent = traversalTree[parent]
  }
  return path.reverse()
}

const bfs = (from, to) => {
  let traversalTree = []
  let visited = new Set
  let queue = []
  queue.push(from)

  while (queue.length) {
    let subtreeRoot = queue.shift()
    visited.add(subtreeRoot.toString())

    if (subtreeRoot.toString() == to.toString()) return buildPath(traversalTree, to)

    for (child of successors(subtreeRoot, m)) {
      if (!visited.has(child.toString())){
        traversalTree[child] = subtreeRoot
        queue.push(child)
      }
    }
  }
}


console.log(bfs([0,0], [4,4]).length) // => 13