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

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

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

В соответствии стеоремой 3.2.1 число шагов выделения «тройки» с помощью алгоритма IAPTA взаданном изображении не может быть меньше, чем  s  4  2  5 14  2  72 . По теореме 3.2.2 верхняя оценка числа шагов составляет O l   max sk   , то есть  k имеет порядокl   max sk   3  85  98 304 k68В действительности на решение этой задачи потребовалось 136 шагов.Алгоритм IAPTA вывел объект «тройка», представленный на рисунке 3.3.4.Рис. 3.3.4. Выделенный объект «тройка».Замечание. В приведенном примере, очевидно, объект «тройка» выделилсяне в явном виде, это скорее объект «Е». Такое выделение произошло из-засвойства симметричности (в частности, относительно вертикали) предикатов V иL, но, если еще раз «прогнать» алгоритм для этой задачи, будет выделена и«тройка».69ГЛАВА 4.

ВЫДЕЛЕНИЕ МАКСИМАЛЬНОЙ ОБЩЕЙ ПРЕДИКАТНОЙПОДФОРМУЛЫ С ПОМОЩЬЮ ОБРАТНОГО МЕТОДА МАСЛОВАОсновные результаты этой главы изложены в статье автора [65].4.1. Использование обратного метода для решения задачи выделениямаксимальной общей подформулыПонятие неполной выводимости предикатной формулы было введено в [42]для распознавания объектов с неполной информацией. При этом рассматриваетсязадача проверки того, что из истинности всех формул множестваистинностьS   следуетA x  или некоторой еѐ максимальной подформулы A~ y  на набореразличных констант из ω, где список переменных является подсписком спискапеременных x .Привыделениимаксимальной общей подформулы двух заданных~элементарных конъюнкций A x  и A y  требуется найти такую подформулу~~~A y формулы A y , что имеет место следствие Ax   yA'  y.

Очевидно, чтов этом следствии наборы x и y  являются наборами переменных. Тем не менее,если в алгоритме IAPTA заменить действие «присвоение значений переменным»на «отождествление переменных», этот алгоритм (после описанных нижемодификаций алгоритма) можно применить и для решения задачи выделениямаксимальной общей подформулы.4.2. Алгоритм PHIAPTA (PartialHatchabilityInverseAntParallelTacticAlgorithm)выделения максимальной общей подформулы1. Строим δ-членный F-набор, формулы в котором не повторяются.

То естьпереписываем без конъюнкций все дизъюнкты вида A( x )  Pki y1 ,..., yn i , приi  1,...,  . Создаем популяцию из δ процессоров.70КаждойпареPk j x1,..., xn j ,потенциальновходящихвконтрарныходинF-набор,формулназначаемPki y1 ,..., yn i ,иприоритетихотождествления равным 1. Остальные приоритеты назначаем равными 0.2. Копируем δ-членный F-набор δ−1 раз. Таким образом получаем ровно δодинаковых F-наборов. Назначаем i-му процессору ( i  1,...,  ) свою начальную – формулу, с которой данный процессор начинает свойитерационный цикл, и потенциально контрарную ей формулу вида P x ,..., x формулу Pki y1 ,..., yn ikjиз1njA x , имеющую приоритет, равный 1. Для каждого процессора назначаемпеременную li  0 ( i  1,...,  ), означающую длину фрагмента формулы~формуле A y.A x  вЕсли какие-то два процессора начинают работу с формулой, начинающейсяс одного и того же предикатного символа, то назначаем для них разные формулыизA x , потенциально контрарные данной.

Если для каких-то двух процессоровне существует разных потенциально контрарных формул, берем для ниходинаковые потенциально контрарные формулы и переходим к п. 3.3.3. Параллельно работают δ процессоров; i-ый процессор ( i  1,...,  )осуществляет отождествление переменных следующим образом.3.1. Если в рабочей формуле данного процессора нет переменных, которыееще не проходили процедуру отождествления, то в качестве рабочей для этого~процессора выбираем формулу Pk t1 ,..., tn (из A y) из следующей элементарнойiiдизъюнкции, содержащую хоть одну «не отождествленную» переменную.

Еслиновая рабочая формула найдена, то переходим к п.3.2, если таковой формулы ненайдено – переходим к п. 4.3.2. Ищем среди формул вA x  формулу Pki  x j1 ,..., x j n  , имеющуюприоритет, равный 1, и потенциально контрарную формулеjPki t1 ,..., tn i, с71которой работает этот процессор. Если какие-то два процессора работают с однойи той же дизъюнкцией, ищем для них разные потенциально контрарныеатомарные формулы. Если найти разные формулы не удалось, один изпроцессоров «засыпает» до тех пор, пока не будет отменено присвоение,приведшее к одинаковой работе двух процессоров.

Если нашли подходящуюпотенциально контрарную формулу, то переходим к п. 3.3. Если ее нет, топомечаем формулу Pki t1 ,..., tn i как удаленную и переходим к п. 3.1.3.3. Решаем систему уравнений вида tl  x jl ( l  1,..., ni ), унифицирующуюсписки переменных. В случае, если эта система имеет решение7, то увеличиваемдлину текущего фрагмента li на единицу, запоминаем это число и текущееотождествление (по сути, являющееся унификатором) и переходим к п. 3.4.

Еслисистема решений не имеет, то понижаем приоритет этого действия до 0 ипереходим к п. 3.2.3.4. Записываем результаты, полученные разными процессорами, ипроверяем их на непротиворечивость следующим образом. Если процессорыодновременно присваивают одним и тем же переменным разные значения илиодин из процессоров присваивает значения, которые уже ранее были присвоеныдругим процессором, то такие результаты считаются противоречивыми. Еслирезультаты действий двух процессоров не противоречат друг другу, топрисвоение полученных значений переменных осуществляется в формулах обоихпроцессоров, тогда для этих процессоров увеличиваются на единицу длинытекущих фрагментов li и текущие унификаторы.3.5.

Заменяем в F-наборе каждого процессора вхождения переменных изсписка на их значения, полученные в п. 3.3 и п. 3.4, если успешно пройденапроверка на непротиворечивость.В данном случае система решений не имеет, только в том случае, если происходит повторное отождествление какой-либо переменной (вправой или левой части уравнений).772~3.6. Если для какого-либо процессора все переменные из A y получили~новое значение, и выведен пустой F-набор, то формула A y полностьюсодержится в формуле3.7.ЕслиA x . Алгоритм заканчивает работу.выведентупиковыйF-набор, проверяем формулывидаDi y'1 ,..., y'ki , x1,..., xn текущего процессора формулы, не имеющие переменные натавтологичность.

Если какая-либо из этих формул тавтологична, увеличиваемдлину фрагмента этого процессора на 1 и добавляем первую формулуDi y'1 ,..., y'ki , x1,..., xn в фрагмент.3.8. Если в F-наборе какого-либо процессора отсутствуют формулы,имеющие переменные, которые еще проходили процедуру отождествления, топереходим к п. 4.3.9. Если для всех процессоров приоритеты всех действий равны 0, топереходим к п. 4.3.3.10. Если в F-наборе какого-либо процессора существуют формулы,имеющие переменные, которые еще не проходили процедуру отождествления, топереходим к п.

3.1.4. Возвратная часть алгоритма.4.1. Отменяем последнее действие п. 3.5, если это возможно, уменьшаемсоответствующий фрагмент и его длину li на 1, запоминаем это число и текущееотождествление и переходим к п. 3.2.4.2. Если для какого-либо процессора отмена последнего действия п. 3.5невозможна, то процессор заканчивает работу.4.3. Если все процессоры закончили работу, то наибольшее число из всех li~на всех шагах является размером наибольшей подформулы A y вA x  . Исоответствующий этому li фрагмент является наибольшей общей подформулой~A y и A x .Схематически работа алгоритма PHIAPTA представлена на рис. 4.2.1.73Рис. 4.2.1. Схема работы алгоритма PHIAPTA.744.3.

Оценка числа шагов работы алгоритма PHIAPTA.Теорема 4.3.1. (Нижняя оценка числа шагов работы алгоритма PHIAPTA)Количествошаговвыделенияэлементарных конъюнкциймаксимальнойобщейподформулыдвухA x  и A~ y , при использовании алгоритма PHIAPTA,не менее4δ + 2δs − 1 + lшагов.Доказательство. Нижняя оценка достигается в том случае, если одному изпроцессоров удается за один «прогон» не просто найти какую-то подформулу, а~показать, что A y полностью содержится в A x  , то есть является ихмаксимальной общей подформулой.Кроме того, нижняя оценка достигается в том случае, когда количествопеременных равно наибольшему количеству аргументов в атомарной формуле иответ получен при решении одной системы lуравнений.На выполнение соответствующих пунктов алгоритма уходитв п. 1 – δшагов на построение F-набора и δsшагов на назначение приоритетов;в п.

2 – (δ − 1) шаг на копирование F-набора;δ шагов на создание популяции процессоров;δ шагов на назначение каждому процессору своего F-набора, своей начальнойформулы с переменными;l шагов на решение системы l уравнений и δsшагов на проверку того, чтополучился пустой F-набор.Итого получаем 4δ + 2δs − 1 + l шагов.■Теорема 4.3.2. (Верхняя оценка числа шагов работы алгоритма PHIAPTA.)Количествошаговвыделениямаксимальнойобщейподформулыдвух75элементарных конъюнкцийA x  и A~ y , при использовании алгоритма PHIAPTA,не превосходитO   l   max sk  k.Доказательство. В случае поиска наибольшей общей подформулы верхняя~оценка будет достигнута, если A y не содержится полностью в A x  .

Тогдакаждому процессору придется перебрать все формулы изA x  и A y . Эта~оценка превосходит верхнюю оценку числа шагов работы алгоритма IAPTAровно на то количество шагов, которое требуется для хранения фрагментов иподсчета размеров этих фрагментов. На это требуется не более 2δ шагов длякаждого процессора на каждом шаге работы алгоритма. Итого имеемO   l   max sk  kшагов.■В приложении В представлено решение следующей задачи с помощьюалгоритма PHIAPTA.Пусть имеется множество контурных изображений, составленных изотрезков прямых, задаваемых своими концами. Заданы два предиката V и L,определяемых так, как представлено на рис.

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

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