Часть 6.

<Цель ><может ><описывать ><состояние, ><например ><выигрышную ><конфигурацию ><в ><игре ><"крестики-нолики" ><(рис. ><П.5) ><или ><"пятнашки" ><(рис. ><3.5). ><С ><другой ><стороны, ><цель ><может ><описывать ><некоторые ><свойства ><допустимых ><путей. ><В ><задаче ><о ><коммивояжере ><(рис. ><3.7 ><и ><3.8) ><поиск ><заканчивается ><при ><нахождении ><кратчайшего ><пути ><через ><все ><вершины ><графа. ><В ><задаче ><грамматического ><анализа ><(раздел ><3.3) ><поиск ><завершается ><нахождением ><пути ><ус><пешного ><анализа ><предложения.>

<Дуги ><в ><пространстве ><состояний ><соответствуют ><шагам ><процесса ><решения, ><а ><пути ><пред><ставляют ><решения ><на ><различной ><стадии ><завершения. ><Путь ><является ><целью ><поиска. ><Он ><на><чинается ><из ><исходного ><состояния ><и ><продолжается ><до ><тех ><пор, ><пока ><не ><будет ><достигнуто ><условие ><цели. ><Порождение ><новых ><состояний ><вдоль ><пути ><обеспечивается ><такими ><операто><рами, ><как ><"допустимые ><ходы" ><в ><игре ><или ><правила ><вывода ><в ><логической ><задаче ><или ><экс><пертной ><системе.>

<Задача ><алгоритма ><поиска ><состоит ><в ><нахождении ><допустимого ><пути ><в ><пространстве ><со><стояний. ><Алгоритмы ><поиска ><должны ><направлять ><пути ><от ><начальной ><вершины ><к ><целевой, ><поскольку ><именно ><они ><содержат ><цепочку ><операций, ><ведущую ><к ><решению ><задачи.>

<Одна ><из ><общих ><особенностей ><графа ><и ><одна ><из ><проблем, ><возникающих ><при ><создании ><алгоритма ><поиска ><на ><графе, ><состоит ><в ><том, ><что ><состояния ><иногда ><могут ><быть ><достигнуты ><разными ><путями. ><Например, ><на ><рис. ><3.3 ><путь ><от ><вершины ><а ><к ><вершине ><может ><проходить ><через ><вершины ><иb и c ><><либо ><непосредственно ><от ><а ><к ><Поэтому ><важно ><выбрать ><оптималь><ный ><путь ><решения ><данной ><задачи. ><Кроме ><того, ><множественные ><пути ><к ><состоянию ><могут ><привести ><к ><петлям ><или ><циклам. ><Тогда ><алгоритм ><никогда ><не ><достигнет ><цели. ><Если ><в ><каче><стве ><целевой ><вершины ><на ><рис. ><3.3 ><выбрать ><вершину ><в, ><а ><в ><качестве ><начальной ><- ><вершину ><а, ><то ><образуется ><циклический ><путь >

<Если ><пространство ><поиска ><описывается ><деревом, ><как ><на ><рис. ><3.4, ><проблема ><зацикли><вания ><не ><возникает. ><Именно ><поэтому ><важно ><отличать ><задачи ><поиска ><на ><деревьях ><от ><задач ><поиска ><на ><графах ><с ><петлями. ><Алгоритмы ><поиска ><на ><произвольных ><графах ><должны ><обна><руживать ><и ><устранять ><петли ><в ><допустимых ><путях. ><При ><этом ><алгоритмы ><поиска ><на ><деревь><ях ><выигрывают ><в ><эффективности ><за ><счет ><отсутствия ><этих ><тестов ><и ><затрат ><на ><них.>

<Игры ><в ><"крестики-нолики" ><и ><"пятнашки" ><можно ><использовать ><для ><иллюстрации ><поиска ><в ><пространстве ><состояний. ><Оба ><эти ><примера ><объясняют ><смысл ><условия ><1 ><в ><предыдущем ><оп><ределении. ><В ><задаче ><о ><коммивояжере ><(пример ><3.1.3) ><цель ><описывается ><условием ><вида ><2.>

<ПРИМЕР ><3.1.1. ><"Крестики-нолики">

<Пространство ><состояний ><игры ><"крестики-нолики" ><изображено ><на ><рис. ><П.5. ><Исходным ><состоянием ><является ><пустая ><игровая ><доска, ><а ><конечным ><или ><целевым ><состоянием ><- ><доска, ><на ><которой ><в ><одной ><строке, ><столбце ><или ><по ><диагонали ><располагается ><три ><крестика ><(предполагается, ><что ><целью ><является ><победа ><игрока ><Путь ><из ><исходного ><состояния ><в ><конечное ><содержит ><последовательность ><ходов, ><ведущих ><к ><победе ><игрока >

<Состояниями ><в ><пространстве ><являются ><все ><возможные ><конфигурации ><из ><крестиков ><и ><ноликов, ><которые ><могут ><возникнуть ><в ><процессе ><игры. ><Конечно, ><большинство ><из ><возмож><ных ><3><9>< ><вариантов ><расположения ><символов ><{пусто, ><О}>< ><в ><девяти ><клетках ><никогда ><не ><возникает ><в ><реальной ><игре. ><Дуги ><определяются ><допустимыми ><ходами ><игры, ><которые ><со-

113>

<<стоят ><в ><поочередном ><записывании ><или ><О ><в ><пустую ><клетку. ><Граф ><пространства ><состоя><ний ><не ><является ><деревом, ><поскольку ><некоторые ><состояния ><третьего ><и ><более ><глубоких ><уровней ><могут ><быть ><достигнуты ><различными ><путями. ><Однако ><в ><пространстве ><состояний ><нет ><циклов, ><так ><как ><ориентированные ><дуги ><графа ><не ><позволяют ><возвращаться ><в ><уже ><пройденное ><состояние. ><Если ><состояние ><достигнуто, ><вернуться ><вверх ><по ><графу ><невозмож><но. ><Следовательно, ><нет ><необходимости ><проверки ><на ><цикл. ><Граф ><с ><этим ><свойством ><назы><вается ><ациклическим ><ориентированным ><графом ><(directed ><сокращенно ><и ><часто ><встречается ><при ><поиске ><в ><пространстве ><состояний.>

<>

<Рис. ><3.5. ><15-головоломка ><и ><8-головоломка>

<Вид ><пространства ><состояний ><дает ><возможность ><определить ><сложность ><задачи. ><В ><игре ><"крестики-нолики" ><возможны ><девять ><первых ><ходов ><и ><восемь ><ответов ><противника ><на ><каждый ><из ><них, ><затем ><следуют ><семь ><возможных ><вариантов ><поставить ><крестик ><и ><т.д. ><Следовательно, ><имеется ><9х8х7х...х1=9! ><всевозможных ><путей. ><Такое ><количество ><путей ><(362880) ><компьютер ><способен ><обработать ><непосредственно ><полным ><перебором. ><Однако ><существует ><немало ><важ><ных ><задач, ><имеющих ><очень ><высокую ><факториальную ><или ><экспоненциальную ><сложность, ><ко><торая ><на ><много ><порядков ><выше, ><чем ><в ><этом ><случае. ><Например, ><в ><шахматах ><имеется ><10><ш>< ><воз><можных ><игровых ><путей; ><в ><шашках ><- ><10><40><, ><причем ><некоторые ><из ><них ><никогда ><не ><возникают ><в ><реальных ><играх. ><Такие ><пространства ><чрезвычайно ><сложны, ><и ><их ><невозможно ><исследовать ><про><стым ><перебором ><вариантов. ><Стратегии ><поиска ><в ><пространствах ><больших ><размеров ><используют ><эвристики, ><позволяющие ><уменьшить ><сложность ><поиска ><(глава ><4).>

<ПРИМЕР ><3.1.2. ><8-головоломка>

<В ><игре ><в ><"пятнашки" ><с ><пятнадцатью ><фишками, ><или ><15-головоломке, ><на ><рис. ><3.5 ><пятна><дцать ><пронумерованных ><фишек ><размещены ><на ><поле ><из ><16 ><клеток. ><Одна ><клетка ><остается ><пустой, ><так ><что ><фишки ><можно ><двигать ><и ><получать ><их ><различные ><конфигурации. ><Цель ><иг><ры ><- ><найти ><такую ><последовательность ><перемещений ><фишек ><в ><пустую ><клетку, ><которая ><привела ><бы ><к ><заранее ><заданной ><целевой ><конфигурации. ><Это ><популярная ><игра, ><которой ><большинство ><из ><нас ><забавлялось ><в ><детстве. ><(Я ><помню ><трехдюймовый ><квадрат ><с ><красными ><и ><белыми ><фишками, ><окаймленными ><черным ><цветом).>

<Некоторые ><аспекты ><этой ><игры ><оказались ><весьма ><интересными ><для ><исследований ><в ><об><ласти ><искусственного ><интеллекта. ><С ><одной ><стороны, ><пространство ><состояний ><этой ><игры ><является ><достаточно ><большим, ><чтобы ><представлять ><интерес, ><а ><с ><другой ><- ><вполне ><дос><тупным ><для ><анализа ><(число ><возможных ><состояний ><составляет ><16!, ><если ><различать ><сим><метричные ><состояния). ><Состояния ><игры ><легко ><представимы. ><Игра ><достаточно ><богата ><для ><апробации ><интересных ><эвристик ><(см. ><главу ><4).>

<8-головоломка- ><это ><версия ><15-головоломки ><размерности ><3x3. ><В ><этой ><головоломке ><8 ><фишек ><можно ><передвигать ><в ><пространстве ><из ><9 ><клеток. ><Поскольку ><пространство ><состоя->

114

<<ний ><этой ><игры ><меньше, ><чем ><в ><15-головоломке, ><именно ><ее ><мы ><будем ><использовать ><в ><по><следующих ><примерах.>

<В ><реальной ><жизни ><ходы ><в ><головоломке ><заключаются ><в ><перемещении ><фишек ><("передвинуть ><фишку ><7 ><вправо ><при ><условии, ><что ><пустая ><клетка ><расположена ><справа ><от ><нее" ><или ><"переместить ><фишку ><3 ><вниз"), ><однако ><значительно ><удобнее ><говорить ><о ><"перемещении ><пустой ><клетки". ><Это ><упрощает ><определение ><хода, ><так ><как ><в ><игре ><участвуют ><8 ><фишек ><и ><только ><одна ><пустая ><клетка. ><Допустимыми ><являются ><следующие ><ходы.>

<Переместить ><пустую ><клетку ><вверх >< ><Переместить ><пустую ><клетку ><вправо ><Переместить ><пустую ><клетку ><вниз >< ><Переместить ><пустую ><клетку ><влево >

<Чтобы ><сделать ><очередной ><ход, ><необходимо ><удостовериться, ><что ><пустая ><клетка ><не ><вый><дет ><за ><пределы ><игрового ><поля. ><Поэтому ><в ><определенных ><ситуациях ><некоторые ><из ><четырех ><ходов ><могут ><оказаться ><недопустимыми. ><Например, ><если ><пустая ><клетка ><находится ><в ><одном ><из ><углов, ><то ><допустимы ><лишь ><два ><хода. ><Если ><определены ><начальное ><и ><конечное ><состоя><ние ><в ><8-головоломке, ><то ><процесс ><решения ><задачи ><можно ><описать ><явно ><(рис. ><3.6). ><Состоя><ния ><описываются ><массивом ><размерности ><3x3. ><Предикатное ><представление ><требует ><ис><пользования ><предиката ><состояния ><с ><девятью ><параметрами ><(для ><локализации ><фишек ><на ><доске). ><Дуги ><в ><пространстве ><состояний ><определяют ><четыре ><процедуры, ><описывающие ><возможные ><перемещения ><пустой ><клетки.>

<>

<Рис. ><3.6. ><Пространство ><состояний ><8-головоломки, ><порожденное ><"перемещением ><пустой ><клетки">

<Как ><и ><при ><игре ><в ><"крестики-нолики", ><пространство ><состояний ><этой ><игры ><является ><графом, ><большинство ><вершин ><которого ><имеет ><много ><предков. ><Но, ><в ><отличие ><от ><кре><стиков-ноликов, ><в ><этом ><графе ><возможны ><циклы. ><Множество ><целевых ><состояний, ><или>

115

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

<Следует ><отметить, ><что ><полное ><пространство ><состояний ><8-головоломки ><или ><15-><головоломки ><состоит ><из ><двух ><несвязных ><подграфов ><(одинакового ><размера). ><Отсюда ><сле><дует, ><что ><ровно ><половина ><состояний ><являются ><недостижимыми ><из ><любой ><заданной ><на><чальной ><вершины. ><Если ><поменять ><местами ><(вопреки ><правилам!) ><две ><соседние ><фишки, ><все ><состояния ><из ><другой ><части ><пространства ><состояний ><окажутся ><достижимыми.>

<ПРИМЕР ><3.1.3. ><Задача ><коммивояжера>

<Предположим, ><коммивояжер ><должен ><посетить ><пять ><городов ><и ><возвратиться ><до><мой. ><Задача ><состоит ><в ><том, ><чтобы ><найти ><кратчайший ><путь. ><На ><рис. ><3.7 ><дан ><пример ><этой ><задачи. ><Вершины ><графа ><представляют ><города, ><а ><метка ><на ><каждой ><дуге ><указыва><ет ><стоимость ><путешествия ><по ><ней. ><Эта ><стоимость ><может ><означать ><длину ><отрезка ><пути ><в ><милях, ><если ><коммивояжер ><пользуется ><автомобилем, ><или ><цену ><авиабилета ><при ><ис><пользовании ><самолета. ><Для ><удобства ><предположим, ><что ><коммивояжер ><проживает ><в ><городе ><А ><и ><должен ><вернуться ><в ><город ><А. ><Это ><предположение ><попросту ><сводит ><задачу ><с ><л-городами ><к ><проблеме ><с ><л-1 ><городом.>

<>

<Рис. ><3.7. ><Пример ><пути ><в ><задаче ><коммивояжера>

<Рассмотрим ><один ><из ><возможных ><путей ><[A,D,C,B,E,A] ><длиной ><(стоимостью ><путешест><вия) ><в ><450 ><миль. ><Целью ><является ><нахождение ><пути ><кратчайшей ><длины, ><т.е. ><построение ><цепочки ><с ><минимальной ><стоимостью. ><Заметим, ><что ><цель ><- ><это ><глобальное ><свойство ><гра><фа, ><а ><не ><свойство ><отдельного ><состояния. ><Это ><пример ><целевого ><состояния ><вида ><2 ><из ><опре><деления ><поиска ><в ><пространстве ><состояний.>

<На ><рис. ><3.8 ><указан ><способ ><представления ><возможных ><путей ><решения ><задачи ><и ><приведены ><результаты ><их ><сравнения. ><Начиная ><от ><вершины ><А, ><к ><пути ><добавляются ><возможные ><следующие ><состояния ><до ><тех ><пор, ><пока ><не ><исчерпается ><список ><городов ><и ><путь ><возвратится ><в ><исходную ><точку. ><Целью ><является ><нахождение ><пути ><кратчайшей ><длины ><(минимальной ><стоимости).>

<Как ><показано ><на ><рис. ><3.8, ><исчерпывающий ><поиск ><в ><задаче ><коммивояжера ><состоит ><в ><переборе ><(N-1)! ><вариантов, ><где ><- ><число ><вершин ><графа ><(или ><число ><городов). ><Для ><9 ><го><родов ><можно ><непосредственно ><проверить ><все ><вершины. ><Но ><в ><реальных ><ситуациях, ><на-

116>

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

<>

<Рис. ><3.8. ><Поиск ><в ><задаче ><коммивояжера. ><Метка ><каждой ><дуги ><соответствует ><сум><марному ><весу ><всего ><пути ><от ><начальной ><вершины ><А ><до ><конечной ><точки ><дуги>

<Разработано ><множество ><методов, ><сокращающих ><сложность ><поиска. ><Один ><из ><них ><- ><это ><метод ><ветвей ><и ><границ ><[Horowitz ><и ><1978]. ><В ><этом ><методе ><на ><каждом ><шаге ><по><рождается ><один ><из ><возможных ><вариантов ><пути, ><при ><этом ><учитывается ><наилучший ><из ><ра><нее ><построенных ><путей. ><Этот ><путь ><используется ><в ><качестве ><границы ><для ><будущих ><канди><датов. ><Поскольку ><на ><каждом ><шаге ><к ><пути ><добавляется ><один ><город, ><алгоритм ><анализирует ><все ><возможные ><продолжения. ><Если ><обнаруживается, ><что ><все ><возможные ><продолжения ><некоторого ><пути ><(ветвь) ><дороже, ><чем ><заданная ><граница, ><алгоритм ><уничтожает ><эту ><ветвь ><и ><все ><возможные ><ее ><продолжения. ><В ><результате ><сложность ><поиска ><существенно ><сокращает><ся, ><но ><все ><же ><остается ><экспоненциальной ><(1,26n место >

<Еще ><одна ><стратегия ><состоит ><в ><конструировании ><пути ><по ><правилу ><"идти ><в ><бли><жайший ><не ><посещенный ><город". ><Путь ><к ><"ближайшему ><соседу" ><на ><рис. ><3.7 ><- ><это ><[А, ><Е, ><В, ><С, ><А], ><его ><стоимость ><375 ><миль. ><Этот ><метод ><высоко ><эффективен, ><так ><как ><на ><каждом ><шаге ><выбирается ><лишь ><один ><вариант! ><К ><сожалению, ><эвристика ><поиска ><ближайшего ><соседа ><не ><всегда ><приводит ><к ><получению ><пути ><кратчайшей ><длины, ><как ><показано ><на ><рис. ><3.9. ><Однако ><она ><является ><возможным ><компромиссом ><в ><случае, ><если ><полный ><перебор ><неосуществим ><практически.>

<В ><разделе ><3.2 ><исследуются ><стратегии ><поиска ><в ><пространстве ><состояний.>

117<<>

<Рис. ><3.9. ><Пример ><пути ><в ><задаче ><коммивояжера, ><полученный ><на ><основе ><поиска ><ближайшего ><соседа. ><Заметим, ><что ><этот ><путь ><{A,E,D,B,C,A) ><имеет ><стоимость ><550 ><и ><не ><является ><кратчайшим. ><Срав><нительно ><высокая ><стоимость ><дуги ><(С,А) ><не ><учи><тывается ><эвристикой>

<3.2. ><Стратегии ><поиска ><в ><пространстве ><состояний>

<><3.2.1. ><Поиск ><на ><основе ><данных ><и ><от ><цели>

<Поиск ><в ><пространстве ><состояний ><можно ><вести ><в ><двух ><направлениях: ><от ><исходных ><дан><ных ><задачи ><к ><цели ><и ><в ><обратном ><направлении ><от ><цели ><к ><исходным ><данным.>

<При ><поиске ><на ><основе ><данных ><(data-driven >

<- ><поиск, ><управляемый ><данными), ><ко><торый ><иногда ><называют ><прямой ><цепочкой ><(forward ><исследователь ><начинает ><про><цесс ><решения ><задачи, ><анализируя ><ее ><условие, ><а ><затем ><применяет ><допустимые ><ходы ><или ><пра><вила ><изменения ><состояния. ><В ><процессе ><поиска ><правила ><применяются ><к ><известным ><фактам ><для ><получения ><новых ><фактов, ><которые, ><в ><свою ><очередь, ><используются ><для ><генерации ><новых ><фактов. ><Этот ><процесс ><продолжается ><до ><тех ><пор, ><пока ><мы, ><если ><повезет, ><не ><достигнем ><цели.>

<Возможен ><и ><альтернативный ><подход. ><Рассмотрим ><цель, ><которую ><мы ><хотим ><достичь. ><Проанализируем ><правила ><или ><допустимые ><ходы, ><ведущие ><к ><цели, ><и ><определим ><условия ><их ><применения. ><Эти ><условия ><становятся ><новыми ><целями, ><или ><подцелями, ><поиска. ><Поиск ><продолжается ><в ><обратном ><направлении ><от ><достигнутых ><подцелей ><до ><тех ><пор, ><пока ><(если ><повезет) ><мы ><не ><достигнем ><исходных ><данных ><задачи. ><Таким ><образом, ><определяется ><путь ><от ><данных ><к ><цели, ><который ><на ><самом ><деле ><строится ><в ><обратном ><направлении. ><Этот ><подход ><называется ><поиском ><от ><цели, ><или ><обратной ><цепочкой. ><Он ><напоминает ><простой ><детский ><трюк, ><заключающийся ><в ><поиске ><выхода ><из ><лабиринта ><из ><конечного ><искомого ><состояния ><к ><заданному ><начальному.>

<Подведем ><итоги: ><поиск ><на ><основе ><данных ><начинается ><с ><условий ><задачи ><и ><выполняется ><путем ><применения ><правил ><или ><допустимых ><ходов ><для ><получения ><новых ><фактов, ><ведущих ><к ><цели. ><Поиск ><от ><цели ><начинается ><с ><обращения ><к ><цели ><и ><продолжается ><путем ><>определения< ><правил, ><которые ><могут ><привести ><к ><цели, ><и ><построения ><цепочки ><подцелей, ><ведущей ><к ><исходным ><данным ><задачи.

118>

<<Наконец ><заметим, ><что ><в ><обоих ><случаях ><(и ><при ><поиске ><на ><основе ><данных ><и ><при ><поиске ><от ><цели) ><исследователь ><работает ><с ><одним ><и ><тем ><же ><графом ><пространства ><состояний, ><од><нако ><порядок ><и ><число ><состояний ><в ><процессе ><поиска ><могут ><различаться. ><Какую ><стратегию ><поиска ><предпочесть, ><зависит ><от ><самой ><задачи. ><При ><этом ><следует ><учитывать ><сложность ><правил, ><"форму" ><пространства ><состояний, ><природу ><и ><доступность ><данных ><задачи. ><Все ><это ><может ><изменяться ><от ><задачи ><к ><задаче.>

<Как ><пример ><зависимости ><сложности ><поиска ><от ><выбора ><стратегии ><рассмотрим ><задачу, ><в ><которой ><нужно ><подтвердить ><или ><опровергнуть ><утверждение ><"Я- ><потомок ><Томаса ><Джефферсона". ><Положительным ><решением ><является ><путь ><по ><генеалогическому ><дереву ><от ><"Я" ><до ><"Томас ><Джефферсон". ><Поиск ><на ><этом ><графе ><можно ><вести ><в ><двух ><направлениях: ><начиная ><от ><вершины ><"Я" ><строить ><цепочку ><предков ><к ><вершине ><"Томас ><Джефферсон", ><или ><начиная ><с ><вершины ><"Томас ><Джефферсон" ><анализировать ><цепочку ><его ><потомков.>

<Простая ><оценка ><позволяет ><сравнить ><сложность ><поиска ><в ><обоих ><направлениях. ><Томас ><Джефферсон ><родился ><примерно ><250 ><лет ><назад. ><Если ><считать, ><что ><новое ><поколение ><рож><дается ><каждые ><25 ><лет, ><то ><длина ><искомого ><пути ><составляет ><примерно ><10. ><Поскольку ><>каждый< ><потомок ><имеет ><двух ><родителей, ><то ><путь ><от ><"Я" ><требует ><анализа ><2><10>< ><предков. ><С ><другой ><стороны, ><поиск ><от ><вершины ><"Томас ><Джефферсон" ><требует ><анализа ><большего ><числа ><со><стояний, ><поскольку ><родители ><обычно ><имеют ><более ><двух ><детей ><(особенно ><это ><касается ><во><семнадцатого ><и ><девятнадцатого ><столетий). ><Если ><допустить, ><что ><каждая ><семья ><имеет ><в ><среднем ><троих ><детей, ><то ><в ><процессе ><поиска ><нужно ><проанализировать ><З><10>< ><вершин ><>генеалогического< ><дерева. ><Таким ><образом, ><этот ><путь ><сложнее. ><Заметим, ><однако, ><что ><оба ><способа ><поиска ><имеют ><экспоненциальную ><сложность.>

<Модуль ><решения ><задачи ><может ><использовать ><как ><стратегию ><поиска ><на ><основе ><данных, ><так ><и ><на ><основе ><цели. ><Выбор ><зависит ><от ><структуры ><решаемой ><задачи. ><Процесс ><поиска ><от ><цели ><рекомендован ><в ><следующих ><случаях.>

<Цель ><поиска ><(или ><гипотеза) ><явно ><присутствует ><в ><постановке ><задачи ><или ><может ><быть

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

<Имеется ><большое ><число ><правил, ><которые ><на ><основе ><полученных ><фактов ><позволяют

><продуцировать ><возрастающее ><число ><заключений ><или ><целей. ><Своевременный ><отбор

><целей ><позволяет ><отсеять ><множество ><возможных ><ветвей, ><что ><делает ><процесс ><поиска

><в ><пространстве ><состояний ><более ><эффективным ><(рис. ><3.10). ><Например, ><в ><процессе

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

<Исходные ><данные ><не ><приводятся ><в ><задаче, ><но ><подразумевается, ><что ><они ><должны

><быть ><известны ><решателю. ><В ><этом ><случае ><поиск ><от ><цели ><может ><служить ><руково><дством ><для ><правильной ><постановки ><задачи. ><В ><программе ><медицинской ><диагности><ки, ><например, ><имеются ><всевозможные ><диагностические ><тесты. ><Доктор ><выбирает ><из><них ><только ><те, ><которые ><позволяют ><подтвердить ><или ><опровергнуть ><конкретную ><ги><потезу ><о ><состоянии ><пациента.>

<Таким ><образом, ><при ><поиске ><от ><цели ><подходящие ><правила ><применяются ><для ><исключе><ния ><неперспективных ><ветвей ><поиска.>

<><Глава ><3. ><Структуры ><и ><стратегии ><поиска ><в ><пространстве ><состояний

119><

<<>

<Данные>

<Рис. ><3.10. ><Пространство ><состояний, ><в ><котором ><при ><поиске ><от ><цели ><ветви ><ненужных ><направлений ><поиска ><эффективно ><отсекаются>

<>

<Цель>

<Направление

><Данные>< ><поиска>

<Рис. ><3.11. ><Пространство ><состояний, ><в ><котором ><поиск ><на ><>основе< ><данных ><отсекает ><ненужные ><данные ><и ><их ><логические ><следствия ><и ><позволяет ><определить ><одну ><из ><нескольких ><>возможных< ><целей>

<Поиск ><на ><основе ><данных ><применим ><к ><решению ><задачи ><в ><следующих ><случаях.>

<Все ><или ><большинство ><исходных ><данных ><заданы ><в ><постановке ><задачи. ><Задача ><интер><претации ><состоит ><в ><выборе ><этих ><данных ><и ><их ><представлении ><в ><виде, ><подходящем

><для ><использования ><в ><интерпретирующих ><системах ><более ><высокого ><уровня. ><На ><стра><тегии ><поиска ><от ><данных ><основаны ><системы ><анализа ><данных ><определенного ><типа.

><Это ><такие ><системы, ><как ><или ><анализаторы ><геологических

><данных, ><определяющие, ><какие ><минералы ><с ><наибольшей ><вероятностью ><могут ><быть

><найдены ><в ><некотором ><месте.>

<Существует ><большое ><число ><потенциальных ><целей, ><но ><всего ><лишь ><несколько ><спосо><бов ><применения ><фактов ><и ><представления ><информации ><о ><конкретном ><примере ><зада><чи ><(рис. ><3.11). ><Примером ><этого ><типа ><систем ><является ><программа ><- ><экспертная ><система ><исследования ><молекулярных ><структур ><органических ><соедине->

120

<<ний ><на ><основе ><формул, ><данных ><масс-спектрографа ><и ><знаний ><из ><химии. ><Для ><любого ><органического ><соединения ><существует ><чрезвычайно ><большое ><число ><возможных ><структур. ><Однако ><данные ><масс-спектрографа ><позволяют ><программе ><>оставить< ><лишь ><небольшое ><число ><таких ><комбинаций.>

<3. ><Сформировать ><цель ><или ><гипотезы ><очень ><трудно. ><Например, ><при ><использовании ><системы ><изначально ><может ><быть ><очень ><мало ><информации ><о ><возможной ><структуре ><соединения.>

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

<Подводя ><итог, ><заметим, ><что ><ничто ><не ><заменит ><тщательного ><анализа ><каждой ><>конкретной< ><задачи. ><Необходимо ><учитывать ><такие ><особенности, ><как ><фактор ><ветвления ><при ><ис><пользовании ><правил, ><доступность ><данных ><и ><простота ><определения ><потенциальных ><целей. ><В ><главе ><4 ><рассказывается ><о ><том, ><сколько ><новых ><состояний ><возникает ><в ><результате ><приме><нения ><правил ><поиска ><в ><обоих ><направлениях.>

<3.2.2. ><Реализация ><поиска ><на ><графах>

<При ><решении ><задач ><путем ><поиска ><на ><основе ><данных ><либо ><от ><цели ><требуется ><найти ><путь ><от ><начального ><состояния ><к ><целевому ><на ><графе ><пространства ><состояний. ><>Последовательность< ><дуг ><этого ><пути ><соответствует ><упорядоченной ><последовательности ><этапов ><>решения< ><задачи. ><Если ><решатель ><задач ><имеет ><в ><своем ><распоряжении ><оракула ><или ><иное ><>непогрешимое< ><средство ><предсказания ><для ><построения ><пути ><решения, ><то ><и ><поиска ><не ><>требуется<. ><Модуль ><решения ><задачи ><должен ><безошибочно ><двигаться ><прямо ><к ><цели, ><запоминая ><путь ><движения. ><Поскольку ><для ><интересных ><задач ><оракулов ><не ><существует, ><решатель ><дол><жен ><рассматривать ><различные ><пути ><до ><тех ><пор, ><пока ><не ><достигнет ><цели. ><Поиск ><с ><>возвратами< ><(backtracking) ><- ><это ><метод ><систематической ><проверки ><различных ><путей ><в ><>пространстве< ><состояний.>

<Начнем ><рассмотрение ><алгоритмов ><с ><поиска ><с ><возвратами, ><поскольку ><это ><один ><из ><>первых< ><алгоритмов ><поиска ><в ><информатике, ><который ><допускает ><естественную ><реализацию ><в ><рекурсивной ><среде, ><ориентированной ><на ><использование ><стеков ><(раздел ><5.1). ><Упрощенная ><версия ><поиска ><с ><возвратами ><на ><примере ><поиска ><в ><глубину ><(раздел ><5.1) ><будет ><реализована ><в ><части ><на ><языках ><и >

<Алгоритм ><поиска ><с ><возвратами ><запускается ><из ><начального ><состояния ><и ><следует ><по ><>некоторому< ><пути ><до ><тех ><пор, ><пока ><не ><достигнет ><цели ><либо ><не ><упрется ><в ><тупик. ><Если ><цель ><достигнута, ><поиск ><завершается, ><и ><в ><качестве ><решения ><задачи ><возвращается ><путь ><к ><цели. ><Если ><же ><поиск ><привел ><в ><тупиковую ><вершину, ><то ><алгоритм ><возвращается ><в ><ближайшую ><из ><пройденных ><вер><шин ><и ><исследует ><все ><ее ><вершины-братья, ><а ><затем ><спускается ><по ><одной ><из ><ветвей, ><ведущих ><от ><вершины-брата. ><Этот ><процесс ><описывается ><следующим ><рекурсивным ><правилом.>

<Если ><исходное ><состояние ><не ><удовлетворяет ><требованиям ><цели, ><то ><из ><списка ><его ><потомков ><выбираем ><первый ><, ><и ><к ><этой ><вершине ><рекурсивно ><применяем ><процедуру ><поиска ><с ><воз><вратами. ><Если ><в ><результате ><поиска ><с ><возвратами ><в ><подграфе ><с ><корнем ><Цель ><не ><обна><ружена, ><то ><повторяем ><процедуру ><для ><вершины-брата ><Эта ><процедура ><продолжается ><до ><тех ><пор, ><пока ><один ><из ><потомков ><рассматриваемой ><вершины-брата ><не ><окажется ><целевым ><узлом, ><либо ><не ><выяснится, ><что ><рассмотрены ><уже ><все ><возможные ><потомки ><(все ><вершины-><братья). ><Если ><же ><ни ><одна ><из ><вершин-братьев ><вершины ><не ><привела ><к ><цели, ><возвращаемся ><к ><предку ><вершины ><и ><повторяем ><процедуру ><с ><вершиной-братом ><и ><т.д.>

<><Глава ><3. ><Структуры ><и ><стратегии ><поиска ><в ><пространстве ><состояний

121><

<<Алгоритм ><работает ><до ><тех ><пор, ><пока ><не ><достигнет ><цели ><либо ><не ><исследует ><все ><>пространство< ><состояний. ><На ><рис. ><3.12 ><изображен ><процесс ><поиска ><с ><возвратами ><в ><>гипотетическом< ><пространстве ><состояний. ><Пунктирные ><стрелки ><в ><дереве ><указывают ><направление ><процесса ><поиска ><в ><пространстве ><состояний ><(вниз ><или ><вверх). ><Числа ><возле ><каждой ><>вершины< ><указывают ><порядок ><их ><посещения. ><Ниже ><приведем ><алгоритм ><поиска ><с ><возвратами. ><В ><нем ><используются ><три ><списка, ><позволяющих ><запоминать ><путь ><от ><узла ><к ><узлу ><в ><>пространстве< ><состояний.>

<(State ><- ><список ><исследованных ><состояний ><рассматриваемого ><пути. ><Если ><цель ><уже ><найдена, ><то ><содержит ><список ><состояний ><пути ><решения.>

<(New ><- ><список ><новых ><состояний, ><он ><содержит ><вершины, ><подлежащие ><рассмотрению, ><т.е. ><список ><вершин, ><потомки ><которых ><еще ><не ><были ><порождены ><и ><рас><смотрены.>

<(Dead ><- ><список ><тупиков, ><т.е. ><список ><вершин, ><потомки ><которых ><уже ><были ><ис><следованы, ><но ><не ><привели ><к ><цели. ><Если ><состояние ><из ><этого ><списка ><снова ><встречается ><в ><процессе ><поиска, ><то ><оно ><обнаруживается ><в ><списке ><и ><исключается ><из ><рассмотрения.>

<При ><описании ><алгоритма ><поиска ><с ><возвратами ><на ><графах ><общего ><вида ><(не ><только ><для ><деревьев) ><необходимо ><учитывать ><возможность ><повторного ><появления ><состояний, ><чтобы ><избежать ><их ><повторного ><рассмотрения, ><а ><также ><петель, ><ведущих ><к ><зацикливанию ><>алгоритма< ><поиска ><пути. ><Это ><обеспечивается ><проверкой ><каждой ><вновь ><порожденной ><вершины ><на ><ее ><вхождение ><в ><один ><из ><трех ><вышеуказанных ><списков. ><Если ><новое ><состояние ><>обнаружится< ><хотя ><бы ><в ><одном ><из ><двух ><списков ><или ><значит, ><оно ><уже ><рассматривалось, ><и ><его ><следует ><проигнорировать.>

<%инициализация:>

< >< >< >< >< >< >< ><%пока ><существуют ><неисследованные ><состояния >

<или>< ><удовлетворяет ><описанию ><цели) >< >< >< >< ><%при ><нахождении ><цели ><вернуть ><список>

<%состояний ><пути.>

<не ><имеет ><потомков ><(исключая ><узлы, ><входящие ><в >

<не ><пуст ><и ><С><=первый ><элемент ><списка >

>

><добавить ><в >< ><%внести ><состояние ><в ><список>

<%тупиков>

<удалить ><первый ><элемент ><из >< ><%возврат ><удалить ><первый ><элемент ><из ><первый ><элемент >

<добавить ><в >

<поместить ><потомок ><(кроме ><узлов, ><уже ><содержащихся ><в >

<или ><в ><первый ><элемент ><добавить ><в >

122>

<

<Обозначим ><текущее ><состояние ><при ><поиске ><с ><возвратами ><через ><(current ><Со><стояние ><всегда ><равно ><последнему ><из ><состояний, ><занесенных ><в ><список ><и ><>представляет< ><"фронтальную" ><вершину ><на ><построенном ><в ><данный ><момент ><пути. ><Правила ><вывода, ><ходы ><в ><игре ><или ><иные ><соответствующие ><операторы ><решения ><задачи ><упорядочиваются ><и ><применяются ><к ><В ><результате ><возникает ><упорядоченное ><множество ><новых ><состояний, ><потомков ><Первый ><из ><этих ><потомков ><объявляется ><новым ><текущим ><состоянием, ><а ><>остальные< ><заносятся ><в ><список ><новых ><состояний ><для ><дальнейшего ><изучения. ><Новое ><>текущее< ><состояние ><заносится ><в ><список ><состояний ><и ><поиск ><продолжается. ><Если ><текущее ><состояние ><не ><имеет ><потомков, ><то ><оно ><удаляется ><из ><списка ><состояний ><(именно ><в ><этот ><момент ><алгоритм ><"возвращается ><назад"), ><и ><исследуется ><какой-либо ><из ><оставшихся ><потомков ><его ><предка ><в ><списке ><состояний >

<Алгоритм ><поиска ><с ><возвратами ><на ><графе ><из ><рис. ><3.12 ><работает ><следующим ><образом.>

<Инициализируем ><списки.>

< >< >< >< ><[]; >< >< >

<>

<Поиск ><с ><возвратами ><в ><данном ><случае ><является ><поиском ><на ><основе ><данных, ><при ><>котором< ><корень ><дерева ><связывается ><с ><начальным ><состоянием, ><а ><потомки ><узлов ><анализируются ><для ><построения ><пути ><к ><цели. ><Этот ><же ><алгоритм ><можно ><интерпретировать ><и ><как ><поиск ><от ><цели. ><Для ><этого ><целевую ><вершину ><следует ><взять ><в ><качестве ><корня ><дерева ><и ><анализировать ><совокупность ><предков ><для ><нахождения ><пути ><к ><начальному ><состоянию. ><При ><>использовании< ><цели ><вида ><2 ><(см. ><подраздел ><3.1.2) ><этот ><алгоритм ><должен ><определить ><целевое ><>состояние<, ><исследуя ><путь ><для >

<Поиск ><с ><возвратами ><(backtrack) ><- ><это ><алгоритм ><поиска ><на ><графе ><пространства ><состояний. ><Алгоритмы ><поиска ><на ><графах, ><которые ><будут ><рассматриваться ><далее, ><включая ><поиск ><в ><глубину ><(depth-first), ><поиск ><в ><ширину ><(breadth-first) ><и ><поиск ><по ><первому ><наилучшему ><совпадению ><(best-><используют ><идеи ><поиска ><с ><возвратами, ><в ><том ><числе ><следующие.>

<Формируется ><список ><неисследованных ><состояний ><(NSL), ><для ><того ><чтобы ><иметь

><возможность ><возвратиться ><к ><любому ><из ><них.>

<Поддерживается ><список ><"неудачных" ><состояний ><(DE), ><чтобы ><оградить ><алгоритм ><от

><проверки ><бесполезных ><путей.

123>

<<>

<Рис. ><3.12. ><Поиск ><с ><возвратами ><в ><>гипотетическом< ><пространстве ><состояний>

<Поддерживается ><список ><узлов ><(SL) ><текущего ><пути, ><который ><возвращается ><по ><достижении ><цели.>

<Каждое ><новое ><состояние ><проверяется ><на ><вхождение ><в ><эти ><списки, ><чтобы ><предотвратить ><зацикливание.>

<В ><следующем ><разделе ><рассматриваются ><алгоритмы ><с ><использованием ><списков, ><>подобные< ><алгоритму ><поиска ><с ><возвратами. ><Эти ><алгоритмы, ><среди ><которых ><поиск ><в ><глубину, ><поиск ><в ><ширину ><и ><поиск ><по ><первому ><наилучшему ><совпадению ><(глава ><4), ><отличаются ><от ><по><иска ><с ><возвратами ><более ><гибкими ><средствами ><и ><стратегиями ><поиска.>

<3.2.3. ><Поиск ><в ><глубину ><и ><в ><ширину>

<Определив ><направление ><поиска ><(от ><данных ><или ><от ><цели), ><алгоритм ><поиска ><должен ><>определить< ><порядок ><исследования ><состояний ><дерева ><или ><графа. ><В ><этом ><разделе ><>рассматриваются< ><два ><возможных ><варианта ><последовательности ><обхода ><узлов ><графа: ><поиск ><в ><глубину ><(depth-fist) ><и ><поиск ><в ><ширину ><(breadth-first).>

<Рассмотрим ><граф, ><представленный ><на ><рис. ><3.13. ><Состояния ><в ><нем ><обозначены ><буквами ><(А, ><В, ><С, ><...), ><чтобы ><на ><них ><можно ><было ><сослаться ><в ><следующих ><рассуждениях. ><При ><поиске ><в ><глубину ><после ><исследования ><состояния ><сначала ><необходимо ><оценить ><все ><его ><потомки ><и ><их ><по><томки, ><а ><затем ><исследовать ><любую ><из ><вершин-братьев. ><Поиск ><в ><глубину ><по ><возможности ><>углубляется< ><в ><область ><поиска. ><Если ><дальнейшие ><потомки ><состояния ><не ><найдены, ><>рассматриваются< ><вершины-братья. ><Поиск ><в ><глубину ><исследует ><состояния ><графа ><на ><рис. ><3.13 ><в ><таком ><по><рядке: ><А, ><В, ><Е, ><К, ><М, ><С, ><Н, ><О, ><Р, ><О, ><Алгоритм ><поиска ><с ><возвратами, ><рассмотренный ><в ><подразделе ><3.2.2, ><осуществляет ><поиск ><в ><глубину.>

<Поиск ><в ><ширину, ><напротив, ><исследует ><пространство ><состояний ><по ><уровням, ><один ><за ><другим. ><И ><только ><если ><состояний ><на ><данном ><уровне ><больше ><нет, ><алгоритм ><переходит ><к ><следующему ><уровню. ><При ><поиске ><в ><ширину ><на ><графе ><из ><рис. ><3.13 ><состояния ><>рассматриваются< ><в ><таком ><порядке: ><А, ><В, ><С, ><Е, ><И, ><К, ><О, ><Р, >

<Поиск ><в ><ширину ><осуществляется ><с ><использованием ><списков ><и ><>позволяющих< ><отслеживать ><продвижение ><в ><пространстве ><состояний. ><Список ><подобно ><в ><алгоритме ><поиска ><с ><возвратами, ><содержит ><сгенерированные ><состояния, ><потомки ><которых ><еще ><не ><были ><исследованы. ><Порядок ><удаления ><состояний ><из ><списка ><>определяет< ><порядок ><поиска. ><В ><список ><заносятся ><уже ><исследованные ><состояния. ><Спи><сок ><объединяет ><списки ><и ><используемые ><в ><алгоритме ><поиска ><с ><возвратами.>

124

<<>

<Рис. ><3.13. ><Граф, ><демонстрирующий ><работу ><алгорит><мов ><поиска ><в ><глубину ><и ><в ><ширину>

<= ><[Start] ><;>< ><%инициализация>

< >< ><:= >< >< ><[ >< >< ><];>

<=>< >< >< ><[ >< >< ><] >< >< >< ><%есть >< ><состояния>

<удалить >< ><крайнее >< ><слева >< ><состояние ><из >< >< ><скажем >

><- >< ><цель >< >< ><%цель >< ><найдена>

<сгенерировать >< ><потомок >

<поместить ><в >< ><список >

<исключить >< ><потомок >< >< ><если ><он ><уже >< ><в >< ><списке>

<или >< ><%проверка ><на ><цикл>

<поместить >< ><остальные >< ><потомки ><в>

<правый ><конец ><списка >< >< >< >< >< >< ><%очередь >

< ><%состояний ><не >< ><осталось>

<Дочерние ><состояния ><генерируются ><правилами ><вывода, ><допустимыми ><ходами ><>игры<, ><или ><другими ><операциями ><перехода ><состояний. ><На ><каждой ><итерации ><>генерируются< ><все ><дочерние ><вершины ><состояния ><и ><записываются ><в ><Заметим, ><что ><список ><действует ><как ><очередь ><и ><обрабатывает ><данные ><в ><порядке ><поступления ><(или ><"первым ><поступил ><- ><первым ><обслужен"). ><Это ><структура ><данных ><Состояния ><добавляются ><в ><список ><справа, ><а ><удаляются ><слева. ><Таким ><образом, ><в ><поиске ><участвуют ><состояния, ><которые ><находятся ><в ><списке ><дольше ><всего, ><>обеспечивая< ><поиск ><в ><ширину. ><Дочерние ><состояния, ><которые ><были ><уже ><записаны ><в ><списки ><или ><отбрасываются. ><Если ><алгоритм ><завершается ><из-за ><невыполнения ><условия ><цикла ><(open= ><[ ><]), ><то ><можно ><заключить, ><что ><весь ><граф ><исследован, ><а ><желаемая ><цель ><не ><достигнута. ><Следовательно, ><поиск ><потерпел ><неудачу.>

125

<<Проследим ><путь ><алгоритма ><поиска ><в ><ширину >breadth_first_search< ><на ><графе, ><изображенном ><на ><рис. ><3.13. ><Числа ><2, ><3, ><4,... ><означают ><номер ><итерации ><цикла ><При ><этом ><- ><это ><желаемое ><целевое ><состояние.>

<1>

<2>

<3,>

<4.>

<5.>

<6.>

<7.>

<8.>

<9.>

<ореп=[А]; ><[]>

<; ><[В,А]>

<; ><[С,В,А]>

<; >

<; >

<(так ><как ><уже ><в ><С,В,А]>

<; >< >< >

<И ><так ><далее, >< >< ><пока ><или ><найдено, >< >< ><или ><ореn=[]>

<На ><рис. ><3.14 ><показан ><граф, ><изображенный ><на ><рис. ><3.13, ><после ><шести ><итераций ><поиска ><в ><ши><рину. ><Состояния ><из ><списков ><и ><на ><рис. ><3.14 ><выделены ><цветом. ><Не ><выделенные ><состояния ><не ><были ><исследованы ><алгоритмом. ><Заметим, ><что ><"пограничные" ><состояния ><поиска ><на ><любой ><стадии ><записываются ><в ><а ><уже ><рассмотренные ><- ><в >

<Поскольку ><при ><поиске ><в ><ширину ><узлы ><графа ><рассматриваются ><по ><уровням, ><сначала ><исследуются ><те ><состояния, ><пути ><к ><которым ><короче. ><Поиск ><в ><ширину, ><таким ><образом, ><>гарантирует< ><нахождение ><кратчайшего ><пути ><от ><начального ><состояния ><к ><цели. ><Более ><того, ><поскольку ><вначале ><исследуются ><состояния, ><найденные ><по ><кратчайшему ><пути, ><при ><>повторном< ><проходе ><это ><состояние ><отбрасывается.>

<Иногда ><помимо ><имен ><состояний ><в ><и ><необходимо ><хранить ><дополнительную ><информацию. ><Например, ><заметим, ><что ><алгоритм ><поиска ><в ><ширину ><не ><поддерживает ><список ><состояний ><на ><текущем ><пути ><к ><цели, ><как ><это ><делалось ><при ><поиске ><с ><возвратами >< (backtrack) ><в ><списке ><Все ><посещенные ><состояния ><хранятся ><в ><Если ><путь ><является ><>решением<, ><то ><он ><возвращается ><алгоритмом. ><Это ><может ><быть ><сделано ><путем ><накопления ><>информации< ><о ><предках ><для ><каждого ><состояния. ><Состояние ><хранится ><вместе ><с ><записью ><>родительского< ><состояния, ><т.е. ><в ><виде ><пары ><(состояние, ><родитель). ><Для ><графа ><на ><рис. ><3.13 ><содержание ><списков ><и ><на ><четвертой ><итерации ><было ><бы ><следующим. ><, ><(Е,В)><, ><(F,B)><, ><(G,C)><, ><(H,C)><]; >< >< ><[(С,А) ><, ><(В,А), ><(A,nil)><]>

<>

<Рис. ><3.14. ><Граф ><из ><рис. ><3.13 ><на ><6 ><итерации ><выполнения ><ал><горитма ><поиска ><в ><ширину. ><Состояния, ><содержащиеся ><в ><списках ><и ><выделены ><цветом

126>

<<Используя ><эту ><информацию, ><можно ><легко ><построить ><путь ><(А, ><В, ><ведущий ><от ><А ><к ><Когда ><цель ><найдена, ><алгоритм ><может ><восстановить ><путь ><решения, ><прослеживая ><его ><в ><об><ратном ><направлении ><от ><цели ><к ><начальному ><состоянию ><по ><родительским ><состояниям. ><За><метим, ><что ><состояние ><А ><имеет ><родителя ><(нуль), ><т.е. ><является ><начальным ><состоянием. ><Это ><служит ><сигналом ><прекращения ><восстановления ><пути. ><Поскольку ><поиск ><в ><ширину ><на><ходит ><каждое ><состояние ><по ><кратчайшему ><пути ><и ><сохраняет ><первую ><версию ><каждого ><со><стояния, ><этот ><путь ><от ><начала ><до ><цели ><является ><самым ><коротким.>

<На ><рис. ><3.15 ><показаны ><состояния, ><удаленные ><из ><и ><исследованные ><алгоритмом ><поиска ><в ><ширину ><для ><8-головоломки. ><Как ><и ><прежде, ><дуги ><соответствуют ><перемещению ><пустой ><клетки ><вправо, ><вниз ><и ><влево. ><Номер ><рядом ><с ><каждым ><состоянием ><указывает ><порядок ><удаления ><из ><В ><графе ><не ><показаны ><состояния, ><оставшиеся ><в ><по ><завершении ><алгоритма.>

<Опишем ><алгоритм ><поиска ><в ><глубину ><- ><упрощенный ><алгоритм ><поиска ><с ><возвратами, ><уже ><представленный ><в ><подразделе ><3.2.3. ><В ><этом ><алгоритме ><состояния-потомки ><добавляются ><и ><>удаляются< ><с ><левого ><конца ><списка ><т.е. ><список ><реализован ><как ><стек ><магазинного ><типа ><или ><структура ><- ><"last-in-first-ouf ><("последним ><пришел ><- ><первым ><обслужен"). ><При ><>организации< ><списка ><в ><виде ><стека ><предпочтение ><отдается ><самым ><"молодым" ><(недавно ><>сгенерированным< ><состояниям), ><т.е. ><осуществляется ><принцип ><поиска ><в ><глубину.>

<; ><%инициализация ><=[];>

<=>< ><[] >< ><%есть ><состояния>

<удалить ><крайнее ><слева ><состояние ><из ><скажем >

><- ><цель >< ><%цель ><достигнута>

<сгенерировать ><потомок >

<поместить ><в ><список >

<исключить ><потомок ><если ><он ><уже ><в ><или >

<%проверка ><цикла ><поместить ><остальные ><потомки ><в ><левый ><конец ><списка >

<%стек >

< ><%состояний ><не ><осталось>

<Ниже ><показан ><процесс ><реализации ><алгоритма ><для ><графа ><из ><рис. ><3.13. ><Каждая ><успешная ><итерация ><цикла ><описана ><одной ><строкой ><(2, ><3, ><4,...). ><>Начальные< ><состояния ><списков ><и ><указаны ><в ><строке ><1. ><Пусть ><-целевое ><состояние.>

<ореn=[А]; ><[]>

<; ><[В,А]>

<; >

<; >

<; >

<; >

<, >

<><Глава ><З. ><Структуры ><и ><стратегии ><поиска ><в ><пространстве ><состояний

127

<< >< >

<; >< >< >

<И ><так ><далее, ><пока ><не ><будет ><обнаружено ><состояние ><или ><ореn= ><[ ><].>

<>

<Рис. ><3.15. ><Поиск ><в ><ширину, ><демонстрирующий ><порядок ><удаления ><состояний ><из ><списка ><в ><8-головоломке>

<Как ><и ><при ><поиске ><в ><ширину, ><в ><списке ><перечислены ><все ><обнаруженные, ><но ><еще ><не ><оцененные, ><состояния ><(текущая ><"граница" ><поиска), ><а ><в ><записаны ><уже ><рас><смотренные ><состояния. ><На ><рис. ><3.16 ><показан ><граф, ><изображенный ><на ><рис. ><3.13, ><после ><>выполнения< ><шести ><итераций ><функции ><Списки ><и ><на ><рис. ><3.16 ><выделены ><цветом. ><Как ><и ><при ><поиске ><в ><ширину ><в ><данном ><алгоритме ><можно ><сохранять ><для ><каждого ><состояния ><записи ><о ><родителях. ><Это ><>позволит< ><алгоритму ><восстановить ><путь, ><ведущий ><от ><начального ><состояния ><к ><целевому.>

<В ><отличие ><от ><поиска ><в ><ширину, ><поиск ><в ><глубину ><не ><гарантирует ><нахождение ><>оптимального< ><пути ><к ><состоянию, ><если ><оно ><встретилось ><впервые. ><Позже ><в ><процессе ><поиска ><мо><гут ><быть ><найдены ><различные ><пути ><к ><любому ><состоянию. ><Если ><длина ><пути ><имеет ><значение ><в ><решении ><задачи, ><то ><в ><случае ><нахождения ><алгоритмом ><некоторого ><состояния ><повторно ><необходимо ><сохранить ><именно ><тот ><путь, ><который ><оказался ><короче. ><Это ><можно ><сделать, ><сохраняя ><для ><каждого ><состояния ><тройку ><значений ><(состояние, ><родитель, ><длина ><пути). ><При ><генерации ><дочерних ><элементов ><значение ><длины ><пути ><просто ><увеличивается ><на ><единицу ><и ><сохраняется ><вместе ><с ><потомками. ><Если ><дочернее ><состояние ><достигнуто ><по ><многим ><путям, ><эту ><информацию ><нужно ><использовать ><для ><сохранения ><лучшей ><версии. ><Эта

128

<<<идея ><развивается ><при ><рассмотрении ><алгоритма ><(algorithm ><А) ><в ><главе ><4. ><Заметим, ><что ><сохранение ><лучшей ><версии ><состояния ><при ><простом ><поиске ><в ><глубину ><вовсе ><не ><>гарантирует<, ><что ><цель ><будет ><достигнута ><именно ><по ><кратчайшему ><пути.>

<>

<Рис. ><3.16. ><Граф, ><изображенный ><на ><рис. ><3.13, ><после ><>выполнения< ><шести ><итераций ><Состояния, ><содержащиеся ><в ><списках ><и ><выделены ><цветом>

<На ><рис. ><3.17 ><рассмотрен ><поиск ><в ><глубину ><на ><примере ><головоломки ><с ><8 ><фишками. ><Как ><отмечалось ><ранее, ><пустая ><клетка ><передвигается ><согласно ><одному ><из ><четырех ><возможных ><правил ><(вверх, ><вниз, ><влево ><и ><вправо). ><Числа ><рядом ><с ><состояниями ><указывают ><порядок, ><в ><котором ><они ><были ><рассмотрены ><и ><удалены ><из ><списка ><показаны ><состояния, ><на><ходящиеся ><в ><когда ><цель ><уже ><найдена. ><Глубина ><поиска ><в ><данном ><случае ><была ><>ограничена< ><пятью ><уровнями, ><чтобы ><не ><"затеряться ><в ><глубинах" ><пространства ><состояний.>

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

<Поиск ><в ><ширину. ><Поскольку ><при ><таком ><подходе ><до ><перехода ><к ><уровню ><п+><1 ><всегда ><исследуются ><все ><узлы ><на ><уровне ><п, ><поиск ><в ><ширину ><всегда ><находит ><самый ><короткий ><путь ><к ><целевой ><вершине. ><Если ><в ><задаче ><существует ><простое ><решение, ><это ><решение ><будет ><>найдено<. ><К ><сожалению, ><при ><большом ><коэффициенте ><ветвления, ><если ><состояния ><имеют ><>высокое< ><среднее ><число ><потомков, ><комбинаторный ><взрыв ><может ><помешать ><алгоритму ><найти ><решения. ><Это ><происходит ><потому, ><что ><все ><перспективные ><и ><неперспективные ><вершины

129>

<<для ><каждого ><уровня ><поиска ><находятся ><в ><списке ><Для ><глубокого ><поиска ><(когда ><цель ><расположена ><глубоко) ><или ><для ><пространства ><состояний ><с ><высоким ><коэффициентом ><>ветвления< ><этот ><поиск ><может ><быть ><весьма ><громоздким.>

<>

<7 >< >< >< >< >< >< >< >< ><10 >< >< >< >< >< >< ><11 >< >< >< >< >< >< >< >< ><13 >< >< >< >< >< >< >< ><14 >< >< >< >< >< >< ><16 >< >< >< >< >< >< ><17 >< >< >< >< >< >< ><22 >< >< >< >< >< >< >< ><23 >< >< >< >< >< >< ><26 >< >< >< >< >< >< >< ><27 >< >< >< >< >< >< ><31>

<Цель ><Рис. ><3.17. ><Поиск ><в ><глубину ><для ><игры ><в ><"пятнашки" ><с ><8 ><фишками, ><ограниченный ><5уровнями>

<Степень ><использования ><пространства ><при ><поиске ><в ><ширину ><измеряется ><в ><терминах ><числа ><состояний ><в ><списке ><и ><является ><экспоненциальной ><функцией ><длины ><пути ><в ><любой ><момент ><времени. ><Если ><каждое ><состояние ><порождает ><в ><среднем ><В ><дочерних ><со><стояний, ><то ><общее ><число ><состояний ><на ><данном ><уровне ><определяется ><умножением ><В ><на ><число ><состояний ><предыдущего ><уровня. ><Значит, ><на ><уровне ><л ><число ><состояний ><составляет ><В". ><При ><исследовании ><уровня ><п ><методом ><поиска ><в ><ширину ><все ><состояния ><помещаются ><в ><что ><может ><быть ><нежелательно, ><если ><путь ><к ><решению ><достаточно ><длинный.>

<Поиск ><в ><глубину ><быстро ><проникает ><в ><глубины ><пространства. ><Если ><известно, ><что ><путь ><решения ><будет ><длинным, ><то ><поиск ><в ><глубину ><не ><будет ><тратить ><время ><на ><поиск ><большого ><количества ><"поверхностных" ><состояний ><на ><графе. ><С ><другой ><стороны, ><поиск ><в ><глубину ><может ><"затеряться ><в ><глубинах" ><графа, ><пропуская ><более ><короткие ><пути ><к ><цели, ><или ><даже ><"застрять" ><на ><не ><ведущем ><к ><цели ><бесконечно ><длинном ><пути.>

<Поиск ><в ><глубину ><эффективен ><для ><областей ><поиска ><с ><высокой ><степенью ><связности, ><по><тому ><что ><ему ><не ><нужно ><помнить ><все ><узлы ><данного ><уровня ><в ><списке ><Степень ><ис><пользования ><пространства ><состояний ><в ><случае ><поиска ><в ><глубину ><- ><это ><линейная ><функция ><длины ><пути. ><На ><каждом ><уровне ><в ><сохраняются ><только ><дочерние ><вершины ><>единственного< ><состояния. ><Если ><у ><каждой ><вершины ><графа ><имеется ><в ><среднем ><В ><дочерних ><вер->

130<<шин, ><и ><если ><поиск ><продвигается ><на ><п ><уровней ><вглубь ><пространства, ><то ><уровень ><использо><вания ><пространства ><составляет ><Вxп.>

<Так ><что ><же ><лучше: ><поиск ><в ><глубину ><или ><поиск ><в ><ширину? ><На ><этот ><вопрос ><можно ><>ответить< ><так. ><Необходимо ><исследовать ><пространство ><состояний ><и ><проконсультироваться ><с ><экспертами ><в ><данной ><области. ><В ><шахматах, ><например, ><поиск ><в ><ширину ><просто ><невозможен. ><В ><более ><простых ><играх ><поиск ><в ><ширину ><не ><только ><возможен, ><но ><даже ><может ><оказаться ><единственным ><способом ><избежать ><проигрышей ><или ><потерь ><в ><игре.>

<3.2.4. ><Поиск ><в ><глубину ><с ><итерационным ><заглублением>

<Хорошим ><решением ><проблем ><поиска ><в ><глубину ><является ><использование ><предельного ><значения ><глубины ><поиска. ><Предельная ><глубина ><позволяет ><ограничить ><поиск ><только ><за><данным ><числом ><уровней. ><Это ><обеспечивает ><некоторое ><подобие ><"развертки" ><области ><по><иска ><в ><ширину ><при ><поиске ><в ><глубину.>

<Ограниченный ><поиск ><в ><глубину ><наиболее ><полезен, ><если ><известно, ><что ><решение ><находит><ся ><в ><пределах ><некоторой ><глубины, ><имеются ><ограничения ><во ><времени ><или ><пространство ><со><стояний ><чрезвычайно ><велико ><(как ><в ><шахматах). ><В ><таких ><задачах ><число ><рассматриваемых ><со><стояний ><ограничивают ><предельной ><глубиной ><поиска. ><На ><рис. ><3.17 ><показан ><поиск ><в ><глубину ><для ><8-головоломки, ><для ><которого ><предельная ><глубина ><ограничена ><пятью ><уровнями. ><Поэто><му ><именно ><на ><этой ><глубине ><возникает ><поперечная ><развертка ><пространства.>

<Такая ><модификация ><позволяет ><исправить ><немало ><недостатков ><как ><поиска ><в ><глубину, ><так ><и ><поиска ><в ><ширину. ><Итерационным ><заглублением ><[Korf, ><1987] ><называется ><поиск ><в ><глубину, ><первая ><итерация ><которого ><ограничена ><1 ><уровнем. ><Если ><цель ><не ><найдена, ><выпол><няется ><еще ><один ><шаг ><с ><предельной ><глубиной ><2. ><В ><процессе ><поиска ><предельная ><глубина ><увеличивается ><на ><1 ><на ><каждой ><итерации. ><На ><каждой ><итерации ><алгоритм ><выполняет ><поиск ><в ><глубину ><с ><учетом ><текущего ><предельного ><числа ><уровней. ><При ><этом ><при ><переходе ><от ><од><ной ><итерации ><к ><другой ><информация ><о ><пространстве ><состояний ><не ><сохраняется.>

<Поскольку ><алгоритм ><исследует ><пространство ><"по ><уровням", ><он ><может ><гарантировать ><нахождение ><кратчайшего ><пути ><к ><цели. ><Поскольку ><на ><каждой ><итерации ><осуществляется ><только ><поиск ><в ><глубину, ><степень ><использования ><пространства ><на ><каждом ><уровне ><л ><>составляет< ><Вхп, ><где ><б ><- ><среднее ><число ><дочерних ><состояний ><вершины.>

<На ><первый ><взгляд ><кажется, ><что ><итерационное ><продвижение ><в ><глубину ><менее ><>эффективно< ><по ><времени, ><чем ><поиск ><глубину ><или ><в ><ширину. ><Однако ><временная ><сложность ><>алгоритма< ><(время ><выполнения ><алгоритма ><в ><зависимости ><от ><размерности ><задачи) ><в ><>действительности< ><имеет ><тот ><же ><самый ><порядок ><величины, ><что ><и ><каждый ><из ><этих ><алгоритмов ><- ><О(><). ><Объяснение ><этого ><кажущегося ><парадокса ><приведено ><в ><[Korf, ><1987].>

<Поскольку ><число ><вершин ><на ><данном ><уровне ><дерева ><растет ><экспоненциально ><с ><увеличением ><глубины, ><почти ><все ><время ><вычислений ><тратится ><на ><самом ><глубоком ><уровне.>

<К ><сожалению, ><можно ><показать, ><что ><в ><наихудшем ><случае ><все ><рассмотренные ><в ><этой ><главе ><стратегии ><поиска ><(поиск ><в ><глубину, ><в ><ширину ><и ><итерационное ><заглубление) ><>обладают< ><экспоненциальной ><сложностью. ><Это ><характерно ><для ><всех ><неинформированных ><алгоритмов ><поиска. ><Для ><снижения ><временной ><сложности ><алгоритмов ><поиска ><>используют< ><направляющие ><эвристики. ><Поиск ><по ><первому ><наилучшему ><совпадению ><- ><это ><>алгоритм< ><поиска, ><подобный ><представленным ><выше ><алгоритмам ><поиска ><в ><глубину ><и ><в ><ши><рину. ><Однако ><в ><процессе ><поиска ><по ><первому ><наилучшему ><совпадению ><состояния ><в ><>списке< >< >< >< >< ><определяющие >< >< ><текущую >< >< ><границу >< >< ><поиска, >< >< ><упорядочиваются >< >< ><согласно>

<><Глава ><3. ><Структуры ><и ><стратегии ><поиска ><в ><пространстве ><состояний><

131

<<некоторому ><эвристическому ><показателю ><качества. ><На ><каждой ><итерации ><поиск ><рассмат><ривает ><не ><самые ><глубокие, ><а ><самые ><"лучшие" ><состояния. ><Поиск ><по ><первому ><наилучше><му ><совпадению ><- ><центральная ><тема ><главы ><4.>

<3.3. ><Представление ><рассуждений ><в ><пространстве ><состояний ><на ><основе ><исчисления ><предикатов>

<><3.3.1. ><Описание ><пространства ><состояний ><логической ><системы>

<В ><разделе ><3.1 ><при ><определении ><графа ><пространства ><состояний ><было ><отмечено, ><что ><его ><вершины ><должны ><отличаться ><друг ><от ><друга, ><поскольку ><каждый ><узел ><представляет ><некоторое ><состояние ><процесса ><решения. ><В ><качестве ><формального ><языка ><для ><описания ><этих ><различий ><и ><отображения ><узлов ><графа ><в ><пространство ><состояний ><можно ><использовать ><исчисление ><>предикатов<. ><Более ><того, ><для ><создания ><дуг ><и ><описания ><связей ><между ><состояниями ><можно ><>использовать< ><правила ><вывода. ><Тогда ><методами ><поиска ><могут ><быть ><решены ><некоторые ><проблемы ><>исчисления< ><предикатов. ><Например, ><таким ><образом ><можно ><определить, ><является ><ли ><некоторое ><конкретное ><выражение ><логическим ><следствием ><данного ><набора ><утверждений.>

<Корректность ><и ><полнота ><правил ><вывода ><исчисления ><предикатов ><обеспечивает ><>корректность< ><подобных ><заключений. ><Возможность ><получить ><формальное ><доказательство ><целостности ><решения ><задачи ><с ><помощью ><алгоритма ><решения ><самой ><задачи ><является ><уни><кальным ><преимуществом ><многих ><методов ><искусственного ><интеллекта.>

<Хотя ><состояния ><многих ><задач ><(например, ><"крестики-нолики") ><более ><естественно ><опи><сываются ><другими ><структурами ><данных ><(например, ><массивами), ><общая ><логика ><и ><специ><фика ><решения ><многих ><задач ><ИИ ><приводят ><к ><использованию ><исчисления ><предикатов ><и ><других ><моделей ><представления ><знаний, ><в ><том ><числе ><правил ><вывода ><(глава ><7), ><семантиче><ских ><сетей ><и ><фреймов ><(глава ><6). ><Для ><всех ><этих ><моделей ><представления ><знаний ><можно ><ис><пользовать ><стратегии ><поиска, ><аналогичные ><представленным ><выше.>

<Пример ><3.3.1. ><Исчисление ><высказываний>

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

q?p<>

r?p

v?q

<><>

<Из ><этого ><набора ><утверждений ><на ><основе ><правила ><модус ><поненс ><могут ><быть ><выведены ><определенные ><высказывания, ><в ><том ><числе ><р, >< ><и ><и. ><Другие ><высказывания, ><в ><частности, ><и ><не ><могут ><быть ><выведены ><таким ><способом. ><Действительно, ><они ><логически ><не ><следуют ><из ><этих ><утверждений. ><Отношения ><между ><начальными ><утверждениями ><и ><выведенными ><из ><них ><описаны ><на ><рис. ><3.18 ><с ><помощью ><ориентированного ><графа.

132>

<<>

<>