#java #algorithm #search #depth
#java #алгоритм #Поиск #глубина
Вопрос:
прошло много времени с тех пор, как я касался Java, поэтому это может показаться странным вопросом. В настоящее время у меня есть этот код поиска по ширине, который я нашел здесь, в StackOverflow, я его модифицировал со своей стороны, но я опубликую исходный код здесь.
public List<Node> getDirections(Node start, Node finish){
List<Node> directions = new LinkedList<Node>();
Queue<Node> q = new LinkedList<Node>();
Node current = start;
q.add(current);
while(!q.isEmpty()){
current = q.remove();
directions.add(current);
if (current.equals(finish)){
break;
}else{
for(Node node : current.getOutNodes()){
if(!q.contains(node)){
q.add(node);
}
}
}
}
if (!current.equals(finish)){
System.out.println("can't reach destination");
}
return directions;
}
Я знаю о других алгоритмах поиска в глубину, но мне также сказали, что можно легко преобразовать поиск в ширину в поиск в глубину, и я бы понял это лучше, если бы это было сделано с этим кодом вместо 2 совершенно разных кодов.
Как я могу изменить это, чтобы это был поиск в глубину?
Комментарии:
1. Вы пробовали конвертировать его в DFS самостоятельно? Если да, то что не сработало?
2. Просто подсказка: я помню некоторое время назад, что если вы напишете свой алгоритм таким образом, вы можете переключаться между DFS и BFS, просто переключаясь между структурами данных LIFO и FIFO, такими как стек или очередь.
3. Я получил его, перемещаясь по левой стороне, но это было с помощью какого-то грязного хакерского кода (путем редактирования кода в цикле for), в течение последних веков было много nullpointerexceptions и headbanging
4. @user799211: чтобы перейти вниз по левой стороне, вы могли бы использовать
List outNodes = new ArrayList(current.getOutNodes()); outNodes.removeAll(q); q.addAll(0, outNodes);
Ответ №1:
Основное различие между поиском в глубину и в ширину заключается в порядке, в котором вы исследуете узлы на своей «границе» (список узлов, которые вам еще предстоит изучить).
Если вы добавите исходящие узлы из вашего текущего узла в конец этого списка, вы будете тестировать все возможности на «уровне» (для упрощения представьте это как дерево), прежде чем перейти к следующему уровню, поэтому у вас есть поиск в ширину.
Если, с другой стороны, вы исследуете недавно добавленные узлы (исходящие узлы из вашей текущей позиции) перед добавленными ранее узлами (которые принадлежат «верхним» уровням дерева), то сначала вы будете исследовать глубину дерева.
С точки зрения структур данных вам нужен стек вместо очереди, но я думаю, что объяснение может пригодиться.
Ответ №2:
Вам нужно будет заменить q.add(node) (который добавляется в конце списка) на q.add(0, node) (для добавления в начале). В принципе, используйте a stack вместо a queue .
Очевидно, вам придется использовать List интерфейс вместо Queue того, чтобы получить доступ к LinkedList .
Комментарии:
1. Deque было бы лучше, чем List здесь.
2. Я бы использовал
ListforremoveAll()иaddAll()и удалил цикл for в своем крестовом походе против вложенности блоков глубокого кода.
Ответ №3:
Deque<Node> q = new LinkedList<Node>();
и используйте pop и push вместо remove и add
по сути, удаление с той же стороны, которую вы добавили (обычная remove и add базовая операция очереди LIFO), сначала depth использует стек FIFO
и другие алгоритмы поиска по сути одинаковы, но используют разные типы очередей (например, для быстрого поиска используется самый простой следующий шаг)
Ответ №4:
Замените Queue и LinkedList на Stack , add на push и remove на pop