ТИПИС

§ 2.5. Организация n-направленного поиска	81

Рис. 2.18. Схема организации контрактной сети

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

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

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

Другой способ организации n-направленного поиска предполагает использование иерархической организации пространства поиска. В [3] описана концепция многоуровневой иерархической базы знаний, предложенная Мизогучи и Какушо в 1979 году. Концепция организации заключается в том, что знания о некоторой предметной области распределены по иерархически связанным уровням от более конкретных к более абстрактным, как это сделано в ЭС САSNЕТ [9]. Схема организации многоуровневой иерархической базы знаний представлена на рис. 2.19.

82		Глава 2. Методы поиска

Рис. 2.19. Схема организации многоуровневой иерархической базы знаний

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

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

В заключении параграфа выделим основные положения, характеризующие особенности организации n-направленного режима поиска.

Неуправляемые слепые методы поиска в n-направленном режиме проявляют низкую эффективность.

Использование апостериорной информации в n-направленном режиме поиска, сохраняемой в памяти методов Мура, позволяет значительно сократить время поиска за счет более эффективного управления направлением генерации каждого метода.

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

83

САМОСТОЯТЕЛЬНЫЕ РАБОТЫ

84		Самостоятельные работы

Самостоятельная работа 1

АНАЛИЗ ЭФФЕКТИВНОСТИ ПРОЦЕДУР ГЕНЕРАЦИИ

Тема

Анализ работы процедур генерации в слепых методах поиска при решении задач в пространстве состояний.

Цель

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

Задача

Провести относительный анализ эффективности использования различных процедур генерации в слепых методах поиска при различных условиях проведения поиска:

1)на кольце;

2)на дереве с одинаковым количеством дочерних состояний у всякого родителя;

3)на графе состояний для игр «В восемь» или «Перестановка».

Результат

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

Самостоятельные работы, помеченные «*», включают задачи повышенной сложности.

Самостоятельные работы	85

Указания и порядок выполнения

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

1.Описание задачи. В данном пункте следует кратко описать смысл задачи на естественном языке. Выбор задачи осуществляется самостоятельно из предложенного списка задач (см. прил. А, Б).

В результате описание задачи должно быть достаточным для дальнейшей формализации.

2.Представление пространства поиска. В данном пункте необходимо охарактеризовать пространство состояния и поиска, отвечая на следующие вопросы:

Каким образом организовано пространство состояний?

Существуют ли в пространстве состояний непересекаемые подмножества состояний, каким образом их можно определить?

Какие существуют отношения между состояниями пространства поиска?

Результатом является модель пространства поиска.

3.Условия задачи:

а) описание начального условия решения задачи. В данном пункте следует охарактеризовать способы генерации и условия проведения поиска (проанализировать свойства пространства поиска);

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

4.Выбор методов генерации. В данном пункте следует на основе теоретических выводов п. 1–3 принять решение о выборе соответствующего задаче наиболее эффективного способа генерации.

Результатом является обоснование, представленное в формальном

виде.

5.Создание программы, реализующей слепые методы поиска. Данный пункт предполагает программную реализацию слепых методов поиска (выполняется самостоятельно).

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

6.Анализ полученных данных и вывод. Полученные в результате работы программы данные должны подтвердить или опровергнуть правильность теоретических выводов (п. 4) о выборе способа генерации в определенных условиях организации пространства поиска.

86		Самостоятельные работы

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

Самостоятельная работа 2

АНАЛИЗ РАБОТЫ МЕТОДА ВЕТВЕЙ И ГРАНИЦ С РАЗЛИЧНЫМИ СПОСОБАМИ ГЕНЕРАЦИИ

Тема

Анализ работы метода ветвей и границ с различными способами генерации при решении задач в пространстве состояний.

Цель

Дать представление о возможности использования различных способов генерации в методе поиска ветвей и границ.

Задача

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

Результат

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

Указания и порядок выполнения

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

1. Описание задачи. В данном пункте следует кратко описать смысл задачи на естественном языке. Выбор задачи осуществляется самостоятельно из предложенного преподавателем списка задач (см. прил. А, Б).

В результате описание задачи должно быть достаточным для дальнейшей формализации.

Самостоятельные работы	87

2.Представление пространства поиска. В данном пункте необходимо охарактеризовать пространство состояния и поиска.

Результатом является модель пространства поиска.

3.Условия задачи:

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

пользуя различные способы генерации в методе ветвей и границ.

4.Выбор способа генерации. В данном пункте следует на основе теоретических выводов п. 1–3 принять решение о выборе способа генерации в методе ветвей и границ, ориентированного на решение той или иной задачи поиска.

Результатомявляетсяобоснование, представленноевформальномвиде.

5.Создание программы, реализующей метод ветвей и границ. Данный пункт предполагает программную реализацию метода ветвей и границ

сразличными способами генерации (выполняется самостоятельно).

6.Анализ полученных данных и вывод. Полученные в результате работы программы данные должны подтвердить или опровергнуть правильность теоретических выводов о выборе способа генерации в методе ветвей и границ, ориентированного на решение задач поиска.

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

Самостоятельная работа 3

АНАЛИЗ РАБОТЫ МЕТОДА МУРА С РАЗЛИЧНЫМИ СПОСОБАМИ ГЕНЕРАЦИИ

Тема

Анализ работы метода Мура с различными способами генерации при решении задач в пространстве состояний.

Цель

Дать представление о возможности использования различных способов генерации в методе Мура.

88		Самостоятельные работы

Задача

Провести относительный анализ эффективности использования различных способов генерации в методе Мура.

Результат

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

Указания и порядок выполнения

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

1.Описание задачи. В данном пункте следует кратко описать смысл задачи на естественном языке. Выбор задачи осуществляется самостоятельно из предложенного преподавателем списка задач (см. прил. А, Б).

В результате описание задачи должно быть достаточным для дальнейшей формализации.

2.Представление пространства поиска. В данном пункте необходимо охарактеризовать пространство состояния и поиска.

Результатом является модель пространства поиска.

3.Условия задачи:

а) описание начального условия решения задачи. В данном пункте следует охарактеризовать способы генерации и условия проведения поиска методом Мура (проанализировать свойства пространства поиска);

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

4.Выбор способа генерации. В данном пункте следует на основе теоретических выводов п. 1–3 принять решение о выборе способа генерации в методе Мура, ориентированного на решение той или иной задачи поиска.

Результатомявляется обоснование, представленноев формальномвиде.

5.Создание программы, реализующей метод Мура. Данный пункт предполагает программную реализацию метода Мура с различными способами генерации (выполняется самостоятельно).

6.Анализ полученных данных и вывод. Полученные в результате работы программы данные должны подтвердить или опровергнуть правильность теоретических выводов о выборе способа генерации в методе Мура, ориентированного на решение задач поиска.

Самостоятельные работы	89

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

Самостоятельная работа 4*

ВЫДЕЛЕНИЕ УСЛОВИЙ ПЕРЕХОДА В КОМБИНИРОВАННОМ МЕТОДЕ ПОИСКА

Тема

Анализ условий перехода в комбинированном методе поиска при решении задач в пространстве состояний.

Цель

Дать представление о возможности использования комбинированного метода поиска при решении задач в пространстве состояний.

Задача

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

Результат

Должна быть создана программа, выполняющая комбинированный метод поиска. Представлены графики, анализирующие достоинства и недостатки процедур проверки в комбинированном методе поиска.

Указания и порядок выполнения

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

1.Описание задачи. В данном пункте следует кратко описать смысл задачи на естественном языке. Выбор задачи осуществляется самостоятельно из предложенного преподавателем списка задач (см. прил. А, Б).

В результате описание задачи должно быть достаточным для дальнейшей формализации.

2.Представление пространства поиска. В данном пункте необходимо охарактеризовать пространство состояния и поиска.

90		Самостоятельные работы

Результатом является модель пространства поиска. 3. Условия задачи:

а) описание начального условия решения задачи. В данном пункте следует охарактеризовать процедуры проверки и условия перехода в комбинированномметодепоисканаосновеанализасвойствпространствасостояний;

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

4.Выбор условий перехода. В данном пункте следует на основе теоретических выводов п. 1–3 принять решение о выборе соответствующего задаче подходящего условия перехода.

Результатомявляетсяобоснование, представленноевформальномвиде.

5.Создание программы, реализующей комбинированный метод поиска. Данный пункт выполняется самостоятельно.

6.Анализ полученных данных и вывод. Полученные в результате работы программы данныедолжны подтвердитьили опровергнутьправильность теоретическихвыводовобусловияхпереходавкомбинированномметодепоиска.

Результатом являются графики, схемы, характеризующие условия перехода в комбинированном методе поиска, позволяющие оценить эффективность использования того или иного условия перехода.

Самостоятельная работа 5* АНАЛИЗ ПРОЦЕДУРЫ ПЛАНИРОВАНИЯ

Тема

Анализ работы эвристических методов на основе оценочной функции при решении задач в пространстве состояний.

Цель

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

Задача

Провести относительный анализ эффективности эвристической процедуры планирования поиска относительно используемой оценочной функции в алгоритме А*, в алгоритме с процедурой возврата и расширенной оценочной функцией.