Поиск и планирование: как ИИ находит решение¶

Коротко

Огромная часть задач искусственного интеллекта сводится к одному: найти путь от текущей ситуации к желаемой, перебирая возможные шаги. Любую такую задачу можно описать через состояния (где мы сейчас), переходы (что можно сделать) и цель (куда хотим прийти). Перебрать все варианты обычно невозможно — их слишком много, поэтому ИИ использует эвристики: разумные подсказки, куда смотреть в первую очередь. Именно так Яндекс Навигатор находит маршрут, а склады Ozon и Wildberries планируют доставку.

Задача как поиск пути¶

Представьте, что вы собираете кубик Рубика, ищете выход из лабиринта или прокладываете маршрут до дачи. Во всех трёх случаях вы делаете одно и то же: смотрите на текущее положение дел, перебираете возможные ходы и пытаетесь добраться до нужного результата. Удивительно, но компьютер «думает» над такими задачами похожим образом.

Чтобы ИИ мог решать задачу, её сначала описывают тремя простыми понятиями:

Состояние — снимок ситуации в конкретный момент. Для навигатора это перекрёсток, на котором вы стоите. Для кубика Рубика — текущая раскраска граней.
Переход — действие, которое превращает одно состояние в другое. Свернуть налево. Повернуть грань кубика. Сделать ход в игре.
Целевое состояние — то, к чему мы стремимся. Нужный адрес. Собранный кубик. Выигрышная позиция.

Решить задачу — значит найти последовательность переходов, которая ведёт от старта к цели. Эту последовательность называют планом, поэтому раздел и называется «поиск и планирование».

Пространство состояний¶

Если выписать вообще все ситуации, в которых может оказаться система, и все переходы между ними, получится своего рода карта возможностей. Её называют так:

Пространство состояний — это множество всех возможных состояний задачи вместе со связями-переходами между ними. По сути, это карта всех ситуаций, в которые система может попасть, и всех ходов, которыми можно из одной ситуации перейти в другую.

Удобно представлять пространство состояний как схему метро. Станции — это состояния, перегоны между ними — переходы. Вы стоите на одной станции (старт) и хотите попасть на другую (цель). Найти решение — значит проложить путь по этой схеме.

Разница лишь в том, что в настоящей задаче «станций» бывает астрономически много, и никто не рисует их заранее: ИИ открывает новые состояния по ходу поиска, шаг за шагом раскрывая соседей текущей ситуации.

Важно

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

Полный перебор против эвристического поиска¶

Самый прямолинейный способ найти решение — проверить вообще все варианты. Это называют полным перебором: ИИ систематически разворачивает все возможные пути, пока не наткнётся на цель. Подход надёжный — если решение существует, перебор его обязательно найдёт. Беда в том, что вариантов почти всегда чудовищно много.

Поэтому на практике используют более умный подход — эвристический поиск.

Эвристика — это практическое правило-подсказка, которое помогает оценить, насколько то или иное состояние близко к цели, и выбрать, куда двигаться в первую очередь. Эвристика не гарантирует идеального ответа, но резко сокращает перебор, отсекая заведомо бесперспективные направления.

Простой пример эвристики для навигатора: «из двух перекрёстков сначала проверь тот, что по прямой ближе к финишу». Это не всегда верно — впереди может оказаться река или тупик, — но в большинстве случаев такая подсказка ведёт в нужную сторону и экономит уйму вычислений.

Сравним два подхода:

	Полный перебор	Эвристический поиск
Что делает	Проверяет все пути подряд	Идёт туда, где цель кажется ближе
Скорость	Медленный на больших задачах	Обычно гораздо быстрее
Надёжность	Найдёт решение всегда	Зависит от качества подсказки
Когда уместен	Маленькие задачи	Реальные задачи с миллионами вариантов

Комбинаторный взрыв: почему «перебрать всё» не работает¶

Главный враг полного перебора имеет имя.

Комбинаторный взрыв — это лавинообразный рост числа вариантов по мере усложнения задачи. Стоит добавить всего пару шагов или элементов, и количество возможных комбинаций увеличивается не на чуть-чуть, а в разы, быстро становясь неподъёмным даже для мощного компьютера.

Почувствовать это легко на маршрутах доставки. Если курьеру нужно объехать несколько адресов и вернуться на склад, число возможных порядков объезда растёт катастрофически быстро. Для 5 точек вариантов — больше сотни. Для 10 — уже миллионы. Для 20 — астрономически много, куда больше, чем звёзд, которые вы увидите на ночном небе. Перебрать их по очереди не успеет ни один сервер.

Пример: маршрут в Яндекс Навигаторе и 2ГИС

Когда вы строите маршрут через город, дорожная сеть — это пространство состояний. Перекрёстки — состояния, улицы между ними — переходы. У каждого перехода есть стоимость: сколько времени или километров он отнимает. Пробка делает участок «дороже» — его вес растёт, и алгоритм охотнее ищет объезд.

Перебирать все мыслимые пути по городу бессмысленно — их слишком много. Поэтому навигатор применяет эвристику: в первую очередь разворачивает те направления, которые ведут географически ближе к точке назначения, и отбрасывает явно лишние. Так маршрут находится за доли секунды, а не за часы. По той же логике планируют доставку склады Ozon и Wildberries: куда сначала заехать курьеру, как загрузить машины, в каком порядке собирать заказы — всё это поиск выгодного пути в огромном пространстве вариантов.

Из-за комбинаторного взрыва прогресс в ИИ — это во многом история про умные способы не перебирать лишнее: хорошие эвристики, отсечение тупиков и аккуратный выбор, какие состояния изучать раньше других.

Где это встречается каждый день¶

Поиск в пространстве состояний работает вокруг вас, даже если вы об этом не задумываетесь:

Навигация. Яндекс Навигатор и 2ГИС прокладывают маршрут с учётом пробок как стоимости пути.
Логистика. Маршрутизация курьеров и сборка заказов в Ozon и Wildberries — поиск выгодного порядка действий.
Расписания. Составить смены сотрудникам или расписание занятий — тоже подбор подходящего варианта из множества.
Игры. Чтобы выбрать ход, программа перебирает будущие позиции. Об этом — следующий урок про минимакс; легендарные партии Гарри Каспарова против компьютера выросли как раз из такого перебора ходов.

Идея поиска тесно связана с другими темами курса. Если интересно, как вообще устроен искусственный интеллект и из чего он состоит, начните с урока Как определить искусственный интеллект.

Упражнение: почему перебор не масштабируется

Курьеру со склада нужно объехать несколько пунктов выдачи и вернуться обратно. Он хочет проехать как можно меньше. Сколько разных порядков объезда придётся проверить полным перебором?

Прикиньте сами. Для 4 точек число вариантов — это 4 × 3 × 2 × 1 = 24. Для 5 точек — 120. Для 6 — 720. Замечаете? Каждая новая точка умножает число вариантов, а не прибавляет к нему. Это и есть комбинаторный взрыв: уже на 15–20 адресах полный перебор становится безнадёжным.

Какую эвристику предложить? Простое и на удивление неплохое правило — «жадный» подход: всегда ехать в ближайший из ещё не посещённых пунктов. Он не гарантирует самый короткий маршрут, но находит хороший за считаные шаги, без перебора миллионов комбинаций. Именно так — отсекая лишнее с помощью разумных подсказок — реальные сервисы доставки и справляются с задачами, которые в лоб решить невозможно.

Проверьте себя¶

Короткий тест по уроку: выберите ответ и нажмите «Проверить» — увидите счёт и разбор.

Частые вопросы¶

Что такое пространство состояний простыми словами?

Это карта всех ситуаций, в которых может оказаться задача, и всех переходов между ними. Представьте схему метро: станции — это состояния, перегоны — переходы. Решить задачу — значит проложить по этой карте путь от старта к цели.

Чем эвристика отличается от точного решения?

Точный метод (полный перебор) гарантированно находит ответ, но может работать недопустимо долго. Эвристика — это разумная подсказка, куда смотреть в первую очередь. Она не даёт стопроцентной гарантии лучшего результата, зато находит хорошее решение быстро. На больших задачах без эвристик не обойтись.

Что такое комбинаторный взрыв?

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

Как навигатор находит маршрут?

Дорожная сеть — это пространство состояний: перекрёстки как состояния, улицы как переходы со стоимостью (время или расстояние). Пробка увеличивает стоимость участка. Навигатор не перебирает все пути, а с помощью эвристики разворачивает в первую очередь те, что ведут ближе к цели, поэтому отвечает почти мгновенно.

В курсе: ← Назад: Философия ИИ: тест Тьюринга и китайская комната · Дальше: Игры против ИИ: минимакс и перебор ходов →

Авторы курса: Герман Коваленко (основатель ENGRAM) и Сергей Добров.

Попробуйте ENGRAM на своих данных

Нейросеть на ваших встречах, документах и переписке: отвечает со ссылкой на источник. Это ваша вторая память на базе ИИ. Данные хранятся в России, старт бесплатный.

Зарегистрироваться бесплатно