3

私は Tetris を (宿題ではなく) 楽しいサイド プロジェクトとして作成しており、AI を実装してコンピューターが自動的にプレイできるようにしたいと考えています。私が聞いた方法は、BFS を使用して利用可能な場所を検索し、最も賢明なドロップ場所の集計スコアを作成することです...

しかし、アルゴリズムを理解するのに苦労しています。これまでのところ、私がそれを理解する方法は次のとおりです。

1) ノードを ArrayList に追加する

  • nodeList.add(n nodes)

2) ノードを接続する

  • 隣接行列を使用します。adjMatrix[sizeOfNodeList][sizeOfNodeList]

  • 接続するノードを渡します: ex: connectNode(nodeA, nodeB);、呼び出し: connectNode(Node from, Node to):

    int fromNode=nodesList.indexOf(from);
int toNode=nodesList.indexOf(to);

//connect node A to B and B to A, set that i,j position = 1
adjMatrix[fromNode][toNode]=1;
adjMatrix[toNode][fromNode]=1;

ここに画像の説明を入力

ノードが隣接行列で接続された後...

3) ノードのキューをループし、訪問済みをキューに追加します

  • 新しいキューを作成します。Queue q = new LinkedList();
  • rootNodeキューに追加:q.add(rootNode)
  • 訪問済みフラグを true に設定します。rootNode.visited(true)

わからない部分です…

  • キューが空ではない間...新しいノードを作成し、キューの削除されたノードと等しくなるように設定する必要があります。Node n = (Node)q.remove()

しかし、それにノードを追加している場合q.add(rootNode)、q.add(child)いつ空になるのでしょうか?

  • 次に、子ノード = 未訪問の子ノードであり、null ではないことを確認しwhile((child=getUnvisitedChildNode(n))!=null)ます。子の訪問済みステータスを変更することになっています =trueその後、それをキューに追加しq.add(child)ます...しかし、これをすべて行っていませんwhile(!q.isEmpty())か? では、追加する場合、いつq空になりますか?

私の Queue の目的は何qですか? 結果のキューですか？

ありがとう

4

2 に答える 2

3

キューqには、まだアクセスしていないノードが保持されます。qまだアクセスしていないノードのみをキューに追加する必要があります。そうすれば空になり、すでに探索したノードはリストに再入力されません。

イメージを例として使用するqと、ノードのみから開始しますA。A訪問済みとしてマークします。これがあなたが始める方法です。

ループは、キューの最初のノードq(この場合は ) を削除し、接続されていてまだアクセスされていないAすべてのノードを追加することで構成されます。A言い換えると、行列の行をたどってAを見つけB、CとDに接続されていることを確認しAます。それらのそれぞれについて、visited()false を返す場合は、それらを追加してq訪問済みとしてマークします。このパスでqはB、CとがありD、 のすべてにA-DVisited() が true として含まれます。

次の反復では、最初のノードは にqなりますB。Aこれをキューから取り出して、 、 、Eおよびに接続されていることを確認しますF。を呼び出すとA戻るので、 には追加しません。追加され、訪問済みとしてマークされます。truevisited()qEF

続行すると、すべてのノードがすでにアクセスされているため、 に何も追加せずにC、D、Eおよびをデキューします。その後、戻り、ループが終了します。Fqq.isEmpty()true

于 2013-05-29T21:06:04.180 に答える