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

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

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

Ищем вS   формулу Pk v1 ,...,vm  при наборе констант v1 ,...,vm сiотрицанием перед выбранным в п. 2.2 предикатным символом. Если нашлиподходящую формулу – помечаем еѐ как удаленную и переходим к пункту 2.4,если еѐ не существует, то переходим к пункту 3.2.4. Решаем систему уравнений, отождествляющую списки переменныхt1 ,...,t m и констант v1 ,...,vm . В случае, если эта система имеет решение, перейтик пункту 2.5, если система решений не имеет, то перейти к пункту 2.3.2.5. Заменяем во всем F-наборе переменные из списка t1 ,...,t m на ихзначение, полученные в пункте 2.4.132.6.

В полученном F-наборе удаляем повторения формул.2.7. Если получился пустой F-набор, то алгоритм заканчивает работу.2.8. Если получился тупиковый F-набор – перейти к пункту 3.2.9. Если в F-наборе все формулы, имеющие переменные помечены какудаленные – переходим к пункту 4.2.10. Если в F-наборе существуют элементарные дизъюнкции, имеющиепеременные, которым еще не присвоено значение, то перейти к пункту 2.2.3. Возвратная часть алгоритма.3.1. Отменяем последнее действие пункта 2.5, если это возможно, ипереходим к пункту 2.33.2. Если отмена последнего действия пункта 2.5 невозможна, то помечаематомарную формулу Pk t1,..., tm как удаленную и переходим к пункту 2.i4. Если все формулы помечены как удаленные значит, формула невыводима.

Алгоритм заканчивает работу.В разделе 2.3 получены асимптотические оценки числа шагов работыалгоритма IMA.Определение5.Однимшагомработыалгоритманазываетсякакприсвоение переменной значения (решение одного уравнения вида х=а), так ипроверка на графическое совпадение атомарных формул или подстановказначений переменных в атомарные формулы, имеющие вхождения данныхпеременных.Пусть l – наибольшее количество аргументов в атомарной формуле;s+1 – количество атомарных формул в каждом из дизъюнктов;sk– количество вхождений в исходную формулу атомарных формул с k-мпредикатным символом.Теорема 1. (Нижняя оценка работы алгоритма IMA)Количество шаговрешения задачи искусственного интеллекта, сведѐнной к доказательству14следствия вида S ()  x Ax  при использовании алгоритма IMA, основанногона тактиках Обратного метода не менее О(sl)шагов.Теорема2.(ВерхняяоценкачислашаговработыалгоритмаIMA)Количество шагов затрачиваемых на решение задачи искусственногоинтеллекта, сведѐнной к доказательству следствия вида S ()  x Ax прииспользовании алгоритма IMA, основанного на тактиках Обратного метода, атакженахождениязначенийдляпеременных,существованиекоторыхутверждается в заключении логического следования задачи не превосходитO   max sk   l  шагов.kВ третьей главе описаны идеи применения муравьиных алгоритмов ипараллельных вычислений для решения задач логико-предметного распознаванияобразов с помощью обратного метода Маслова.Используя идеи муравьиных алгоритмов, создаем многопроцессорнуюсистему, в которой действия между процессорами распределены поровну.

Равноеразделение действий необходимо для того, чтобы каждое действие имеловозможность стать первым выполненным. Каждый процессор может выполнятьследующие простые действия:1) присвоение значения переменным;2) замена всех вхождений переменной на еѐ значение;3) проверка формул на графическое совпадение;4) отмена присвоения значения переменным;5) отмена замены всех вхождений переменной;6) изменение приоритета данного действия на 0.В разделе 3.1 сформулирован алгоритм IAPTA, основанный на примененииобратного метода, муравьиных тактик и параллельных вычислений.Алгоритм IAPTA (Inverse Ant Parallel Tactic Algorithm)151. Строим δ-членный F-набор, формулы в котором не повторяются.

То естьпереписываем без конъюнкций все дизъюнкты вида  S    Pk  x1,..., xn  приiii  1,..., . Создаем популяцию из δ процессоров.КаждойпареPk  a j ,..., a jnii  1,потенциальноконтрарныхформулPk  x1,..., xn iiивходящих в один F-набор, назначаем приоритет ихотождествления равным 1. Остальные приоритеты назначаем равными 0.2. Копируем δ-членный F-набор δ – 1 раз. Получаем ровно δ одинаковых Fнаборов. Назначаем i-му процессору i  1,...,  свою начальную формулуPk  x1,..., xn ii– формулу, с которой данный процессор начинает свойитерационный цикл, и потенциально контрарную ей формулу из S   , имеющуюприоритет, равный 1.

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

Если в рабочей формуле данного процессора нет переменных, то вкачестве рабочей для этого процессора выбираем формулу из следующейэлементарной дизъюнкции, содержащую хоть одну переменную.16i3.2. Ищем среди формул в S   формулу P  a ,..., a  , имеющуюki  j1jn приоритет, равный 1, и потенциально контрарную формуле Pk  t1,..., tn  , сiiкоторой работает этот процессор. Если нашли подходящую формулу, топереходим к п.

3.3. Если ее нет, то переходим к п. 4.3.3. Решаем систему уравнений вида t  a l  1,..., n , унифицирующуюljliсписок переменных и констант со списком констант. В случае, если эта системаимеет решение, то переходим к п. 3.4. Если система решений не имеет, топонизить приоритет этого действия до 0 и переходим к п. 3.2.3.4. Записываем результаты, полученные разными процессорами, ипроверяем их на непротиворечивость следующим образом.

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

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

Если получился тупиковый F-набор, то переходим к п. 4.3.8. Если для всех процессоров приоритеты всех действий равны 0, тоформула не выводима. Алгоритм заканчивает работу.3.9. Если в F-наборе какого-либо процессора существуют формулы,имеющие переменные, которым еще не присвоено значение, то переходим к п.3.1.4. Возвратная часть алгоритма.174.1. Отменяем последнее действие п. 3.5, если это возможно, и переходим кп. 3.2.4.2. Если для какого-либо процессора отмена последнего действия п.

3.5невозможна, то алгоритм заканчивает работу.4.3. Если все процессоры закончили работу, но пустой F-набор не получен,то алгоритм заканчивает работу. Формула не выводима.В разделе 3.2 получены асимптотические оценки числа шагов работыалгоритма IAPTAТеорема 3. (Нижняя оценка числа шагов работы алгоритмаIAPTA)КоличествошаговS    x Ak x идоказательствалогическогоследованиявиданахождения значений переменных, для которых этоследование имеет место, при использовании алгоритма IAPTA, не менее 2δ(s + 2)+ 2 шагов.Теорема 4. (Верхняя оценка числа шагов работы алгоритмаIAPTA)КоличествошаговS    x Ak x идоказательствалогическогоследованиявиданахождения значений переменных, для которых этоследование имеет место, при использовании алгоритма IAPTA составляет  O l   max sk   kВ шагов.четвертойглаверассматриваетсярешениезадачивыделениямаксимальной общей подформулы с использованием алгоритма IAPTA.В разделе 4.1 приведена постановка задачи выделения максимальной общейA x  и A y , с точностью~подформулы двух заданных элементарных конъюнкцийдоимѐнпеременных,какдоказательствалогическогоследования[42] y ~A y  ,~~AAx   yA y  с нахождением такой подформулы имеет место следствиеформулычто~Ax   yA y , а также общего унификатора λ формул18A x  и A y, то есть такой подстановки имѐн переменных y  вместо некоторых~имѐн переменных из списка x , что~A yявляется подформулой A x  послеприменения унификатора λ.Если в алгоритме IAPTA заменить действие «присвоение значенийпеременным»на«отождествлениепеременных»,этоталгоритмможномодифицировать до алгоритма PHIAPTA, и применить и для решения задачивыделения максимальной общей подформулы.В разделе 4.2 приведен алгоритм PHIAPTA выделения максимальной общейподформулы двух заданных элементарных конъюнкций с точностью до имѐнпеременных.Алгоритм PHIAPTA (Partial Hatchability Inverse Ant Parallel TacticAlgorithm)1.

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

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