СтатьиПодборкиДвижкиИнфраструктураСтратегииПроекты
Статьи/арбитраж

Подготовка: графы и кратчайшие пути на пальцах

Короткий урок с нуля для курса по арбитражу. Что такое граф, как хранить его в Python, как перечислить все маршруты между двумя точками и почему перебор каждого маршрута перестает работать, когда карта растет.

2 мин. чтенияарбитраж курс подготовка

Вспомогательный урок к курсу "Собери своего арбитражного бота". В уроках с 5 по 8 валюты рассматриваются как граф. Здесь разберем это слово на карте, а не на деньгах.

Граф как карта

Возьмем небольшой район. В нем четыре места: Home (дом), Park (парк), Cafe (кафе), Work (работа). Некоторые из них соединены дорогами, и на каждую дорогу уходит несколько минут.

  • От Home до Cafe: 4. От Home до Park: 2. От Park до Cafe: 1. От Cafe до Work: 5. От Park до Work: 8.

Места называют узлами (или вершинами). Дороги называют ребрами. Количество минут на дороге является ее весом. Все вместе это граф. Ничего больше. Карта метро и сеть друзей тоже являются графами, как и таблица обменных курсов: валюты являются узлами, а курс является ребром.

Хранение графа

Для каждой вершины сохраним список дорог, которые из нее выходят. В Python это словарь списков:

roads = {("Home", "Cafe"): 4, ("Home", "Park"): 2, ("Park", "Cafe"): 1,
         ("Cafe", "Work"): 5, ("Park", "Work"): 8}

neighbours = {}
for (a, b), minutes in roads.items():
    neighbours.setdefault(a, []).append((b, minutes))
print(neighbours["Home"])

[('Cafe', 4), ('Park', 2)]

Из Home можно попасть в Cafe (4 минуты) или в Park (2 минуты).

Прямой способ: перечислить все маршруты

Как быстрее всего добраться из Home в Work? Самый прямой способ состоит в том, чтобы перечислить каждый маршрут и выбрать кратчайший.

def all_routes(here, goal, route=None, total=0):
    route = (route or []) + [here]
    if here == goal:
        yield route, total
        return
    for nxt, minutes in neighbours.get(here, []):
        if nxt not in route:
            yield from all_routes(nxt, goal, route, total + minutes)

for route, total in sorted(all_routes("Home", "Work"), key=lambda x: x[1]):
    print(" -> ".join(route), total, "min")

Home -> Park -> Cafe -> Work 8 min
Home -> Cafe -> Work 9 min
Home -> Park -> Work 10 min

Самый быстрый маршрут проходит через Park и Cafe, он занимает 8 минут. Прямая на вид дорога из Home в Cafe не лучшая, потому что путь через Park экономит минуту. Это задача поиска кратчайшего пути.

Где прямой способ перестает работать

Посчитайте маршруты. На карте с 4 местами их было 3. Добавляйте места и дороги, и число маршрутов умножается: карта, в которой каждое место соединено с 10 другими, имеет около 10 × 10 × 10 ... маршрутов длины n. Для 10 шагов это 10 миллиардов. Перечислить их невозможно. В настоящих графах бывают сотни вершин.

Умные алгоритмы из уроков 6 и 7 не перечисляют маршруты. Для каждой вершины они хранят лучший найденный итог и шаг за шагом его улучшают. В этом вся идея, поэтому они остаются быстрыми.

Ваше упражнение

  1. Запустите код. Добавьте дорогу ("Cafe", "Park"): 1 в другом направлении. Изменится ли число маршрутов?
  2. Добавьте место Gym с дорогами от Home до Gym длиной 3 и от Gym до Work длиной 6. Какой маршрут теперь самый быстрый?
  3. Нарисуйте карту на бумаге и найдите самый быстрый маршрут на глаз. Проверьте его кодом.

Далее: вспомогательный урок о средних и разбросе (arbitrage-prereq-3-mean-stdev).

Читать далее