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

Question

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

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

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

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

Answer 1

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

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

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

Answer 2

U может использовать что-то вроде этого:

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