Публикации по теме 'depth-first-search'
ГЛУБИННЫЙ ПОИСК
… введение
Поиск в глубину ( DFS ) - это алгоритм обхода или поиска структур данных в виде дерева или графа. Алгоритм начинается с корневого узла (выбирая некоторый произвольный узел в качестве корневого узла в случае графа) и исследует, насколько это возможно, вдоль каждой ветви перед обратным отслеживанием.
Прежде чем продолжить, давайте формально определим граф и некоторые из его компонентов;
Узел (также называемый вершиной): это фундаментальная часть всех графов. Он..
Вопросы по теме 'depth-first-search'
Почему я получаю StackOverFlowError при попытке DFS этого графа?
Я пытаюсь написать алгоритм, который определяет, связан ли граф или нет. Я думаю, что мой код почти правильный, хотя я продолжаю получать StackOverFlowError. Я лично думаю, что из-за того, что в графе, с которым я тестирую свой алгоритм, есть цикл,...
486 просмотров
schedule
26.10.2023
Завершить итеративный поиск в глубину с углублением
На данный момент у меня есть объект, который выглядит примерно так.
C#
public class Step {
int id;
List<Step> nextSteps;
}
И я пытаюсь преобразовать его в другой объект, который выглядит очень похоже, за исключением того факта, что...
1976 просмотров
schedule
10.11.2023
Нечетный порядок в итеративной DFS по сравнению с рекурсивной DFS
Я решаю эту проблему dfs/bfs .
Я написал как итеративную версию, так и рекурсивную версию DFS.
Порядок посещения узла другой, и я не понимаю, почему.
итеративный поиск в глубину:
static void DFS (Integer root, Graph graph){
//...
2327 просмотров
schedule
16.11.2023
Реализация графика в Java
Мне дали задание реализовать график в java. В конечном итоге он будет использоваться для тестирования методов поиска (сначала в ширину, сначала в глубину и итеративное углубление). Три создаваемых класса должны реализовать три соответствующих...
4944 просмотров
schedule
25.10.2023
Бесконечный цикл и рекурсия в Python
Я работаю над реализацией итеративного поиска с углублением в глубину, чтобы найти решения для проблемы-головоломки 8 . Я не заинтересован в поиске самих фактических путей поиска, а просто в том, чтобы определить, сколько времени требуется для...
2412 просмотров
schedule
29.09.2022
Реализация обхода в глубину для графа с использованием матрицы смежности C++
У меня есть набор узлов и несколько ребер, которые представляют, какие узлы связаны. V_nodes 1 7 22 97 48 11 V_arcs (1 22) (97 22) (7 1) (11 48) (48 7) (11 0) V_weight 1
Я создал его матрицу смежности, которая показывает 1 для соединенных и 0 для...
4169 просмотров
schedule
21.01.2024
Решатель 8 плиток с повторяющимися узлами — Python
Я пытаюсь решить головоломку с 8 плитками, используя такие методы, как поиск BFS, DFS, Greedy и A *, используя манхэттенское расстояние в качестве моего эвристического решения.
Проблема в том, что, хотя я могу решить большое количество задач,...
3413 просмотров
schedule
27.09.2022
Все возможные пути
В настоящее время я работаю над ИИ для игры в Dots ( ссылка ). Цель состоит в том, чтобы удалить как можно больше точек, соединив точки одинакового цвета линией. Я просмотрел доску и сгруппировал каждый набор соседних точек одного цвета. Все группы...
195 просмотров
schedule
01.01.2024
Ребра графа
Чтобы найти вид ребер графа, на котором мы применили алгоритм поиска в глубину, мы могли бы использовать это:
ребра дерева: x -> y, когда [d[y],f[y]] ⊂ [d[x],f[x]]
передние ребра: x -> y, когда [d[x],f[x]] ⊂ [d[y],f[y]]
задние ребра: x -> y,...
518 просмотров
schedule
30.10.2023
Как найти наименьшее значение, достижимое из узла в DAG за линейное время?
Я пытаюсь следовать 3.25(a) с http://seed.ucsd.edu/mediawiki/images/4/43/Sol3.pdf
Я понимаю, что сначала вам нужно выполнить топологическую сортировку на графике. Но я не понимаю, как они получают min в cost[w]. Если есть 2 исходящих ребра из...
276 просмотров
schedule
25.11.2023
Отношение эквивалентности в DFS
Я читаю о компонентах с сильной связью по ссылке ниже.
https://www.ics.uci.edu/~eppstein/161/960220.html
Здесь автор упомянул
Напомним, что отношение — это еще одно слово для набора пар объектов (если хотите, вы можете думать об отношении...
329 просмотров
schedule
10.01.2024
Отфильтруйте список иерархии и сохраните путь
В С#, как я могу выполнить поиск в списке иерархии, а также сохранить путь в конце. Например:
Объект
public class Node
{
public IEnumerable<Node> Children { get; set; }
public string Id { get; set; }
}
Результат...
645 просмотров
schedule
29.12.2023
Можно ли использовать DFS для распознавания звездных образов?
Я изучаю искусственный интеллект. Я читал лекцию по нейронным сетям, и в качестве примера мой учитель привел пример подсчета всех звезд в наблюдаемой Вселенной. Обсуждение продолжилось и остановилось на сопоставлении с образцом. Поскольку время...
174 просмотров
schedule
12.02.2024
Сколько различных DFS и BFS мы можем сделать из графа? у DFS больше разнообразия или у BFS?
я пытаюсь выяснить, сколько разных деревьев BFS и DFS я могу построить из данного графа, если это невозможно точно определить, тогда я хочу знать, имеет ли DFS больше разнообразия, чем BFS, уверен, что все они связаны с данный график!
Спасибо
74 просмотров
schedule
26.09.2022
Как посчитать суммарный вес путей ориентированного взвешенного графа в DFS за одну итерацию?
G = (V,E) - ориентированный взвешенный граф.
D -> G (w:4)
D -> C (w:2)
D -> E (w:2)
C -> F (w:5)
C -> A (w:4)
B -> D (w:3)
B -> E (w:10)
G -> F (w:1)
E -> G (w:6)
A -> D (w:1)
A -> B (w:2)
изображение
Я...
1486 просмотров
schedule
27.11.2023
Поиск в глубину в Satstuma Graph
Есть ли простой способ выполнить поиск в глубину на графике с помощью Satsuma Graph в .NET? В документации Satsuma я обнаружил, что clas DFS является абстрактным, поэтому у него не может быть экземпляров, и я не знаю, как его использовать....
183 просмотров
schedule
05.11.2022
Заливка через узел поиска в глубину, связывающийся сам с собой. С++
Работа над программой решения задачи заливки:
Я считаю, что я до одного последнего вопроса. Моя структура данных выглядит следующим образом: у меня есть вектор указателей узлов, и каждый узел содержит массив целых чисел и адрес следующего узла....
83 просмотров
schedule
17.02.2024
Решение лабиринта с помощью DFS
В школьном проекте нам нужно было решить лабиринт, заданный параметром программы. Для этого нам нужно использовать алгоритм поиска в глубину.
Мне удалось найти псевдокод алгоритма DFS и даже перекодировать его с помощью C. Алгоритм способен найти...
863 просмотров
schedule
31.12.2023
Подсчитайте облака в массиве 2d
Я пытаюсь выяснить эту проблему с помощью CodeFights, но у меня нет большого опыта в обходе графа, поэтому я борюсь. Одним из советов, которые я прочитал для этой конкретной проблемы, был «обход графа», поэтому я сделал BFS, но я не уверен, как...
866 просмотров
schedule
14.03.2024
Рекурсия находит все пути в матрице графа DFS
Я пытаюсь реализовать две функции на основе поиска в глубину с использованием метода рекурсии. В конечном итоге я пытаюсь сравнить время выполнения с алгоритмом warshall (который у меня уже работает). Когда я печатаю свою матрицу, она отклоняется на...
835 просмотров
schedule
14.12.2023
