Жадный выбор и его предел
Брать лучшее прямо сейчас — работает почти всегда и иногда даёт не лучший ответ.
Что это
На каждом шаге берём то, что выгоднее сейчас, не заглядывая вперёд.
Курьер едет к ближайшему адресу. Витрина берёт товар с наибольшим рейтингом. В сумку кладётся то, что помещается.
ostalos = list(range(len(adresa)))
gde = 0
put = []
while ostalos:
blizhayshiy = min(ostalos, key=lambda n: abs(adresa[n] - gde))
put.append(blizhayshiy)
gde = adresa[blizhayshiy]
ostalos.remove(blizhayshiy)
Чего жадный выбор не даёт
Лучшего ответа. Он может увести в сторону так, что потом придётся возвращаться.
Классический пример — сдача монетами. Номиналы 1, 3, 4; надо выдать 6. Жадно: 4 + 1 + 1 — три монеты. Лучше: 3 + 3 — две.
На привычных номиналах (1, 2, 5, 10) жадный выбор всегда верен, и именно поэтому ловушка не видна: проверяешь на обычных деньгах — работает.
Почему его всё равно берут
Настоящий лучший маршрут требует перебора, а перебор для тридцати адресов не посчитается никогда — вариантов больше, чем атомов в обозримой вселенной.
Жадный выбор даёт ответ за один проход и обычно хуже лучшего на считанные проценты. В курьерских службах ездят жадно, и это не упрощение задачи, а то, как есть.
На что смотреть в коде
Состояние обновляется. Курьер едет от текущей отметки, а не от склада. Забыть обновить — самая частая ошибка, и половина тестов при этом проходит.
Ничья решается явно. При равных вариантах должен побеждать предсказуемый, иначе ответ меняется от запуска к запуску.
Цикл кончается. Если подходящих вариантов не осталось, надо прекратить, а не крутиться. На сайте незавершённый цикл выглядит как зависший запрос.