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

Проблем

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

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

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

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

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

Идеята

Планът

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

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

Упражнение

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

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

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

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

Решение

record Street(String to, int minutes) {}

record Stop(String place, int minutes) {}

static void addStreet(Map<String, List<Street>> city,
        String a, String b, int minutes, boolean twoWay) {
    city.computeIfAbsent(a, k -> new ArrayList<>()).add(new Street(b, minutes));
    city.computeIfAbsent(b, k -> new ArrayList<>());
    if (twoWay) city.get(b).add(new Street(a, minutes));
}

static Map<String, List<Street>> readMap(String text) {
    Map<String, List<Street>> city = new HashMap<>();
    for (String line : text.strip().split("\n")) {
        String[] p = line.trim().split("\\s+");
        addStreet(city, p[0], p[2], Integer.parseInt(p[3]), p[1].equals("-"));
    }
    return city;
}

static String neighbors(Map<String, List<Street>> city, String place) {
    List<String> parts = new ArrayList<>();
    for (Street s : city.get(place)) parts.add(s.to() + " " + s.minutes());
    return place + ": " + String.join(", ", parts);
}

String text = new String(System.in.readAllBytes(), StandardCharsets.UTF_8);
Map<String, List<Street>> city = readMap(text);
System.out.println("кръстовища: " + city.size());
System.out.println(neighbors(city, "Склад"));
System.out.println(neighbors(city, "Пазар"));
System.out.println(neighbors(city, "Парк"));

Нужни са import java.io.IOException;, import java.nio.charset.StandardCharsets; и import java.util.*;, а main е с throws IOException заради readAllBytes.

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

Упражнение

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

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

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

Решение

static List<String> route(Map<String, String> prev, String end) {
    List<String> places = new ArrayList<>();
    for (String at = end; at != null; at = prev.get(at)) places.add(at);
    Collections.reverse(places);
    return places;
}

static List<String> fewestStreets(
        Map<String, List<Street>> city,
        String start, String end) {
    Map<String, String> prev = new HashMap<>();
    Set<String> seen = new HashSet<>(List.of(start));
    Deque<String> queue = new ArrayDeque<>(List.of(start));
    while (!queue.isEmpty()) {
        String at = queue.poll();
        if (at.equals(end)) return route(prev, end);
        for (Street s : city.get(at)) {
            if (seen.add(s.to())) {
                prev.put(s.to(), at);
                queue.add(s.to());
            }
        }
    }
    return List.of();
}

String text = new String(System.in.readAllBytes(), StandardCharsets.UTF_8);
Map<String, List<Street>> city = readMap(text);
System.out.println("най-малко улици: " + String.join(" → ", fewestStreets(city, "Склад", "Болница")));

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

Упражнение

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

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

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

Решение

static int minutesOf(Map<String, List<Street>> city, List<String> route) {
    int total = 0;
    for (int i = 1; i < route.size(); i++) {
        for (Street s : city.get(route.get(i - 1))) {
            if (s.to().equals(route.get(i))) {
                total += s.minutes();
                break;
            }
        }
    }
    return total;
}

static String describe(Map<String, List<Street>> city, List<String> route) {
    return String.join(" → ", route) + " (" + (route.size() - 1) + " улици, "
            + minutesOf(city, route) + " мин)";
}

String text = new String(System.in.readAllBytes(), StandardCharsets.UTF_8);
Map<String, List<Street>> city = readMap(text);
System.out.println("най-малко улици: " + describe(city, fewestStreets(city, "Склад", "Болница")));

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

Виж го

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

static List<String> fastest(
        Map<String, List<Street>> city,
        String start, String end) {
    Map<String, Integer> dist = new HashMap<>();
    Map<String, String> prev = new HashMap<>();
    PriorityQueue<Stop> queue = new PriorityQueue<>(
            Comparator.comparingInt(Stop::minutes));
    dist.put(start, 0);
    queue.add(new Stop(start, 0));
    while (!queue.isEmpty()) {
        Stop stop = queue.poll();
        String at = stop.place();
        if (stop.minutes() > dist.get(at)) continue;
        if (at.equals(end)) return route(prev, end);
        for (Street s : city.get(at)) {
            int t = stop.minutes() + s.minutes();
            Integer best = dist.get(s.to());
            if (best == null || t < best) {
                dist.put(s.to(), t);
                prev.put(s.to(), at);
                queue.add(new Stop(s.to(), t));
            }
        }
    }
    return List.of();
}

static List<String> fewestStreets(
        Map<String, List<Street>> city,
        String start, String end) {
    Map<String, String> prev = new HashMap<>();
    Set<String> seen = new HashSet<>(List.of(start));
    Deque<String> queue = new ArrayDeque<>(List.of(start));
    while (!queue.isEmpty()) {
        String at = queue.poll();
        if (at.equals(end)) return route(prev, end);
        for (Street s : city.get(at)) {
            if (seen.add(s.to())) {
                prev.put(s.to(), at);
                queue.add(s.to());
            }
        }
    }
    return List.of();
}

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

Картата: 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 мин)

Решение

static List<String> fastest(
        Map<String, List<Street>> city,
        String start, String end) {
    Map<String, Integer> dist = new HashMap<>();
    Map<String, String> prev = new HashMap<>();
    PriorityQueue<Stop> queue = new PriorityQueue<>(
            Comparator.comparingInt(Stop::minutes));
    dist.put(start, 0);
    queue.add(new Stop(start, 0));
    while (!queue.isEmpty()) {
        Stop stop = queue.poll();
        String at = stop.place();
        if (stop.minutes() > dist.get(at)) continue;
        if (at.equals(end)) return route(prev, end);
        for (Street s : city.get(at)) {
            int t = stop.minutes() + s.minutes();
            Integer best = dist.get(s.to());
            if (best == null || t < best) {
                dist.put(s.to(), t);
                prev.put(s.to(), at);
                queue.add(new Stop(s.to(), t));
            }
        }
    }
    return List.of();
}

String text = new String(System.in.readAllBytes(), StandardCharsets.UTF_8);
Map<String, List<Street>> city = readMap(text);
System.out.println("най-малко улици: " + describe(city, fewestStreets(city, "Склад", "Болница")));
System.out.println("най-бързо: " + describe(city, fastest(city, "Склад", "Болница")));

PriorityQueue<Stop> с Comparator.comparingInt(Stop::minutes) вади записа с най-малко минути. record Stop е двойката кръстовище и минути. Нужен е dist.get в Integer, защото за ново кръстовище е null.

Пробвай

Попълни

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

if (stop.minutes() > dist.get(at)) ;

Пробвай

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

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

String text = new String(System.in.readAllBytes(), StandardCharsets.UTF_8);
Map<String, List<Street>> city = readMap(text);
System.out.println("обратно: " + describe(city, fastest(city, "Болница", "Склад")));

Отговор

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

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

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

Упражнение

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

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

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

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

import java.io.IOException;
import java.nio.charset.StandardCharsets;
import java.util.*;

record Street(String to, int minutes) {}

record Stop(String place, int minutes) {}

public class Main {
    static void addStreet(Map<String, List<Street>> city,
            String a, String b, int minutes, boolean twoWay) {
        city.computeIfAbsent(a, k -> new ArrayList<>()).add(new Street(b, minutes));
        city.computeIfAbsent(b, k -> new ArrayList<>());
        if (twoWay) city.get(b).add(new Street(a, minutes));
    }

    static Map<String, List<Street>> readMap(String text) {
        Map<String, List<Street>> city = new HashMap<>();
        for (String line : text.strip().split("\n")) {
            String[] p = line.trim().split("\\s+");
            addStreet(city, p[0], p[2], Integer.parseInt(p[3]), p[1].equals("-"));
        }
        return city;
    }

    static List<String> route(Map<String, String> prev, String end) {
        List<String> places = new ArrayList<>();
        for (String at = end; at != null; at = prev.get(at)) places.add(at);
        Collections.reverse(places);
        return places;
    }

    static List<String> fewestStreets(
            Map<String, List<Street>> city,
            String start, String end) {
        Map<String, String> prev = new HashMap<>();
        Set<String> seen = new HashSet<>(List.of(start));
        Deque<String> queue = new ArrayDeque<>(List.of(start));
        while (!queue.isEmpty()) {
            String at = queue.poll();
            if (at.equals(end)) return route(prev, end);
            for (Street s : city.get(at)) {
                if (seen.add(s.to())) {
                    prev.put(s.to(), at);
                    queue.add(s.to());
                }
            }
        }
        return List.of();
    }

    static int minutesOf(Map<String, List<Street>> city, List<String> route) {
        int total = 0;
        for (int i = 1; i < route.size(); i++) {
            for (Street s : city.get(route.get(i - 1))) {
                if (s.to().equals(route.get(i))) {
                    total += s.minutes();
                    break;
                }
            }
        }
        return total;
    }

    static String describe(Map<String, List<Street>> city, List<String> route) {
        return String.join(" → ", route) + " (" + (route.size() - 1) + " улици, "
                + minutesOf(city, route) + " мин)";
    }

    static List<String> fastest(
            Map<String, List<Street>> city,
            String start, String end) {
        Map<String, Integer> dist = new HashMap<>();
        Map<String, String> prev = new HashMap<>();
        PriorityQueue<Stop> queue = new PriorityQueue<>(
                Comparator.comparingInt(Stop::minutes));
        dist.put(start, 0);
        queue.add(new Stop(start, 0));
        while (!queue.isEmpty()) {
            Stop stop = queue.poll();
            String at = stop.place();
            if (stop.minutes() > dist.get(at)) continue;
            if (at.equals(end)) return route(prev, end);
            for (Street s : city.get(at)) {
                int t = stop.minutes() + s.minutes();
                Integer best = dist.get(s.to());
                if (best == null || t < best) {
                    dist.put(s.to(), t);
                    prev.put(s.to(), at);
                    queue.add(new Stop(s.to(), t));
                }
            }
        }
        return List.of();
    }

    public static void main(String[] args) throws IOException {
        String text = new String(System.in.readAllBytes(), StandardCharsets.UTF_8);
        Map<String, List<Street>> city = readMap(text);
        System.out.println("най-малко улици: " + describe(city, fewestStreets(city, "Склад", "Болница")));
        System.out.println("най-бързо: " + describe(city, fastest(city, "Склад", "Болница")));
        System.out.println("обратно: " + describe(city, fastest(city, "Болница", "Склад")));
    }
}

Пробвай

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

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

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

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

Виж го

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

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

static Map<String, List<Street>> gridCity(int size) {
    Map<String, List<Street>> city = new HashMap<>();
    for (int r = 0; r < size; r++) {
        for (int c = 0; c < size; c++) {
            String at = r + ":" + c;
            if (c + 1 < size) addStreet(city, at, r + ":" + (c + 1), 1 + (r * 7 + c * 13) % 9, true);
            if (r + 1 < size) addStreet(city, at, (r + 1) + ":" + c, 1 + (r * 11 + c * 5) % 9, true);
        }
    }
    return city;
}

Map<String, List<Street>> city = gridCity(100);
System.out.println("кръстовища: " + city.size());
List<String> few = fewestStreets(city, "0:0", "99:99");
System.out.println("най-малко улици: " + (few.size() - 1) + " улици, " + minutesOf(city, few) + " мин");
List<String> fast = fastest(city, "0:0", "99:99");
System.out.println("най-бързо: " + minutesOf(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 не пускаме, за да не замръзне страницата.

static List<String> fastest(
        Map<String, List<Street>> city,
        String start, String end) {
    Map<String, Integer> dist = new HashMap<>();
    Map<String, String> prev = new HashMap<>();
    PriorityQueue<Stop> queue = new PriorityQueue<>(
            Comparator.comparingInt(Stop::minutes));
    dist.put(start, 0);
    queue.add(new Stop(start, 0));
    while (!queue.isEmpty()) {
        Stop stop = queue.poll();
        String at = stop.place();
        if (stop.minutes() > dist.get(at)) continue;
        if (at.equals(end)) return route(prev, end);
        for (Street s : city.get(at)) {
            int t = stop.minutes() + s.minutes();
            Integer best = dist.get(s.to());
            if (best == null || t < best) {
                dist.put(s.to(), t);
                prev.put(s.to(), at);
                queue.add(new Stop(s.to(), t));
            }
        }
    }
    return List.of();
}

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

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 на улица

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

Бисквитки