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


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


PR-проблема представляет собой четверку Z=(S , Г, Ро, Ф), где (S , Г)-схема PR-проблемы, РоэS - начальная проблема, ФМ S -множество конечных проблем. Решение Z представляет собой накрывающий путь (S , Г) из Ро в Ф/xМ Ф, множество решений xz, есть множество всех решений Z.

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

Импликата проблемы Р есть пара (p, y), где p =PiP2... Pk - цепочка проблем, y -отображение из Хр1 C Хр2 ... C Хрk в Хр( Хрi обозначает множество решений Рi<). Импликативная схема есть тройка L =(Р, p , y ), такая, что Р - проблема, (p , y ) - импликата Р. Множество Т импликативных схем называется импликативной сетью. Множество проблем импликативной сети

W t={x|($ L )((L =(Р, p , y ))L ((х=Р)\/(х - символ p ))}.

Объединим синтаксис и семантику подхода, основанного на разбиении проблемы на подпроблемы. PR-проблема Z=(S , Г, Ро, Ф) представляет импликативную сеть Т тогда и только тогда, когда S =Wt и для каждого L =(Р, p , y )эT существует в точности одно g эГ, такое, что Рg =p , и для каждого g эГ, и для каждого Р из области определения g существует в точности одно L =(Р, p , Y )' T, такое,что p =Pg Проблема Р решена тогда и только тогда, когда Хp- непустое множество.

Если PR-проблема представляет импликативную сеть, то проблема Р0 разрешима. Для существования решения достаточно, чтобы импликативные схемы в импликативной сети Т существовали только для всех пар (xi, у,),i=0,..., k-1, входящих в накрывающий путь схемы PR-проблемы. В этом случае синтаксис и семантика PR-проблемы не совпадают. В данном случае PR-проблема частично представляет импликативную сеть Т.




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