Системы искусственного интеллекта

Аренда экскаватора саратов |

Комплексная схема нечеткого планирования - часть 3


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

Рассмотрим понятие, объединяющее подходы разбиения проблемы на под-проблемы и поиска в пространстве состояний. 1-проблемой (объединенной проблемой) называется четверка R=(B, Г, Р0, Т), где В-множество SS-проблем;

(В, Г)-схема PR-проблем; Р0эB -основная проблема;T-импликативная сеть, такая, что WTЗB"Ж. Кроме того, R есть решение SS-проблемы Р0. Учитывая связь между существованием импликативной сети и разрешимостью проблемы, легко показать, что если для заданной I-проблемы найден накрывающий путь х из Р0 на множество Ф'Н В, проблемы Ф' разрешимы как SS-проблемы, если х частично представляет импликативную сеть Т, то и проблема R разрешима как SS-проблема.

Рассмотрим головоломку "Ханойская башня" . Имеются три стержня 1, 2 и 3 и три диска различных размеров А, В, С с отверстием в центре, которые могут одеваться на стержни. В исходной позиции диски находятся на стержне 1; самый большой диск С-внизу, самый маленький диск А- наверху. Требуется перенести все диски на стержень 3, перемещая за один раз только один диск. Брать можно только самый верхний диск на стержне, причем его нельзя класть на диск, меньший по размерам. Используем для записи состояний и операторов классическую формализацию. Выражение ijk обозначает конфигурацию, при которой диск С находится на стержне i, диск В - на стержне j и диск А-на стержне k. Выражение xij обозначает действие, при котором диск х перемещается со стержня i на стержень j. С помощью этого формализма можно просто записать все состояния и переходы головоломки в виде треугольного графа, где вершины соответствуют расположению дисков на стержнях, а дуги-возможным перекладываниям дисков (рис.1). На этой головоломке легко проиллюстрировать все основные понятия обобщенной стратегии проблем.

Представим головоломку в виде модели I-проблемы.


Начало  Назад  Вперед



Книжный магазин