Breadth First Search Algorithm Does Not Work Results in Infinite Loop-CodePudding

I am trying to do a BFS search where I dynamically create the Nodes of the graph as I search the State Space. I followed the book but it does not work the frontier keeps on running and the explored set stays at the start value only. Please help, I have been stuck here for 4 days. Still a beginner programmer.

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

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

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

    }
}

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

Main Program

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

This is actually for my assignment hence I named it test.
I am trying to implement the pseudocode from here: (Page 82) https://zoo.cs.yale.edu/classes/cs470/materials/aima2010.pdf

Update
It does not stuck now but it does not input anything into the console after the loop runs it is supposed to get the links between the goal node and the start node via the "Parent property".

CodePudding user response：

You are never checking if nodes are already explored, so you will likely enter an infinite loop:

explored.Add(next.Data.Data);

should be

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

But there might be other problems with the code. I would highly recommend reading Eric Lipperts article How to debug small programs since problems like this should be fairly easy to find and fix yourself with the help of a debugger. Learning how to use a debugger is an invaluable skill that will make troubleshooting much easier.

I would also recommend removing all the strings from your program. Instead you should create type representing a coordinate, i.e. a Point, or vector2Int. I would recommend making this a readonly struct, and add ToString overload, IEquality<Point> implementation, operators for addition subtraction, equality etc. This type could then be used both for representing the state, and to represent the offsets. Such a type would be reusable for all kinds of different projects.