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

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

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

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

Если все формулы помечены как удаленные значит, формула невыводима. Алгоритм заканчивает работу.На рис. 2.2.1 представлена схема работы этого алгоритма.3Отмена последнего действия пункта 2.5 невозможна, если больше нечего отменять, то есть на данном этапеработы алгоритма ни одной переменной не присвоено значение.52Рис. 2.2.1.Схема работы алгоритма IMA.532.3. Оценка числа шагов работы алгоритма IMAПусть x1,..., xn   & Di a1,..., ak , x1,..., xn  – рассматриваемая формула, где: k i 1– количество констант; n – количество переменных ( k  n , так как переменные недолжны совпадать) и элементарные дизъюнкции Di a1,..., ak , x1,..., xn  имеют вид . S a1,..., ak   Pki xОпределение 2.3.1.Однимшагомработы алгоритма называется, какприсвоение переменной значения (решение одного уравнения вида х=а), так ипроверка на графическое совпадение атомарных формул или подстановказначений переменных в атомарные формулы, имеющие вхождения данныхпеременных.Пусть l – наибольшее количество аргументов в атомарной формуле;s+1 – количество атомарных формул в каждом из дизъюнктов (так как дизъюнктыимеют структуру  S a1,..., ak   Pki x , то во всех дизъюнктах одинаковое числоатомарных формул);sk – количество вхождений в исходную формулу атомарных формул с k-мпредикатным символом;Теорема 2.3.1.

(Нижняя оценка работы алгоритма IMA)Количество шаговрешения задачи искусственного интеллекта, сведѐнной к доказательствуследствия видаS ( )  x A x при использовании алгоритма IMA, основанного на тактиках Обратного методане менее О(sl).Доказательство. Нижняя оценка достигается в том случае, когдаколичество переменных равно наибольшему количеству аргументов в атомарной54формуле и ответ получен при решении одной системы lуравнений. Но, учитываяпри этом шаги, затраченные на сортировку формул (или поиск в первой формулепервого подходящего для сравнения предикатного символа) имеем оценкупорядкаО(sl).■Теорема2.3.2.(ВерхняяоценкачислашаговработыалгоритмаIMA)Количество шагов, затрачиваемых на решение задачи искусственногоинтеллекта, сведѐнной к доказательству следствия видаS ( )  x A x при использовании алгоритма IMA, основанного на тактиках Обратного метода,а также нахождения значений для переменных, существование которыхутверждается в заключении логического следования задачи не превосходитO   max sk   l k.Доказательство.

Первым рассматриваемым F-набором является списокэлементарных дизъюнкций следующего вида: S a1,..., ak   Pk1 x1,..., xn1. S a1,..., ak   Pk x1,..., xnВерхняя оценка будет достигнута, если ответ на вопрос, выводима лиформула, будет получен на последнем шаге работы алгоритма, то есть еслипридется обойти все ветви дерева представленного на рис. 2.2.1. Уровней в этомдереве δ, так как надо присвоить значения переменным в δ формулах.55Рис.

2.2.1 Вид дерева, соответствующего поиску вывода, согласно алгоритму IMAИз верхнего узла выходит δ ребер, из узлов каждого следующего уровня –по max sk ребер, то есть на этом уровне O    max sk  1  ребер, причем,kkсогласно выбранной тактике, на этом уровне решаются системы не более чем l  уравнений, то есть имеем O    max sk  1  l  шагов. На следующем уровнеимеемkO    max sk 2  max sk  1 k  kребер, и системы l уравнений(здесьнаибольшее число решаемых уравнений тоже l, так как на каждом следующемуровне все равно может понадобиться решать систему lуравнений), то есть всегоO    max sk 2  max sk  1  l  шагов.

Продолжая этот подсчет, на нижнемk   kуровне имеем:O    max sk  1    max sk  1  l  k   k O   max sk  1    max sk1  max sk 0    O    max sk   1  l kk   k  kшагов. То есть верхняя оценка имеет видO   max sk   l k,56где δ – количество дизъюнктивных членов в исходной формуле;sk – количество вхождений в исходную формулу атомарных формул с k-мпредикатным символом;s+1 – общее число атомарных формул в каждом дизъюнкте;l – наибольшее количество аргументов в атомарных формулах.■В приложении А показано что, несмотря на то, что верхняя оценка числашагов работы алгоритмов, основанных на обратном методе, достаточно высока,на практике решение задач этим методом заметно быстрее, чем теоретическаяоценка числа шагов решения этой задачи.Пусть имеется множество контурных изображений, составленных изотрезков прямых, задаваемых своими концами.

Заданы два предиката V и L,определяемых так, как представлено на рис. 2.4.1.Рис. 2.4.1. Предикаты V и L.Задан класс объектов Ω1 – класс контурных изображений «троек».Схематическое изображение эталонного объекта имеет вид (см. рис. 2.4.2 (а)):Рис. 2.4.2 (а) Контурное изображение «тройка».Рис.

2.4.2 (б) Контурное изображение.57Описание класса «тройка» задается следующей формулой:A x1,..., x6   V  x2 , x1, x4  & V  x4 , x2 , x3  & V  x4 , x3 , x6  & V  x6 , x4 , x5  & L x4 , x2 , x6  .Пусть задано контурное изображение, представленное на рис. 2.4.2 (б), вкотором требуется найти хотя бы один объект, принадлежащий классу «троек».Это изображение имеет описание:S a1,, a6   {V a1, a2 , a3  & V a2 , a1, a4  & V a3 , a1, a4  & V a3 , a4 , a5  & La3 , a1, a5 & V a4 , a2 , a3  & V a4 , a3 , a6  & La4 , a2 , a6  & V a5 , a3 , a6  & V a6 , a4 , a5 }Оценка числа шагов решения этого примера (так как s=10, δ=5) имеетпорядок105 .Однакодля решения этого примера с помощью алгоритма IMAпотребовалось 209 шагов, был выделен объект «тройка»(см.

рис. 2.2.3).Рис. 2.2.3. Выделенный на заданном контурном изображении объект «тройка».Если расширить условие задачи до поиска всех объектов, допускающихклассификацию, то решение этой задачи потребует неоднократного примененияалгоритма к формуле. Что логически приблизит количество шагов, затрачиваемыхна решение задачи, к верхней оценке алгоритма. Но, как не трудноубедиться,проделав все необходимые операции, эта оценка будет равна 2 056шагов, что значительно меньше оценочных 100 000 шагов.58ГЛАВА 3. АЛГОРИТМ, ОСНОВАННЫЙ НА ПРИМЕНЕНИИ ОБРАТНОГОМЕТОДА, МУРАВЬИНЫХ ТАКТИК И ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙОсновные результаты этой главы изложены в следующих публикацияхавтора [67], [68], [97].3.1. Применение идей муравьиных алгоритмов и параллельных вычислений длярешения задач логико-предметного распознавания образовИспользуя идеи муравьиных алгоритмов, создаем многопроцессорнуюсистему, в которой действия между процессорами распределены поровну.

Равноеразделение действий необходимо для того, чтобы каждое действие имеловозможность стать первым выполненным. Каждый процессор может выполнятьследующие простые действия:1) присвоение значения переменным;2) замена всех вхождений переменной на еѐ значение;3) проверка формул на графическое совпадение;4) отмена присвоения значения переменным;5) отмена замены всех вхождений переменной;6) изменение приоритета данного действия на 0.Для начала работы алгоритма необходимо выбрать количество процессоров.Их, вообще говоря, может быть любое количество, но так как формулаx1,..., xn   & Di a1,..., ak , x1,..., xn  i 1(3.1.1)содержит δ не повторяющихся дизъюнктов, то логично использовать δпроцессоров.

Именно такой выбор количества процессоров обеспечиваетнаибольшую эффективность работы алгоритма, представленного ниже.Для того чтобы решить задачу логико-предметного распознавания образовследует доказать или опровергнуть выводимость формулы, т. е. предъявить наборне равных между собой значений переменных x , при котором формула выводима,или доказать отсутствие такого набора.59Всвязисэтимможносформулироватьрешения(InverseAntParallelTacticAlgorithm)алгоритмзадачIAPTAлогико-предметногораспознавания образов, основанный на тактиках муравьиных алгоритмов,параллельного вычисления и обратного метода Маслова. При этом каждыйпроцессор начинает итерационный цикл со своего дизъюнкта и действуетсогласно алгоритму IMA поиска вывода, приведенному выше.Но при этом при каждом присвоении переменным значений процессорысвязываются друг с другом и сравнивают результаты.Алгоритм IAPTA1.

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

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