C中的路径查找算法

Question

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

XY YX XX

XX YY XY

YX XY XX

将样品溶液路径将是：XY-> XX-> YX-> XX-> XY-> YY-> YX-> XX-> XY

我正在考虑使用BFS，但我还没有学习过队列，所以我能够在没有它们的情况下使用它？这是在C顺便说一句，原因是我正在采取的编程课程只包括C.

Answer 1

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

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

Answer 2

注意，即使找到一个解决方案，而不是所有的人都为NP-Hard问题，因为visit each element once and only once约束。您的问题实际上是网格上的Hamiltonian-Path Problem的变体。

因此，没有已知的多项式解决方案做出决定，如果这样的路径甚至存在，更不用说找到他们所有。

@ 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) 

注：这是高层次的面向对象式的伪代码。由于这个问题被标记为家庭作业 - 我将把实际的实施留给你。
祝你好运！

Answer 3

#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 
*/