Сведение задач к подзадачам. И/ИЛИ-графы


13 1 Представление задач в виде И / ИЛИграфов
13. 1.    Представление задач в виде И / ИЛИ-графов В главах 11 и 12, говоря о решении задач, мы сконцентрировали свое внимание на пространстве состояний как средстве представления...
Рисунок 13 1 Поиск маршрута из
Рисунок 13. 1.  Поиск маршрута из  а  в  z  на карте дорог. Через рекуможно переправиться в городах  f  и   g.  И / ИЛИ-представление этойзадачи показа...
Рисунок 13 2 И / ИЛИпредставление
Рисунок 13. 2.  И / ИЛИ-представление задачи поиска маршрута Рисунок 13.1.Вершины соответствуют задачам или подзадачам, полукруглые дугиозначают, что все (точнее, обе) подзадачи должны быть р...
Рисунок 13 3 (а) Решить Р это
Рисунок 13. 3.  (а)  Решить   Р  -  это значит решить  Р1  или   Р2  или  ...(б)  Решить  Q  -  это значит решить все:  ...
Рисунок 13 4 (а) Пример И / ИЛИграфа
Рисунок 13. 4.  (а)  Пример И / ИЛИ-графа:  d,  g  и  h  -   целевые вершины;a  -  исходная задача.  (b)   и   (с)  Два р...
13 2 Примеры И/ИЛИпредставления задач
13. 2.    Примеры И/ИЛИ-представления задач...
13 2 1 И / ИЛИпредставление задачи поиска маршрута
13. 2. 1.    И / ИЛИ-представление задачи поиска маршрута Для задачи отыскания кратчайшего маршрута (Рисунок 13.1) И / ИЛИ-граф вместе с функцией стоимости можно определить следующи...
Рисунок 13 5 Решающее дерево минимальной
Рисунок 13. 5.  Решающее дерево минимальной стоимости для задачипоиска маршрута Рисунок 13.1, сформулированной в терминах И / ИЛИ-графа. 13.5 показан решающий граф, имеющий стоимость 9. Это д...
13 2 2 Задача о ханойской башне
13. 2. 2.    Задача о ханойской башне Задача о ханойской башне (Рисунок 13.6) - это еще один классический пример эффективного применения метода разбиения задачи на подзадачи и постр...
Рисунок 13 6 Задача о ханойской башне
Рисунок 13. 6.  Задача о ханойской башне Порядок этот можно установить при помощи следующего рассуждения: самая трудная цель - это цель 3 (диск  с  -  на колышек 3), потому чт...
13 2 3 Формулировка игровых задач в терминах И / ИЛИграфов
13. 2. 3.    Формулировка игровых задач в терминах И / ИЛИ-графов Такие игры, как шахматы или шашки, естественно рассматривать как задачи, представленные И / ИЛИ-графами. Игры таког...
Рисунок 13 7 Формулировка игровой
Рисунок 13. 7.  Формулировка игровой задачи для игры двух лиц вформе И / ИЛИ-дерева; участники игры: "игрок" и "противник". та хода противника. Другими словами, игрок выиг...
13 3 Базовые процедуры поиска в И / ИЛИграфах
13. 3.    Базовые процедуры поиска в И / ИЛИ-графах В этом разделе нас будет интересовать какое-нибудьрешение задачи независимо от его стоимости, поэтому проигнорируем пока стоимост...
Рисунок 13 8 Поиск в глубину для
Рисунок 13. 8.  Поиск в глубину для И / ИЛИ-графов. Эта программа можетзацикливаться. Процедура решитьнаходит решающее дерево, апроцедура отобр показывает его пользователю. В процедуре отобрп...
Упражнения
Упражнения 13. 1.    Закончите составление программы поиска в глубину (с ограничением) для И / ИЛИ-графов, намеченную в настоящем разделе. 13. 2.    Определите на Про...
13 4 Поиск с предпочтением в И / ИЛИграфах
13. 4.    Поиск с предпочтением в И / ИЛИ-графах...
13 4 1 Эвристические оценки и алгоритм поиска
13. 4. 1.    Эвристические оценки и алгоритм поиска Базовые процедуры поиска предыдущего раздела производят систематический и полный просмотр И / ИЛИ-дерева, не руководствуясь при э...
Рисунок 13 9 Получение оценки Н трудности задач И / ИЛИграфа
Рисунок 13. 9.  Получение оценки  Н  трудности задач  И / ИЛИ-графа. Обозначим через Н( В) оценку трудности вершины  В.  Для самой верхней вершины текущего дерева пои...
Рисунок 13 10 Трассировка процесса
Рисунок 13. 10.  Трассировка процесса поиска с предпочтением вИ / ИЛИ-графе ( h = 0) при решении задачи Рисунок 13.4. прекращается. В результате процесс поиска не успевает "осознать"...
13 4 2 Программа поиска
13. 4. 2.    Программа поиска Программа, в которой реализованы идеи предыдущего раздела, показана на Рисунок 13.12. Прежде, чем мы перейдем к объяснению отдельных деталей этой прогр...
Рисунок 13 11 Представление дерева поиска
Рисунок 13. 11.  Представление дерева поиска. можностей имеется в виду. Это может быть одна из следующих комбинаций:         лист     решлист...
Рисунок 13 12 Программа поиска с предпочтением в И / ИЛИграфе
Рисунок 13. 12.  Программа поиска с предпочтением в И / ИЛИ-графе. Еще одна процедура         собрать( ОстДер, НовДер, ЕстьРеш1, НовДеревья, ЕстьРеш) связыв...
13 4 3 Пример отношений определяющих конкретную задачу поиск маршрута
13. 4. 3.    Пример отношений, определяющих конкретную задачу: поиск маршрута Давайте теперь сформулируем задачу нахождения маршрута как задачу поиска в И / ИЛИ-графе, причем сделае...
Упражнение
Упражнение 13. 4. Напишите процедуру         отобр2( РешДер) для отображения решающего дерева, найденного программой и_или Рисунок 13.12. Формат отображения пуст...
Резюме
И / ИЛИ-граф - это формальный аппарат для представления задач. Такое представление является наиболее естественным и удобным для задач, которые разбиваются на независимые подзадачи. Пример...
Литература
Литература И / ИЛИ-графы и связанные с ними алгоритмы поиска являются частью классических механизмов искусственного интеллекта для решения задач и реализации машинных игр. Ранним примером прикладн...


- Начало -