Основные стратегии решения задач

11 1 Предварительные понятия и примеры
11. 1.    Предварительные понятия и примеры Рассмотрим пример, представленный на Рисунок 11.1. Задача состоит в выработке плана переупорядочивания кубиков, поставленных друг на друг...
Рисунок 11 1 Задача перестановки кубиков
Рисунок 11. 1.  Задача перестановки кубиков. Ясно, что альтернативу "поставить С на стол" не имело смысла рассматривать всерьез, так как этот ход никак не влияет на ситуацию. Как по...
Рисунок 11 3 "Игра в восемь" и ее представление в форме графа
Рисунок 11. 3.  "Игра в восемь" и ее представление в форме графа. нять козу от волка и капусту от козы. С описанной парадигмой согласуются также многие задачи, имеющие практическое...
11 2 Стратегия поиска в глубину
11. 2.    Стратегия поиска в глубину Существует много различных подходов к проблеме поиска решающего пути для задач, сформулированных в терминах пространства состояний. Основные две...
Рисунок 11 4 Пример простого пространства
Рисунок 11. 4.  Пример простого пространства состояний:  а  -  стартоваявершина,   f    и   j   -  целевые вершины. Порядок, в кото...
Рисунок 11 5 Начинаясь в а поиск вглубину заканчивается бесконечным циклом между d и h a b d h d h d
Рисунок 11. 5.  Начинаясь в а, поиск вглубину заканчиваетсябесконечным циклом между  d  и  h:   a, b, d, h, d, h, d... . Очевидное усовершенствование нашей программы поиск...
Рисунок 11 6 Отношение вглубину( Путь В Решение)
Рисунок 11. 6.  Отношение вглубину( Путь, В, Решение). Для облегчения программирования вершины в списках, представляющих пути, будут расставляться в обратном порядке. Аргумент Путьнужен для т...
Рисунок 11 7 Программа поиска в глубину без зацикливания
Рисунок 11. 7.  Программа поиска в глубину без зацикливания. Теперь наметим один вариант этой программы. Аргументы Путь и Вершпроцедуры вглубину можно объединить в один список [Верш | Путь]....
Рисунок 11 8 Программа поиска в глубину с ограничением по глубине
Рисунок 11. 8.  Программа поиска в глубину с ограничением по глубине. Для того, чтобы предотвратить бесцельное блуждание по бесконечным ветвям, мы можем добавить в базовую процедуру поиска в...
Упражнения
Упражнения 11. 1.    Напишите процедуру поиска в глубину (с обнаружением циклов)         вглубину1( ПутьКандидат, Решение) отыскивающую решающий п...
11 3 Поиск в ширину
11. 3.    Поиск в ширину В противоположность поиску в глубину стратегия поиска в ширину предусматривает переход в первую очередь к вершинам, ближайший к стартовой вершине. В результ...
Рисунок 11 9 Простое пространство
Рисунок 11. 9. Простое пространство состояний:  а  - стартовая вершина,f  и  j  - целевые вершины. Применение стратегии поиска в ширинудает следующий порядок прохода по ве...
11 3 1 Списковое представление множества кандидатов
11. 3. 1.    Списковое представление множества кандидатов В нашей первой реализации этой идеи мы будем использовать следующее представление для множестваline();    &n...
Рисунок 11 10 Реализации поиска в ширину
Рисунок 11. 10.  Реализации поиска в ширину. путей-кандидатов. Само множество будет списком путей, а каждый путь - списком вершин, перечисленных в обратном порядке, т. е. головой списка будет...
Рисунок 11 11 Программа поиска
Рисунок 11. 11.  Программа поиска в ширину более эффективная, чемпрограмма Рисунок 11.10. Усовершенствование основано на разностномпредставлении списка путей-кандидатов. (1)   ...
11 3 2 Древовидное представление множества кандидатов
11. 3. 2.  Древовидное представление множества кандидатов Рассмотрим теперь еще одно изменение нашей программы поиска в ширину. До сих пор мы представляли множества путей-кандидатов как списк...
Рисунок 11 12 Отношение paсширить(
Рисунок 11. 12.  Отношение paсширить( Путь, Дер, Дер1, ЕстьРеш, Решение):s -   стартовая вершина,  g-  целевая вершина. Решение - это Путь,продолженный вплоть до  g. ...
Рисунок 11 13 Реализация поиска
Рисунок 11. 13.  Реализация поиска в ширину с использованиемдревовидного представления множества путей-кандидатов. Мы разработали эту более сложную реализацию поиска в ширину не только для то...
Упражнения
Упражнения 11. 5.    Перепишите программу поиска в ширину Рисунок 11.10, используя разностное представление для списка путей-кандидатов и покажите, что в результате получится програ...
11 4 Замечания относительно поиска в графах оптимальности к сложности
11. 4.    Замечания относительно поиска в графах, оптимальности к сложности Сейчас уместно сделать ряд замечаний относительно программ поиска, разработанных к настоящему моменту: во...
Рисунок 11 14 (а) Пространство
Рисунок 11. 14.    (а)     Пространство состояний;  а -   стартовая вершина.(b)     Дерево всех возможных ациклических путей, ведущих из ...
Резюме
Резюме Пространство состояний есть формализм для представления задач. Пространство состояний - это направленный граф, вершины которого соответствуют проблемным ситуациям, а дуги - возможным...
Литература
Литература Поиск в глубину и поиск в ширину - базовые стратегии поиска, они описаны в любом учебнике по искусственному интеллекту, см., например, Nilsson (1971, 1980) или Winston (1984). Р. Коваль...