Поиск в глубине действительно нашел решение проблем миссионеров и каннибалов

Question

Я делаю свой проект на миссионеров и людоедов с использованием C#. Я использовал два алгоритма поиска, а именно поиск по ширине и поиск по глубине. Используя поиск по ширине, программа находит результат на уровне 12 от корня. Но используя поиск в глубину, он не может найти решение, и это зависает на моем компьютере. Я думаю, что это входит в цикл на графике. Итак, мой вопрос: не могу ли я использовать поиск в глубину для решения проблемы миссионеров и каннибалов?

Код для поиска в ширину

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

и код для глубины первого поиска

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

Answer 1

Трудно сказать ответ, увидев ваш код. Однако, исходя из моего опыта: поиск в DFS не дает полного решения. Существует хорошая вероятность того, что ваш код мог застрять в каком-то бесконечном цикле (что характерно для dfs) ​​или (поскольку вы проверяете isVisited), есть вероятность того, что вы не достигли конечной цели.

Answer 2

Итак, мой вопрос: не могу ли я использовать поиск в глубину для решения проблемы миссионеров и каннибалов?

Да, это возможно, посмотрите на этот сайт: http://www.aiai.ed.ac.uk/~gwickler/missionaries.html

С данным кодом трудно сказать, где ваша проблема.