-1

所以我必须编写这个算法（这个版本不需要在骑士开始的同一个地方结束），我让它工作，但它太慢了。它适用于 size=8 的起始位置 x=0 和 y=0，但如果我尝试将 x 和 y 操作为例如 2 和 4，它不会在几分钟后结束。任何人都可以帮忙吗？

#include <stdio.h>
#define size 8
int ruch_x[]={ -1,  1, -2,  2, -2,  2, -1,  1}; //arrays of possible knight moves, for example 2nd move is [1,2]//
int ruch_y[]={  2,  2,  1,  1, -1, -1, -2, -2};

int done(int szach[][size])
{
   for(int i=0;i<size;i++)
   {
      for(int j=0;j<size;j++)
      {
         if(szach[i][j]==0)
            return 0;
      }
   }
   return 1;
}
//licz - variable for counting knights moves//
void konik(int szach[][size], int x, int y, int licz)
{
    szach[x][y]=licz;
    if(licz<size*size){
        for(int i=0;i<=7;i++){ //loop that checks every possible knight move//
            if(szach[x+ruch_x[i]][y+ruch_y[i]]==0&&x+ruch_x[i]>=0&&x+ruch_x[i]<size&&y+ruch_y[i]>=0&&y+ruch_y[i]<size)
// checking if candidat was already visited and if it's not outside of the board//
            {
                konik(szach, x+ruch_x[i], y+ruch_y[i], licz+1);}}}

    if(done(szach)==1) return; //checking if whole board is filled with numbers, if yes then skip zeroing current move//
    szach[x][y]=0;
}

int main()
{
    int i, j, x,y;
    printf("set x\n");
    scanf("%d", &x);
    printf("set y\n");
    scanf("%d", &y);

    int szach[size][size];
    for(i=0;i<size;i++) {  //zeroing array//
            for(j=0;j<size; j++) {
                    szach[i][j]=0; }}
    konik(szach, x, y, 1);

    for(int i=0;i<size;i++) {
            for(int j=0;j<size; j++) {
                    printf("%d\t",szach[j][i]); }
            printf("\n\n");}
    printf("\n");
    return 0;
}
4

3 回答 3

1

简单的蛮力可能是个坏主意，因为对于 8x8 板，可能的序列数量可能超过 10^50。

Knight在 wikipedia 上的旅游文章有关于这个问题的不错信息，我建议从那里开始。

寻找哈密顿路径的最著名的启发式方法之一如下：从任何节点u开始，按照图中的度数按非递减顺序排列邻居。假设从uknight 可以移动到pand q（即u有两个邻居），然后在您的递归中首先考虑p它的可用邻居是否少于q。这通常会导致显着的优化，尤其是在这种情况下，如果图有很多汉密尔顿路径。

关于你的代码。您不需要每次都调用 done() 。如果在任何时候licz >= size*size，那么你知道你找到了答案。例如，您可以存储一个全局boolean done变量。这应该会有所帮助，但并非在所有情况下都有帮助。

PS如果您的项目需要任何单一的解决方案，我建议您存储一个 Hamilton cycle，并且任何x,y只需简单地改变序列以获得有效的解决方案。

于 2013-12-05T21:36:57.607 回答
0

这绝不是一个答案，只是一个可能有用的想法。

我记得对于某些尺寸，一个简单的螺旋图案将填充板的外边缘，并将问题减少到一个更简单的size小 4 的问题。

你可以使用这个想法来简化你的问题。例如，填充 8x3 和 8x5 板而不是 8x8 板（您必须更新算法以寻找合适的结束位置）。

于 2013-12-05T20:55:09.047 回答
0

ile 的建议似乎不错。当我只实施一个来首先考虑图表中度数最低的候选者（从该位置可能移动的次数）时（近似为四个角中最近的一个），找到起始位置x的解决方案的运行时间=2和y=4从十个半小时减少到一分 15 秒。程序变化如下：

// arrays of possible knight moves, for example 2nd move is [1,2]
// rearranged so that adjacent moves differ by 45 angular degrees
int ruch_x[]={  2,  1, -1, -2, -2, -1,  1,  2};
int ruch_y[]={  1,  2,  2,  1, -1, -2, -2, -1};


#include <stdlib.h>

//licz - variable for counting knights moves//
void konik(int szach[][size], int x, int y, int licz)
{
    szach[x][y]=licz;
    if (licz<size*size)
    {   static char firstmove[2][2][2] = { 1, 0, 6, 7, 2, 3, 5, 4 };
        int m = firstmove[x<size/2][y<size/2][abs(size-1-x*2)<abs(size-1-y*2)];
        for (int s=0; s<=7; s++) //loop that checks every possible knight move//
        {   static int ply[8] = { 0, -1, 1, -2, 2, -3, 3, -4 };
            int i = m+ply[s];   // firstmove towards corner, then back and forth
            if (i < 0) i += 8;
            else
            if (i > 7) i -= 8;
            // checking if candidate ...
            if (x+ruch_x[i]>=0&&x+ruch_x[i]<size    // not outside of the board
             && y+ruch_y[i]>=0&&y+ruch_y[i]<size
             && szach[x+ruch_x[i]][y+ruch_y[i]]==0  // not already visited
               )
                konik(szach, x+ruch_x[i], y+ruch_y[i], licz+1);
        }
    }

    if (done(szach)==1) return; //checking if whole board is filled with numbers
                                //if yes then skip zeroing current move//
    szach[x][y]=0;
}

顺便说一句，原始程序的行为没有严格定义，因为szach[x+ruch_x[i]][y+ruch_y[i]]在检查x+ruch_x[i],y+ruch_y[i]不在板数组之外之前进行了检查。

于 2016-09-16T14:15:56.240 回答