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

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

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

Строим δ-членный F-набор, формулы в котором не повторяются. То есть  , припереписываем без конъюнкций все дизъюнкты вида A( x )  Pk  y1 ,..., yniii  1,...,  . Создаем популяцию из δ процессоров.КаждойпареPk  x1,..., xn  ,jjпотенциальновходящихвконтрарныходинF-набор,формулPk  y1 ,..., yn  ,iiназначаемприоритетиихотождествления равным 1. Остальные приоритеты назначаем равными 0.2. Копируем δ-членный F-набор δ−1 раз. Таким образом получаем ровно δодинаковых F-наборов.

Назначаем i-му процессору ( i  1,...,  ) свою начальнуюформулу Pk  y1 ,..., yn  – формулу, с которой данный процессор начинает свойiiитерационныйцикл,Pk  x1,..., xn  изjjипотенциальноконтрарнуюейформулувидаA x , имеющую приоритет, равный 1. Для каждого19процессора назначаем переменную li  0 ( i~фрагмента формулы A x  в формуле A y . 1,...,  ),означающую длинуЕсли какие-то два процессора начинают работу с формулой, начинающейсяс одного и того же предикатного символа, то назначаем для них разные формулыизA x , потенциально контрарные данной.

Если для каких-то двух процессоровне существует разных потенциально контрарных формул, берем для ниходинаковые потенциально контрарные формулы и переходим к п. 3.3.3. Параллельно работают δ процессоров; i-ый процессор ( i 1,...,  )осуществляет отождествление переменных следующим образом.3.1.

Если в рабочей формуле данного процессора нет переменных, которыееще не проходили процедуру отождествления, то в качестве рабочей для этогопроцессора выбираем формулу из следующей элементарной дизъюнкции,содержащую хоть одну «не отождествленную» переменную.3.2. Ищем среди формул в A x  формулу Pk  x j ,..., x j  , имеющуюnji 1приоритет, равный 1, и потенциально контрарную формуле Pk  t1 ,..., tn  (изii~A y), с которой работает этот процессор. Если нашли подходящую формулу,то переходим к п. 3.3.

Если ее нет, то переходим к п. 4.3.3. Решаем систему уравнений вида tl  x j ( l 1,..., ni ), унифицирующуюlсписки переменных. В случае, если эта система имеет решение, то увеличиваемдлину текущего фрагмента li на единицу, запоминаем это число и текущееотождествление и переходим к п. 3.4. Если система решений не имеет, топонизить приоритет этого действия до 0 и переходим к п. 3.2.3.4. Записываем результаты, полученные разными процессорами, ипроверяем их на непротиворечивость.203.5.

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

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

Исоответствующие этому li отождествления являются наибольшей подформулой~A y в A x .В разделе 4.3 получены оценки числа шагов работы алгоритма PHIAPTA.Теорема 5. (Нижняя оценка числа шагов работы алгоритма PHIAPTA)Количествошаговвыделениямаксимальнойобщейподформулыдвух21элементарных конъюнкцийA x  и A y , при использовании алгоритма~PHIAPTA, не менее 4δ + 2δs − 1 + l шагов.Теорема 6. (Верхняя оценка числа шагов работы алгоритма PHIAPTA.)Количествошаговвыделенияэлементарных конъюнкцийA x не превосходит O   l   max sk  kмаксимальной общей подформулы двух~и A y , при использовании алгоритма PHIAPTA, шагов.В приложениях А, В и С приведены модельные примеры примененияалгоритмов IMA, IAPTA и PHIAPTA соответственно для решения задач логикопредметного распознавания образов.В заключенииприведены итоги выполненного исследования, которыезаключаются в следующем:1.

Сформулирована и обоснована адаптация обратного метода Маслова длядоказательства выводимости формул вида x1,..., xn   & Di a1,..., ak , x1,..., xn  , к i 1доказательству выводимости которых сводятся многие задачи ИскусственногоИнтеллекта, объекты исследования в которых характеризуются свойствами своихэлементовиотношениямимеждуэтимиэлементами,аследовательно,допускающие формализацию средствами языка исчисления предикатов.2.РазработаналгоритмIMAвыводимостиформулвидаx1,..., xn   & Di a1,..., ak , x1,..., xn  , основанный на разработанной адаптации i 1обратного метода. Доказаны асимптотические оценки числа шагов работы этогоалгоритма.3.

Разработана модификация IAPTA алгоритма IMA, использующая тактикимуравьиных алгоритмов и параллельных вычислений. Доказаны асимптотическиеоценки числа шагов работы этого алгоритма.224. Обоснована возможность применения обратного метода Маслова длярешения задачи выведения максимальной общей подформулы. Сформулированалгоритм PHIAPTA выделения максимальной общей с точностью до именаргументовподформулыдвухэлементарныхконъюнкций.Доказаныасимптотические оценки числа шагов работы этого алгоритма.Былисформулированыследующиерекомендациипоприменениюрезультатов работы.1. Сформулированная конкретизация обратного метода Маслова являетсяпростым и понятным средством доказательства выводимости формул видаx1,..., xn   & Di a1,..., ak , x1,..., xn  , i 1поэтомуеѐможноприменятьдляпервоначального знакомства с обратным методом.2.

Построенные алгоритмы полностью готовы к программной реализации имогут быть применены для решения различных задач Искусственного Интеллектав рамках логико-предметного подхода.Так же были предложены перспективы дальнейшей разработки тематикиможно указать построение модификаций предложенных алгоритмов для решенияразличныхзадачискусственногоинтеллекта,программнуюреализациюпостроенных алгоритмов, а так же качественное сравнение полученного метода ссуществующими методами решения задач логико-предметного распознаванияобразов и теории выводимости, например, с методом резолюций.23ГЛАВА 1.

ОБЗОР СОВРЕМЕННОГО СОСТОЯНИЯ ПРЕДМЕТНОЙ ОБЛАСТИ1.1. Постановка задач Искусственного Интеллекта при логико-предметномподходе.В диссертации рассматриваются оценки числа шагов решения частныхзадач Искусственного Интеллекта – задачлогико-предметного распознаванияобразов в приведѐнной ниже постановке[39].Пусть имеется множество Ω конечных множеств   a1,..., ak . Частью τобъекта ω называется любое его подмножество. Пусть также на частях τ заданнабор предикатов p1,..., pl , характеризующих свойства и отношения междуэлементами ω.Задано разбиение множества Ω на К (возможно пересекающихся) классовk jj 1Логическим описанием S   объекта называется набор всех истинныхпостоянных формул pi   или pi   , выписанных для всех возможных частей τобъекта ω.Здесь и далее посредством x обозначается список элементов конечногомножества х, соответствующий некоторой перестановке его элементов.

Тот факт,что элементами списка x являются элементы множества у, будем записывать ввиде x  y . Для того, чтобы записать, что значения для переменных списка x ,удовлетворяющие формуле A x  , различны, вместо формулы n 1 nx1...xn  & & xi  x j & Ax1,..., xn  i 1 j i 1x  .будет использоваться обозначение x A24Логическим описанием класса  j называется такая формула Aj x  сосвободными переменными x , что1.Aj x  содержит в качестве атомарных только формулы вида pi  y  ,где y  x .2.Aj x  не содержит кванторов.3.Aj x  имеет вид дизъюнкции элементарных конъюнкций.4.если для некоторого упорядоченного множества  всех элементовмножества ω истинна формула Aj x  , то    j .С помощью построенных описаний предлагается решать следующие задачираспознавания образов[39].Задачаидентификации.Выделитьчастьобъектаω,котораяпринадлежитклассу  j .Задача классификации. Найти все такие номера классов j, что    j .Задача анализа сложного объекта.

Найти и классифицировать все частиτобъекта ω, для которых   .Решение задач идентификации, классификации и анализа сложного объектасведено к доказательству логических следованийS    ? x Aj x  , S    ?kj 1 ? x A j x  ,S    ?kj 1 A j   ,(1.1.1)(1.1.2)(1.1.3)k где Aj x  – дизъюнкция элементарных конъюнкций, а обозначения ? x  и ? j 1используются для слов «при каких различных x» и «при каких j  j  1,..., k  » [38].В силу «конструктивности» секвенциального исчисления предикатовпроверкалогическихвыводимости секвенцийследований(1.1.1)–(1.1.3)равносильнапроверке25S    x A j x  , (1.1.4)kS     A j   , (1.1.5)j 1kS     x A j  x  .(1.1.6)j 1В [37] доказано, что задачи (1.1.4)–(1.1.6) NP-полны и, следовательно,(1.1.1)–(1.1.3) NP-трудны, то есть для них не известен алгоритм, имеющийполиномиальную верхнюю оценку числа шагов.Это, в свою очередь, равносильно истинности формул& S    x Aj x ,k& S   & S    A j  j 1,k x A j x j 1при любых наборах значений ω.

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

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