广度优先搜索算法在无限循环中不起作用

Question

我正在尝试进行 BFS 搜索，在搜索状态 Space 时动态创建图形的节点。我遵循了这本书，但它不起作用边界保持运行并且探索集仅保持在起始值。请帮助，我已经被困在这里4天了。还是个初级程序员。

问题Class

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

搜索Class

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

节点Class

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

    }
}

状态Class

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 页） https://zoo.cs.yale.edu/classes/cs470/materials/aima2010.pdf

更新
它现在没有卡住，但是在循环运行后它没有向控制台输入任何内容它应该通过 "Parent 属性"[= 获取目标节点和起始节点之间的链接42=].

Answer 1

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

explored.Add(next.Data.Data);

应该是

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

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

我还建议从您的程序中删除所有字符串。相反，您应该创建表示坐标的类型，即 Point 或 vector2Int。我建议将其设为只读结构，并添加 ToString 重载、IEquality<Point> 实现、加减运算符、相等性等。此类型可用于表示状态和表示偏移量.这样的类型将可重复用于各种不同的项目。

广度优先搜索算法在无限循环中不起作用

Breadth First Search Algorithm Does Not Work Results in Infinite Loop

c#

algorithm

graph

artificial-intelligence

breadth-first-search