Как представить данные, которые будут использоваться для DFS / BFS - PullRequest
2 голосов
/ 02 февраля 2012

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

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

Graph

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

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

Ответы [ 2 ]

1 голос
/ 02 февраля 2012

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;
    ....
}
1 голос
/ 02 февраля 2012

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

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

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

...