1

好的，所以我有一块板，我需要找到它所有可能的解决方案。它从板的左上角开始，仅水平或垂直移动，它必须访问板的每个元素。为了成功移动到另一个元素，第一个字母或第二个字母必须与前一个字母匹配。它只能访问每个元素一次且只能访问一次，但它可以跳过它。因此，如果我有这样的板：

XY YX XX

XX YY XY

YX XY XX

示例解决方案路径为：XY->XX->YX->XX->XY->YY->YX->XX->XY

我正在考虑使用 BFS，但我还没有了解队列，所以我可以在没有它们的情况下使用它吗？顺便说一句，这是在 C 中，原因是我正在学习的编程课程只涉及 C。

4

3 回答 3

3

您可以尝试回溯和修剪。它使用递归而不是队列。

http://en.wikipedia.org/wiki/Backtracking

于 2012-04-10T04:52:24.100 回答
3

请注意，即使找到一种解决方案，但并非所有解决方案都是NP-Hard问题，因为存在visit each element once and only once约束。您的问题实际上是网格上哈密顿路径问题的变体。

因此，没有已知的多项式解决方案可以确定这样的路径是否存在，更不用说找到所有路径了。

@Doct0rz 建议使用回溯可能是解决此问题的最佳方法。具体来说，我会选择只为相关分支维护设置的DFS的一些变体。visited

伪代码：

specialDFS(v,visited):
  if (visited.size == |V|):
      print this path by following the "father" field up to the root.
  for each edge (v,u):
     if (u is in visited): //do not check vertices that are already on the path
          continue
     visited.add(u)
     u.father <- v
     specialDFS(u,visited) //recursive call
     visited.remove(u) //clean the work environment, we maintain visited set only for the same path

调用：

visited <- {source} //add the single source here
source.father <- null //source is the root of all paths
specialDFS(source,visited)

注意：这是高级 OOP 风格的伪代码。由于问题被标记为作业 - 我将实际实施留给您。
祝你好运！

于 2012-04-10T06:27:31.503 回答
0 
#include <stdio.h>

typedef struct data {
  const char *element;
  int  visited;
} Data;

#define Size 3

Data Board[Size][Size] = {
    {{ "XY", 0 }, { "YX", 0 },{ "XX", 0 }},
    {{ "XX", 0 }, { "YY", 0 },{ "XY", 0 }},
    {{ "YX", 0 }, { "XY", 0 },{ "XX", 0 }}
};

#define PathLen (Size*Size)

int Path[PathLen];

Data *pos(int *x, int *y){
    if(*x < 0)     *x += Size;
    if(*x >= Size) *x -= Size;
    if(*y < 0)     *y += Size;
    if(*y >= Size) *y -= Size;
    return &Board[*y][*x];
}

void neighbor(int x, int y, int wx, int wy, int level);

void search_path(int x, int y, int level){
    Path[level] = Size * y + x;
    if(level == PathLen - 1){
        int i;
        for(i=0;i<PathLen;++i){
            int x = Path[i] % Size;
            int y = Path[i] / Size;
            if(i == PathLen - 1)
                printf("%s\n", Board[y][x].element);
            else
                printf("%s->", Board[y][x].element);
        }
    } else {
        neighbor(x, y, x - 1, y, level);//origin -> left
        neighbor(x, y, x + 1, y, level);//origin -> right
        neighbor(x, y, x, y - 1, level);//origin -> up
        neighbor(x, y, x, y + 1, level);//origin -> down
    }
}
//subroutine
//origin(x,y) -> neighbor(wx,wy)
void neighbor(int x, int y, int wx, int wy, int level){
    Data *wk;
    wk = pos(&wx,&wy);
    if(wk->visited == 0 &&
       (Board[y][x].element[0] == Board[wy][wx].element[0] ||
        Board[y][x].element[1] == Board[wy][wx].element[1])){
        wk->visited = 1;
        search_path(wx, wy, level + 1);
        wk->visited = 0;
    }
}

int main(void){
    int x = 0, y = 0, level = 0;
    Board[0][0].visited = 1;
    search_path(x, y, level);
    return 0;
}
/*
XY->XX->YX->YY->XY->XX->YX->XX->XY
XY->XX->YX->YY->XY->XX->YX->XX->XY
XY->XX->YX->YY->XY->XX->XY->XX->YX
XY->XX->XY->XX->YX->XX->XY->YY->YX
XY->XX->XY->XX->YX->YY->XY->XX->YX
XY->XX->YX->XX->XY->YY->XY->XX->YX
XY->XX->YX->XX->XY->YY->YX->XX->XY
XY->XX->YX->XX->XY->XX->YX->YY->XY
*/
于 2012-04-10T18:02:56.407 回答