Для чего поиск в ширину полезен?
Вот другой пример, который был протестирован и будет соответствовать поиску & шаблоны замены:
import fileinput
import sys
def replaceAll(file,searchExp,replaceExp):
for line in fileinput.input(file, inplace=1):
if searchExp in line:
line = line.replace(searchExp,replaceExp)
sys.stdout.write(line)
использование В качестве примера:
replaceAll("/fooBar.txt","Hello\sWorld!$","Goodbye\sWorld.")
8 ответов
Когда вы хотите достичь узла, пройдя как можно меньше ребер, то есть когда вы хотите найти кратчайший путь в невзвешенном графе.
Также пространственная сложность - сначала глубина поиск может быть выше, чем поиск в ширину, когда, например, каждый узел имеет только один дочерний узел, т.е. когда граф глубокий, но не очень широкий.
Если ваш домен поиска бесконечен, поиск в глубину не гарантирует прекращения / поиска решения, даже если конечное решение действительно существует.
Также вы можете видеть более сложные алгоритмы, такие как A *, как особый подтип поиска в ширину.
В целом, bfs является оптимальным и полным (с конечным фактором ветвления), а dfs - нет.
1119626]
Может использоваться для решения задачи поиска с минимальным количеством шагов. Углубление вначале может привести (если не ограничено каким-либо образом) к бесконечной глубине.
Пример: поиск ближайшего к корню узла, который удовлетворяет условию.
Одним из примеров является обход файловой системы (с ограниченной рекурсивной глубиной).
Согласно wikipedia , это также полезно для некоторых алгоритмов графов (двудольность, связанные компоненты).
Когда вам нужно получить кратчайший путь к вершине из графа без веса ребер.
При глубоком первом поиске вы можете найти «локальные» решения - чтобы действительно найти глобальное решение, вам нужно пройти через весь граф (или использовать эвристику).
BFS иногда действительно полезен. Предположим, у вас есть дерево, которое представляет, скажем, WBS. Вы можете захотеть представить вашему пользователю только 1 его уровень.
Когда имеет смысл использовать поиск в ширину?
Например, когда вам нужно найти кратчайший путь на графе - DFS просто не может который. Есть и другие приложения, но в целом DFS и BFS - это один и тот же алгоритм, работающий с разными структурами данных (BFS использует очередь, а DFS работает со стеком).