Навигация
3.1.2. Поиск методом редукции
При поиске методом редукции решение задачи сводится к решению совокупности образующих ее подзадач. Этот процесс повторяется для каждой подзадачи до тех пор, пока каждая из полученного набора подзадач, образующих решение исходной задачи, не будет иметь очевидное решение. Процесс решения задачи разбиением ее на подзадачи можно представить в виде специального направленного графа G, называемого И/ИЛИ-графом; Каждой вершине этого графа ставится в соответствие описание некоторой задачи (подзадачи). В графе выделяют два типа вершин: конъюнктивные вершины и дизъюнктивные вершины.
Решение задачи при поиске методом редукции (при поиске в И/ИЛИ-графе) сводится к нахождению в И/ИЛИ-графе решающего графа.
Цель процесса поиска в И/ИЛИ-графе - показать, что начальная вершина разрешима, т.е. для этой вершины существует решающий граф. Определение разрешимой вершины в И/ИЛИ-графе можно сформулировать рекурсивно следующим образом:
Конечные (целевые) вершины разрешимы, так как их решение известно по исходному предположению.
Вершина ИЛИ разрешима тогда и только тогда, когда разрешима по крайней мере одна из ее дочерних вершин.
Вершина И разрешима тола и только тогда, когда разрешима каждая из ее дочерних вершин.
Решающий граф определяется как подграф из разрешимых вершин, который показывает, что начальная вершина разрешима (в соответствии с приведенным выше определением). На рис. 3.3. разрешимые вершины зачернены, а неразрешимые оставлены белыми.
Для графа И/ИЛИ, так же как для поиска в пространстве состояний, можно определить поиск в глубину и поиск в ширину как в прямом, так и в обратном направлении. На рис. 3.4. приведен пример поиска в ширину (рис. 3.4., а) и поиска в глубину (рис. 3.4., б). На рисунке вершины пронумерованы в том порядке, в котором они раскрывались, конечные вершины обозначены квадратами, разрешимые вершины зачернены, дуги решающего графа выделены двойными линиями.
3.1.3. Эвристический поиск
При увеличении пространства поиска методы слепого поиска требуют чрезмерных затрат времени и (или) памяти. Это привело к созданию эвристических методов поиска, т.е. методов, использующих некоторую информацию о предметной области для рассмотрения не всего пространства поиска, а таких путей в нем, которые с наибольшей вероятностью приводят .к цели. '
3.1.4.Поиск методом "генерация-проверка"
Процесс поиска может быть сформулирован в терминах "генерация-проверка". Для осуществления процесса поиска необходимо генерировать очередное возможное решение (состояние или подзадачу) и проверить, не является ли оно результирующим.
3.2. ПОИСК В ИЕРАРХИИ ПРОСТРАНСТВ
Методы поиска в одном пространстве не позволяют решать сложные задачи, так как с увеличением размера пространства время поиска экспоненциально растет. При большом размере пространства поиска можно попробовать разбить общее пространство на подпространства и осуществлять поиск сначала в них. Пространство поиска представлено иерархией пространств.
Методы поиска решения в иерархических пространствах обычно делятся на:
· поиск в факторизованном пространстве,
· поиск в фиксированном множестве пространств
· поиск в изменяющемся множестве пространств.
3.2.1. Поиск в факторизованном пространстве
Во многих приложениях требуется найти все решения. Например - постановка диагноза. Пространство называется факторизованным, если оно разбивается на непересекающиеся подпространства (классы) частичными (неполными) решениями. Причем по виду частичного решения можно определить, что оно не приведет к успеху, т.е. что все полные решения, образованные из него, не приведут к целевым решениям. Поиск в факторизованном пространстве осуществляется на основе метола "иерархическая генерация-проверка". Если пространство поиска удается факторизовать, то поиск даже в очень большом пространстве можно организовать эффективно.
3.2.2. Поиск в фиксированном множестве пространств
Применение метода факторизации пространства ограничено тем, что для ряда областей не удается по частичному решению сделать заключение о его непригодности. Например задачи планирования и конструирования. В этих случаях могут быть применены методы поиска, использующие идею абстрактного пространства. Абстракция должна подчеркнуть важные особенности рассматриваемой задачи, позволить разбить задачу на более простые подзадачи и определить последовательность подзадач (план решения), приводящую к решению основной задачи.
3.2.3. Поиск в изменяющемся множестве иерархических пространств
В ряде приложений не удается все решаемые задачи свести к фиксированному набору подзадач. План решения задачи в данном случае должен иметь переменную структуру и не может быть сведен к фиксированному набору подзадач. Для решения подобных задач может быть использован метод нисходящего уточнения. Этот метод базируется на следующих предположениях:
· возможно осуществить частичное упорядочение понятий области, приемлемое для всех решаемых задач;
· решения, принимаемые на верхних уровнях, нет необходимости отменять на более нижних.
Похожие работы
... 0 Так как нет отрицательных оценок ∆j, значит выполняется признак оптимальности и не вводились искусственные переменные, то получено оптимальное решение. Ответ: Максимальное значение функции Fmax =400 достигается в точке с координатами: =0 =8 =20 =0 =0 =96 Задача №2 (Метод Литтла) Найти кратчайший путь в графе, заданном графически в виде чертежа, методом Литтла. Из ...
... наибольшую прибыль? Группа оборудования, штук для производства единицы продукции Прибыль, грн 1 2 3 4 А 1 0 5 3 4 В 1 1 0 2 6 Построение математической модели Для реализации графического метода решения задач линейного программирования необходимо определить целевую функцию: Z=4*x1+6*x2, где Z→max – целевая функция, x1 – количество изготовленной ...
... способами. Проверяя правильность хода решения, мы тем самым убеждаемся и в правильности результата. Второй способ проверки результата заключается в получении того же результата применением другого метода решения задачи, поэтому полезно всегда задавать решающему вопрос: "Нельзя ли тот же результат получить иначе?" Иными словами, стоит последовать совету: "Решите задачу другим способом". Если при ...
... ограничения несовместны, множество планов пусто и задача ЛП решения не имеет. Рис. 1.4 Рис. 1.5 Рис. 1.6 2. Симплекс-метод 2.1 Идея симплекс-метода Рассмотрим универсальный метод решения канонической задачи линейного программирования , , , с n переменными и m ограничениями-равенствами, известный как симплекс-метод. Множество планов канонической задачи – ...
0 комментариев