Указания и порядок выполнения лабораторной работы № 4
ОТЧЕТ ПО ЛАБОРАТОРНОЙ РАБОТЕ №2
«Выделение условий перехода в комбинированном методе поиска»
Преподаватель __________ Перфильев Д. А.
подпись, дата инициалы, фамилия
Студент КИ 10-14-3 ______________ __________ Рыжкова В.В.
номер группы номер зачетной книжки подпись, дата инициалы, фамилия
Красноярск 2013
Цель:Дать представление о возможности использования «комбинированного» метода поиска при решении задач в пространстве состояний.
Задача:Провести относительный анализ эффективности использования условий перехода в «комбинированном» методе поиска при различных условиях его проведения.
Результат:В результате должна быть создана программа, выполняющая «комбинированный» метод поиска. Представлены графики, анализирующие достоинства и недостатки процедур проверки в «комбинированном» методе поиска.
Указания и порядок выполнения лабораторной работы № 4.
1. Описание задачи. Методы поиска на основе апостериорной информации образуют собственный класс простейших эвристических методов поиска. Очевидно, что
характерным отличительным признаком класса простейших эвристических методов поиска является процедура проверки.
Наиболее яркими представителями простейших эвристических методов поиска являются:
1) метод кратчайших путей Мура (в действительности определяет минимальное расстояние, количество итераций поиска до ближайшего состояния);
2) метод ветвей и границ определяет минимальный путь до ближайшего состояния (в действительности относительно минимальное расстояние до заданного, обычно ближайшего, целевого состояния)
Введем следующие обозначения:
Vп - вектор скорости преследователя (П);
Vц - вектор скорости цели (Ц);
r = r (t) - текущее расстояние между П и Ц;
γ - курсовой угол преследователя, т.е. угол между вектором
скорости Vп и линией визирования (линией преследователь - цель);
φ - курсовой угол цели (угол между вектором скорости Vц и
линией визирования);
η - угол визирования (угол между фиксированным направлением
ПN и линией визирования);
ψ - курс преследователя(угол между UNn вектором Vn).
В методе Мура результаты процедуры проверки позволяют управ-
лять направлением генерации. Обычно метод Мура применяют в условиях,
когда необходимо найти расстояние до ближайшего состояния. Поэтому в
методе Мура целесообразно использовать круговой обзор, т. е. генерацию
с наиболее широким фронтом.
Метод ветвей и границ предназначен:
1) для поиска расстояния Hi до ближайшего из заданных целевых со-
стояний sti St;
2) для определения возможно минимального расстояния Hmin до
ближайшего целевого состояния.
СХЕМА ПОИСКА МЕТОДОМ МУРА
siо
Процедура генерации
в ширину
Si2 Fi = Si+1
Процедура проверки
1) sj Si2 SP
MS = {siо, sjt, S1, …, Si-12, Si2,…}
2) si Si2, sjt St
Si1
еищукеТ Si-11
фронты
Si, Si+1
Начальное
состояние
siо Sо
tjs Si+1 = Si+11 Si+12
Целевое
состояние
sjt St
Si2
Si-12
Подмножество
оригинальных
состояний
§ 2.3. Процедура проверки
Поэтому обычно в методе ветвей и границ последовательно выпол-
няются две задачи:
1) определение граничной глубины (количества итераций) поиска в
пространстве состояний;
2) поиск минимального расстояния (ветви), ведущего к целевому со-
стоянию.
Значимость первой задачи зависит от выбранного способа генерации,
а второй – от ресурса ПС, отведенного на поиск.
Метод ветвей и границ используется в следующих условиях, удовле-
творяющих решению: St 1 и sti St. Таким образом, в данном методе
целесообразно использовать генерацию, определяемую отношением мно-
жеств S и St. Обычно метод применяют в условиях, когда отношение
пространства поиска и целевых состояний стремится к единице. Поэтому в
методе применяют секторные способы генерации.
2. Представление пространства поиска. В данном пункте
необходимо охарактеризовать пространство состояния и поиска.
Результатом является: модель пространства поиска.
3. Условия задачи:
а) Описание начального условия решения задачи. В данном пункте
следует охарактеризовать процедуры проверки и условия перехода в
«комбинированном» методе поиска на основе анализа свойств пространства
состояний.
б) Описание требуемого результата решения задачи. При
заполнении данного пункта необходимо определить: Какие результаты
возможно получить, используя предложенный «комбинированный» метод
поиска?
4. Выбор условий перехода. В данном пункте следует на основе
теоретических выводов п.1-3 принять решение о выборе соответствующего
задаче подходящего условия перехода.
Результатом является: обоснование (представленное в формальном
виде).
5. Создание программы, реализующей «комбинированный» метод