Moins de déplacements vers le bord de l'échiquier

Question

Aujourd'hui, lors d'un examen, on m'a donné un problème algorithmique où j'ai reçu la taille N*M d'un échiquier et je devais déterminer quel est le nombre minimum de coups qu'un cavalier peut faire depuis le coin inférieur gauche de l'échiquier pour se rendre au coin supérieur droit. Comment cela peut-il être fait ?

Answer 1

Une solution utilisant BFS et la mémoïsation:

# Mémoïsation
memo = une matrice de NOVISITED de taille N x M

# Position de départ
# (ligne, colonne, sauts)
queue.push((0, 0, 0))

tant que la file n'est pas vide:
  # Obtenir la prochaine position non visitée
  ligne, colonne, sauts = queue.pop()

  # Marquer comme visitée
  memo[ligne][colonne] = sauts

  pour chaque mouvement possible (nouvelle_ligne, nouvelle_colonne) à partir de (ligne, colonne):
    si memo[nouvelle_ligne][nouvelle_colonne] est NOVISITED:
      # Ajouter le prochain mouvement possible à la file
      queue.append((nouvelle_ligne, nouvelle_colonne, sauts + 1))

NOVISITED peut avoir pour valeur -1 ou null si nous considérons les distances possibles comme un nombre non négatif [0,+inf).

Le nombre minimum de sauts pour chaque carré sera accessible dans memo[ligne][colonne], donc la réponse pour le coin en haut à droite du coin en bas à gauche sera à memo[N - 1][M - 1].

---

MISE À JOUR

Remarquez que si la matrice est carrée N x N, vous pouvez appliquer des principes de symétrie.

Answer 2

Je crois que vous pouvez réduire cela à trois cas:

1. Vous avez un tableau sans solution exemple: 2l * 4h

2. Vous avez un tableau avec une solution de 1: 2l * 3h

3. Vous avez un tableau qui est carré et donc a une solution de 4: 3l * 3h

Si vous avez un tableau plus grand que ceux-ci, vous pouvez le réduire à l'un d'eux en définissant le point final d'un mouvement en tant que point de départ d'un tableau plus grand.

Exemple: un tableau de taille 4l * 5h:

_ _ _ _
_ _ _ _
_ e _ _
_ _ _ _
s _ _ _

où s est le départ et e est la fin.

Ensuite, réduisez-le à un tableau carré:

_ 1 e
3 _ _
s _ 2

Où il faut 4 mouvements pour atteindre la fin. Donc vous avez 1 + 4 mouvements = 5 pour cette taille.

J'espère que cela suffit pour vous mettre sur la bonne voie.

EDIT: Cela ne semble pas être parfait tel quel. Cependant, cela illustre une façon heuristique de résoudre ce problème. Voici un autre cas pour votre plaisir visuel:

_ _ _ e
_ 3 _ _
_ _ _ _
_ _ 2 _
_ _ _ _
_ 1 _ _
_ _ _ _
s _ _ _

qui comporte 4 mouvements jusqu'à la fin dans un tableau 4x8.

À l'aide d'un langage de programmation, il serait peut-être préférable de commencer par cartographier tous les mouvements possibles à partir de votre emplacement actuel et de voir s'ils correspondent au point final. Si ce n'est pas le cas, vérifiez si votre problème est désormais un problème plus simple que vous avez résolu auparavant. Cela est réalisé grâce à la mémorisation, comme l'a souligné un commentateur.

Cependant, si vous le faites manuellement, je parie que vous pouvez le résoudre en l'isolant dans un petit nombre de cas comme je l'ai commencé à le faire.

Answer 3

Vous pouvez simuler le déplacement du cavalier en utilisant BFS ou DFS. Personnellement, je préfère l'approche DFS, car elle peut être implémentée de manière récursive. Si vous avez une fonction process qui prend comme paramètres la position x actuelle, la position y actuelle, les lignes du tableau, les colonnes du tableau et un compteur, alors la solution ressemblera à ceci :

/* .......... */
process(x-1, y-2, R, C, count+1);
process(x+1, y-2, R, C, count+1);
process(x-2, y-1, R, C, count+1);
process(x-2, y+1, R, C, count+1);
process(x-1, y+2, R, C, count+1);
process(x+1, y+2, R, C, count+1);
process(x+2, y-1, R, C, count+1);
process(x+2, y+1, R, C, count+1);
/* .......... */

Lorsque vous atteignez votre destination, vous retournez la valeur actuelle de count.

EDIT: cela peut également être résolu en utilisant la programmation dynamique. Vous définissez dp(i,j) comme étant la meilleure façon d'atteindre le carré (i,j). Ainsi dp(i,j) est égal à :

dp(i,j) = min{dp(tous les carrés pouvant atteindre (i,j) en un mouvement)} + 1

Answer 4

Voici la solution efficace.

Tout d'abord, les cas spéciaux. Si n = 1, vous ne pouvez pas sauter, et le problème n'est résoluble que pour (1, 1). Si n = 2 par inspection, il n'y a qu'un seul chemin possible à prendre, et le problème n'est résoluble que si m = 4k + 3, auquel cas vous avez besoin de 2k + 1 sauts pour y arriver. L'inverse est vrai si m = 1,2.

Passons maintenant au cas général. Un cavalier dispose de 8 sauts possibles, il se déplace de 2 dans une direction, puis de 1 dans une autre. Les directions possibles sont r, l, u, d (droite, gauche, haut, bas). Alors laissez nru être le nombre de fois où il saute 2 vers la droite, puis 1 vers le haut, et de même pour les 7 autres sauts possibles. Ensuite, la réponse doit être une solution au couple d'équations suivant:

n - 1 = 2*nru + nur - nul - 2*nlu - 2*nld - ndl + ndr + 2*nrd
m - 1 = nru + 2*nur + 2*nul + nlu - nld - 2*ndl - 2*ndr - nrd

Et le nombre de sauts est:

nru + nur + nul + nlu + nld + ndl + ndr + nrd

Nous nous attendons à ce que le nombre de sauts soit aussi bas que possible. Intuitivement, si nous avons un ensemble de nombres qui satisfait les deux premières équations, et que nous avons minimisé le nombre de sauts, nous ne devrions pas avoir trop de difficulté à trouver un ordre pour placer les sauts qui reste à l'intérieur du quadrillage. Je ne vais pas le prouver, mais cela se révèle vrai si 2 < n et 2 < m.

Résolvez donc ce problème de programmation entière (résolvez ces deux équations en gardant le nombre de sauts aussi bas que possible) et nous avons notre réponse. Il existe des solveurs pour cela, mais ce problème particulier est très simple. Faisons simplement la "chose évidente" pour nous rapprocher de notre objectif, trouvons quelques sauts supplémentaires, et il n'est pas difficile de prouver que c'est une solution optimale aux équations entières, et doit donc être la réponse au problème d'échecs.

Alors, quelle est la chose évidente? Tout d'abord, si m < n, nous pouvons simplement retourner le plateau pour que, sans perte de généralité, nous puissions supposer que n < m. (Le plateau va au moins aussi loin de vous que sur les côtés.) Étant donné ce fait, la chose évidente est de sauter en haut à gauche jusqu'à ce que vous atteigniez le mur, ou que vous touchiez la diagonale s'étirant vers le bas depuis le coin que vous voulez. À ce moment-là, avancez le long du mur ou de cette diagonale vers votre cible.

Si vous atterrissez directement sur la cible, vous avez votre meilleure réponse possible.

Si vous avez longé le mur et avez manqué de 1, il s'avère qu'en convertissant l'un de vos sauts en une paire, vous arriverez là où vous devez être. Si vous avez longé le mur et avez manqué de 2 (c'est-à-dire que vous êtes sur une diagonale), alors vous avez besoin d'insérer 2 sauts. (La distance montre que vous avez besoin d'au moins un de plus, et un simple argument de parité montre que vous en avez besoin d'au moins 2, et une paire de sauts y parviendra.)

Si vous avez longé la diagonale et avez manqué de 1, insérez une paire de sauts et vous êtes bon.

Si vous avez longé la diagonale et avez manqué de 2, alors convertissez une paire haut-droite/droite-haut en droite-haut/droite-haut/haut-gauche/gauche-haut et vous pourrez le faire avec juste 2 sauts supplémentaires.

Si vous n'avez pas parcouru la diagonale mais avez eu un saut en haut à gauche, convertissez-le en un triplet droite-haut/haut-gauche/droite-haut et une fois de plus vous pourrez le faire avec juste 2 sauts supplémentaires.

Le cas spécial restant est un plateau de 3x3, qui nécessite 4 sauts.

(Je vous laisse trouver toutes les inégalités appropriées et les modulos qui font que cette image fonctionne.)