Как представить данные для использования в DFS/BFS

Question

Мне была поставлена ​​задача решить с помощью различных методов поиска. Эта проблема очень похожа на проблему Escape From Zurg или задачу Bridge and Torch. Моя проблема в том, что я заблудился относительно того, как представлять данные в виде дерева.

Это мое предположение о том, как это сделать, но поиск не имеет особого смысла.

Другой способ - использовать двоичное дерево, отсортированное по времени ходьбы. Однако я все еще не уверен, правильно ли я атакую ​​эту проблему, поскольку алгоритмы поиска не обязательно требуют бинарных деревьев.

Любые советы по представлению этих данных будут оценены.

Answer 1

Обычно, когда вы используете поиск по дереву для решения проблемы, каждый узел представляет какое-то возможное "состояние" мира (например, кто на какой стороне моста), а дочерние элементы каждого узла представляют все возможные "состояния-преемники" (новые состояния, которые могут быть достигнуты за один ход из предыдущего состояния). Поиск в глубину затем представляет собой попытку выполнить один из вариантов до тупика, затем выполнить резервное копирование до последнего состояния, в котором был доступен другой параметр, и выполнить его. Поиск в ширину представляет собой одновременную проверку множества вариантов и определение, когда первый из них найдет целевой узел.

С точки зрения фактического способа кодирования этого, вы бы представляли это как многоходовое дерево. Каждый узел, вероятно, будет содержать текущее состояние, а также список указателей на дочерние узлы.

Надеюсь это поможет!

Answer 2

Вы могли бы использовать что-то вроде этого:

public class Node
{
   public int root;
   public List<Node> neighbours;
   public Node(int x)
   {
       root=x;
   }
   public void setNeighboursList(List<Node> l)
   {
       neighbours = l;
   }
   public void addNeighbour(Node n)
   {
       if(neighbours==null) neighbours = new ArrayList<Node>();
       neighbours.add(n);
   }
   ...
} 

public class Tree
{
    public Node root;
    ....
}