дополнительное пространство для рекурсивного поиска в глубину для хранения путей - PullRequest
Новая
       35

дополнительное пространство для рекурсивного поиска в глубину для хранения путей

5 голосов
/ 09 января 2010

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

Как я понимаю, при рекурсии явная структура стека не требуется для поиска в глубину, поэтому мне было интересно, смогу ли я еще больше упростить мой код ниже, как-нибудь обойдясь без явного стека: 

public class DFSonWeightedDirectedGraph {

    private static final String START = "A";
    private static final String END = "E";
    private int pathLength = 0;
    private int stops = 0;

    public static void main(String[] args) {
        //this is a directed weighted graph
        WeightedDirectedGraph graph = new WeightedDirectedGraph();
        graph.addEdge("A", "B", 15);
        graph.addEdge("A", "D", 15);
        graph.addEdge("A", "E", 27);
        //(...) more edges added


        Stack<String> visited = new Stack<String>();        
        visited.push(START);

        new DFSonWeightedDirectedGraph().depthFirst(graph, visited);
    }

    private void depthFirst(WeightedDirectedGraph graph, Stack<String> visited) {

        Collection<Map.Entry<String, Integer>> tree_of_children 
            = graph.get_tree_of_children(visited.peek());

        for (Map.Entry<String, Integer> child : tree_of_children) {


            if(pathLength + child.getValue()>= 20){
                continue;
            }       


            visited.push(child.getKey());
            pathLength += child.getValue();
            stops += 1;         

            if (child.getKey().equals(END)) {
                printPath(visited);
            }

            depthFirst(graph, visited); 
            visited.pop();  
            pathLength -= child.getValue();
            stops -= 1; 
        }
    }

    private void printPath(Stack<String> visited) {
        for (String node : visited) {
            System.out.print(node);
            System.out.print(" ");
        }
        System.out.println("[path length: "+pathLength +
                " stops made: " + stops +"]");
    }
}

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

Ответы [ 4 ]

1 голос
/ 09 января 2010

Если вам нужно сохранить путь, вам нужна структура данных для этого. Ваш стек в порядке; Вы можете заменить его другой структурой данных, но не избавитесь от нее.

Если было бы нормально напечатать путь (а не записать его), вам не нужен стек. Затем вы можете изменить сигнатуру метода, чтобы получить только график и фактический узел (и, возможно, фактическую длину пути и «остановки»).

0 голосов
/ 13 января 2010

Вам не нужны посещенные узлы. Просто передайте ваш текущий дочерний узел рекурсивному методу вместо параметра посещенных узлов и используйте возвращаемое значение для переноса пути.

Если вы можете обрабатывать элемент path по элементам, то есть переписать printPath (), чтобы он мог вызываться один раз для каждого элемента, просто требуется тип ключа в качестве возвращаемого типа. Если вы хотите получить весь путь, вам нужен список значений ключей в качестве типа возврата.

На самом деле, вы относительно близки к решению. Просто используйте стек вызовов рекурсивных вызовов методов для представления пути.

0 голосов
/ 10 января 2010

Просто добавьте дополнительное поле в структуру узла, которое является "посещаемым" полем. Это будет быстрее всего. Вы должны снять все отметки после этого (или до того, как начнете поиск).

Или просто хэшируйте идентификатор узла в хеш-таблице. Это будет быстрее, чем проверка стека. Если у вас нет идентификатора для узла, рекомендуется создать его, чтобы помочь с отладкой, выводом и т. Д.

Вам действительно нужно дополнительное пространство, но для добавления логического поля к каждому узлу потребуется наименьшее пространство, поскольку оно будет составлять 1 бит на узел по сравнению с 1 указателем на узел для стека.

На самом деле вам не нужно отсечение расстояния, так как вы ищете конечный граф и посещаете каждый узел только один раз, поэтому вы посетите не более N узлов в графе N-узлов. Вам понадобится ограничение глубины, если вы ищете бесконечное пространство, например, при поиске в пространстве состояний (например, интерпретатор пролога ищет доказательства).

0 голосов
/ 09 января 2010

Изменить: Этот ответ совершенно не по теме и был опубликован из-за неправильного толкования вопроса.

В реализации DFS есть несколько ошибок. Да, он посещает все узлы в глубине и в конечном итоге ему удается найти путь между START и END, но он не пытается проверять уже посещенные узлы и сохраняет стек без какой-либо реальной причины. Единственная причина, по которой вы не впадаете в бесконечную рекурсию циклов, заключается в том, что вы ограничиваете максимальную длину пути, и вам все равно потребуется много времени на графах, которые имеют несколько различных путей между всеми парами вершин.

Единственное, для чего вы используете стек - это пропуск узла, который вы хотите посетить, рядом с функцией dfs. Вы можете просто избавиться от стека и передать узел напрямую.

Итак, вместо 

private void depthFirst(WeightedDirectedGraph graph, Stack<String> visited) {
   ...
   visited.push(child);
   ...
   depthFirst(graph, visited);

Вы можете просто написать это как 

private void depthFirst(WeightedDirectedGraph graph, String node) {
   ...
   //visited.push(child); <-- No longer needed
   ...
   depthFirst(graph, child);

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

Вы можете изменить свой существующий код, чтобы он называл Set посещенным (сделайте его глобальной переменной или переменной класса или передайте его через рекурсивные вызовы, как вы делали со своим стеком), где вы сохраняете все уже посещенные узлы и вызываете только deepFirst () те узлы, которых еще нет в этом наборе.

Это должно заставить ваш код выглядеть примерно так 

private void depthFirst(WeightedDirectedGraph graph, String node, Set<String> visited) {
   visited.add(node); // mark current node as visited
   ...
   //visited.push(child); <-- No longer needed
   ...
   if (!visited.contains(child)){ // don't visit nodes we have worked on already
      depthFirst(graph, child);
   }

Пока что мой ответ - попытаться изменить ваш код, чтобы он работал. Но мне кажется, что вам нужно лучше понять, что такое DFS и как она работает на самом деле. Чтение соответствующей главы о любой хорошей книге «Алгоритм / Теория графиков» очень вам поможет. Я бы порекомендовал CLRS (там есть очень хорошая глава о простых обходах графов), но подойдет любая хорошая книга. Простой и правильный рекурсивный DFS может быть реализован намного проще с использованием массивов, без необходимости прибегать к стекам или наборам.

Edit: Я не упомянул, как можно получить путь после замены стека. Это можно легко сделать с помощью карты, в которой хранится родительский элемент каждого узла при его исследовании. Путь (если он найден) можно получить с помощью рекурсивной функции printPath (String node), которая печатает переданный ему узел и снова вызывает себя у его родителя.

...