Диссертация (1150569), страница 18

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 18)

3.5 ушло 7 шагов. Согласно п. 3.6 первый процессор получилпустой F-набор (8 шагов).Алгоритм заканчивает работу. Объект «тройка» выведен:На его выделение потребовалось 136 шагов.111ПРИЛОЖЕНИЕ C. Пример решения задачи выделения наибольшей общейподформулы с помощью алгоритма PHIAPTA.Пусть имеется множество контурных изображений, составленных изотрезков прямых, задаваемых своими концами.

Заданы два предиката V и L,определяемых так, как представлено на рис. 1.Рис. 1. Предикаты V и L.Задан класс объектов Ω1 – класс контурных изображений «девять».Схематическое изображение эталонного объекта имеет вид, представлены нарисунке 2.Рис. 2. Контурное изображение «девять».Описание класса задается следующей формулой:A1  x1 ,..., x5   V  x1 , x2 , x3  & V  x2 , x4 , x1  & V  x2 , x5 , x1  && V  x3 , x1 , x4  & V  x4 , x3 , x2  & V  x4 , x5 , x3  & L x4 , x2 , x5  .Задан класс объектов Ω2 – класс контурных изображений «четыре».Схематическое изображение эталонного объекта имеет вид, представлено нарисунке 3.112Рис. 3.

Контурное изображение «четыре».Это изображение имеет описание:A2  y1,, y4   V  y1, y3 , y2  & V  y1, y4 , y2  & V  y2 , y1, y3  && V  y3 , y2 , y1  & V  y3 , y4 , y2  & L y3 , y1, y4 Требуется найти максимальную общую подформулу этих двух классов.Так как при выделении максимальной общей подформулы двух заданных~~элементарных конъюнкций A x  и A y  требуется найти такую подформулу A y ~~формулы A y , что имеет место следствие Ax   y A'  y  , то первое, чтонеобходимо сделать, чтобы решить поставленную задачу, это выбрать какую из~двух формул A1  x1 ,..., x5  или A2  y1,, y4  взять за A x  , а какую за A y . Так какв полученных оценках числа шагов работы алгоритмов, основанных на обратномметоде, в показателе степени стоят параметры правой части, то в качествеA x возьмем формулу, в которой больше атомарных формул.

В нашем случае этоA1  x1,..., x5 .Таким образом, требуется проверить частичную выводимостьA1x   p yA2  y .Тогда δ = 6, s1  6 , s2  1 ,l = 3, следовательно, верхняя оценка числа шагов6решения этой задачи имеет порядок   l   max sk   6  3  6  839 808 шагов. kИтак, первый F-набор D имеет вид113  V  y1 , y3 , y2   V  x1 , x2 , x3   V  x2 , x4 , x1   V  x2 , x5 , x1         V  x3 , x1 , x4   V  x4 , x3 , x2   V  x4 , x5 , x3   L x4 , x2 , x5    V  y1 , y4 , y2   V  x1 , x2 , x3   V  x2 , x4 , x1   V  x2 , x5 , x1      Vx,x,xVx,x,xVx,x,xLx,x,x3 1 44 3 24 5 34 2 5   V  y2 , y1 , y3   V  x1 , x2 , x3   V  x2 , x4 , x1   V  x2 , x5 , x1         V  x3 , x1 , x4   V  x4 , x3 , x2   V  x4 , x5 , x3   L x4 , x2 , x5    V  y3 , y2 , y1   V  x1 , x2 , x3   V  x2 , x4 , x1   V  x2 , x5 , x1         V  x3 , x1 , x4   V  x4 , x3 , x2   V  x4 , x5 , x3   L x4 , x2 , x5    V  y3 , y4 , y2   V  x1 , x2 , x3   V  x2 , x4 , x1   V  x2 , x5 , x1         V  x3 , x1 , x4   V  x4 , x3 , x2   V  x4 , x5 , x3   L x4 , x2 , x5    L y3 , y1 , y4   V  x1 , x2 , x3   V  x2 , x4 , x1   V  x2 , x5 , x1         V  x3 , x1 , x4   V  x4 , x3 , x2   V  x4 , x5 , x3   L x4 , x2 , x5  На п.

1 алгоритма PHIAPTA ушло 54 шага (6 шагов на создание F-набора, 6шагов на создание популяции из шести процессоров, 42 шага на расстановкуприоритетов).Мы имеем шесть процессоров. Первый из них начинает работу с формулыV  y1, y3 , y2  , второй – с V  y1, y4 , y2  , третий – с V  y2 , y1, y3  , четвертый – сV  y3 , y2 , y1  , пятый – с V  y3 , y4 , y2  , а шестой – с L y3 , y1 , y4  . У всехпроцессоров F-наборы одинаковые, но разные рабочие формулы.На выполнение п. 2 алгоритма потребовалось:5 шагов на копирование F-набора для каждого процессора;6 шагов на назначение рабочей атомарной формулы с переменными для каждогопроцессора;1 шаг на назначение первого «унификатора» первому процессору (то естьотождествление списков  y1, y3 , y2  и  x1 , x2 , x3  );1 шаг на сравнение имен рабочих предикатов и 2 шага на назначение первого«унификатора» второму процессору, отличного от уже назначенного первомупроцессору (то есть отождествление списков  y1, y4 , y2  и  x2 , x4 , x1  );1141 шаг на сравнение имен рабочих предикатов и 3 шага на назначение первого«унификатора» третьему процессору, отличного от уже назначенных первому ивторому процессорам (то есть отождествление списков  y2 , y1, y3  и  x2 , x5 , x1 );1 шаг на сравнение имен рабочих предикатов и 4 шага на назначение первого«унификатора» четвертому процессору, отличного от уже назначенных первому,второму и третьему процессорам (то есть отождествление списков  y3 , y2 , y1  и x3 , x1, x4  );1 шаг на сравнение имен рабочих предикатов и 5 шагов на назначение первого«унификатора» пятому процессору, отличного от уже назначенных первому,второму, третьему и четвертому процессорам (то есть отождествление списков y3 , y4 , y2  и x4 , x3 , x2  );1 шаг на сравнение имен рабочих предикатов и 1 шаг на назначение первого«унификатора» шестому процессору (то есть отождествление списков  y3 , y1, y4 и  x4 , x2 , x5  ); Итого 32 шага.Согласно п.

3.3 процессоры решают следующие системы уравнений (3шага), запоминаем текущие унификаторы (3 шага), длина фрагмента для каждогопроцессора li1  1 (1 шаг)ПРОЦЕССОРПЕРВЫЙВТОРОЙТРЕТИЙЧЕТВЕРТЫЙy1  x1y2  x3y3  x 2y1  x2y2  x1y1  x5y 2  x2y3  x1y1  x4y 2  x1y3  x3y 4  x4ПЯТЫЙШЕСТОЙy1  x2y 2  x2y3  x4y4  x3y3  x4y4  x5Решения всех процессоров попарно противоречивы (16 шагов).Согласно п.

3.5 имеем следующие шесть F-наборов (формулы с нулевымиприоритетами удалены из F-набора).первый процессор115  V  x1, x2 , x3   V  x1, x2 , x3   V  x2 , x4 , x1   V  x2 , x5 , x1      V  x3 , x1, x4   V  x4 , x3 , x2   V  x4 , x5 , x3  V  x , y , x   V  x , x , x   V  x , x , x   V  x , x , x   1 4 31 2 32 4 12 5 1  V  x3 , x1, x4   V  x4 , x3 , x2   V  x4 , x5 , x3   V  x3 , x1, x2   V  x1, x2 , x3   V  x2 , x4 , x1   V  x2 , x5 , x1      V  x3 , x1, x4   V  x4 , x3 , x2   V  x4 , x5 , x3   V  x2 , x3 , x1   V  x1, x2 , x3   V  x2 , x4 , x1   V  x2 , x5 , x1     V  x3 , x1, x4   V  x4 , x3 , x2   V  x4 , x5 , x3 Vx,y,xVx,x,xVx,x,xVx,x,x2 4 31 2 32 4 12 5 1   V  x3 , x1, x4   V  x4 , x3 , x2   V  x4 , x5 , x3 Lx2 , x1, y4   Lx4 , x2 , x5 на замену всех вхождений переменных на их значения уходит 12 шагов (рамкойвыделены формулы, в которых всем переменным yi присвоены значения изсписка x );второй процессор V  x2 , y3 , x1   V  x1, x2 , x3   V  x2 , x4 , x1   V  x2 , x5 , x1       V  x3 , x1, x4   V  x4 , x3 , x2   V  x4 , x5 , x3   V  x , x , x   V  x , x , x   V  x , x , x   V  x , x , x    2 4 11 2 32 4 12 5 1 V  x3 , x1, x4   V  x4 , x3 , x2   V  x4 , x5 , x3   V  x , x , y   V  x , x , x    V  x , x , x   V  x , x , x    1 2 31 2 32 4 12 5 1  V  x3 , x1, x4   V  x4 , x3 , x2   V  x4 , x5 , x3   V  y , x , x   V  x , x , x    V  x , x , x   V  x , x , x    3 1 21 2 32 4 12 5 1  Vx,x,xVx,x,xVx,x,x3 1 44 3 24 5 3  V  y , x , x   V  x , x , x    V  x , x , x   V  x , x , x    3 4 11 2 32 4 12 5 1   V  x3 , x1, x4   V  x4 , x3 , x2   V  x4 , x5 , x3 L y3 , x2 , x4   Lx4 , x2 , x5 на замену всех вхождений переменных на их значения уходит 10 шагов;третий процессор116  V  x5 , x1, x2   V  x1, x2 , x3   V  x2 , x4 , x1   V  x2 , x5 , x1      V  x3 , x1, x4   V  x4 , x3 , x2   V  x4 , x5 , x3  V  x , y , x   V  x , x , x   V  x , x , x   V  x , x , x   5 4 21 2 32 4 12 5 1  V  x3 , x1, x4   V  x4 , x3 , x2   V  x4 , x5 , x3   V  x2 , x5 , x1   V  x1, x2 , x3   V  x2 , x4 , x1   V  x2 , x5 , x1      V  x3 , x1, x4   V  x4 , x3 , x2   V  x4 , x5 , x3   V  x1, x2 , x5   V  x1, x2 , x3   V  x2 , x4 , x1   V  x2 , x5 , x1     V  x3 , x1, x4   V  x4 , x3 , x2   V  x4 , x5 , x3 Vx,y,xVx,x,xVx,x,xVx,x,x1 4 21 2 32 4 12 5 1   V  x3 , x1, x4   V  x4 , x3 , x2   V  x4 , x5 , x3 L y3 , x2 , x4   Lx4 , x2 , x5 на замену всех вхождений переменных на их значения уходит 12 шагов;четвертый процессор  V  x4 , x3 , x1   V  x1, x2 , x3   V  x2 , x4 , x1   V  x2 , x5 , x1      V  x3 , x1, x4   V  x4 , x3 , x2   V  x4 , x5 , x3  V  x , y , x   V  x , x , x   V  x , x , x   V  x , x , x   4 4 11 2 32 4 12 5 1  V  x3 , x1, x4   V  x4 , x3 , x2   V  x4 , x5 , x3   V  x1, x4 , x3   V  x1, x2 , x3   V  x2 , x4 , x1   V  x2 , x5 , x1      V  x3 , x1, x4   V  x4 , x3 , x2   V  x4 , x5 , x3   V  x3 , x1, x4   V  x1, x2 , x3   V  x2 , x4 , x1   V  x2 , x5 , x1     V  x3 , x1, x4   V  x4 , x3 , x2   V  x4 , x5 , x3  V  x3 , y4 , x1   V  x1, x2 , x3   V  x2 , x4 , x1   V  x2 , x5 , x1     V  x3 , x1, x4   V  x4 , x3 , x2   V  x4 , x5 , x3 L y3 , x2 , x4   Lx4 , x2 , x5 на замену всех вхождений переменных на их значения уходит 11 шагов;пятый процессор117 V  y1, x4 , x2   V  x1, x2 , x3   V  x2 , x4 , x1   V  x2 , x5 , x1       V  x3 , x1, x4   V  x4 , x3 , x2   V  x4 , x5 , x3  V  y1, x3 , x2   V  x1, x2 , x3   V  x2 , x4 , x1   V  x2 , x5 , x1       V  x3 , x1, x4   V  x4 , x3 , x2   V  x4 , x5 , x3  V  x2 , y1, x4   V  x1, x2 , x3   V  x2 , x4 , x1   V  x2 , x5 , x1       V  x3 , x1, x4   V  x4 , x3 , x2   V  x4 , x5 , x3  V  x4 , x2 , y1   V  x1, x2 , x3   V  x2 , x4 , x1   V  x2 , x5 , x1      Vx,x,xVx,x,xVx,x,x3 1 44 3 24 5 3  V  x , x , x   V  x , x , x   V  x , x , x   V  x , x , x    4 3 21 2 32 4 12 5 1  V  x3 , x1, x4   V  x4 , x3 , x2   V  x4 , x5 , x3 L y3 , x2 , x4   Lx4 , x2 , x5 на замену всех вхождений переменных на их значения уходит 10 шагов;шестой процессор V  x2 , x4 , y2   V  x1, x2 , x3   V  x2 , x4 , x1   V  x2 , x5 , x1      Vx,x,xVx,x,xVx,x,x3 1 44 3 24 5 3 V  x2 , x5 , y2   V  x1, x2 , x3   V  x2 , x4 , x1   V  x2 , x5 , x1       V  x3 , x1, x4   V  x4 , x3 , x2   V  x4 , x5 , x3  V  y2 , x2 , x4   V  x1, x2 , x3   V  x2 , x4 , x1   V  x2 , x5 , x1       V  x3 , x1, x4   V  x4 , x3 , x2   V  x4 , x5 , x3  V  x4 , y2 , x2   V  x1, x2 , x3   V  x2 , x4 , x1   V  x2 , x5 , x1      Vx,x,xVx,x,xVx,x,x3 1 44 3 24 5 3 V  x4 , x5 , y2   V  x1, x2 , x3   V  x2 , x4 , x1   V  x2 , x5 , x1      Vx,x,xVx,x,xVx,x,x3 1 44 3 24 5 3L x4 , x2 , x5   L x4 , x2 , x5 на замену всех вхождений переменных на их значения уходит 10 шагов.Всего число шагов выполнения п.

Характеристики

Список файлов диссертации