Вопросы по теме 'breadth-first-search'
вставка в очередь при ее перечислении
Я хочу выполнить поиск по дереву в ширину, используя очередь
var q = new Queue<T>();
q.Enqueue(Root);
foreach(T root in q)
{
foreach(T t in root.Children)
q.Enqueue(t);
}
Однако я получаю сообщение «Коллекция была изменена после...
1540 просмотров
schedule
14.11.2023
Сначала в ширину против сначала в глубину
При перемещении по дереву / графику какая разница между сначала в ширину и сначала в глубину? Любые примеры кодирования или псевдокода были бы хороши.
122456 просмотров
schedule
06.07.2022
Найти первый нуль в двоичном дереве с ограниченной памятью
У меня есть двоичное дерево, в котором каждый узел может иметь значение.
Я хочу найти узел в дереве, который имеет значение null и находится ближе всего к корню. Если есть два узла на одинаковом расстоянии от корня, подойдет любой. Мне нужно...
669 просмотров
schedule
09.06.2022
Решение лабиринта с использованием графа
Эй, я был на местном соревновании по программированию, и они задали мне этот вопрос, который я не мог ответить, поэтому, пожалуйста, помогите мне с этим.
Напишите программу, которая загружает из файла размер лабиринта, а затем сам лабиринт. Для...
3477 просмотров
schedule
24.11.2023
Алгоритм BFS - кратчайший обход по сетке с ограниченными шагами
Проблема заключается в следующем: Странник начинает с координат сетки (x,y) и хочет достичь координат (0,0). Из каждой точки сетки странник может пройти 8 шагов на север ИЛИ 3 шага на юг ИЛИ 5 шагов на восток ИЛИ 6 шагов на запад (8N/3S/5E/6W)....
1552 просмотров
schedule
04.03.2024
Возврат только вершин фактического кратчайшего пути
Я знаю, что заголовок немного сумбурный, но я не знаю, как его лучше объяснить.
Что я пытаюсь сделать:
Используя граф, найденный в текстовом файле, найдите и распечатайте кратчайший путь (минимальное количество вершин) из вершины A в вершину...
12487 просмотров
schedule
25.03.2023
Вопрос о поиске в ширину C++
Это мой первый раз, когда я программирую на C++, и меня попросили закодировать поиск в ширину, где задан этот класс.
class route {
friend ostream& operator<<(ostream& os, const route& p);
public:
route(const string&...
1637 просмотров
schedule
17.04.2022
C++ реализация графового алгоритма
Я пытаюсь реализовать алгоритм поиска в ширину , чтобы найти кратчайшее расстояние между двумя вершинами. Я разработал объект Queue для хранения и извлечения объектов, и у меня есть двумерный массив для хранения длины ребер между двумя заданными...
1958 просмотров
schedule
29.12.2023
Очереди в Java. Что не так с моей реализацией и какую из них я могу использовать?
Я пытаюсь выполнить поиск в ширину, чтобы решить головоломку со сдвигом квадратов (та, где вы перемещаете квадраты в пустое пространство, пока она не будет решена). Мой алгоритм поиска в ширину использует очередь. К сожалению, кажется, что это...
333 просмотров
schedule
28.03.2023
Анализ дерева, сгенерированного BFS
Я думал задать этот вопрос на Mathexchange, но он не столько о расчетах и да/нет, сколько об алгоритме, связанном с информатикой, поэтому я задаю его здесь.
В алгоритме BFS можно пометить каждый уровень обхода как слои. Например, если s...
394 просмотров
schedule
07.06.2023
Библиотека графов Boost, распределенная в ширину, ошибка времени выполнения MPI_Unpack
Я использую библиотеку графов повышения и имею ошибку времени выполнения, которую я не могу понять, как исправить.
Когда я создаю и сначала ищу в ширину граф rmat с неправильной комбинацией количества вершин и количества процессоров, я получаю...
587 просмотров
schedule
28.04.2022
Поиск в ширину для поиска всех путей между любыми двумя узлами в циклическом графе.
Я пытаюсь использовать BFS для получения всех путей между двумя узлами в циклическом графике. Я обнаружил, что BFS не отслеживает свой предыдущий узел, поэтому нужно добавить какую-то другую коллекцию, чтобы добиться того же.
Вопрос в том,...
877 просмотров
schedule
06.06.2024
Реализация BFS на Java
Я новичок в Java, и мне нужна помощь.
Я пытаюсь реализовать алгоритм поиска в ширину для решения игры-головоломки (разблокировать игру на Android). Я закончил с графическим интерфейсом, но я застрял в алгоритме.
Пока я могу подсчитать доступные...
40563 просмотров
schedule
02.08.2023
Отслеживание глубины в нерекурсивном поиске в ширину
У меня есть следующий алгоритм поиска в ширину:
q := []
q.append(root node of tree)
while q:
n := q.pop(0)
yield n
if n has children:
c := children of node
for i in c:
q.append(i)
1) Как...
2965 просмотров
schedule
27.03.2023
Является ли время выполнения BFS и DFS на двоичном дереве O (N)?
Я понимаю, что время выполнения BFS и DFS на универсальном графе составляет O (n + m), где n — количество узлов, а m — количество ребер, и это связано с тем, что для каждого узла необходимо учитывать его список смежности. Однако каково время...
21802 просмотров
schedule
08.05.2022
Фермер, волк, коза и капуста Поиск в ширину и в глубину в Java
Итак, я начал эту задачу, где я должен перевезти капусту, волка и козу через реку, не оставляя капусту с козой или волка и козу поодиночке на одной стороне.
Я начал и сильно запутался в том, как подойти к этому. По сути, я думал добавить кучу...
3326 просмотров
schedule
15.12.2022
Почему временная сложность DFS и BFS зависит от способа представления графа?
Сайт http://web.eecs.utk.edu/~huangj/CS302S04/notes/graph-searching.html описывает, что при использовании списка смежности DFS и BFS имеют сложность O(V+E), а если используется матрица смежности, сложность равна O (В 2 ). Почему это?
24806 просмотров
schedule
20.10.2023
Оптимизация обмена монет
Я пытаюсь решить эту проблему:
Предположим, у меня есть набор из n монет {a_1, a2, ..., a_n}. Монета со значением 1 всегда будет появляться. Какое минимальное количество монет мне нужно, чтобы достичь M?
Ограничения:
1 ≤...
1359 просмотров
schedule
15.12.2023
Поиск в ширину, как найти конкретный путь из нескольких ветвей
Итак, я понимаю поиск в ширину , но у меня проблемы с реализацией. Когда есть несколько ветвей, вы расширяете ребра или преемников каждой ветви на каждой итерации функции. Но когда один из ваших узлов возвращает GOAL, как вы получаете все...
105 просмотров
schedule
16.02.2022
глубина поиска в ширину
Я новичок в Algos и DS. Мне нужно реализовать веб-краулер с помощью BFS. Я зашел так далеко... но, поскольку я использую очередь, я не могу получить глубину.
public void BFS() {
String link = "";
while (mainSet.size() <= 100...
486 просмотров
schedule
04.02.2023
