Depth first search did find solution state in Missionaries and Cannibals problems

Question

I am doing my project on Missionaries and Cannibals using C#. I have used two search algorithms namely breadth first search and depth first search. Using Breadth first search, the program finds the result at level 12 from the root. But using Depth first search, it can not find solution and this hangs my computer. I think it enters a cycle in the graph. So my question is, can't i use Depth first search to solve Missionaries and cannibals problem?

Code for Breadth first search is

public State getSolutionStatesBFS(State StartState, State EndState) 
        {
            State CurState = new State();
            ArrayList visited = new ArrayList();
            addStateToAgenda(StartState, true);
            while (searchAgenda.Count > 0) {
                CurState = (State)searchAgenda.Dequeue();

              if (CurState.Equals(EndState)) {
                    break;
              } else {
                  if (!isVisited(CurState, visited))
                  {
                      generateSucessors(CurState, true);
                      visited.Add(CurState);
                  }
              }

            }
            return CurState;
        }

and the code for depth first search is

public State getSolutionStatesDFS(State StartState, State EndState)
        {
            State CurState = new State();
            ArrayList visited = new ArrayList();
            addStateToAgenda(StartState, false);
            while (searchAgendaS.Count > 0)
            {
                CurState = (State)searchAgendaS.Pop();

                if (CurState.Equals(EndState))
                {
                    break;
                }
                else
                {
                    if(!isVisited(CurState,visited))
                    {
                        generateSucessors(CurState, false);
                    }
                }
            }
            return CurState;
        }

Are we supposed to guess how `addStateToAgenda` and `generateSucessors` are implemented? have you debugged your code? DFS/BFS problems are rather to easy to solve with a common *debugger* — Shai, Aug 01 '12 at 12:52

score 3 · Accepted Answer · answered Feb 10 '13 at 23:01

3

It is hard to tell answer seeing your code. However, based upon my experience: a DFS search does not provide complete solution. There is a good possibility that your code might have got stuck into some infinite loop (which is common with dfs) or (since, you are checking isVisited), there is a possibility that you are not reaching the end goal.

answered Feb 10 '13 at 23:01

prabodhprakash

3,825
24
48

before using isVisited, it enters into infinite loop. But isVisited prevents it from entering into infinite state and it give the answer. – Feb 11 '13 at 02:18

score 1 · Answer 2 · answered Aug 01 '12 at 13:19

So my question is, can't i use Depth first search to solve Missionaries and cannibals problem?

Yes, it is deffinatly possible, take a look at this site: http://www.aiai.ed.ac.uk/~gwickler/missionaries.html

With the code given its hard to tell where your issue is.

Depth first search did find solution state in Missionaries and Cannibals problems

2 Answers2