1

ノードとグラフの非常に基本的な知識があると言って始めましょう。

私の目標は、配列として格納されている迷路のソルバーを作成することです。私は解決するためのアルゴリズムを実装する方法を正確に知っています (私は実際にそれらのいくつかを実装しています) が、私の問題は、ソルバーが各空のセルで使用するノードを実装する方法について非常に混乱していることです。

配列の例を次に示します。

char maze[5][9] = 
        "#########",
        "#  #    #",
        "# ## ## #",
        "#     # #",
        "#########"

私のソルバーは左上から始まり、ソリューション (出口) は右下にあります。

ノードの仕組みとグラフの実装方法について読んだので、これを作成する必要があると思う方法は次のとおりです。

  • 始点がノードになる
  • 各ノードには、プロパティとして列と行番号があります
  • 各ノードは、訪問された状態もプロパティとして持ちます
  • 訪問した状態はvisited、、、visited and leads to dead endnot visited
  • ノードが訪問されるたびに、直接隣接する空のセルおよび訪問されていないすべてのセルが、訪問されたノードの子になります
  • 訪問したすべてのノードは、solutionPath スタックの一番上に配置されます (マップ上で「*」としてマークされます)。
  • 行き止まりになったすべてのノードがスタックから削除されます (マップ上で「~」としてマークされます)。

完成した迷路の例:

"#########",
"#*~#****#",
"#*##*##*#",
"#****~#*#",
"#########"

基本的に私の質問は、私の考え方でここで本当にばかげたことをしているのですか (私は本当にノードの経験が浅いため)、そうである場合は、その理由を説明していただけますか? また、可能であれば、他のウェブサイトを提供して、実際のアプリケーションでグラフの例を実装しているものを確認して、それをよりよく理解できるようにします。

4

1 に答える 1

1

答えは、問題の中で何が最も重要かによって異なります。効率と速度を求めている場合は、追加するノードが多すぎます。そんなに多くは必要ありません。

効率的な方法

ソルバーは、パスの始点と終点、およびマップ上の可能なすべてのコーナーにあるノードのみを必要とします。このような：

"#########",
"#oo#o  o#",
"# ## ## #",
"#o  oo#o#",
"#########"

マップ上の他の場所を実際にテストする必要はありません。それらの場所を通り抜ける必要があるか、わざわざテストする必要さえありません。

それが役に立てばdigraph、単純なグラフ表現用に設計したテンプレート クラスを取得しました。あまりうまく書かれていませんが、考えられる解決策を示すのに最適です。

#include <set>
#include <map>

template <class _nodeType, class _edgeType>
class digraph
{
public:
    set<_nodeType> _nodes;
    map<pair<unsigned int,unsigned int>,_edgeType> _edges;
};

このクラスを使用して、ダイクストラのアルゴリズムを使用してタワー ディフェンス ゲームでパスを見つけます。表現は、他のアルゴリズムでも十分なはずです。

ノードは任意のタイプにすることができます。おそらく最終的にはpair<unsigned int, unsigned int>. 2つを_edgesつなげてセットに。_nodesposition

簡単にコーディングできる方法

一方、実装が簡単なメソッドを探している場合は、配列内のすべての空き領域を可能なノードとして扱うだけで済みます。それがあなたの探しているものなら、グラフを設計する必要はありません。なぜなら、配列は問題を完璧な方法で表しているからです。

この方法で解決するために専用のクラスは必要ありません。

bool myMap[9][5]; //the array containing the map info. 0 = impassable, 1 = passable
vector<pair<int,int>> route; //the way you need to go
pair<int,int> start = pair<int,int>(1,1); //The route starts at (1,1)
pair<int,int> end = pair<int,int>(7,3); //The road ends at (7,3)

route = findWay(myMap,start,end); //Finding the way with the algorithm you code

のプロトタイプfindWayがありvector<pair<int,int>> findWay(int[][] map, pair<int,int> begin, pair<int,int> end)、必要なアルゴリズムを実装しています。関数の内部には、テストされた場所を示す bool 型の別の 2 次元配列が必要になるでしょう。

アルゴリズムが経路を見つけた場合、通常は逆に読み取る必要がありますが、アルゴリズムに依存していると思います。

あなたの特定の例では、 myMap には次が含まれます。

bool myMap[9][5] = {0,0,0,0,0,0,0,0,0,
                    0,1,1,0,1,1,1,1,0,
                    0,1,0,0,1,0,0,1,0,
                    0,1,1,1,1,1,0,1,0,
                    0,0,0,0,0,0,0,0,0};

そして、含むをfindWay返しますvector(1,1),(1,2),(1,3),(2,3),(3,3),(4,3),(4,2),(4,1),(5,1),(6,1),(7,1),(7,2),(7,3)

于 2013-11-09T22:26:32.193 に答える