При решении ряда задач удобно бывает свести задачу к подзадачам – метод редукции. Задача разбивается на дочерниеподзадачи и т. д. Множество задач и подзадач представляется в виде графа, содержащего вершины типа И и вершины типа ИЛИ.
Поиск решения на таких графах отмечается тем, что проверяется не совпадение очередной вершины с нулевой, а разрешимость подзадач.
Заключительные вершины должны быть разрешимы – это элементарные задачи. Прочие вершины разрешимы, если:
- для вершин типа И разрешимы все ее подзадачи;
- для вершины типа ИЛИ разрешима хотя бы одна из подзадач.
Методы поиска решений на графах И/ИЛИ очень похожи на методы поиска в пространстве состояний. Пример.
Дуга, замыкающая ребра означает, что подзадачи объединяются по И. Для решения задачи S0 надо решить задачу S1 и S2 или задачу S3 или задачи S4 и S5. Заштрихованные подзадачи – заключительные, решения их известны.
Задачи S8 и S12 пока к подзадачам не сведены.
Опубликовал Kest
January 11 2010 14:27:05 ·
0 Комментариев ·
10453 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
