BFS: търсене в ширина в Python

Проблем

Шест улици вместо четири

Диспечерът на куриерите иска маршрут от склада до болницата с най-малко улици. В града всяка улица е светофар, завой и спиране, затова броят улици е по-важен от метрите.

Колегата е написал търсене, което тръгва по първата свободна улица и продължава, докато стигне. Ако заседне, се връща и опитва следващата:

def any_route(graph, at, target, seen):
    if at == target:
        return [at]
    seen.add(at)
    for nxt in graph[at]:
        if nxt in seen:
            continue
        rest = any_route(graph, nxt, target, seen)
        if rest is not None:
            return [at] + rest
    return None

route = any_route(graph, "Склад", "Болница", set())
print(" → ".join(route) + ": " + str(len(route) - 1) + " улици")

Склад → Гара → Площад → Пазар → Парк → Стадион → Болница: 6 улици

Път има, но е с 6 улици. Погледни картата от предишния урок: Склад → Гара → Площад → Кино → Болница са 4. Търсенето не е сгрешило: то не е питало за най-краткия, а е взело първия, който е намерило.

Идеята

Вълна от склада

Представи си, че от склада тръгва вълна. Първо стига до всички спирки на една улица разстояние. После от тях до всички нови на две. После на три. Спирка, до която вълната е стигнала, вече е заета: следващите вълни не я пипат.

Така спирката получава разстояние в момента, в който вълната я докосне за първи път, а то е най-малкото възможно.

Редът „първо по-близките“ го пази опашка: откритите спирки влизат отзад, а обработваната излиза отпред. Това е BFS (breadth-first search, обхождане в ширина).

dist пази разстоянието на всяка открита спирка. Той е и множеството на видените: спирка с dist не влиза в опашката втори път.
prev пази откъде е открита всяка спирка. С него после се връща самият път.

Виж го

Слой по слой

from collections import deque


def bfs(graph, start):
    dist = {start: 0}
    prev = {}
    queue = deque([start])
    while queue:
        stop = queue.popleft()
        for nxt in graph[stop]:
            if nxt in dist:
                continue
            dist[nxt] = dist[stop] + 1
            prev[nxt] = stop
            queue.append(nxt)
    return dist, prev

def bfs(graph, start):
    dist = {start: 0}
    prev = {}
    queue = deque([start])
    while queue:
        stop = queue.popleft()
        for nxt in graph[stop]:
            if nxt in dist:
                continue
            dist[nxt] = dist[stop] + 1
            prev[nxt] = stop
            queue.append(nxt)
    return dist, prev


def path_to(prev, target):
    path = []
    at = target
    while at is not None:
        path.append(at)
        at = prev.get(at)
    path.reverse()
    return path

Стъпка по стъпка, с думи

Започваме от Склад: dist = 0 и е единствената спирка в опашката.
Склад излиза от опашката. Съседите Гара и Пазар са нови: dist = 1, prev = Склад, и влизат в края на опашката.
Гара: Склад вече има dist и се прескача. Площад получава dist = 2.
Пазар също вижда Площад, но Площад вече е в опашката с dist = 2. Всяка спирка влиза в опашката само веднъж. Парк: dist = 2.
Слой 2 излиза от опашката и отваря слой 3: Кино отвъд моста и Стадион. В опашката има най-много два слоя, по-близкият е отпред.
Кино открива Болница: dist = 4. Когато и Стадион стигне до нея, тя вече има dist: първото пристигане е най-краткото.
Около Болница няма нищо ново. Опашката е празна: всяка спирка има разстоянието си от Склад.
pathTo върви назад по prev: Болница ← Кино ← Площад ← Гара ← Склад. Обърнат, това е маршрутът: 4 улици.

Програмата пуска BFS от склада, печата разстоянието до всяка спирка и пътя до болницата:

dist, prev = bfs(graph, "Склад")
for stop in stops:
    print(stop + ": " + str(dist[stop]))
path = path_to(prev, "Болница")
print(" → ".join(path) + ": " + str(len(path) - 1) + " улици")

Склад: 0
Гара: 1
Пазар: 1
Площад: 2
Парк: 2
Кино: 3
Болница: 4
Стадион: 3
Склад → Гара → Площад → Кино → Болница: 4 улици

deque от collections е опашка: append слага отзад, popleft взима отпред. Как работи опашката отвътре, е в урока „Стек и опашка“.

Пробвай

Подреди редовете

Това е сърцето на BFS: едно завъртане на цикъла. Подреди редовете:

prev[nxt] = stop
for nxt in graph[stop]:
dist[nxt] = dist[stop] + 1
stop = queue.popleft()
queue.append(nxt)
continue
if nxt in dist:

Пробвай

Предвиди изхода

Същият BFS, но тръгва от Кино. Какво печата програмата за Склад, Стадион и Парк?

dist, prev = bfs(graph, "Кино")
print(*(dist[s] for s in ["Склад", "Стадион", "Парк"]))

Отговор

3 3 4

4 2 3

3 2 3

Идеята

Пътят назад

dist казва колко улици са, но не кои. Пътят е в prev: Болница е открита от Кино, Кино от Площад, Площад от Гара, Гара от Склад. Склад няма prev, защото оттам е тръгнало всичко.

Затова пътят се чете отзад напред: от целта по prev до началото, а накрая се обръща.

def path_to(prev, target):
    path = []
    at = target
    while at is not None:
        path.append(at)
        at = prev.get(at)
    path.reverse()
    return path

at = target
while at is not None:
    path.append(at)
    at =

По-точно, за любопитните

Пътищата в prev образуват дърво: всяка спирка сочи една-единствена, тази, от която е открита, а коренът е складът. Това се казва дърво на BFS. Всеки клон от корена до спирка е най-краткият път до нея. Затова един BFS от склада дава най-късите пътища до всички спирки наведнъж, не само до болницата.

Ако спирката изобщо не е открита (няма път), тя няма dist. Провери това, преди да викаш path_to: иначе ще получиш „път“ от една спирка, самата цел.

Идеята

Защо първото пристигане е най-краткото

Опашката държи най-много два слоя: d и d + 1, като по-близкият е отпред. Спирка на d + 1 улици се открива от спирка на d улици, а спирките на d + 2 идват чак когато започнат да излизат тези на d + 1. Затова спирката получава dist от най-краткия път, а всеки по-късен път до нея е поне толкова дълъг и се прескача.

Тук е важно и кога спирката се отбелязва като видяна: в момента, в който влиза в опашката, а не когато излиза. Иначе Площад, който се вижда и от Гара, и от Пазар, щеше да влезе два пъти.

По-точно, за любопитните

Доказателството в една фраза: по индукция по d, всички спирки на разстояние d излизат от опашката преди всички на разстояние d + 1, и всяка получава dist = d. Това важи само ако всяко ребро струва 1. Ако улиците имат различни дължини, по-малко улици не значи по-малко метри. Тогава опашката се сменя с приоритетна опашка по изминатото разстояние, и това е Dijkstra (урокът за Dijkstra в този модул).

Идеята

Колко струва

Всяка спирка влиза в опашката най-много веднъж и излиза веднъж. Когато излезе, поглежда своите улици. Двупосочна улица се вижда от двата си края. Общо: V излизания и 2E погледа, O(V + E).

Това важи за списък от съседи. С матрица „кои са съседите“ е целият ред, и BFS прави V погледа на спирка: O(V²). Пусни и двата върху град-решетка от n кръстовища:

BFS със списък от съседи O(n)
BFS с матрица O(n²)

Алгоритъм	n = 10	n = 1000	n = 5000	n = 100 000
BFS със списък от съседи	36	4872	24 716	498 734
BFS с матрица	110	1 001 000	25 005 000	≈ 10 002 000 000

Кодът се пуска в твоя браузър на JavaScript. Броят операции е същият на всеки език, защото алгоритъмът е същият. Времето зависи от машината, затова е само за сравнение. „≈“ е оценка по кривата: толкова голямо n не пускаме, за да не замръзне страницата.

def bfs(graph, start):
    dist = {start: 0}
    prev = {}
    queue = deque([start])
    while queue:
        stop = queue.popleft()
        for nxt in graph[stop]:
            if nxt in dist:
                continue
            dist[nxt] = dist[stop] + 1
            prev[nxt] = stop
            queue.append(nxt)
    return dist, prev

Броят се всяка спирка, излязла от опашката, и всеки поглед към съсед. При 1000 кръстовища списъкът прави 4 872 операции, а матрицата 1 001 000. При 100 000 кръстовища списъкът прави 498 734, около 5 на кръстовище: едно излизане и до 4 улици. Матрицата при 5000 вече е 25 005 000.

Пробвай

Намери грешката

Колега реши, че разстоянието на новата спирка е „следващият номер“. Програмата печата:

def bfs(graph, start):
    dist = {start: 0}
    prev = {}
    queue = deque([start])
    while queue:
        stop = queue.popleft()
        for nxt in graph[stop]:
            if nxt in dist:
                continue
            dist[nxt] = len(dist)
            prev[nxt] = stop
            queue.append(nxt)
    return dist, prev

Склад: 0
Гара: 1
Пазар: 2
Площад: 3
Парк: 4
Кино: 5
Болница: 7
Стадион: 6
Склад → Гара → Площад → Кино → Болница: 4 улици

Пътят е верен, 4 улици, а Болница излиза на 7. На кой ред е грешката?

Избери реда с грешката.

По-точно

Опашката във всеки език

collections.deque взима отпред за O(1). list.pop(0) мести всички останали елементи с едно място: O(n) на всяко взимане, и BFS става O(V²) дори със списък от съседи. Това е най-честата причина BFS на Python да е бавен. queue.Queue пък е за нишки и е по-бавна заради заключването.

Упражнение

Слоевете на града

Реши задачата в редактора си.

Слоеве и мостове. С BFS от склада изведи спирките по слоеве (спирките на всеки слой в реда на stops) и най-далечната спирка. После затвори двата моста: махни ги от списъка от съседи, пусни BFS пак и изведи до кои спирки вече не се стига.

bridges = [
    ("Пазар", "Парк"), ("Площад", "Кино"),
]

Слой 0: Склад
Слой 1: Гара, Пазар
Слой 2: Площад, Парк
Слой 3: Кино, Стадион
Слой 4: Болница
Най-далеч: Болница (4 улици)
Без мостовете не се стига до: Парк, Кино, Болница, Стадион

Още задачи

Най-близката аптека. Някои спирки имат аптека. Пусни един BFS, който тръгва едновременно от всички аптеки (всички са в опашката с dist 0), и изведи за всяка спирка колко улици я делят от най-близката.
Лабиринт от сгради. Складът е решетка от рафтове (#) и пътеки (.). Намери най-малко стъпки от входа до изхода, като съседите на клетка са горе, долу, ляво и дясно.
Всички най-къси. Преброй колко различни най-къси пътя има от склада до всяка спирка.

Тест

Провери се

1. Защо първият път, по който BFS стига до спирка, е най-краткият в улици?Защото BFS опитва всички пътища и пази най-краткияОпашката обработва всички спирки на d улици, преди да стигне до тези на d + 1Защото съседите в списъка са подредени по разстояние

2. Колега смени опашката със стек: взима последната добавена спирка. Какво става?Обходът спира да върви на слоеве, и dist може да излезе по-голямо от най-краткотоНищо: редът няма значениеПрограмата зацикля

3. Улиците имат дължини в метри. Дава ли BFS най-краткия път в метри?Да, ако списъкът от съседи пази и метритеДа, винагиНе: BFS брои улиците, всяка улица е една стъпка, колкото и да е дълга

4. Колко работа прави BFS върху град с V кръстовища и E улици, пазен като списък от съседи?O(V + E): всяка спирка излиза веднъж, всяка улица се поглежда два пътиO(V · E)O(V²)

BFS: най-малко спирки

Бисквитки