一个星型搜索算法

这里我有一个关于a星搜索算法的查询。我正在制作所谓的8块拼图。这是一个有9个位置(1个为空)的游戏，你必须按照正确的顺序排列瓷砖以达到目标位置。

我只需要验证我是否正确地编写了算法，以便我可以在代码的其他地方寻找问题。

我个人认为这个算法是正确的，因为它能够解决我创建的第一个预先设置的谜题，只需要一次移动就可以到达目标位置。然而，它无法解决需要更多移动的谜题。

我试过用三种不同的方法来解决这个问题，但都带来了同样的问题。

尝试1:

while (openList.Count() > 0)
        {
            PuzzleNode currentNode;
            var orderedOpenList = openList.OrderBy(PuzzleNode => PuzzleNode.getPathCost());
            currentNode = orderedOpenList.First();
            if (compare(currentNode.getPuzzle(), goalArray) == true)
            {
                //openList.RemoveAt(0); //POLL
                break;
                // otherwise push currentNode onto closedList & remove from openList
            }
            else
            {
                openList.Remove(currentNode);
                closedList.Add(currentNode);
            }
            //generate all the neighbor nodes
            generateSuccessors(currentNode, tempList);
            for (int i = 0; i < tempList.Count(); i++)
            {
                PuzzleNode tempNode = tempList[i];
                //skip the node if it's in the closed list
                if (closedList.Contains(tempNode))
                {
                    continue;
                }//end if
                //We need to ensure that the G we have seen here is the shortest one
                int gScore = currentNode.getG() + 1;
                if (!openList.Contains(tempNode) || gScore < tempNode.getG())
                {
                    tempNode.setParentNode(currentNode);
                    tempNode.setH(tempNode.calcH(currentHueristic, tempNode.getPuzzle(), goalArray));
                    tempNode.setG(gScore);
                    tempNode.updatePathCost();
                    if (!openList.Contains(tempNode))
                    {
                        openList.Add(tempNode);
                    }//end if

                }//end if
            }//end for
        }//end while

尝试2:

while (openList.Count() > 0)
        {
            PuzzleNode currentNode = GetBestNodeFromOpenList(openList);
            openList.Remove(currentNode);
            closedList.Add(currentNode);
            generateSuccessors(currentNode, tempList);
            foreach (PuzzleNode successorNode in tempList)
            {
                if (compare(successorNode.getPuzzle(), goalArray) == true)
                {
                    //goto thebreak;
                    return successorNode;
                }
                successorNode.setG(currentNode.getG() + 1);
                successorNode.setH(successorNode.calcH(currentHueristic, successorNode.getPuzzle(), goalArray));
                successorNode.updatePathCost();

                if (OpenListHasBetterNode(successorNode, openList))
                    continue;
                openList.Add(successorNode);
            }
        }//end while
private static PuzzleNode GetBestNodeFromOpenList(IEnumerable<PuzzleNode> openList)
    {
        return openList.OrderBy(n => n.getPathCost()).First();
    }
private static bool OpenListHasBetterNode(PuzzleNode successor, IEnumerable<PuzzleNode> list)
    {
        return list.FirstOrDefault(n => n.getG().Equals(successor.getG())
                && n.getPathCost() < successor.getPathCost()) != null;
    }

尝试2是我在网上找到的一个算法的修改:解决8个难题

然而，我尽我最大的努力遵循维基百科上的伪代码:

function A*(start,goal)
     closedset := the empty set    // The set of nodes already evaluated.
     openset := {start}    // The set of tentative nodes to be evaluated, initially containing the start node
     came_from := the empty map    // The map of navigated nodes.
     g_score[start] := 0    // Cost from start along best known path.
     // Estimated total cost from start to goal through y.
     f_score[start] := g_score[start] + heuristic_cost_estimate(start, goal)
     while openset is not empty
         current := the node in openset having the lowest f_score[] value
         if current = goal
             return reconstruct_path(came_from, goal)
         remove current from openset
         add current to closedset
         for each neighbor in neighbor_nodes(current)
             tentative_g_score := g_score[current] + dist_between(current,neighbor)
             if neighbor in closedset
                 if tentative_g_score >= g_score[neighbor]
                     continue
             if neighbor not in openset or tentative_g_score < g_score[neighbor] 
                 came_from[neighbor] := current
                 g_score[neighbor] := tentative_g_score
                 f_score[neighbor] := g_score[neighbor] + heuristic_cost_estimate(neighbor, goal)
                 if neighbor not in openset
                     add neighbor to openset

我问你是否能找到一个问题，因为我很困惑，为什么它只适用于一个谜题。仅将这些谜题分开，是解决到目标状态所需的移动量。

我已经调试了几个小时了，我就是看不到它，我也看不出我的代码中的其他地方可能有问题。我只是想问，你觉得这样对吗?

任何问题一定要问，我会尽可能提供更多信息!提前感谢!

void enqueueAll(CustomPriorityQueue<PuzzleNode> a, ArrayList<PuzzleNode> b)
{
    foreach(PuzzleNode c in b) a.enqueue(c, h(c));
}
// A* heuritic: h = f + g ; h <= h*
int h(PuzzleNode n);
// returns TRUE if n is a solution
bool isSolution(PuzzleNode n);
// expand n into list of neighbors
ArrayList<PuzzleNode> expand(PuzzleNode n);
PuzzleNode Astar(PuzzleNode startPoint)
{
    CustomPriorityQueue list = new CustomPriorityQueue<PuzzleNode>();
    PuzzleNode current = null;
    list.enqueue(startPoint, h(startPoint));
    while (list.size() > 0)
    {
        current = list.dequeue();
        if (isSolution(current))
        {
            return current;
        }
        enqueueAll(list, expand(current));
    }
}