Навигация в града с BFS и Dijkstra в Python

Проблем

Куриерът пита за маршрут

Куриерската фирма от модула „Графи“ има склад в града. Картата е текстов файл, по една улица на ред: откъде, накъде и колко минути се кара по нея. - е двупосочна улица, -> е еднопосочна:

Склад - Гара 4
Склад - Пазар 3
Гара - Площад 3
Пазар - Площад 2
Пазар -> Парк 4
Площад - Кино 5
Кино - Болница 3
Парк - Стадион 2
Стадион - Болница 2
Склад - Стадион 16

Диспечерът иска маршрут от Склада до Болницата. Куриерът с велосипед пита за маршрута с най-малко кръстовища, защото на всяко спира. Куриерът с бус пита за най-бързия. Отговорите не са едни и същи.

Този проект е програмата, която чете картата и отговаря и на двата въпроса. Строиш я на стъпки, всяка с изход, с който да сравниш своя.

Идеята

Планът

Картата като граф. Кръстовищата са върхове, улиците са ребра с тегло: минутите. Както в „Граф: списък от съседи и матрица“, пазиш списък от съседи: речник от кръстовище към списък от улици.
Най-малко улици. BFS от Склада на слоеве: първо кръстовищата на една улица, после на две.
Минутите по маршрута. Сбор от минутите на улиците, за да сравниш двата отговора.
Най-бързо. Dijkstra с приоритетна опашка: винаги вади кръстовището с най-малко минути досега.
Обратно. Същата програма от Болницата към Склада. Еднопосочната улица прави пътя обратно различен.

Програмата чете картата от стандартния вход, за да работи с всяка карта. Пускаш я с файла: python3 main.py < map.txt.

Упражнение

Стъпка 1: картата

Прочети картата в речник от кръстовище към списък от улици (до кое кръстовище и колко минути). Двупосочната улица влиза в списъците и на двата края, еднопосочната само в списъка на началото. Кръстовище без изходящи улици също трябва да е в речника, с празен списък.

Отпечатай броя кръстовища и съседите на Склада, Пазара и Парка, в реда на редовете от файла:

кръстовища: 8
Склад: Гара 4, Пазар 3, Стадион 16
Пазар: Склад 3, Площад 2, Парк 4
Парк: Стадион 2

Решение

def add_street(city, a, b, minutes, two_way):
    city.setdefault(a, []).append((b, minutes))
    city.setdefault(b, [])
    if two_way:
        city[b].append((a, minutes))


def read_map(text):
    city = {}
    for line in text.strip().splitlines():
        a, kind, b, minutes = line.split()
        add_street(city, a, b, int(minutes), kind == "-")
    return city


def neighbors(city, place):
    return f"{place}: " + ", ".join(f"{to} {m}" for to, m in city[place])


city = read_map(sys.stdin.read())
print(f"кръстовища: {len(city)}")
print(neighbors(city, "Склад"))
print(neighbors(city, "Пазар"))
print(neighbors(city, "Парк"))

Най-горе е import sys (по-късно и heapq и deque).

Парк има един съсед, Стадиона: Пазар -> Парк е еднопосочна и Пазарът не е в списъка на Парка.

Упражнение

Стъпка 2: най-малко улици

Напиши fewestStreets(city, start, end): BFS от start, който спира, щом извади end, и връща маршрута като списък от кръстовища. За да построиш маршрута, пази за всяко кръстовище откъде си дошъл (prev), а после върви назад от end и обърни списъка.

най-малко улици: Склад → Стадион → Болница

Решение

def route(prev, end):
    places = []
    at = end
    while at is not None:
        places.append(at)
        at = prev.get(at)
    places.reverse()
    return places


def fewest_streets(city, start, end):
    prev = {}
    seen = {start}
    queue = deque([start])
    while queue:
        at = queue.popleft()
        if at == end:
            return route(prev, end)
        for to, _ in city[at]:
            if to not in seen:
                seen.add(to)
                prev[to] = at
                queue.append(to)
    return []


city = read_map(sys.stdin.read())
print(f"най-малко улици: {" → ".join(fewest_streets(city, "Склад", "Болница"))}")

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

Упражнение

Стъпка 3: колко минути

Добави minutesOf(city, route), който събира минутите на улиците по маршрута, и describe(city, route), който връща маршрута, броя улици и минутите. Отпечатай маршрута от стъпка 2 с describe:

най-малко улици: Склад → Стадион → Болница (2 улици, 18 мин)

Решение

def minutes_of(city, route):
    total = 0
    for a, b in zip(route, route[1:]):
        total += next(m for to, m in city[a] if to == b)
    return total


def describe(city, route):
    return f"{' → '.join(route)} ({len(route) - 1} улици, {minutes_of(city, route)} мин)"


city = read_map(sys.stdin.read())
print(f"най-малко улици: {describe(city, fewest_streets(city, "Склад", "Болница"))}")

Две улици, но 18 минути: шестнайсет от тях са по околовръстното.

Виж го

Два маршрута на една карта

def fastest(city, start, end):
    dist = {start: 0}
    prev = {}
    queue = [(0, start)]
    while queue:
        minutes, at = heapq.heappop(queue)
        if minutes > dist[at]:
            continue
        if at == end:
            return route(prev, end)
        for to, length in city[at]:
            t = minutes + length
            if to not in dist or t < dist[to]:
                dist[to] = t
                prev[to] = at
                heapq.heappush(queue, (t, to))
    return []

def fewest_streets(city, start, end):
    prev = {}
    seen = {start}
    queue = deque([start])
    while queue:
        at = queue.popleft()
        if at == end:
            return route(prev, end)
        for to, _ in city[at]:
            if to not in seen:
                seen.add(to)
                prev[to] = at
                queue.append(to)
    return []

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

Картата: 8 кръстовища и 10 улици с минутите им. Пазар → Парк е еднопосочна, околовръстното от Склад до Стадион е 16 мин.
BFS, на една улица от Склад: Гара, Пазар, Стадион. Минутите не го интересуват.
На две улици: Площад, Парк, Болница. Болница вече е в опашката, от Стадион.
Най-малко улици: Склад → Стадион → Болница, 2 улици, но 18 мин: 16 от тях са по околовръстното.
Dijkstra: опашката е подредена по минути. Склад 0, съседите му влизат в опашката: Гара 4, Пазар 3, Стадион 16.
Най-бързото в опашката е Пазар, 3 мин. Ново: Площад 5, Парк 7.
Гара, 4 мин: през него нищо не става по-бързо.
Най-бързото в опашката е Площад, 5 мин. Ново: Кино 10.
Парк с 7 мин. През него Стадион пада от 16 на 9.
Най-бързото в опашката е Стадион, 9 мин. Ново: Болница 11.
Кино, 10 мин: през него нищо не става по-бързо.
Болница излиза с 11 мин: нищо в опашката не е по-бързо, значи това е отговорът.
Най-бързо: Склад → Пазар → Парк → Стадион → Болница, 4 улици, 11 мин.
Два отговора на два въпроса: 2 улици и 18 мин или 4 улици и 11 мин. За куриера важат минутите.

BFS вижда само броя улици и избира околовръстното. Dijkstra вади кръстовищата по минути и стига до Болницата за 11 мин през Пазара, еднопосочната улица и Стадиона. Стадионът първо е с 16 мин по шосето, после пада на 9 през Парка.

Упражнение

Стъпка 4: най-бързо

Напиши fastest(city, start, end) с Dijkstra: dist пази най-малките минути досега, опашката е подредена по минути, а prev пази маршрута. Отпечатай и двата маршрута:

най-малко улици: Склад → Стадион → Болница (2 улици, 18 мин)
най-бързо: Склад → Пазар → Парк → Стадион → Болница (4 улици, 11 мин)

Решение

def fastest(city, start, end):
    dist = {start: 0}
    prev = {}
    queue = [(0, start)]
    while queue:
        minutes, at = heapq.heappop(queue)
        if minutes > dist[at]:
            continue
        if at == end:
            return route(prev, end)
        for to, length in city[at]:
            t = minutes + length
            if to not in dist or t < dist[to]:
                dist[to] = t
                prev[to] = at
                heapq.heappush(queue, (t, to))
    return []


city = read_map(sys.stdin.read())
print(f"най-малко улици: {describe(city, fewest_streets(city, "Склад", "Болница"))}")
print(f"най-бързо: {describe(city, fastest(city, "Склад", "Болница"))}")

heapq пази списъка като heap. Записите са двойки (минути, кръстовище): кортежите се сравняват първо по минутите.

Пробвай

Попълни

Кръстовище може да влезе в опашката няколко пъти, когато минутите до него паднат. Старият запис остава. Какво прави програмата, когато го извади?

if minutes > dist[at]:

Пробвай

Предвиди пътя обратно

Куриерът се връща от Болницата към Склада. Програмата пита fastest(city, "Болница", "Склад"). Какво печата?

city = read_map(sys.stdin.read())
print(f"обратно: {describe(city, fastest(city, "Болница", "Склад"))}")

Отговор

обратно: Болница → Кино → Площад → Пазар → Склад (4 улици, 13 мин)

обратно: Болница → Стадион → Склад (2 улици, 18 мин)

обратно: Болница → Стадион → Парк → Пазар → Склад (4 улици, 11 мин)

Упражнение

Стъпка 5: цялата програма

Добави пътя обратно. Цялата програма печата:

най-малко улици: Склад → Стадион → Болница (2 улици, 18 мин)
най-бързо: Склад → Пазар → Парк → Стадион → Болница (4 улици, 11 мин)
обратно: Болница → Кино → Площад → Пазар → Склад (4 улици, 13 мин)

Цялата програма

import heapq
import sys
from collections import deque


def add_street(city, a, b, minutes, two_way):
    city.setdefault(a, []).append((b, minutes))
    city.setdefault(b, [])
    if two_way:
        city[b].append((a, minutes))


def read_map(text):
    city = {}
    for line in text.strip().splitlines():
        a, kind, b, minutes = line.split()
        add_street(city, a, b, int(minutes), kind == "-")
    return city


def route(prev, end):
    places = []
    at = end
    while at is not None:
        places.append(at)
        at = prev.get(at)
    places.reverse()
    return places


def fewest_streets(city, start, end):
    prev = {}
    seen = {start}
    queue = deque([start])
    while queue:
        at = queue.popleft()
        if at == end:
            return route(prev, end)
        for to, _ in city[at]:
            if to not in seen:
                seen.add(to)
                prev[to] = at
                queue.append(to)
    return []


def minutes_of(city, route):
    total = 0
    for a, b in zip(route, route[1:]):
        total += next(m for to, m in city[a] if to == b)
    return total


def describe(city, route):
    return f"{' → '.join(route)} ({len(route) - 1} улици, {minutes_of(city, route)} мин)"


def fastest(city, start, end):
    dist = {start: 0}
    prev = {}
    queue = [(0, start)]
    while queue:
        minutes, at = heapq.heappop(queue)
        if minutes > dist[at]:
            continue
        if at == end:
            return route(prev, end)
        for to, length in city[at]:
            t = minutes + length
            if to not in dist or t < dist[to]:
                dist[to] = t
                prev[to] = at
                heapq.heappush(queue, (t, to))
    return []


city = read_map(sys.stdin.read())
print(f"най-малко улици: {describe(city, fewest_streets(city, "Склад", "Болница"))}")
print(f"най-бързо: {describe(city, fastest(city, "Склад", "Болница"))}")
print(f"обратно: {describe(city, fastest(city, "Болница", "Склад"))}")

Пробвай

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

Колега е опростил addStreet. Сега пътят обратно излиза 11 мин:

обратно: Болница → Стадион → Парк → Пазар → Склад (4 улици, 11 мин)

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

Виж го

Измери: градът расте

Истинският град има хиляди кръстовища. Решетката е проверка на скоростта: n кръстовища в квадрат, улиците са между съседите, с минути по формула. Куриерът тръгва от горния ляв ъгъл към долния десен:

def grid_city(size):
    city = {}
    for r in range(size):
        for c in range(size):
            at = f"{r}:{c}"
            if c + 1 < size:
                add_street(city, at, f"{r}:{c + 1}", 1 + (r * 7 + c * 13) % 9, True)
            if r + 1 < size:
                add_street(city, at, f"{r + 1}:{c}", 1 + (r * 11 + c * 5) % 9, True)
    return city


city = grid_city(100)
print(f"кръстовища: {len(city)}")
few = fewest_streets(city, "0:0", "99:99")
print(f"най-малко улици: {len(few) - 1} улици, {minutes_of(city, few)} мин")
fast = fastest(city, "0:0", "99:99")
print(f"най-бързо: {minutes_of(city, fast)} мин")

кръстовища: 10000
най-малко улици: 198 улици, 990 мин
най-бързо: 693 мин

Пусни двата алгоритъма в браузъра. BFS гледа всяка улица веднъж: O(n). Dijkstra също, но всеки запис в heap-а струва O(log n): O(n log n). При n = 1000 това са 3966 срещу 15 778 операции, а при n = 100 000 са 398 158 срещу 2 348 779:

BFS: най-малко улици O(n)
Dijkstra: най-бързо O(n log n)

Алгоритъм	n = 10	n = 1000	n = 100 000
BFS: най-малко улици	22	3966	398 158
Dijkstra: най-бързо	34	15 778	2 348 779

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

def fastest(city, start, end):
    dist = {start: 0}
    prev = {}
    queue = [(0, start)]
    while queue:
        minutes, at = heapq.heappop(queue)
        if minutes > dist[at]:
            continue
        if at == end:
            return route(prev, end)
        for to, length in city[at]:
            t = minutes + length
            if to not in dist or t < dist[to]:
                dist[to] = t
                prev[to] = at
                heapq.heappush(queue, (t, to))
    return []

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

Dijkstra е по-бавен, но отговаря на въпроса за минутите, а BFS не може. И двата спират, щом извадят целта: за близка цел огледат малка част от града.

Навигациите за цели държави не пускат обикновен Dijkstra от всяко място. Те предварително обработват картата (например contraction hierarchies) и търсят с A*, който добавя оценка колко остава до целта. Основата пак е Dijkstra.

Упражнение

Ремонт на улицата

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

Затворена улица. Улицата Парк – Стадион е затворена за ремонт. Добави към readMap множество от затворени улици ("Парк Стадион"), което пропуска тези редове в двете посоки. Отпечатай двата маршрута от Склада до Болницата:

най-малко улици: Склад → Стадион → Болница (2 улици, 18 мин)
най-бързо: Склад → Пазар → Площад → Кино → Болница (4 улици, 13 мин)

Още задачи

Само минутите. Напиши вариант на fastest, който връща минутите до всяко кръстовище, без да спира при целта. Кое кръстовище е най-далеч от Склада?
Без кръстовище. Площадът е затворен за събитие. Как ще го пропуснеш, без да пипаш картата?
Свободно шосе. През нощта околовръстното е празно и се кара за 6 мин. Смени минутите в картата: кой е най-бързият маршрут сега и съвпада ли с този на BFS?

Тест

Провери се

1. BFS и Dijkstra дават различни маршрути от Склада до Болницата. Кой е грешният?Dijkstra, защото минава повече улициНито един: BFS отговаря на „най-малко улици“, Dijkstra на „най-малко минути“BFS, защото е по-бавен

2. Защо BFS не намира най-бързия маршрут в този град?Улиците имат различни минути, а BFS брои всяка улица за еднаЗащото опашката е FIFOЗащото има еднопосочна улица

3. В Dijkstra записът, който излиза от опашката, понякога е с повече минути от dist. Какво прави програмата?Прескача го: кръстовището вече е извадено с по-малко минутиОбновява dist с по-голямото числоСпира

Когато минутите до кръстовище паднат, програмата слага нов запис, а старият остава в опашката. Когато старият излезе, той е остарял: minutes > dist[at], и се прескача.

4. Пазар -> Парк е еднопосочна. Какво трябва да има в списъка със съседи?Парк в съседите на Пазара, но не Пазар в съседите на ПаркаИ дветеСамо Пазар в съседите на Парка

5. Градът е решетка с n кръстовища. Как расте броят операции на двата алгоритъма?И двата O(n)И двата O(n²)BFS O(n), Dijkstra O(n log n): heap-ът добавя log n на улица

Навигация в града

Бисквитки