1

わかりましたので、私はボードを持っており、そのすべての可能な解決策を見つける必要があります。ボードの左上隅から始まり、水平または垂直に移動するだけで、ボードの各要素にアクセスする必要があります。別の要素に正常に移動するには、最初の文字または 2 番目の文字が前の文字と一致する必要があります。各要素にアクセスできるのは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

制約があるため、1つの解決策を見つけても、すべてがNP困難な問題であるとは限らないことに注意してください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 に答える
3

バックトラックとプルーニングを試すことができます。キューの代わりに再帰を使用します。

http://en.wikipedia.org/wiki/バックトラッキング

于 2012-04-10T04:52:24.100 に答える
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 に答える