c# - 迭代深化深度优先搜索找不到带有 8 个谜题的目标状态

Question

我尝试使用迭代深化深度优先搜索来解决 8 个难题，但有时它有时不起作用。

例如，当我从这个状态开始时：1、2、5、0、3、4、6、7、8 它会找到目标状态。

但在这种状态下找不到它：1、2、5、6、3、4、0、7、8

这是迭代深化搜索的代码：

public List<Node> DepthFirstStackDeepening(Node root, int depth, int[] initialState)
    {
        int increasingDepth = 0;
        for (int j = 0; j <= increasingDepth; j++)
        {
            if (j > depth)
                break;
            Node newRoot = new Node(initialState);
            var solution = DepthLimitedSearch(newRoot, increasingDepth);
            if (solution != null && solution.Any())
                return solution;
            increasingDepth++;
        }
        return null;
    }

    public List<Node> DepthLimitedSearch(Node root, int increasingDepth)
    {
        int nodeLevel = 0;
        bool goalFound = false;
        List<Node> PathToSolution = new List<Node>();
        Stack<Node> OpenList = new Stack<Node>();
        List<Node> ClosedList = new List<Node>();

        OpenList.Push(root);

        if (root.IsGoal())
        {
            Console.WriteLine("Goal Found");
            goalFound = true;
            PathTrace(PathToSolution, root);
        }

        while (OpenList.Count > 0 && !goalFound)
        {
            if (nodeLevel < increasingDepth)
            {
                nodeLevel++;
                Node currentNode = OpenList.Pop();
                ClosedList.Add(currentNode);

                currentNode.ExpandNode();

                for (int i = currentNode.children.Count - 1; i >= 0; i--)
                {
                    Node currentChild = currentNode.children[i];
                    //currentChild.PrintPuzzle();
                    if (currentChild.IsGoal())
                    {
                        Console.WriteLine("Goal Found");
                        goalFound = true;
                        PathTrace(PathToSolution, currentChild);
                    }

                    if (!Contains(OpenList.ToList(), currentChild) && !Contains(ClosedList, currentChild))
                        OpenList.Push(currentChild);
                }
            }
            else
            {
                nodeLevel++;
                Node currentNode = OpenList.Pop();
                ClosedList.Add(currentNode);

                if (currentNode.IsGoal())
                {
                    Console.WriteLine("Goal Found");
                    goalFound = true;
                    PathTrace(PathToSolution, currentNode);
                }

                for (int i = currentNode.children.Count - 1; i >= 0; i--)
                {
                    Node currentChild = currentNode.children[i];
                    //currentChild.PrintPuzzle();
                    if (currentChild.IsGoal())
                    {
                        Console.WriteLine("Goal Found");
                        goalFound = true;
                        PathTrace(PathToSolution, currentChild);
                    }

                    if (!Contains(OpenList.ToList(), currentChild) && !Contains(ClosedList, currentChild))
                        OpenList.Push(currentChild);
                }
            }
        }
        increasingDepth++;
        return PathToSolution;
    }

    public void PathTrace(List<Node> path, Node n)
    {
        Console.WriteLine("Tracing Path...");
        Node current = n;
        path.Add(current);

        while (current.parent != null)
        {
            current = current.parent;
            path.Add(current);
        }
    }

    public static bool Contains(List<Node> list, Node c)
    {
        bool contains = false;

        for (int i = 0; i < list.Count; i++)
        {
            if (list[i].IsSamePuzzle(c.puzzle))
                contains = true;
        }
        return contains;
    }
}

这是节点类：

public List<Node> children = new List<Node>();
    public Node parent;
    public int[] puzzle = new int[9];
    public int x = 0;
    public int col = 3;
    int[] goalState = new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8 };

    public Node(int[] p)
    {
        SetPuzzle(p);
    }


    public void SetPuzzle(int[] p)
    {
        for (int i = 0; i < puzzle.Length; i++)
        {
            this.puzzle[i] = p[i];
        }
    }

    public void ExpandNode()
    {
        for (int i = 0; i < puzzle.Length; i++)
        {
            if (puzzle[i] == 0)
            {
                x = i;
                break;
            }
        }

        MoveToRight(puzzle, x);
        MoveToLeft(puzzle, x);
        MoveToUp(puzzle, x);
        MoveToDown(puzzle, x);
    }

    public void MoveToRight(int[] p, int i)
    {
        if (i % col < col - 1)
        {
            int[] pc = new int[9];
            CopyPuzzle(pc, p);

            int temp = pc[i + 1];
            pc[i + 1] = pc[i];
            pc[i] = temp;

            Node child = new Node(pc);
            children.Add(child);
            child.parent = this;
        }
    }

    public void MoveToLeft(int[] p, int i)
    {
        if (i % col > 0)
        {
            int[] pc = new int[9];
            CopyPuzzle(pc, p);

            int temp = pc[i - 1];
            pc[i - 1] = pc[i];
            pc[i] = temp;

            Node child = new Node(pc);
            children.Add(child);
            child.parent = this;
        }
    }

    public void MoveToUp(int[] p, int i)
    {
        if (i - col >= 0)
        {
            int[] pc = new int[9];
            CopyPuzzle(pc, p);

            int temp = pc[i - col];
            pc[i - col] = pc[i];
            pc[i] = temp;

            Node child = new Node(pc);
            children.Add(child);
            child.parent = this;
        }
    }

    public void MoveToDown(int[] p, int i)
    {
        if (i + col < puzzle.Length)
        {
            int[] pc = new int[9];
            CopyPuzzle(pc, p);

            int temp = pc[i + col];
            pc[i + col] = pc[i];
            pc[i] = temp;

            Node child = new Node(pc);
            children.Add(child);
            child.parent = this;
        }
    }

    public void PrintPuzzle()
    {
        Console.WriteLine();
        int m = 0;

        for (int i = 0; i < col; i++)
        {
            for (int j = 0; j < col; j++)
            {
                Console.Write(puzzle[m] + " ");
                m++;
            }
            Console.WriteLine();
        }
    }

    public bool IsSamePuzzle(int[] p)
    {
        bool samePuzzle = true;
        for (int i = 0; i < p.Length; i++)
        {
            if (puzzle[i] != p[i])
                samePuzzle = false;
        }
        return samePuzzle;
    }

    public void CopyPuzzle(int[] a, int[] b)
    {
        for (int i = 0; i < b.Length; i++)
        {
            a[i] = b[i];
        }
    }

    public bool IsGoal()
    {
        for (int i = 0; i < puzzle.Length; i++)
        {
            if (puzzle[i] != this.goalState[i])
                return false;
        }
        return true;
    }