Дорога от Роттердамма предвосхитила нейросети
Вот есть простые алгоритмы для поиска пути, где выбираются соседи и что-то с ними происходит и они ну нормальные, но без стоимости выбора этого соседа уже не уйти далеко, если твоя система сложнее двух пикселей. Ну вот и что получится, если взять алгоритм поиска пути и сказать ему "туда идти далеко" еще до того, как он сам это поймет? Получится Dijkstra - первый, кому важно не количество шагов, а их цена.
Автор этого алгоритма - Эдсгер Дейкстра, получивший от меня премию за самое сложно-произносимое и сложно-запоминаемое имя. Серьезно, я на русском называю его Дейкстра, а на английском читаю всегда Джийкстра и из-за этого на секунду торможу, а его имя я могу вспомнить только с помощью гугла "и чета там на Э начинается".
Дак вот, алгоритм он придумал в далеком 1956-м, за 20 минут, сидя в амстердамском кафе — по легенде самого Дейкстры, без бумаги и карандаша, решая задачу "как проще добраться из Роттердама в Гронинген". Опубликовал только в 1959-м, статья заняла три страницы и до сих пор входит в число самых цитируемых в компьютер саенсе. И не просто так, добавить вес, точнее, стоимость к перемещению - это как сказать "если пойдешь туда - будешь долго идти, оно тебе надо?" для вычислительной машины, которая раньше светилась лампочками, а сейчас считает, насколько долго тебе ехать до Сызрани.
Идея алгоритма строится в приоритетной очереди: на каждом шаге берёшь не первого попавшегося соседа, а того, до кого сейчас дешевле всего добраться, и пересчитываешь расстояния до его соседей. Взял точку 1, увидел, что от нее добраться до 3 дешевле, чем до 2, выбрал путь 1 > 3, потом снова и снова.
Применений хватает везде, где вес ребра - необходимость. GPS-навигация считает так же, только вес — это время в пробке, а не длина дороги. Маршрутизатор роутит пакеты по сети похожим образом, вес — задержка канала. В играх часто используют в связке со стоимостью перехода, чтоб определить, что по воде идти дольше, чем по чистой дороге, когда ты отправляешь юнитов в стратегии. Это очень важный алгоритм для всевозможных графов и его чуть более навороченная версия сейчас буквально отвечает за веса в ллм, в которой ты спрашиваешь, сколько калорий в твоем йогурте.
Меня, кстати, на одном собеседовании завалили и пытались высмеять за объяснение узлов и весов через города и длину дорог между ними — что, если откинуть техничку, было абсолютно рабочим описанием, просто без обёртки из терминов. Собеседование именно из-за этого и завалил, потому что лид команды разработки посчитал, что это слабость и недостаточное знание темы.
