Comments 21
Все же не правильно говорить, что отличие только в структуре данных - в Дейкстры и А* используется дополнительная информация (в принципе она может быть добавлена и в алгоритм в ширину как количество переходов).
Но да, безусловно все методы можно обощить до одного алгоритма с разными стратегиями обхода.
Я бы сказал, что Дейкстра - частный случай обхода в ширину с оптимизацией по начальному пути.
А А* - частный случай обхода в ширину с оптимизацией по начальному и предполагаемому пути.
К сожалению, не всё так просто, и у алгоритмов есть несколько отличий, которые автор не учёл. Начну с поиска в глубину. Алгоритм автора жадно кладёт в стек (и отмечает "серыми") всех соседей посещённой вершины, в то время как настоящий алгоритм делает это строго по одной. Да и "чёрным" автор красит вершину слишком рано, настоящий алгоритм делает это только с полностью обработанными вершинами...
Это не простая придирка, это всё приводит к неправильному порядку обхода. Так, на картинке из поста
должен быть переход из 11 в 7, но его нет.
К поиску в ширину претензий нет.
А вот алгоритм Дейкстры снова некорректный: автор забыл обновлять приоритеты после обновления веса вершины. На картинке это не заметно, поскольку автор хитро построил путь из "единичек" до целевого узла, да и альтернативных путей там маловато. Но вот в таком графе:
алгоритм при попытке найти путь между вершинами 1 и 4 выберет прямой переход стоимостью 5 вместо пути 1-5-3-4 стоимостью 4, потому что у вершины 3 окажется приоритет 11.
По поводу поиска в глубину. Формулировка "настоящий алгоритм делает это строго по одной" не совсем ясна. Что значит "настоящий алгоритм"? Обратимся например к википедии и увидим: "Кладём в стек всех её белых соседок в порядке, обратном порядку обхода (если таковой важен)."
Перехода из 11 в 7 быть не должно. Ровно по той же причине, почему нет перехода в узел 1. Ведь они лежат ниже в стеке чем узла, добавленные позднее.
По поводу алгоритма Дейкстры. Действительно, массив
self.distancesбудет обновляться, т.к. передан в класс по ссылке, а веса внутри элементов кучи останутся старыми.
Настоящий DFS — рекурсивный. Нерекурсивные варианты возможны, но если они обходят вершины в другом порядке — они уже не могут называться поиском/обходом в грлубину.
Перехода из 11 в 7 быть не должно. Ровно по той же причине, почему нет перехода в узел 1. Ведь они лежат ниже в стеке чем узла, добавленные позднее.
Это вы объясняете с точки зрения своей реализации. Но в DFS переход из 11 в 7 быть обязан.
Настоящий DFS — рекурсивный
Не уверен, что это так. По крайней мере никогда не встречал такого утверждения, что рекурсивный - настоящий, а итеративный - ненастоящий.
Итеративный тоже может быть настоящим. Но он должен обходить вершины в том же порядке что и рекурсивный.
Я правда никогда не встречал такого термина "настоящий DFS". Поделитесь, пожалуйста, если где-то кроме этой беседы он присутствует.
Возможно, если бы нам важен был порядок обхода, то имело бы место такое замечание. И нужно бы было, как говорит Википедия развернуть порядок вершин при укладывании их в стек. Но мы здесь решаем простую задачу - хотим понять, есть ли путь от одной вершины до другой. Поэтому порядок обхода нам не важен.
Можно представить себе, что в списке соседей каждого узла соседи лежат в обратном порядке, или при выборе соседей мы разворачиваем получаемый список, и тогда мы пойдём по-другому. Так, как вам кажется "по-настоящему".
Я правда никогда не встречал такого термина "настоящий DFS". Поделитесь, пожалуйста, если где-то кроме этой беседы он присутствует.
Потому что есть просто DFS, а есть другие алгоритмы, которые DFS не являются. Прилагательное "настоящий" я использую чтобы различить тот алгоритм, который является DFS, и тот алгоритм, который вы считаете DFS.
Но мы здесь решаем простую задачу — хотим понять, есть ли путь от одной вершины до другой. Поэтому порядок обхода нам не важен.
Прежде всего, вы здесь сравниваете алгоритмы, и показываете их реализацию.
К слову, DFS вообще редко используется именно для поиска пути. Основное использование DFS — топологическая сортировка, и вот там порядок обхода как раз важен (собственно, он и является выходом алгоритма).
Можно представить себе, что в списке соседей каждого узла соседи лежат в обратном порядке, или при выборе соседей мы разворачиваем получаемый список, и тогда мы пойдём по-другому. Так, как вам кажется "по-настоящему".
Ну да, ваш граф такой, что и правда можно придумать такой порядок выбора соседей при котором ваш алгоритм даст такой же результат что и DFS. Но требуется-то девать верный результат на любых исходных данных, а не на конкретных!
У Седжвика DFS определяется как рекурсивный алгоритм, и затем строятся аналогичные итеративные алгоритмы. Алгоритм из статьи, когда порядок посещения узлов не соответствует DFS, обсуждается как не являющийся поиском в глубину, но заслуживающий внимания как раз по причине, вынесенной в заголовок статьи.
У Кормена к ключевым свойствам DFS относятся свойства, происходящие из рекурсивной структуры вызовов. В том числе, моменты открытия и закрытия вершин (покраски в серый и черный) должны образовывать скобочную структуру. Как @mayorovp и написал, в статье это происходит в нарушенном порядке.
На практике где-то конечно разница может быть не важна, но раз разговор зашел про настоящий, то есть строгие критерии.
На практике где-то конечно разница может быть не важна, но раз разговор зашел про настоящий, то есть строгие критерии.
Важна эта разница. Алгоритм из статьи нельзя использовать для поиска двусвязных компонент в графе.
конечно же можно.
Если граф имеет две компоненты связности, то мы просто не попадём из одной компоненты связности в другую, т.к. ходим только по рёбрам.
И ещё раз повторю. Мы здесь решаем другую задачу - поиск пути в графе.
Нет, вы этим вашим алгоритмом не сможете найти компоненты двусвязности. Ибо алгоритм поиска этих компонент использует фишку, что ребра могут идти только к потомкам (и их можно игнорировать) или к предку (и это можно использовать для нахождения самого высокого предка в текущей компоненте двусвязности.
Да, ваша модификация обхода в глубину ищет произвольный путь в графе. Но это не тот же самый "настоящий" обход в ширину, о котором доказаны всякие леммы и теоремы.
В этой ветке разговор о разнице между "настоящим" алгоритмом и вашим. И она есть. Даже если вашим алгоритмом тоже можно найти произвольный путь в графе.
"Настоящий" DFS обладает некоторыми уникальными свойствами.
Одно из них, весьма важное: если построить дерево из ребер, по которым DFS прошелся, то все оставшиеся в графе ребра будут идти между вершиной и ее предком в этом дереве. Никаких ребер между ветками не будет. Потому что "настоящая", рекурсивная реализация обязательно бы прошла по этому ребру когда была бы рекурсивно вызвана от первой из двух вершин.
Именно это свойство позволяет использовать DFS при поиске мостов, точек сочленения и всяких двусвязных компонент в графах.
В вашей реализации этого свойства нет. Переход из 11 в 7 не произойдет никогда, потому что 7 уже в стеке и серого цвета. Но если прехода нет, то алгоритм перейдет в 7 из 4, а ребро 11-7 будет как раз между двумя ветками дерева.
Но это можно исправить. Не надо красить вершины в серый цвет при запихивании в стек. В этом случае вершины в стеке будут много раз, поэтому при доставании надо проверить, а не черная ли вершина. Другой вариант, надо для каждой вершины хранить состояние — какой ее сосед еще не просмотрен. Брать из стека. Если еще не все дети просмотрены, сдвигать состояние и запихивать и эту вершину и ее соседа.
Такие реализации идентичны и в обходе в ширину и в обходе в глубину. Но вот дейкстру с A* на этот глобус уже натянуть не получится.
Помнится, давным-давно, с десяток лет назад, читал в какой-то книге (вроде BGL book) что алгоритм Прима и Краскала - это один алгоритм с минимальными отличиями. И им удалось сделать одну абстракцию, которую можно было compile-time флагами переключить с одной реализации на другую.
Я тогда подумал, что абстракция с таким функционалом могла бы выглядеть так:
void msp(/*...*/) {
#ifndef USE_KRUSKAL
_prim(/*...*/);
#else
_kruskal(/*...*/);
#endif // USE_KRUSKAL
}
Формально, то же самое, что сделали они... Но где же та грань, между "это один и тот же алгоритм, просто с разными настройками" и "я просто выбираю более подходящий алгоритм из списка решающих мою задачу".
А этой грани не существует, из-за отсутствия точного определения. Как и у вас: эдак можно любую программу назвать просто еще одной разновидностью алгоритма: на входе сигнал, на выходе сигнал, внутри только чет поменяли.
Но спасибо, что в очередной раз привлекаете внимание к алгоритмам: в любом случае приятно освежить в памяти.
Команда Яндекс Практикума, раз уж вы продолжаете рекламировать свои курсы, хочу напомнить, что 12 января в 12:00 буду ждать вас в суде по делу о не качественно оказанных образовательных услугах. Предложенная вами компенсация за отзыв заявления хоть и покрывает стоимость прошедшего курса, но не полностью покрывает затрат на адвоката, т.ч. был вынужден отказаться от нее.
Остальным, крайне не рекомендую связываться с яндекс практикумом.
Поиск в глубину, поиск в ширину, алгоритмы Дейкстры и А* — это один и тот же алгоритм