Путь отряда: куча, A* и честная эвристика

Если ты знаешь, почему эвристика A* должна быть не больше остатка пути и что делать с недостижимой целью, листай до «Теперь сам».

Как думаешь, что даст эвристика быстрее

У отряда есть цель в противоположном углу карты 20 × 20. Дейкстра расходится от старта кругом и раскрывает почти всю карту. Если добавить к приоритету клетки «сколько ещё идти по прямой», поиск потянется к цели. А если добавить «втрое больше, чем идти по прямой», - потянется ещё сильнее. Что потеряем?

Ответь себе до чтения. Сильнее тянуть к цели - меньше клеток раскрыть, и это правда. Но тогда поиск слишком рано решает, что обход через луг «не стоит того», и может пройти прямо через лес. Эвристика, которая обещает больше, чем на самом деле осталось, отсекает настоящий кратчайший путь. Правило игры в этой точке простое: эвристика не должна переоценивать.

На что это похоже

Навигатор в машине. Он предлагает ехать «в сторону дома», и почти всегда это верно. Но если он думает, что каждый километр в сторону от дома стоит втрое дороже, чем на деле, он упрямо поведёт тебя по пробке напрямик, хотя объезд по кольцу быстрее. Чем увереннее навигатор в прямом пути, тем быстрее он считает - и тем чаще ошибается.

Механизм: f = g + h и условие честности

A из раздела 11 берёт из кучи клетку с наименьшим f = g + h: g - пройденная цена, h - оценка остатка. Эвристика честная (допустимая), если h никогда не больше настоящей цены остатка - тогда первый раз, когда цель достаётся из кучи, найден кратчайший путь. Программа ниже не открывает обработанную клетку повторно, и для этого нужно больше - согласованность* из раздела 11: h(v) ≤ цена хода в u + h(u) для каждого соседа. Манхэттен, умноженный на цену самой дешёвой клетки, согласован: шаг уменьшает его не больше чем на эту цену.

Для карты «Архипелага» честную эвристику строят из двух фактов: отряд ходит по четырём сторонам, и самая дешёвая клетка стоит 1. Значит, любой путь из (r, c) в цель делает хотя бы |r − r₀| + |c − c₀| шагов, и каждый стоит хотя бы 1 - манхэттенское расстояние не больше настоящего остатка. Если бы на карте была дорога ценой 0,5, честной была бы только половина манхэттенского расстояния: эвристику масштабируют по самой дешёвой клетке, а не по типичной.

Цена стартовой клетки в путь не входит: g старта - 0. Ключ кучи - одно число f · 1000 + клетка, цены целые (дорогу ценой 0,5 делают ценой 1, а остальные цены удваивают), клеток меньше тысячи; на карте 128 × 128 множитель берут не меньше 16 384 - числа клеток, - иначе номер клетки при распаковке испортится. Когда клетке нашли путь короче, в кучу кладут новую запись, а старую не удаляют: она «устареет» и будет пропущена при извлечении, если клетка уже обработана.

Правило

Эвристика A должна быть честной: не больше настоящей цены остатка. На клеточной карте это манхэттенское расстояние, умноженное на цену самой дешёвой клетки. Завышенная эвристика ускоряет поиск, но перестаёт гарантировать кратчайший путь; недостижимую цель A не отличит от далёкой, пока не обойдёт всю компоненту.

Разбор: три поиска на одной карте

Карта 20 × 20: каждая клетка с вероятностью 12% гора, 33% лес, остальное луг. Ищем путь из угла в угол тремя способами.

import random

N = 20
random.seed(41)
karta = []                    # цена входа: 1 луг, 3 лес, 0 - гора
for r in range(N):
    stroka = []
    for c in range(N):
        x = random.random()
        if x < 0.12:
            stroka.append(0)
        elif x < 0.45:
            stroka.append(3)
        else:
            stroka.append(1)
    karta.append(stroka)
START = 0                     # клетка - число r * N + c
CEL = N * N - 1
karta[0][0] = 1
karta[N - 1][N - 1] = 1

def v_kuchu(k, x):
    k.append(x)
    i = len(k) - 1
    while i > 0 and k[(i - 1) // 2] > k[i]:
        k[i], k[(i - 1) // 2] = k[(i - 1) // 2], k[i]
        i = (i - 1) // 2

def iz_kuchi(k):
    verh = k[0]
    k[0] = k[len(k) - 1]
    k.pop()
    i = 0
    while True:
        m = i
        for d in [2 * i + 1, 2 * i + 2]:
            if d < len(k) and k[d] < k[m]:
                m = d
        if m == i:
            return verh
        k[i], k[m] = k[m], k[i]
        i = m

def poisk(ves_h):
    # A* с эвристикой ves_h · (манхэттенское расстояние до цели);
    # ves_h = 0 - это Дейкстра. Ключ кучи: f * 1000 + клетка
    g = {}
    g[START] = 0
    kucha = [0 * 1000 + START]
    raskryto = 0
    gotovo = set()
    while len(kucha) > 0:
        v = iz_kuchi(kucha) % 1000
        if v in gotovo:
            continue                 # устаревшая запись в куче
        gotovo.add(v)
        raskryto = raskryto + 1
        if v == CEL:
            return [g[v], raskryto]
        r = v // N
        c = v % N
        for d in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
            nr = r + d[0]
            nc = c + d[1]
            if 0 <= nr < N and 0 <= nc < N and karta[nr][nc] > 0:
                u = nr * N + nc
                ng = g[v] + karta[nr][nc]
                if u not in g or ng < g[u]:
                    g[u] = ng
                    h = ves_h * (abs(N - 1 - nr) + abs(N - 1 - nc))
                    v_kuchu(kucha, (ng + h) * 1000 + u)
    return [-1, raskryto]

print("Дейкстра:            ", poisk(0),
      "- [цена пути, раскрыто клеток]")
print("A*, h = расстояние:  ", poisk(1))
print("A*, h = 3·расстояние:", poisk(3))

Дейкстра:             [46, 359] - [цена пути, раскрыто клеток]
A*, h = расстояние:   [46, 258]
A*, h = 3·расстояние: [52, 41]

Дейкстра раскрыла 359 клеток - почти все доступные. A* с честной эвристикой нашёл путь той же цены 46, раскрыв 258, на 28% меньше. Это и есть цена, которую даёт эвристика при честности: путь не хуже, работы меньше. Программа печатает только цену: сам путь, нужный отряду, восстанавливают по родителям, как в разделе 11, - для этого рядом с g хранят, откуда пришли в клетку. Завышенная втрое эвристика раскрыла всего 41 клетку - почти идёт по прямой, - но её путь стоит 52, на 13% дороже. Есть известная граница: если эвристику умножить на w, найденный путь не дороже w кратчайших. Иногда это выгодный обмен - для отрядов, которые идут далеко и «примерно» сойдёт, - но это решение дизайнера, а не оптимизация незаметно для него.

Разбор: недостижимая цель и метки компонент

На другой карте цель в углу отрезана горами. A* об этом не знает - он ищет, пока куча не опустеет. Метки компонент из урока о генерации отвечают на «достижима ли» до поиска: один обход по всей карте раздаёт клеткам номера компонент, и дальше каждый запрос - одно сравнение.

import random

N = 20
random.seed(44)
karta = []                    # цена входа: 1 луг, 3 лес, 0 - гора
for r in range(N):
    stroka = []
    for c in range(N):
        x = random.random()
        if x < 0.12:
            stroka.append(0)
        elif x < 0.45:
            stroka.append(3)
        else:
            stroka.append(1)
    karta.append(stroka)
karta[0][0] = 1
karta[N - 1][N - 1] = 1

def v_kuchu(k, x):
    k.append(x)
    i = len(k) - 1
    while i > 0 and k[(i - 1) // 2] > k[i]:
        k[i], k[(i - 1) // 2] = k[(i - 1) // 2], k[i]
        i = (i - 1) // 2

def iz_kuchi(k):
    verh = k[0]
    k[0] = k[len(k) - 1]
    k.pop()
    i = 0
    while True:
        m = i
        for d in [2 * i + 1, 2 * i + 2]:
            if d < len(k) and k[d] < k[m]:
                m = d
        if m == i:
            return verh
        k[i], k[m] = k[m], k[i]
        i = m

def poisk(START, CEL):
    # A* с эвристикой «манхэттенское расстояние до цели»
    g = {}
    g[START] = 0
    kucha = [START]
    raskryto = 0
    gotovo = set()
    while len(kucha) > 0:
        v = iz_kuchi(kucha) % 1000
        if v in gotovo:
            continue                 # устаревшая запись в куче
        gotovo.add(v)
        raskryto = raskryto + 1
        if v == CEL:
            return [g[v], raskryto]
        r = v // N
        c = v % N
        for d in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
            nr = r + d[0]
            nc = c + d[1]
            if 0 <= nr < N and 0 <= nc < N and karta[nr][nc] > 0:
                u = nr * N + nc
                ng = g[v] + karta[nr][nc]
                if u not in g or ng < g[u]:
                    g[u] = ng
                    h = abs(CEL // N - nr) + abs(CEL % N - nc)
                    v_kuchu(kucha, (ng + h) * 1000 + u)
    return [-1, raskryto]

def metki():
    # один обход по всей карте: номер компоненты у каждой клетки
    m = [-1] * (N * N)
    nomer = 0
    for v in range(N * N):
        if m[v] == -1 and karta[v // N][v % N] > 0:
            m[v] = nomer
            och = [v]
            golova = 0
            while golova < len(och):
                x = och[golova]
                golova = golova + 1
                for u in [x - N, x + N, x - 1, x + 1]:
                    # сосед: та же строка или тот же столбец
                    ryadom = u // N == x // N or u % N == x % N
                    if 0 <= u < N * N and ryadom and m[u] == -1:
                        if karta[u // N][u % N] > 0:
                            m[u] = nomer
                            och.append(u)
            nomer = nomer + 1
    return m

zaprosy = [[0, N * N - 1], [0, 5 * N + 7], [N * N - 1, 2 * N]]
komp = metki()
for z in zaprosy:
    # гора компоненты не имеет (-1): две горы не «связаны» между собой
    dostizhima = komp[z[0]] != -1 and komp[z[0]] == komp[z[1]]
    print("из", z[0], "в", z[1], "| одна компонента:", dostizhima,
          "| A*:", poisk(z[0], z[1]))

из 0 в 399 | одна компонента: False | A*: [-1, 337]
из 0 в 107 | одна компонента: True | A*: [14, 27]
из 399 в 40 | одна компонента: False | A*: [-1, 2]

Первый запрос - худший случай A*: цели нет в компоненте старта, и поиск раскрыл все 337 клеток этой компоненты, прежде чем сдался. Метки ответили бы «нет» сразу. Третий запрос стартует из угла 399 в крошечном кармане: там две клетки, поиск сдался быстро - но лишь потому, что повезло с компонентой старта. Метки считаются один раз на карту и обновляются, когда карта меняется. Граница правила: если горы рушатся и строятся каждый ход, метки придётся пересчитывать; на добавлении переходов поможет объединение непересекающихся множеств, а на удалении - нет, и тогда метки пересчитывают целиком.

Что ломается без этого

Эвристика по типичной клетке. На карте появилась дорога ценой 0,5, а эвристика осталась «расстояние × 1» - и отряды перестали её замечать: путь по дороге казался дороже, чем он есть.

Поиск в недостижимую цель. Игрок кликает по острову без моста - и сервер на каждом таком клике обходит весь материк. Двадцать кликов в секунду - и ход затянулся.

Удаление из кучи. Попытка честно удалить устаревшую запись из середины кучи стоит линейного поиска по куче на каждую вставку; ленивое удаление при извлечении поиска не требует, а платит лишь памятью под устаревшие записи и их пустым извлечением.

Зачем это в работе

Навигация роботов на складе, маршрутизация в сети с метриками, поиск ходов в головоломках - везде, где цель известна и есть дешёвая нижняя оценка остатка, A* экономит работу без потери точности. А проверка «достижима ли цель» по заранее посчитанным компонентам - стандартный фильтр перед дорогим поиском.

Теперь сам

1. На карте добавили болото ценой 5 и дорогу ценой 1/2. Какую эвристику взять, чтобы она осталась честной?
2. Почему метка компоненты отвечает на «достижима ли», но не на «как далеко»?
3. Эвристику умножили на 1,5. Насколько дороже кратчайшего может оказаться найденный путь?