2

まだ何も実装していませんが、再帰を使用して、特定のセルに「アクティブに接続」されているグリッド内のすべてのセル、つまり「アクティブ」で面を共有することによって直接接続されているセルを識別することを考えていました問題の (アクティブな) セルと、またはその (アクティブな) 隣接セルの 1 つと面を共有することにより、より遠く/間接的に接続されます。グリッド内の一部のセルが「非アクティブ」と見なされる可能性があるため、切断が発生します (定義が何であれ)。私のアイデア/疑似コードは次のとおりです。

//Call function to traverse connections
traverse_connections(cell);

//Traverse function definition
bool traverse_connections(cell) {
  //Check if cell is inactive or traversed - base case
  if (current cell is inactive or traversed) {
     return true;
  }
  //-Mark cell then move on to its neighbors
  Mark cell as traversed and add it to the list of 'actively connected' cells;
  bool ok = true;
  for(neighbor_cell in neighbors of cell) {
     ok &= traverse_connections(neighbor_cell);
  }
  return ok;
}

これは基本的なケースをカバーし、セルにマークを付け、次にその隣人、その隣人の隣人などに対して同じことを行うと思います。これは大丈夫に見えますか？私が見逃している明らかなギャップはありますか？グラフの接続性と再帰の専門知識を持っている人なら誰でも参加できれば幸いです。また、反復的な同等のものを考え出すのに苦労しています。それについてのアイデアも大歓迎です。

前もって感謝します！

4

2 に答える 2

2

「トラバース」と「アクティブ/接続」の概念が混同されているため、このソリューションは機能しません。この 2 つは直交しています。たとえば、セルは非アクティブで通過する場合もあれば、アクティブで通過しない場合もあります。疑似コードのif先頭にあるステートメントはtrue両方に対して返されますが、これは正しくありません。

トラバースされたセルをマークするテーブルは、アクティブなセルをマークするテーブルとは別に保持する必要があります。再帰呼び出しに入る前に、セルがトラバース済みとしてマークされていることを確認する必要があります。そうしないと、ソリューションが遅すぎたり、スタックが不足したりする可能性があります。

最後に、ソリューションは再帰的である必要はありません。再帰の代わりにキューを使用して実行できる単純な幅優先検索によって、必要なことを達成できます。

于 2013-10-08T14:16:41.057 に答える
1

現時点でセルをマークしている方法は、おそらく問題を引き起こす可能性があります。たとえば、マークしているこれらのセルの 1 つに、後で走査する必要がある隣接セルがある場合、それらのセルは走査されない可能性があります。

A* (A-Star) アルゴリズムを調べると、グラフ トラバーサルの良いアイデアが得られるはずです。UCS (uniform cost search) も、グラフ トラバーサルを使用する別のアルゴリズムです。

于 2013-10-08T14:29:30.033 に答える