Chevalier du plus court Chemin d'Échecs Question

Question

J'ai pratiqué pour la prochaine programmation de la concurrence et je suis tombé sur une question que je suis complètement déconcerté au. Cependant, j'ai l'impression que c'est un concept que je devrais savoir maintenant, plutôt que de me croiser les doigts qu'il ne vient jamais vers le haut.

Fondamentalement, il s'agit d'un chevalier de la pièce sur un échiquier. Vous disposez de deux entrées: lieu de départ et une destination. Le but est de calculer et d'imprimer le chemin le plus court que le chevalier peut prendre pour se rendre à l'emplacement cible.

Je n'ai jamais eu affaire avec le chemin le plus court-esque de choses, et je ne sais même pas par où commencer. Ce que la logique dois-je employer pour résoudre cela?

P. S. Si c'est de toute pertinence, ils veulent que vous pour compléter le Chevalier normal de la capacité de déplacement en lui permettant de se déplacer aux quatre coins de la place, un Chevalier de déplacer les chemins de créer si dans le centre de la carte.

Answer 1

En fait, il est un O(1) formule

C'est une image que j'ai faite pour le visualiser ( Carrés un chevalier peut atteindre à la N^{de la th} se déplacer sont peints avec de la même couleur ).

Pouvez-vous avis le patron ici?

Bien que l'on peut voir le modèle, il est vraiment difficile de trouver la fonction f( x , y ) qui renvoie le nombre de coups nécessaires pour aller de la place ( 0 , 0 ) à carré ( x , y )

Mais ici, c'est la formule qui fonctionne lorsqu' 0 <= y <= x

int f( int x , int y )
{
    int delta = x - y;

    if( y > delta )
        return 2 * ( ( y - delta ) / 3 ) + delta;
    else
        return delta - 2 * ( ( delta - y ) / 4 );
}

Remarque: Cette question a été posée sur les SACO 2007 Jour 1
Et les solutions sont ici

Answer 2

Vous avez un graphique ici, où tous les mouvements disponibles sont connectés (valeur=1), et l'indisponibilité de mouvements sont déconnectés (valeur=0), la matrice creuse serait:

(a1,b3)=1,
(a1,c2)=1,
  .....

Et le chemin le plus court de deux points dans un graphique peut être trouvé à l'aide de http://en.wikipedia.org/wiki/Dijkstra's_algorithm

Pseudo-code de wikipedia-page:

   function Dijkstra(Graph, source):
   for each vertex v in Graph:           // Initializations
       dist[v] := infinity               // Unknown distance function from source to v
       previous[v] := undefined          // Previous node in optimal path from source
   dist[source] := 0                     // Distance from source to source
   Q := the set of all nodes in Graph
   // All nodes in the graph are unoptimized - thus are in Q
   while Q is not empty:                 // The main loop
       u := vertex in Q with smallest dist[]
       if dist[u] = infinity:
          break                         // all remaining vertices are inaccessible from source
       remove u from Q
       for each neighbor v of u:         // where v has not yet been removed from Q.
           alt := dist[u] + dist_between(u, v) 
           if alt < dist[v]:             // Relax (u,v,a)
               dist[v] := alt
               previous[v] := u
   return dist[]

EDIT:

1. comme moron, a déclaré à l'aide de la http://en.wikipedia.org/wiki/A*_algorithm peut être plus rapide.
2. le moyen le plus rapide, est pour pré-calculer toutes les distances et l'enregistrer dans un 8x8 matrice complète. eh bien, je dirais que la tricherie, et ne fonctionne que parce que le problème est petit. Mais parfois, les compétitions va vérifier la vitesse de votre programme s'exécute.
3. Le point principal est que si vous vous préparez pour une programmation de la concurrence, vous devez savoir commune, y compris les algorithmes de Dijkstra est. Un bon point de départ est la lecture Introduction to Algorithms ISBN 0-262-03384-4. Ou vous pourriez essayer de wikipédia, http://en.wikipedia.org/wiki/List_of_algorithms

Answer 3

Oui, Dijkstra et BFS, vous obtiendrez la réponse, mais je pense que le jeu d'échecs contexte de ce problème fournit la connaissance de ce que peuvent produire une solution qui est beaucoup plus rapide qu'un générique du chemin le plus court de l'algorithme, en particulier sur une infinité de jeu d'échecs.

Pour des raisons de simplicité, nous allons décrire le jeu d'échecs comme (x,y) d'avion. L'objectif est de trouver le chemin le plus court à partir de (x0,y0) (x1,y1) en utilisant seulement le candidat étapes (+-1, +-2) et (+-2, +-1), comme décrit dans la question du P. S.

Voici la nouvelle observation: dessiner un carré avec coins (x-4,y-4) (x-4,y+4), (x+4,y-4), (x+4,y+4). Cet ensemble (appelons-S4) contient 32 points. Le chemin le plus court à partir de ces 32 points (x,y) implique exactement deux coups.

Le chemin le plus court à partir de la 24 points dans l'ensemble S3 (défini de la même manière) à (x,y) nécessite au moins deux déplacements.

Par conséquent, si |x1-x0|>4 ou |y1-y0|>4, le chemin le plus court à partir de (x0,y0) (x1,y1) est exactement deux coups de plus que le chemin le plus court à partir de (x0,y0) à S4. Et le dernier problème peut être résolu rapidement avec une simple itération.

Soit N = max(|x1-x0|,|y1-y0|). Si N>=4, alors le chemin le plus court à partir de (x0,y0) (x1,y1) a ceil(N/2) étapes.

Answer 4

Ce que vous devez faire est de penser à la des coups du chevalier comme un graphe, où chaque position sur la carte est un nœud et les coups possibles à d'autres position de pointe. Il n'est pas nécessaire pour l'algorithme de dijkstra, parce que chaque arête a le même poids ou la distance (ils sont tous tout aussi facile ou court pour faire). Vous pouvez tout simplement faire une BFS recherche à partir de votre point de départ jusqu'à atteindre la position de fin.

Answer 5

/*
This program takes two sets of cordinates on a 8*8 chessboard, representing the
starting and ending points of a knight's path.
The problem is to print the cordinates that the knight traverses in between, following
the shortest path it can take.
Normally this program is to be implemented using the Djikstra's algorithm(using graphs)
but can also be implemented using the array method.
NOTE:Between 2 points there may be more than one shortest path. This program prints
only one of them.
*/

#include<stdio.h>

#include<stdlib.h>

#include<conio.h>

int m1=0,m2=0;

/*
This array contains three columns and 37 rows:
The rows signify the possible coordinate differences.
The columns 1 and 2 contains the possible permutations of the row and column difference 
between two positions on a chess board;
The column 3 contains the minimum number of steps involved in traversing the knight's 
path with the given permutation*/

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

void printMoves(int,int,int,int,int,int);
void futrLegalMove(int,int,int,int);
main()
{
  printf("KNIGHT'S SHORTEST PATH ON A 8*8 CHESSBOARD :\n");
  printf("------------------------------------------");
  printf("\nThe chessboard may be treated as a 8*8 array here i.e. the (1,1) ");
  printf("\non chessboard is to be referred as (0,0) here and same for (8,8) ");
  printf("\nwhich is to be referred as (7,7) and likewise.\n");
  int ix,iy,fx,fy;
  printf("\nEnter the initial position of the knight :\n");
  scanf("%d%d",&ix,&iy);
  printf("\nEnter the final position to be reached :\n");
  scanf("%d%d",&fx,&fy);
  int px=ix,py=iy;
  int temp;
  int tx,ty;
  printf("\nThe Knight's shortest path is given by :\n\n");
  printf("(%d, %d)",ix,iy);
  futrLegalMove(px,py,m1,m2);
  printMoves(px,py,fx,fy,m1,m2);
   getch();
} 

/*
  This method checkSteps() checks the minimum number of steps involved from current
  position(a & b) to final position(c & d) by looking up in the array arr[][].
*/

int checkSteps(int a,int b,int c,int d)
{  
    int xdiff, ydiff;
    int i, j;
    if(c>a)
        xdiff=c-a;
    else
        xdiff=a-c;
    if(d>b)
        ydiff=d-b;
    else
        ydiff=b-d;
    for(i=0;i<37;i++)
        {
            if(((xdiff==arr[i][0])&&(ydiff==arr[i][1])) || ((xdiff==arr[i][1])&& (ydiff==arr[i] [0])))
            {
                j=arr[i][2];break;
            }
        }

        return j;
}   

/*
This method printMoves() prints all the moves involved.
*/

void printMoves(int px,int py, int fx, int fy,int a,int b)
{    
 int temp;
 int tx,ty;
 int t1,t2;
  while(!((px==fx) && (py==fy)))
  {   
      printf(" --> ");
      temp=checkSteps(px+a,py+b,fx,fy);
      tx=px+a;
      ty=py+b;
      if(!(a==2 && b==1))
      {if((checkSteps(px+2,py+1,fx,fy)<temp) && checkMove(px+2,py+1))
      {temp=checkSteps(px+2,py+1,fx,fy);
       tx=px+2;ty=py+1;}}
      if(!(a==2 && b==-1))
      {if((checkSteps(px+2,py-1,fx,fy)<temp) && checkMove(px+2,py-1))
      {temp=checkSteps(px+2,py-1,fx,fy);
       tx=px+2;ty=py-1;}}
      if(!(a==-2 && b==1))
      {if((checkSteps(px-2,py+1,fx,fy)<temp) && checkMove(px-2,py+1))
      {temp=checkSteps(px-2,py+1,fx,fy);
       tx=px-2;ty=py+1;}}
      if(!(a==-2 && b==-1))
      {if((checkSteps(px-2,py-1,fx,fy)<temp) && checkMove(px-2,py-1))
      {temp=checkSteps(px-2,py-1,fx,fy);
       tx=px-2;ty=py-1;}}
      if(!(a==1 && b==2))
      {if((checkSteps(px+1,py+2,fx,fy)<temp) && checkMove(px+1,py+2))
      {temp=checkSteps(px+1,py+2,fx,fy);
       tx=px+1;ty=py+2;}}
      if(!(a==1 && b==-2))
      {if((checkSteps(px+1,py-2,fx,fy)<temp) && checkMove(px+1,py-2))
      {temp=checkSteps(px+1,py-2,fx,fy);
       tx=px+1;ty=py-2;}}
      if(!(a==-1 && b==2))
      {if((checkSteps(px-1,py+2,fx,fy)<temp) && checkMove(px-1,py+2))
      {temp=checkSteps(px-1,py+2,fx,fy);
       tx=px-1;ty=py+2;}}
      if(!(a==-1 && b==-2))
      {if((checkSteps(px-1,py-2,fx,fy)<temp) && checkMove(px-1,py-2))
      {temp=checkSteps(px-1,py-2,fx,fy);
       tx=px-1;ty=py-2;}}
       t1=tx-px;//the step taken in the current move in the x direction.
       t2=ty-py;//" " " " " " " " " " " " " " " " " " " " " y " " " " ".
       px=tx;
       py=ty;
       printf("(%d, %d)",px,py);
       futrLegalMove(px,py,t1,t2);
       a=m1;
       b=m2;
   }

} 

/*
The method checkMove() checks whether the move in consideration is beyond the scope of
board or not.
*/   

int checkMove(int a, int b)
{
    if(a>7 || b>7 || a<0 || b<0)
        return 0;
    else
        return 1;
}

/*Out of the 8 possible moves, this function futrLegalMove() sets the valid move by
  applying the following constraints
      1. The next move should not be beyond the scope of the board.
      2. The next move should not be the exact opposite of the previous move.
  The 1st constraint is checked by sending all possible moves to the checkMove() 
  method;
  The 2nd constraint is checked by passing as parameters(i.e. a and b) the steps of the 
  previous move and checking whether or not it is the exact opposite of the current move.
*/

void futrLegalMove(int px,int py,int a,int b)
{
     if(checkMove(px+2,py+1) && (a!=-2 && b!=-1))
         m1=2,m2=1;
     else
     {
         if(checkMove(px+2,py-1)&& (a!=-2 && b!=1))
             m1=2,m2=-1;
     else
     {
         if(checkMove(px-2,py+1)&& (a!=2 && b!=-1))
              m1=-2,m2=1;
     else
     {
         if(checkMove(px-2,py-1)&& (a!=2 && b!=1))
               m1=-2,m2=-1;
     else
     {
         if(checkMove(px+1,py+2)&& (b!=-2 && a!=-1))
               m2=2,m1=1;
     else
     {
         if(checkMove(px+1,py-2)&& (a!=-1 && b!=2))
               m2=-2,m1=1;
     else
     {
         if(checkMove(px-1,py+2)&& (a!=1 && b!=-2))
               m2=2,m1=-1;
     else
     {
         if(checkMove(px-1,py-2)&& (a!=1 && b!=2))
               m2=-2,m1=-1;
     }}}}}}}
}

//End of Program.

Je n'ai pas étudié les graphiques encore..comme par le problème de la mettre en œuvre par simplement des tableaux, je ne pouvais pas tirer aucune solution autre que cela. J'ai traité la position pas que des rangs et des fichiers(L'habitude d'échecs notation), mais comme des indices de tableau. Pour info, c'est pour un 8*8 échiquier seulement. Toute amélioration des conseils sont toujours les bienvenues.

*Les commentaires devraient suffire pour votre compréhension de la logique. Cependant, vous pouvez toujours demander.

*Vérifié sur DEV-C++ 4.9.9.2 compilateur(de l'effusion de Sang du Logiciel).