Тема 2. Поиск и логический вывод

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

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

Задачи поиска в пространстве состояний

Формализация задачи поиска

Многие задачи ИИ можно свести к поиску пути в некотором абстрактном пространстве. Рассмотрим классический учебный пример — головоломку «восьмёрка» (англ. 8-puzzle). Имеется поле $3 \times 3$ с восемью пронумерованными фишками и одной пустой клеткой. За один ход разрешается переместить фишку, соседнюю с пустой клеткой, на освободившееся место. Требуется привести фишки в стандартный порядок. На таком масштабе пространство достижимых конфигураций обозримо — $9!/2 = 181\,440$ состояний, и в учебных схемах далее мы пользуемся именно «восьмёркой» для наглядности. Её старший вариант, «пятнашки» (англ. 15-puzzle) на поле $4 \times 4$ с пятнадцатью фишками, даёт уже $16!/2 \approx 10^{13}$ состояний — на этом масштабе полный перебор исключён.

Чтобы решить эту задачу алгоритмически, её нужно формализовать. Обозначим конфигурацию поля как состояние (англ. state). Начальная конфигурация — начальное состояние $s_0$, упорядоченная конфигурация — целевое состояние $s^*$. Каждый допустимый ход — это оператор перехода, переводящий одно состояние в другое. Множество всех достижимых состояний вместе с переходами между ними образует пространство состояний (англ. state space).

Формально задача поиска задаётся четвёркой: $\langle S, s_0, A, G \rangle,$ где $S$ — множество состояний, $s_0 \in S$ — начальное состояние, $A$ — множество операторов (действий), $G \subseteq S$ — множество целевых состояний. Решением является последовательность операторов $a_1, a_2, \ldots, a_n$, переводящая $s_0$ в некоторое $s^* \in G$.

Пространство состояний естественно представляется в виде графа: вершины — состояния, рёбра — допустимые переходы. При этом алгоритм поиска обычно работает не с полным графом (он может быть слишком велик или даже бесконечен), а строит дерево поиска (англ. search tree) «на лету», раскрывая вершины по мере необходимости. Корень дерева — начальное состояние; дочерние вершины порождаются применением операторов; лист (англ. leaf) — вершина без детей, которая либо ещё не раскрыта алгоритмом, либо является тупиком, у которого нет применимых операторов (рис. 2.1).

Слева на рисунке — фрагмент графа пространства состояний: начальное состояние $s_0$ и четыре его соседа по одному ходу (B, C, D, E). Рёбра графа двунаправленные: любой ход «восьмёрки» обратим — фишку, передвинутую в пустую клетку, можно тут же передвинуть назад. Справа тот же фрагмент развёрнут в дерево поиска из корня $s_0$. Среди потомков корня снова появляется $s_0$ (красный лист в легенде), и это прямое следствие обратимости ходов: каждый ребёнок корня — это $s_0$ плюс один ход; среди четырёх возможных ходов из этого ребёнка один обязательно возвращает обратно в $s_0$. На рисунке такие дубликаты показаны под B и E; под C и D они точно такие же (там, где в дереве стоит «…»). Если алгоритм не ведёт список уже посещённых вершин, дубликаты раскрываются повторно, и дерево раздувается в разы по сравнению с самим графом.

Чтобы оценить, как масштабируется такой перебор, удобно сравнить «восьмёрку» с «пятнашками»: 181 440 против $\approx 10^{13}$ — отличие в семь порядков при увеличении поля всего на одну строку и один столбец. Это типичная картина для задач поиска: пространство состояний растёт комбинаторно от размера задачи, и выбор стратегии обхода дерева оказывается решающим уже на скромных масштабах.

Алгоритмы поиска оценивают по четырём критериям:

• Полнота (англ. completeness): гарантирует ли алгоритм нахождение решения, если оно существует?
• Оптимальность (англ. optimality): находит ли алгоритм решение с минимальной стоимостью?
• Временная сложность (англ. time complexity): сколько вершин алгоритм раскрывает в худшем случае?
• Пространственная сложность (англ. space complexity): сколько вершин алгоритм одновременно хранит в памяти?

Дальнейший анализ алгоритмов опирается на три параметра дерева поиска. Фактор ветвления $b$ — среднее число дочерних вершин при раскрытии. Глубина решения $d$ — длина кратчайшего пути от корня до целевой вершины, то есть число ходов в оптимальном решении. Для «восьмёрки» полным перебором установлено, что $d \leq 31$: никакая решаемая начальная конфигурация не требует больше 31 хода до цели. Максимальная глубина дерева $m$ — длина самой длинной ветви, по которой алгоритм может спуститься; в графах с циклами без отсечения повторов она может оказаться сколь угодно большой.

Неинформированный поиск

Неинформированные (слепые) алгоритмы не используют никаких сведений о том, насколько текущее состояние «близко» к цели. Они различаются лишь порядком, в котором раскрывают вершины.

Поиск в ширину (англ. breadth-first search, BFS) обходит дерево слоями. Глубина вершины — это длина пути от корня до неё: корень имеет глубину 0, его дети — глубину 1, их дети — глубину 2, и так далее. BFS сначала раскрывает корень, затем все вершины на глубине 1, затем все на глубине 2, и пока слой $k$ не разобран до конца, к слою $k+1$ алгоритм не переходит (рис. 2.2). Реализуется это очередью FIFO (англ. first-in-first-out): новые порождённые вершины кладутся в хвост очереди, а на раскрытие берётся та, что стоит в голове, — то есть попавшая туда раньше всех. Поскольку дети любой вершины оказываются в очереди позже самой вершины, послойный порядок выдерживается автоматически.

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

Платит BFS за свои гарантии памятью: на глубине $d$ при факторе ветвления $b$ в очереди может оказаться до $O(b^d)$ вершин. Для «восьмёрки» с $b \approx 2.67$ и оптимальной длиной решения $d \leq 31$ хранение нескольких десятков миллионов вершин ещё допустимо в памяти настольной машины. Для «пятнашек» с $b \approx 3$ и $d \approx 80$ оценка $b^d$ выходит за пределы реалистичных ресурсов — BFS становится практически неприменимым.

Поиск в глубину (англ. depth-first search, DFS) идёт в противоположном направлении. Алгоритм раскрывает вершину и сразу переходит к одному из её детей, углубляясь по выбранной ветви, пока не достигнет листа или тупика; только после этого возвращается к ближайшему непросмотренному ветвлению и продолжает оттуда (рис. 2.3). Реализуется это стеком LIFO (англ. last-in-first-out): новые порождённые вершины кладутся на верх стека, а на раскрытие берётся та, что положена туда последней — самая «свежая». Естественной альтернативой стеку служит обычная рекурсия: рекурсивный вызов сам кладёт состояние на стек выполнения, а возврат из вызова — снимает.

В отличие от BFS, DFS не полон в общем случае: если в пространстве состояний есть бесконечная ветвь (например, из-за неотсекаемых циклов), алгоритм может уйти в неё навсегда и так и не добраться до решения, даже если оно существует на конечной глубине. Оптимальность тоже не гарантируется — даже если решение найдено, оно может оказаться сколь угодно длиннее оптимального: DFS возвращает первое решение, которое попалось, а оно лежит на той ветви, куда алгоритм случайно свернул раньше других.

Зато по памяти DFS радикально экономнее BFS: на стеке в каждый момент хранится только текущая ветвь и не раскрытые ещё соседи каждой её вершины — в худшем случае $O(bm)$, где $m$ — максимальная глубина дерева. Для «пятнашек» это уже терпимо. Поэтому в задачах с гигантским пространством состояний DFS остаётся применимым там, где BFS не помещается в память, — ценой потерь в полноте и оптимальности.

На практике выбор между BFS и DFS — это выбор между гарантией результата и расходом памяти. Существует ли компромисс?

Поиск с итеративным углублением (англ. iterative deepening depth-first search, IDDFS) пытается совместить достоинства BFS и DFS ¹. Алгоритм выполняет серию запусков DFS с возрастающим ограничением глубины: сначала просматривает только корень (предел 0), затем корень и его детей (предел 1), потом — до глубины 2, и так далее, пока на каком-то пределе не найдёт целевую вершину (рис. 2.4). Каждая отдельная итерация — это обычный DFS, но с жёстким запретом спускаться ниже текущего предела глубины.

На первый взгляд кажется, что повторное раскрытие верхних уровней — расточительство: при поиске на глубине 3 алгоритм заново обходит все вершины глубин 1 и 2, которые уже раскрывались. Однако при факторе ветвления $b > 1$ основная масса вершин сосредоточена на последнем уровне (там их в $b$ раз больше, чем на предпоследнем), и накладные расходы на повторы составляют не более $\frac{b}{b-1}$ от стоимости однократного обхода. Для $b = 3$ это всего лишь полуторакратное увеличение.

IDDFS наследует преимущества обоих родительских алгоритмов. Он полон: ограничение глубины растёт неограниченно, и любое решение на конечной глубине рано или поздно будет найдено. Он оптимален при одинаковой стоимости переходов: глубина увеличивается шагами по единице, и первая нашедшаяся цель неизбежно лежит на минимальной возможной глубине. И при этом по памяти он экономен как DFS — $O(bd)$, — потому что каждая итерация это обычный DFS. Сочетание этих свойств делает IDDFS предпочтительным неинформированным алгоритмом для задач с большим пространством состояний.

Сравнение трёх алгоритмов на одной задаче поучительно. Положим задачу нахождения решения в дереве глубиной $d = 12$ с $b = 3$. BFS гарантированно найдёт оптимальное решение, удерживая в памяти около $3^{12} \approx 5 \cdot 10^5$ вершин. DFS уложится в $3 \cdot 12 = 36$ вершин памяти, но может уйти в неоптимальную ветвь и вернуть решение длиной, скажем, 17 вместо 12. IDDFS повторит часть верхних уровней, раскрыв в полтора раза больше вершин, чем BFS, — но при тех же $36$ единицах памяти и с гарантией оптимальности. Когда задача исчерпывает оперативную память при BFS, IDDFS обычно становится единственно реалистичным неинформированным выбором.

Информированный (эвристический) поиск

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

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

Жадный поиск (англ. greedy best-first search) всегда раскрывает вершину с наименьшим $h(n)$. Он устремляется к цели напрямик и может найти решение быстро, но без гарантии оптимальности: алгоритм легко попадает в локальные «ловушки», выбирая путь, который выглядит многообещающим, но ведёт в тупик.

Алгоритм A* (англ. A-star) использует более взвешенную стратегию ². Для каждой вершины вычисляется оценочная функция $f(n) = g(n) + h(n),$ где $g(n)$ — стоимость пути от начальной вершины до $n$ (известна точно), а $h(n)$ — эвристическая оценка оставшегося пути. Алгоритм раскрывает вершину с наименьшим $f(n)$, то есть учитывает и уже понесённые затраты, и прогнозируемый остаток.

A* гарантирует нахождение оптимального решения при выполнении двух условий. Первое — допустимость (англ. admissibility) эвристики: $h(n) \leq h^*(n)$ для всех $n$, где $h^*(n)$ — истинная стоимость оптимального пути от $n$ до цели. Иначе говоря, эвристика не должна переоценивать расстояние до цели. Манхэттенское расстояние для «восьмёрки» — допустимая эвристика, поскольку каждая фишка должна сделать не менее стольких ходов, сколько клеток отделяет её от целевой позиции. Второе условие — состоятельность (англ. consistency, иногда monotonicity): для любой вершины $n$ и её потомка $n'$, полученного действием $a$, выполняется $h(n) \leq c(n, a, n') + h(n')$, где $c$ — стоимость перехода. Состоятельность — более сильное требование, чем допустимость, и оно гарантирует, что A* не станет повторно раскрывать уже обработанные вершины.

Качество эвристики на практике определяет, сколько вершин раскроет A*. Эвристика $h_1$ доминирует над $h_2$, если $h_1(n) \geq h_2(n)$ для всех $n$ при сохранении допустимости. Доминирующая эвристика никогда не приводит к раскрытию большего числа вершин. Классический пример для «восьмёрки»: тривиальная эвристика «число фишек не на своих местах» допустима, но слабая; манхэттенское расстояние её доминирует и на типичных задачах сокращает число раскрываемых вершин в десятки раз. Это объясняет, почему инженерия эвристики — отдельный пункт при проектировании систем планирования.

Разница между жадным поиском и A* наглядна на примере навигации. Положим, требуется проложить маршрут из точки А в точку Б на карте. Жадный поиск выберет дорогу, которая «смотрит» в сторону Б (минимальное расстояние по прямой), — но эта дорога может оказаться просёлочной, петляющей и в итоге длинной. A* учтёт и уже пройденный путь $g(n)$, и оставшееся расстояние $h(n)$, и предпочтёт скоростную магистраль, даже если она сначала ведёт в сторону от цели.

На практике A* применяется в навигационных приложениях, компьютерных играх (поиск пути для персонажей), робототехнике (планирование движения), логистике (оптимизация маршрутов). Ограничение алгоритма — требования к памяти: как и BFS, A* хранит все раскрытые вершины, и при больших пространствах состояний это может стать проблемой. Существуют модификации, смягчающие это ограничение: IDA* ¹ комбинирует A* с итеративным углублением и потребляет $O(bd)$ памяти, SMA* ³ работает в фиксированном бюджете памяти, отбрасывая наименее перспективные вершины. Подробное рассмотрение этих модификаций выходит за рамки курса; систематическое изложение — в ⁴.

Логический вывод и представление знаний

Базы знаний и экспертные системы

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

Именно для таких задач в 1970–1980-х годах были разработаны экспертные системы (англ. expert systems) ⁵⁶. Архитектура классической экспертной системы включает три компонента:

• База знаний (англ. knowledge base) — хранилище фактов о предметной области и правил, связывающих факты с выводами. Факты описывают известные свойства объектов («температура пациента — 38.5°C», «бактерия грамположительная»). Правила задают логику вывода.
• Механизм вывода (англ. inference engine) — программный модуль, который применяет правила к фактам и порождает новые заключения.
• Пользовательский интерфейс — обеспечивает диалог с пользователем: запрашивает недостающие факты и объясняет ход рассуждения.

Правила в экспертных системах чаще всего записываются в форме продукций (англ. production rules): «ЕСЛИ условие, ТО действие». Рассмотрим фрагмент, стилизованный под систему диагностики:

ЕСЛИ инфекция является первичной бактериемией
  И окраска по Граму положительная
  И морфология — кокки в цепочках
ТО с вероятностью 0.7 возбудитель — Streptococcus

Подобных правил в реальных системах могли быть сотни. MYCIN содержала около 450 правил и показывала точность диагностики, сопоставимую с экспертами-инфекционистами.

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

Обратный вывод (англ. backward chaining) действует в противоположном направлении. Система начинает с гипотезы (например, «возбудитель — Streptococcus») и ищет правила, которые могли бы её подтвердить. Если условия правила не подтверждены имеющимися фактами, они становятся новыми подцелями, которые система пытается доказать рекурсивно. Обратный вывод характерен для диагностических систем: есть подозрение — нужно проверить, подтверждается ли оно данными.

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

Рассмотрим миниатюрный пример. Пусть база знаний содержит два правила: «ЕСЛИ лихорадка И кашель, ТО грипп» и «ЕСЛИ грипп, ТО назначить покой». Известный факт — «лихорадка». Прямой вывод раскрутит цепочку так: ищем правила, у которых выполнены условия. Первое правило требует ещё и «кашель» — система спросит у пользователя про кашель; получив подтверждение, добавит «грипп» в базу фактов, затем сработает второе правило и появится «назначить покой». Обратный вывод стартует с гипотезы «назначить покой»: ищет правила, которые её выводят, находит второе; чтобы оно сработало, нужен «грипп». Грипп не факт — ищется правило, его выводящее: первое. Его условия — «лихорадка» (есть в фактах) и «кашель» (неизвестно — спрашиваем). Дальше — как в прямом выводе. Различие — в порядке вопросов: прямой обходит правила «снизу вверх» от фактов, обратный — «сверху вниз» от целей. На небольшой базе различие незаметно, но при сотнях правил разница в числе бесполезных запросов к пользователю определяет, удобна ли система.

Ограничения символьного подхода

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

Первое — проблема приобретения знаний (англ. knowledge acquisition bottleneck). Правила приходилось извлекать из голов экспертов вручную, в ходе длительных интервью. Эксперт далеко не всегда способен объяснить, как именно он принимает решения: значительная часть профессионального опыта существует в форме интуиции и неявного знания. Создание базы знаний для одной предметной области занимало месяцы и годы, а при изменении области — например, при появлении нового оборудования или новых стандартов — базу приходилось перерабатывать заново.

Второе — хрупкость (англ. brittleness). Экспертная система работает уверенно ровно в тех ситуациях, которые предусмотрены её правилами. Стоит столкнуться с незнакомой комбинацией фактов — и система либо даёт некорректный ответ, либо не даёт никакого. У неё нет механизма обобщения, позволяющего перенести опыт из одной ситуации в другую. Человек-эксперт может рассуждать по аналогии; продукционная система — нет.

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

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

Ответом стало машинное обучение: вместо ручного формирования правил — автоматическое извлечение закономерностей из данных. Вместо явной базы знаний — модель, параметры которой настраиваются в ходе обучения. Этот переход — от знаний к данным, от правил к статистике — составляет содержание следующих тем курса, начиная с темы 3.

Литература

1. Korf R. E. Depth-First Iterative-Deepening: An Optimal Admissible Tree Search. — Artificial Intelligence, 1985, С. 97–109, DOI: 10.1016/0004-3702(85)90084-0.
2. Hart P. E., Nilsson N. J., Raphael B. A Formal Basis for the Heuristic Determination of Minimum Cost Paths. — IEEE Transactions on Systems Science and Cybernetics, 1968, С. 100–107, DOI: 10.1109/TSSC.1968.300136.
3. Russell S. J. Efficient Memory-Bounded Search Methods. — Proceedings of the 10th European Conference on Artificial Intelligence (ECAI), 1992, С. 1–5.
4. Russell S., Norvig P. Artificial Intelligence: A Modern Approach. — Pearson, 2021.
5. Shortliffe E. H. Computer-Based Medical Consultations: MYCIN. — Elsevier, 1976.
6. McDermott J. R1: A Rule-Based Configurer of Computer Systems. — Artificial Intelligence, 1982, С. 39–88, DOI: 10.1016/0004-3702(82)90021-2.

Практическое занятие 2. Поиск пути и логический вывод

• Объём: 4 академических часа
• Раздел курса: учебное пособие, тема 2 «Поиск и логический вывод»

Введение

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

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

Цель работы

Реализовать базовые алгоритмы поиска и логического вывода и эмпирически проверить теоретические свойства, заявленные в теме.

После выполнения работы студент сможет:

• реализовать BFS, DFS, IDDFS и A* как универсальный обход графа состояний и применить их к головоломке «восьмёрка»;
• собрать сравнительную таблицу алгоритмов по числу раскрытых вершин, времени, длине решения и пиковой памяти и объяснить расхождения с теоретическими $O(\cdot)$-оценками;
• реализовать продукционную базу знаний и два простых механизма вывода (прямой и обратный) для заданной предметной области;
• провести сценарии с разным составом начальных фактов и объяснить, почему количество вопросов к пользователю различается между режимами вывода.

Теоретический минимум

Концептуальная база — учебное пособие, тема 2: разделы «Формализация задачи поиска», «Неинформированный поиск», «Информированный (эвристический) поиск», «Базы знаний и экспертные системы». Здесь приводятся только сведения, специфичные для реализации.

«Восьмёрка» (англ. 8-puzzle) — головоломка на поле $3\times3$ с восемью пронумерованными фишками и одной пустой клеткой. Состояние удобно представлять как tuple из 9 чисел 0..8 (где 0 — пустая клетка) — это даёт хешируемый ключ для словаря посещённых состояний. Целевое состояние стандартное: (1,2,3,4,5,6,7,8,0). Из текущего состояния порождаются от 2 до 4 потомков перемещением пустой клетки на одну позицию вверх/вниз/влево/вправо.

Манхэттенское расстояние для «восьмёрки» вычисляется как сумма по всем фишкам $1\ldots 8$ модуля разности их фактических и целевых координат в сетке $3\times3$: $h(n) = \sum_i (|r_i - r_i^*| + |c_i - c_i^*|)$. Пустая клетка в сумму не входит. Эта эвристика допустима и состоятельна.

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

Перечень оснащения

• Python 3.10 или новее в виртуальном окружении, развёрнутом по практическому занятию 1.
• Jupyter Notebook или эквивалент.
• Стандартная библиотека Python и pandas для сводных таблиц; внешних специализированных библиотек поиска не используется.
• Заготовка проекта — каталог pz-env/ рядом с этим файлом: интерфейсы алгоритмов поиска, генератор начальных конфигураций «восьмёрки», шаблон базы знаний и валидатор отчёта.

Порядок выполнения работы

Часть 1. Алгоритмы поиска на «восьмёрке»

Задание

1. Реализовать общий обход графа состояний параметризованной стратегией извлечения из фронтира: FIFO (BFS), LIFO с ограничением глубины (DLS), итеративное углубление поверх DLS (IDDFS), очередь с приоритетом по $f(n) = g(n) + h(n)$ (A* с манхэттенским расстоянием). Запрещено пользоваться сторонними реализациями поиска; стандартные структуры данных (collections.deque, heapq) — допустимы.
2. Реализовать корректное отслеживание посещённых состояний во всех четырёх алгоритмах. Для DFS — с откатом при выходе из ветви, для остальных — глобально.
3. Подобрать тестовый набор из пяти начальных конфигураций с заведомо известными длинами оптимальных решений 4, 8, 12, 16 и 20 ходов (из своего варианта; см. § «Варианты заданий»).
4. На каждой конфигурации запустить все четыре алгоритма с одинаковым лимитом времени (например, 30 с) и собрать метрики: число раскрытых вершин, длина найденного решения, общее время в секундах, размер фронтира на пике.
5. Сложить результаты в таблицу с пятью строками (по конфигурации) и колонками по алгоритмам. Подсчитать среднее по строкам.

Результат

Сводная таблица сравнения и краткий (3–5 предложений на алгоритм) комментарий: какие теоретические свойства подтвердились, какие — нет, и какие наблюдаются расхождения с $O$-оценками из лекции. Минимум одна конфигурация должна быть такой, на которой DFS не вернул оптимальное решение, а IDDFS — вернул; этот случай прокомментировать отдельно.

Часть 2. Мини-экспертная система

Задание

1. Выбрать предметную область из своего варианта (см. § «Варианты заданий»). Сформулировать 8–12 продукционных правил и 5–7 начальных фактов, потенциально доступных через диалог с пользователем.
2. Реализовать базу знаний в виде Python-структуры: список правил (каждое — пара «список условий» / «заключение») и множество фактов. Запрещено использовать готовые движки правил (durable_rules, experta и т. п.) — реализация целиком собственная.
3. Реализовать прямой вывод как функцию, которая многократно проходит по правилам и порождает новые факты до фиксации (нет новых выводов). Запрос недостающих фактов у пользователя реализовать через input().
4. Реализовать обратный вывод как рекурсивную функцию, доказывающую заданную цель: цель есть либо в фактах, либо в заключении правила, чьи условия можно доказать рекурсивно, либо запрашивается у пользователя.
5. Прогнать систему в двух режимах на трёх сценариях с разным составом исходных фактов. Сценарий 1: все факты, нужные для вывода главной цели, известны; сценарий 2: половина фактов известна, половину придётся запросить; сценарий 3: главная цель недоказуема при имеющихся правилах.

Результат

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

Часть 3. Анализ результатов и формирование выводов

Завершающий этап. На основании собранных метрик первой части и журналов второй сформулировать в отчёте 3–5 содержательных выводов. Минимальные тезисы, которые должны быть в выводах:

• какая стратегия поиска оказалась предпочтительной для класса задач, на котором проводилось сравнение, и при каких условиях этот выбор изменился бы;
• в каком сценарии прямой вывод имеет преимущество перед обратным и обратно;
• какие практические ограничения подходов на собственном опыте подтвердились (взрыв памяти у BFS, неоптимальность DFS, ручное составление правил у ЭС).

Эталон решения

Эталонные реализации и метрики готовятся преподавателем и в этот документ не выкладываются. Для самопроверки студент сравнивает свои метрики с типичными ориентирами:

• BFS на конфигурации с оптимальной длиной 16 раскрывает порядка $10^4$ вершин; на длине 20 — порядка $10^5$. Расхождение в пределах одного порядка укладывается в норму.
• A* с манхэттенским расстоянием на тех же конфигурациях раскрывает на один-два порядка меньше вершин, чем BFS.
• DFS без ограничения глубины может вернуть решение длиной 60–100 ходов даже там, где оптимум — 16; это ожидаемое поведение, не ошибка реализации.
• В прямом выводе при полностью известных фактах ни один вопрос пользователю не задаётся; в обратном — обычно задаются вопросы только по условиям подцелей, попадающих в путь доказательства. Если в обратном выводе задаётся столько же или больше вопросов, чем в прямом, — реализация рекурсии, скорее всего, не использует уже доказанные подцели.

Варианты заданий

Вариант студента определяется остатком от деления номера в журнале на 5. Внутри части варианты комбинируются (для головоломки — таблица «А», для экспертной системы — таблица «Б»).

А. Начальные конфигурации «восьмёрки» (для части 1)

Каждый файл варианта содержит пять конфигураций с заведомо известными длинами оптимальных решений 4, 8, 12, 16 и 20 ходов.

Б. Предметная область экспертной системы (для части 2)

Состав 8–12 правил и 5–7 фактов студент проектирует самостоятельно. База знаний должна быть нетривиальной: хотя бы одно правило с тремя и более условиями, хотя бы одна цепочка длиной 3 и более правил.

Форма отчёта

Отчёт сдаётся в виде Jupyter-ноутбука и сопроводительного report.md в ветке студента по практическому занятию 2. Помимо общих требований к составу отчёта (см. правила выполнения работ практикума), специфично для этой работы:

• ноутбук 01_search.ipynb: реализации четырёх алгоритмов, прогон на пяти конфигурациях варианта, сводная таблица как pandas DataFrame, текстовый блок с анализом по части 1;
• ноутбук 02_inference.ipynb: база знаний (правила + начальные факты), реализации прямого и обратного вывода, журналы трёх сценариев в каждом режиме, текстовый блок с анализом по части 2;
• report.md: сводные выводы по части 3 (3–5 содержательных тезисов с опорой на конкретные цифры из ноутбуков).

Контрольные вопросы

1. Почему BFS оптимален при одинаковой стоимости переходов, а DFS — нет? Что должно поменяться в DFS, чтобы он стал оптимальным?
2. У IDDFS и A* пространственная сложность одного порядка — $O(bd)$. Какое практическое следствие из этого вытекает для задач с большим $b^d$?
3. Эвристика «число фишек не на своих местах» доминируется манхэттенским расстоянием. Можно ли построить ещё более сильную допустимую эвристику для «восьмёрки» — и какой ценой?
4. В чём разница между «допустимостью» и «состоятельностью» эвристики? Приведите пример эвристики, допустимой, но не состоятельной.
5. В каком классе сценариев обратный вывод задаёт меньше вопросов пользователю, чем прямой? Поясните на материале своего варианта.
6. Что такое «комбинаторный взрыв» в продукционной системе и какие меры на практике используют для его сдерживания?
7. Может ли A* с недопустимой эвристикой найти оптимальное решение? Если да, то при каких условиях; если нет, то почему?
8. Как изменится поведение прямого вывода, если в правиле случайно поменять местами условие и заключение?