これらのヒューリスティックで A* 検索を使用して 8 パズルを解こうとしています: - h1: 間違って配置されたタイルの数 - h2: マンハッタンの合計距離 - h3: 上記の合計
移動タイルは 0 として知られています。
私の目標は、これらのセットを解決することです:
4 1 2
5 8 3
7 0 6
と
8 6 7
2 5 4
3 0 1
私が抱えている問題は、現在の A* の実装では、最初の問題は解決できますが、2 番目の問題は解決できないということです。
だから、私のA *コードの何が問題なのかを理解するのを手伝ってください：
int[,] current = コンソールから文字列 (412583706) として入力され、パズルを表す 2D int に変換されます。正しい場合も同じで、0 は右下隅にあります。
var openList = new List<int[,]> { current };
var closedList = new List<int[,]>();
while (openList.Count > 0)
{
steps++;
current = GetBestNodeFromList(correct, dimensions, openList, useHeuristic);
// "GetBestNodeFromList()" finds the cheapest node in the openList.
// cheapest node: lowest value of h3.
openList.Remove(current);
h1 = getHeuristic1b(current, correct, dimensions);
h2 = getHeuristic2b(current, correct, dimensions);
h3 = h1 + h2;
if (h1 == 0 && h2 == 0) { break; }
openList = Puzzle_PossibleNext(current, closedList);
// the method "PossibleNext()" finds possible next moves from the current
// position. if the next move exists in the closedList, it is discarded.
// Drawing the puzzle and showing heuristics.
DrawCurrentState(h1, h2, h3, current, steps);
// adding last visited position to the closedlist.
closedList.Add(current);
}
最初の問題は 7 つのステップで解決されます。私がテストした別のプログラムによると、次の問題は 32 ステップで解決できます。
私のプログラムが他のプログラムと異なる点は、最初の 4 つのステップが同じで、他のプログラムが別のルートを選択することです。私のプログラムが最も安いノードを選択したように見えるので、何が悪いのか理解できません。
経路探索アルゴリズムは初めてなので解いてみたいと思います。私はこの問題を 3 日間抱えていて、多くの解決策を試したような気がしますが、どれもうまくいきません T_T
よろしくお願いします。
----編集----- 追加コード:
// Put heuristic value from all in list, then return list item with lowest h-value.
static int[,] GetBestNodeFromList(int[,] correct, int d, List<int[,]> list, string useHeuristic)
{
int[,] n = new int[d,d];
if (list.Count > 0)
{
List<Int32> heuristicsValueList = new List<Int32>();
for (int i = 0; i < list.Count; i++)
{
if (useHeuristic == "h1") { heuristicsValueList.Add(getHeuristic1b(list[i], correct, d)); }
else if (useHeuristic == "h2") { heuristicsValueList.Add(getHeuristic2b(list[i], correct, d)); }
else { heuristicsValueList.Add(getHeuristic3(list[i], correct, d)); }
}
n = list[heuristicsValueList.IndexOf(heuristicsValueList.Min())];
}
return n;
}
---------編集 2-------- 私のコードを少し変更しましたが、パズルのセットアップ/ノードとそのヒューリスティックはすべて PuzzleNode オブジェクトにあります。
// 現在のノードから次に可能な移動のリストを返します。// closedNodeList 内で見つかった移動は含まれません。
static List<PuzzleNode> Puzzle_GenerateNextNodes(PuzzleNode node, List<PuzzleNode> closedNodeList)
{
List<PuzzleNode> nextList = new List<PuzzleNode>();
Point isNow = new Point(0, 0);
// 1) Find where [0] is.
int dimensions = (int)Math.Sqrt((double)node.n.Length);
for (int x = 0; x < dimensions; x++) {
for (int y = 0; y < dimensions; y++) { if (node.n[x, y] == 0) { isNow.X = y; isNow.Y = x; break; } }
}
// 2) Check possible moves.
bool moveUp = false, moveDown = false, moveLeft = false, moveRight = false;
if (isNow.X == 0)
{
moveRight = true;
if (isNow.Y == 0) { moveDown = true; }
else if (isNow.Y == 1) { moveUp = true; moveDown = true; }
else if (isNow.Y == 2) { moveUp = true; }
}
else if (isNow.X == 1)
{
moveRight = true;
moveLeft = true;
if (isNow.Y == 0) { moveDown = true; }
else if (isNow.Y == 1) { moveUp = true; moveDown = true; }
else if (isNow.Y == 2) { moveUp = true; }
}
else if (isNow.X == 2)
{
moveLeft = true;
if (isNow.Y == 0) { moveDown = true; }
else if (isNow.Y == 1) { moveUp = true; moveDown = true; }
else if (isNow.Y == 2) { moveUp = true; }
}
// 3) Create list of possible moves.
// Add moved puzzle node to list over next moves
if (moveRight)
{
int[,] right = new int[dimensions, dimensions];
Array.Copy(node.n, right, node.n.Length);
PuzzleNode tmp = new PuzzleNode( PuzzleMoveRight(right, isNow.X, isNow.Y) );
if (!ListHasThisValue(tmp.n, closedNodeList, dimensions)) { nextList.Add(tmp); }
}
// moveleft, up, down, same structure as moveRight
if (moveLeft)
{
..
}
if (moveUp)
{
..
}
if (moveDown)
{
..
}
return nextList;
}
-----------編集3----------------
ところで、A* のさまざまなステップの実装が正しく理解されているかどうかを尋ねたいと思います。現時点では、私のプログラムの A* 検索はこれを行います:
- 初期リスト OPEN および CLOSED を作成し、開始ノードを OPEN に追加します
- ループを開始し、OPEN から最も安価なノードを削除し、CLOSED に追加します *最も安価なノードは、そのマンハッタン距離値によって決定されます。
- ノードを使用して隣人/子供/次の動きを見つけ、これらを SUCCESSOR リストに追加します。
- SUCCESSOR リストを探索し、それらのいずれかに目標状態が含まれているかどうかを確認し、そうでない場合は OPEN リストに追加します
- 2 ～ 4 を繰り返し、リスト内のノードを調べます。
Q1 でこれらの手順を試すと、7 つの手順で解決策が得られます。これは正しいです。これも手探りで発見。しかし、第 2 四半期では、OPEN リストが空になり、他に探索するものがなくなるまで続きます。それで、私は何が欠けていますか？