c# - 星搜索算法

Question

这里我有一个关于 A 星搜索算法的查询。我正在构建所谓的 8 block 拼图。这是一个有 9 个位置的游戏(1 个是空的)，您必须按照正确的顺序排列方 block 以达到目标位置。

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

我个人认为该算法是正确的，因为它能够解决我创建的第一个预设拼图，只需一步即可到达目标位置。但是，它无法解决需要更多移动的难题。

我尝试以 3 种不同的方式让它工作，但都带来了同样的问题。

尝试 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 是对我在 Internet 上找到的算法的更改:Solving the 8-Puzzle Problem

不过我尽力遵循维基百科上的伪代码:

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

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

我已经调试了几个小时，但我就是看不到它，我也看不到我的代码中还有什么地方可能有问题。所以我想我只是想问，这对你来说正确吗？

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

Answer 1

注意:我正在使用 CustomPriorityQueue 类(由 itowlson 编写)，您可以找到 here

所以在这里我主要使用 PriorityQueue，它将根据启发值排列问题状态

这是一个用 C# 编写的简单 A* 模板，说明了 A* 搜索的工作原理:

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));
    }
}

希望对你有帮助