广度首先搜索算法不起作用导致无限循环

Question

我正在尝试进行BFS搜索，在此时，我在搜索状态空间时动态创建图形的节点。我遵循了这本书，但它不起作用，边境一直在运行，而探索的集合仅处于起始值。请帮忙，我被困在这里4天。仍然是初学者程序员。

问题类

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Test
{
    internal class Problem
    {
        public State start { get; set; }
        public State end { get; set; }

        public string[] action = { "UP", "LEFT", "DOWN", "RIGHT" };

        public Problem(State x, State y)
        {
            start = x;
            end = y;
        }

        public State Result(State s , string a)
        {
            State up;

            if (a == "UP" && s.X - 1 >= 0)
            {
                 up = new State(s.X - 1, s.Y);
               
            }
            else if (a == "LEFT" && s.Y - 1 >= 0)
            {
                up = new State(s.X, s.Y-1);
                
            }
            else if (a == "DOWN" && s.X + 1 <  5)
            {
                up = new State(s.X, s.Y+1);
               
            }
            else if( a == "RIGHT" && s.Y + 1 < 11)
            {
                up = new State(s.X + 1, s.Y);
                
            }
           
            return up;

           
        } 
    
        public bool GoalTest(Node<State> goal)
        {
            if (goal.Data.Equals(end))
            {
                return true;
            }
            return false;
        }
    
    }
}

搜索类

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Test
{
    internal class Search
    {
        public void BFS(Problem p)
        {
            Queue<Node<State>> frontier = new Queue<Node<State>>();
            HashSet<string> explored = new HashSet<string>();
            List<Node<State>> nNodes = new List<Node<State>>();

            Node<State> root = new Node<State>() {Data = p.start,};
            frontier.Enqueue(root);

            while(frontier.Count > 0)
            {
                Node<State> next = frontier.Dequeue();
                if(!explored.Add(next.Data.Data)) continue;
               

                next.Children = new List<Node<State>>();
                foreach(string action in p.action)
                {
                    next.Children.Add(new Node<State>() { Data = p.Result(next.Data, action), Parent = next });
                }

                for(int i = 0; i < next.Children.Count; i++)
                {
                    
                        if (p.GoalTest(next.Children[i]) == true)
                        {
                            //Solution(next.Children[i]);
                            break;
                        }
                        frontier.Enqueue(next.Children[i]);
                    
                }
            }
        }

        public void Solution(Node<State> n)
        {
            while(n.Parent != null)
            {
                Console.WriteLine(n.Parent.Data);
            }
        }
    }
}

节点类别

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Test
{
    internal class Node<T>
    {
        public T Data { get; set; }
        public Node<T>? Parent { get; set; }
        public List<Node<T>> Children { get; set; }

    }
}

状态类

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Test
{
    internal class State
    {
        public int X { get; set; }
        public int Y { get; set; }
        public string Data { get; }

        public State(int x, int y)
        {
            X = x;
            Y = y;
            Data = $"{X}-{Y}";
        }
    }
}

主要程序

using Test;

State start = new State(0, 1);
State end = new State(3, 7);

Problem p = new Problem(start, end);

Search s = new Search();
s.BFS(p);

这实际上是我的作业因此我将其命名为测试。
我正在尝试从这里实现伪代码：（第82页）

更新
它现在不陷入困境，但在循环运行后不会将任何内容输入到控制台中，它应该通过“ parent property” 在目标节点和开始节点之间获得链接。

Answer 1

您永远不会检查是否已经探索了节点，因此您可能会输入无限循环：

explored.Add(next.Data.Data);

应该是

if(!explored.Add(next.Data.Data)) continue;

，但代码可能还有其他问题。我强烈建议您阅读Eric Lipperts文章如何调试由于这样的问题应该很容易找到并在调试器的帮助下进行修复。学习如何使用调试器是一项宝贵的技能，它将使故障排除更加容易。

我还建议删除您程序中的所有字符串。相反，您应该创建代表坐标的类型，即一个点或vector2int。我建议将其变为可读的结构，并添加 toString Overload， iqeality＆lt; point＆gt; 实现，加法扣除，平等的运算符。代表国家并代表偏移。对于各种不同的项目，这种类型都可以重复使用。