Содержание к диссертации
Введение
ГЛАВА 1. Обзор современного состояния предметной области
1.1. Постановка задач Искусственного Интеллекта при логико-предметном подходе 23
1.2. Обратный метод С.Ю. Маслова для решения задач логико-предметного распознавания образов 27
Общая схема обратного метода 28
1.3. Алгоритмы Муравья 36
1.4. Параллельные вычисления 38
1.5. Совместное применение идей муравьиных алгоритмов и параллельных вычислений 40
1.6. Понятие неполной выводимости предикатных формул 41
ГЛАВА 2. Адаптация обратного метода маслова решения задач логико-предметного распознавания образов 42
2.1. Формулировка обратного метода для решения задач логико-предметного распознавания образов 42
2.2. Алгоритм IMA (InverseMethodAlgorithm), использующий тактику обратного метода 47
Алгоритм IMA (Inverse Method Algorithm) 50
2.3. Оценка числа шагов работы алгоритма IMA 53
ГЛАВА 3. Алгоритм, основанный на применении обратного метода, муравьиных тактик и параллельных вычислений 58
3.1. Применение идей муравьиных алгоритмов и параллельных вычислений для решения задач логико-предметного распознавания образов 58
3.2. Оценка числа шагов работы алгоритма IAPTA 63
ГЛАВА 4. Выделение максимальной общей предикатной подформулы с помощью обратного метода маслова 69
4.1. Использование обратного метода для решения задачи выделения максимальной общей подформулы 69
4.2. Алгоритм PHIAPTA (PartialHatchabilityInverseAntParallelTacticAlgorithm) выделения максимальной общей подформулы 69
4.3. Оценка числа шагов работы алгоритма PHIAPTA. 74
Заключение 78
Литература 80
- Обратный метод С.Ю. Маслова для решения задач логико-предметного распознавания образов
- Алгоритм IMA (InverseMethodAlgorithm), использующий тактику обратного метода
- Оценка числа шагов работы алгоритма IAPTA
- Алгоритм PHIAPTA (PartialHatchabilityInverseAntParallelTacticAlgorithm) выделения максимальной общей подформулы
Введение к работе
Актуальность темы. Во многих задачах искусственного интеллекта исследуемый объект характеризуется не только своими глобальными признаками, задающими его свойства как единого целого, но и свойствами его частей и отношений между ними. При распознавании контурного изображения объект может быть представлен как множество его вершин и вида соединений этих вершин. В задачах диагностики объект задатся набором своих составляющих, а также зависимостями между этими элементами, позволяющими объекту функционировать.
Такой подход ещ в 70-ые годы XX века был сформулирован в литературе. Однако, в те годы, практического применения он практически не получил в силу высокой вычислительной сложности возникающих при этом задач, которые являются NP-трудными. Тем не менее, ввиду постоянно возрастающей производительности вычислительной техники, в последние 15 лет интерес к этому вопросу возрос.
При изучении алгоритмов одно из ключевых мест занимает анализ времени их работы. Первым шагом является нахождение асимптотических оценок: верхней и нижней границ работы алгоритмов.
В настоящее время для множества задач найдены только такие алгоритмы, которые перебирают экспоненциально зависящее от длины записи исходных данных количество вариантов. Такие задачи, как правило,являются NP-трудными. Ясно, что при больших размерах решаемых задач применение алгоритмов с экспоненциальной оценкой иррационально, хотя для задач небольшого объема экспоненциальные решения могут оказаться лучше полиномиальных (например, при п>100 экспоненциальная оценка 1.1" лучше, чем 10п3).
В данной работе построены и доказаны оценки числа шагов работы алгоритмов решения задач логико-предметного распознавания образов, использующих тактики обратного метода, который был предложен в середине 60ых годов советским логиком СЮ. Масловым (1932 - 1983).
Обратный метод СЮ. Маслова не является менее эффективным методом автоматического доказательства теорем, чем, например, метод резолюций.При практическом применении, как показано вдиссертации, он является даже более эффективным, но не получил широкого распространения в программировании. Одной из причин этого является сложность обратного метода в оригинальном изложении СЮ. Маслова.
В диссертации предложена конкретизация обратного метода для частного случая формул исчисления предикатов, к которым сводится решение некоторых задач искусственного интеллекта. А также разработаны алгоритмы решения задач логико-предметного распознавания образов, использующие тактики обратного метода Маслова, и доказаны оценки числа их шагов. Эффективность этих алгоритмов проиллюстрирована на примерах. Представленные алгоритмы пригодны для программной реализации.
Степень разработанности темы исследования. Термин «обратный метод» впервые введен С.Ю. Масловым в 1964 году. Автором был разработан метод установления выводимости для формул классического исчисления предикатов без равенства и функциональных символов.
Интерес к обратному методу установления выводимости появился в связи с серией работ С.Ю. Маслова и группы математической логики ЛОМИ АН СССР, опубликованных в период с 1694 по 1972 годы. В 1973 году Н. Нильсон написал книгу,посвященную методам поиска решений в пространстве состояний. В 1976 году Р. Дуда и П. Харт изложили исистематизировали методы распознавания образов и дали анализ пространственных сцен по их плоскому изображению. В
1981 году Г.Е. Минц, назвав обратный метод «резолютивными исчислениями»,
применил его к неклассическим пропозициональным логическим исчислениям. В
1982 году М. Гэри и Д. Джонсон написали книгу, посвященную вопросам
сложности решения задач.В 1985 году А.А. Воронков рассмотрел обратный метод
для классической логики без равенства. В 1989 году выходит работа В.
Лифшица в которой представлены основные идеи обратного метода в
форме, подчеркивающей его связь с методом резолюций. В 1992 году А.А.
Воронковым и А.Н. Дегтяревым были предложены метод свободных переменных
для классической логики с равенством, а также ряд критериев избыточности. В
1996 году А.А. Воронковприводит описание обратных исчислений свободных
переменных для неклассических предикатных логик. А в 1996 году Т. Таммет
предложил реализацию обратного метода для предикатной интуиционистской
логики. В 2001 году В.В. Бурлуцким была предложена реализация обратного
метода для модальной логики КТ. В 2004 году В.П. Оревков применил обратный
метод и доказал разрешимость нового хорновскогофрагмента исчисления
предикатов. В 2005 году Д.С. Ларионов разработал конкретизацию обратного
метода для автоэпистемической логики, которая применялась при построении
экспертных систем. Г.Е. Минц в 2010 году доказал разрешимость класса Е,
используя обратный метод. Кроме того, в 2010 году была предложена
реализация обратного метода с применением оператора получения
благоприятного набора. А в 2015 году В.А. Филипповским была предложена и
реализована система автоматического поиска доказательств теорем, основанная
на обратном методе, а также проведено сравнение обратного метода и метода
резолюций.
Целью диссертационной работы является научное обоснование
иразработкаалгоритмов решения задач логико-предметного распознавания образов на основе обратного метода Маслова, а также доказательство асимптотических оценок числа шагов работы этих алгоритмов. Для выполнения поставленной цели необходимо было решить следующие задачи:
1. Провести исследование обратного метода, муравьиных алгоритмов, параллельных вычислений и задачи нахождения наибольшей общей подформулы.
-
Сформулировать конкретизацию обратного метода для решения задач логико-предметного распознавания образов, допускающих формулировку средствами языка исчисления предикатов.
-
На основе сформулированного метода разработать алгоритм решения задач логико-предметного распознавания образов.
-
Модифицировать этот алгоритм, используя тактики муравьиных алгоритмов и параллельных вычислений.
-
Использовать последний алгоритм для решения задачи нахождения наибольшей общей подформулы.
6. Получить асимптотические оценки всех построенных алгоритмов.
Цели и задачи диссертационной работы соответствуют области исследований
паспорта специальности 05.13.17 – «Теоретические основы информатики»: пунктам 2 (Исследование информационных структур, разработка и анализ моделей информационных процессов и структур), 5 (Разработка и исследование моделей и алгоритмов анализа данных, обнаружения закономерностей в данных и их извлечениях разработка и исследование методов и алгоритмов анализа текста, устной речи и изображений) и 7(Разработка методов распознавания образов, фильтрации, распознавания и синтеза изображений, решающих правил. Моделирование формирования эмпирического знания).
Объектами исследования диссертационной работы являются формулы исчисления предикатов, к которым сводятся многие задачи искусственного интеллекта, и обратный метод Маслова. Предметом исследования являются разработка и реализация алгоритмов решения задач искусственного интеллекта.
Методология работы основана на методах математического моделирования, анализа и синтеза теоретического и практического материала. Для решения задач, поставленных в работе, использовались методы следующие теоретические методы: построения математических моделей сложных систем, теории сложности алгоритмов, теории распознавания образов. В практической части работы применялись методы построения и анализа алгоритмов.
Научная новизна данной работы заключается в следующем.
-
Сформулирована конкретизация обратного метода для решения задач логико-предметного распознавания образов, допускающих формулировку средствами языка исчисления предикатов.
-
Разработан алгоритм IMA решения задач логико-предметного распознавания образов, основанный на обратном методе. На основе этого алгоритма построен алгоритм IAPTA, использующий тактики муравьиных алгоритмов и параллельных вычислений. Сформулирован алгоритм PHIAPTA для решения задачи нахождения наибольшей общей подформулы. Получены асимптотические оценки всех построенных алгоритмов.
Теоретическая и практическая значимость работы. Полученные
результаты исследования применимы при разработке систем распознавания образов, объекты исследования в которых характеризуются свойствами своих элементов и отношениями между ними, вследствие чего они допускают
формализацию на языке исчисления предикатов. Разработанные алгоритмы отличаются легкостью практической реализации.
Степень достоверности и апробация результатов. Результаты
диссертационной работы были представлены и обсуждались на научных конференциях: СПИСОК-2012, Санкт-Петербург, Россия, 25-27 апреля 2012; XV Международная научная конференция «Informationtheoriesandapplications» (ITA 2012), Варна, Болгария, 18 июня-6 июля 2012; СПИСОК-2013, Санкт-Петербург, Россия, 23-26 апреля 2013; XVI Международная научная конференция «Informationtheoriesandapplications» (ITA 2013), Варна, Болгария, 29 июня-11 июля 2012, СПИСОК-2016, Санкт-Петербург, Россия, 26-29 апреля 2016.
Основные результаты диссертации были получены в рамках выполнения исследований при финансовой поддержке РФФИ (проект 14-08-01276).
Публикации результатов. По теме диссертации опубликовано 7 работ, из
них 3 статьи в научных журналах из перечня российских рецензируемых
журналов, в которых должны быть опубликованы основные научные результаты
диссертаций на соискание учных степеней доктора и кандидата наук [1, 2, 3], 2
статьи в зарубежных научных журналах на английском языке [4, 5] и тезисы 2
докладов [6, 7]. В статьях [1, 2, 4 и 5] диссертанту принадлежит построение
алгоритмов решения задач логико-предметного распознавания образов,
основанных на обратном методе Маслова и нахождение асимптотических оценок этих алгоритмов. В статье [3] диссертантом предложено применение построенных ранее алгоритмов для решения задачи нахождения наибольшей общей с точностью до имн аргументов подформулы двух элементарных конъюнкций атомарных формул.
Личный вклад автора. Результаты, представленные в диссертационной
работе, получены соискателем либо самостоятельно, либо при его
непосредственном участии.
Положения, выносимые на защиту
1. Построен алгоритм IMA поиска вывода формул, к доказательству которых
сводятся многие задачи Искусственного Интеллекта, основанный на тактиках
обратного метода Маслова. Доказаны асимптотические оценки числа шагов
работы этого алгоритма.
-
Построен алгоритм IAPTA поиска вывода формул, к доказательству которых сводятся многие задачи Искусственного Интеллекта, основанный на тактиках обратного метода Маслова, а также тактиках муравьиных алгоритмов с использованием идей параллельных вычислений. Доказаны асимптотические оценки числа шагов работы этого алгоритма.
-
Построен алгоритм PHIAPTA поиска наибольшей общей подформулы, основанный на алгоритме IAPTA. Доказаны асимптотические оценки числа шагов работы этого алгоритма.
Структура и объем диссертации. Работа состоит из введения, четырех глав,
разбитых на разделы подразделы, заключения, списка литературы и
Обратный метод С.Ю. Маслова для решения задач логико-предметного распознавания образов
Характерной чертой многих современных вычислительных систем является возможность одновременного или параллельного использования для обработки информации большого числа процессоров. Идея параллельного вычисления состоит в следующем. Есть задача, которая должна быть решена, причем достаточно быстро. Есть несколько процессоров (возможно, даже сколь угодно много), каждый из которых способен эту задачу решить, но недостаточно быстро[16], [75], [81], [91], [102]. Берем из имеющегося числа процессоров не один, а несколько, и заставляем их одновременно работать над различными частями этой задачи, надеясь получить соответствующее ускорение.
Разрабатывая систему параллельного вычисления следует разделить задачу на фрагменты, которые можно решать с использованием разных процессоров независимо друг от друга.
Существует принципиальное различие между реализацией алгоритмов на классической однопроцессорной вычислительной системе и реализацией тех же алгоритмов на параллельных вычислительных системах [16].
Оно определяется следующими обстоятельствами. Любой алгоритм описывается, в конечном счете, направленным графом, вершины которого отождествляются с выполняемыми операциями, а дуги – с информационными связями между ними. Процесс его реализации на классической однопроцессорной вычислительной системе можно трактовать как процесс последовательного исключения по одной из входных вершин графа до полного его исчерпывания. Так как такой процесс можно осуществить для любого безконтурного графа, то нет принципиальных ограничений в эффективной реализации любого алгоритма на однопроцессорной вычислительной системе.
Если вычислительная система имеет процессоров и достаточно большое, то положение изменяется радикально. Во-первых, эффективная реализация алгоритма теперь означает, что каждый раз в графе должно исключаться вершин. Но при р 1 граф алгоритма в силу своей внутренней структуры может просто не обладать возможностью допускать каждый раз исключение вершин. В этом случае, ни на одной вычислительной системе, имеющей процессоров, при реализации данного алгоритма нельзя загрузить процессоры полностью и, следовательно, нельзя достичь максимальной производительности системы.
Во-вторых, эффективной реализации алгоритма могут помешать особенности коммуникационной сети, связывающей процессоры между собой. При большом р эта сеть не может обеспечить быстрые передачи информации от каждого процессора к каждому. Поэтому ограниченные возможности быстрых связей коммуникационной сети могут также быть не согласованными со структурой связей в алгоритме. При р 1 структура памяти системы влияет на эффективность реализации алгоритма значительно сильнее, чем в случае однопроцессорной вычислительной системы.
В целом сказанное означает, что, чем выше быстродействие параллельной вычислительной системы, достигаемое за счет архитектурных решений, тем уже класс алгоритмов, которые на ней эффективно реализуются [16].
Совместная работа процессов параллельной программы осуществляется с помощью их взаимодействия. Взаимодействие программируется с применением разделяемых переменных или пересылки сообщений. Поскольку взаимодействие между процессорами требует времени, то нельзя утверждать, что если решение задачи требует время Т, то при использовании п процессоров (и тщательном распределении операций по процессорам) время составит Т/п. Как правило, эту величину следует умножить на log2(n) [20]. При редком взаимодействии между процессорами эта величина может быть существенно меньше.
Известно [87], что в муравьиных алгоритмах муравей – это программный агент, который является членом большой колонии и используется для решения какой-либо проблемы. Он снабжается набором простых правил, которые позволяют ему выбирать действие, которое он должен совершить. Муравей поддерживает список табу, т. е. список действий, которые он уже совершил или не может совершить вообще.
Настоящий муравей во время перемещения по пути будет оставлять за собой феромон. В математической модели количеству феромона соответствует числовой параметр (приоритет), приписываемый атомарным формулам [87]. В алгоритме муравья агент оставляет феромон, помечая действия, которые уже совершил, и изменяя величину числового параметра (количество феромона). Как и настоящие муравьи, агенты довольно просто устроены.Они требуют небольшое количество памяти для выполнения своих обязанностей и на каждом шаге работы выполняют несложные вычисления.
После создания популяция искусственных муравьев поровну распределяет между собой действия. Необходимо равное разделение муравьев между действиями, чтобы каждое действие имело возможность стать первым. Так как все муравьи получают индивидуальные задания и действуют независимо друг от друга, можно считать, что муравьи основывают систему параллельного вычисления и каждый из них является процессором. Тогда распределение и пересчет феромона будем считать назначением и изменением весов на ребрах графа поиска вывода, которые согласно алгоритму, будут назначать приоритет выбора действия.
Алгоритм IMA (InverseMethodAlgorithm), использующий тактику обратного метода
В главе 1 показано, что многие задачи Искусственного Интеллекта, допускающие формализацию на языке исчисления предикатов,сводятся к доказательству формулы вида (&ф))-»ЭМ(г), где А(х)- элементарная конъюнкция, множество постоянных атомарных формул.Это равносильно доказательству истинности формулы 3{хъ...,хп)ф & для любых наборов значений констант ah...,ak, где Dj(ah...,ak,xh...,xn)имеет вид
Обратный метод Маслова разработан для эффективизации процедуры построения вывода в исчислении предикатов. В диссертации представлена формулировка обратного метода для доказательства выводимости формул вида
Эта формула является частным случаем формул, для которых разработан обратный метод Маслова, описанный выше [61]. Обратный метод ориентирован на существенное сокращение перебора при доказательстве выводимости формул гораздо более общего вида, имеющих три, а не две перемены кванторов. В (2.1.1) дизъюнкты имеют вид A(«1,..., ,x1,..., )=(v («1,..., )v 7(x1,...,xjj 1 где обозначение для дизъюнкции отрицаний атомарных формул, входящих в S(aj,...,ак). В [61] этот метод сформулирован для формул вида (8 \ \/z1,...,zk3(x1,...,xn) \/y1,...,ym &Ц(21,...,2к,х1,...,хп,у1,...,ут) , (2.1.3) V=1 J частным случаем которых являются рассматриваемые в диссертации формулы. В них отсутствуют переменные под внутренним квантором всеобщности, и, соответственно, операции, связанные с этими переменными, следует опустить.
Кроме того, все значения переменных Х1,...,хп должны быть различными. Так как в (2.1.1) йк - константы, а dm отсутствуют, то условия 1 - 3 определения 1.2.6 выполняются для любого Вг(а1,...,ак,х1,...,хп), и таким образом имеем следующее определение. Определение 2.1.1. Любой список формул Г вида Ог(а1,...,аьс1,...,сп) является допустимым для формул вида (2.1.1). Определение 2.1.2. Любой список Г формул вида Ог(а1,...,аьс1,...,сп) являетсяЕ-набором для формул вида (2.1.1), если формулы в этом списке не повторяются.
Пусть u,...,up- список без повторений всех переменных, входящих в равенства системы (2ЛЛ). Систему (2ЛЛ) будем называть системой уравнений в переменныхu,.,up.Решением системы уравнений (5) будем называть всякий набор значенийконстант уъ...,уp из списка ah...,ak такой, что в результате одновременной замены всех переменных u,...,up на константы Уі,...,уp соответственно левые и правые части каждого равенства системы совпадут. Система уравнений (11 А) не имеет решений, если в списке уъ...,уp есть повторения, или если в системе уравнений (21 А) приходится сравнивать разные константы. Процедура отождествления переменных с константами Пусть Г - список формул вида Di\aъ...,ak,uъ...,up)$ - система уравнений в переменных u,...,up; - решение этой системы. Процедура отождествления переменных с константами в списке Г согласно системе S состоит в замене во всех формулах списка Г переменных u,...,up на их значения в решении .
В рассматриваемом случае процедура отождествления формул рассматриваться не будет, так как переменных d ,...,dm иc\у..,cm нет.
Далее в [61] была определена процедура преобразования списков формул в F-наборы. В рассматриваемом случае первый пункт этой процедуры не надо выполнять, так как любой список допустим. Четвертый пункт тоже, очевидно, выполнять не надо, а пятый при отсутствии четвертого дублирует второй, таким образом, процедура преобразования списков формул в F-наборы принимает вид.
Процедура преобразования списков формул в F-наборы Пусть Г - список формул вида Di(a1у..,ak,x1у..,xn). Процедура преобразования списка Г в F-набор состоит в удалении повторений формул в этом списке. В нашем случае эта процедура склейки формул в F-наборах из [61] использоваться не будет, так как не используется процедура отождествления формул. Процедура построения замкнутого F-набора Пусть в формулах Di(a1,...,ak ...,tsиDj(ab...,akvb...,vst1,...,ts переменные, ai,...,ak - константы. Обозначим первую формулу посредством А, вторую - В. Предположим, что в А входит в качестве дизъюнкции атомарная формула P t-»0, в В - отрицание формулы P(ah...,as), то есть где Р - s-местный предикат. Процедура построения замкнутого F-набора по парам формул А, P(tb...,ts) и В, - P(a1у..,as), состоит в последовательном выполнении следующих действий: 1. Применить к списку формул(А, В) процедуру отождествления переменных с константами согласно системе уравнений в переменных 2. В случае успешного завершения процедуры отождествления, применить процедуру преобразования полученного списка формул в F набор. Определение 2.1.4. F-набор будем называть замкнутым, если он может быть получен в результате применения процедуры построения замкнутого F набора к подходящим парам формул А, P(th...ts)и В, -iP(ah...,as). В нашем случае, ввиду отсутствия переменных , правило Б имеет вид, приведенный ниже. Процедура применения правила Б к F-наборам списки формул вида Ц(а1у..,ак,х1у..,хп). Если какие-нибудь два из этих наборов содержат общую переменную, переименуем е на новую переменную. Таким способом добьемся, чтобы F-наборы (2.1.5) не содержали общих переменных. Применим к списку Гі,…,Г процедуру отождествления переменных согласно системе уравнений в переменных а затем к полученному списку - процедуру преобразования списков формул в F-наборы. Построенный таким образом F-набор является результатом применения правила Б к F-наборам (2.1.5). Так как при решении системы уравнений (2.1.4) F-наборов объединяются в один, процедура применения правила Б к рассматриваемым формулам приобретает следующий вид.
Оценка числа шагов работы алгоритма IAPTA
Используя идеи муравьиных алгоритмов, создаем многопроцессорную систему, в которой действия между процессорами распределены поровну. Равное разделение действий необходимо для того, чтобы каждое действие имело возможность стать первым выполненным. Каждый процессор может выполнять следующие простые действия: 1) присвоение значения переменным; 2) замена всех вхождений переменной на е значение; 3) проверка формул на графическое совпадение; 4) отмена присвоения значения переменным; 5) отмена замены всех вхождений переменной; 6) изменение приоритета данного действия на 0.
Для начала работы алгоритма необходимо выбрать количество процессоров. Их, вообще говоря, может быть любое количество, но так как формула (3.1.1) содержит не повторяющихся дизъюнктов, то логично использовать процессоров. Именно такой выбор количества процессоров обеспечивает наибольшую эффективность работы алгоритма, представленного ниже.
Для того чтобы решить задачу логико-предметного распознавания образов следует доказать или опровергнуть выводимость формулы, т. е. предъявить набор не равных между собой значений переменных x, при котором формула выводима, или доказать отсутствие такого набора. В связи с этим можно сформулировать алгоритм IAPTA (InverseAntParallelTacticAlgorithm) решения задач логико-предметного распознавания образов, основанный на тактиках муравьиных алгоритмов, параллельного вычисления и обратного метода Маслова. При этом каждый процессор начинает итерационный цикл со своего дизъюнкта и действует согласно алгоритму IMA поиска вывода, приведенному выше.
Но при этом при каждом присвоении переменным значений процессоры связываются друг с другом и сравнивают результаты.
1. Строим -членный F-набор, формулы в котором не повторяются. То есть переписываем без конъюнкций все дизъюнкты вида v—iS((o)v Рк. \хъ...,хп. ] при г = \,...,S. Создаем популяцию из процессоров. Каждой паре потенциально контрарных формул Pk.[xi,...,xn.) и , входящих в один F-набор, назначаем приоритет их отождествления равным 1. Остальные приоритеты назначаем равными 0.
2. Копируем -членный F-набор S 1 раз. Получаем ровно одинаковых F-наборов. Назначаем г-му процессору Q = i,...,s) свою начальную формулу Рк.{хъ...,хп.) - формулу, с которой данный процессор начинает свой итерационный цикл, и потенциально контрарную ей формулу из S(G ), имеющую приоритет, равный 1. Если каким-то двум процессорам назначены формулы, начинающиеся с одного и того же предикатного символа (таких формул не более д), то назначаем для них разные формулы из потенциально контрарные данной. Если для каких-то двух процессоров не существует разных потенциально контрарных формул, то формула не выводима4. Алгоритм заканчивает работу. Иначе, переходим к п. 3.3. 3. Параллельно работают процессоров; і-й процессор Q = 1,...,s) осуществляет присвоение значений переменным. 3.1. Если в рабочей формуле данного процессора нет переменных, то в качестве рабочей для этого процессора выбираем формулу из следующей элементарной дизъюнкции, содержащую хоть одну переменную. 3.2. Ищем среди формул в S(w) формулу-.iifа,- ,...,а- \ в о \ш) формулу-/ . \aj1,...,cij і имеющую приоритет, равный 1, и потенциально контрарную формуле Pk.{t1,...,tn.), с которой работает этот процессор5. Если какие-то два процессора работают с одной и той же дизъюнкцией, ищем для них разные потенциально контрарные атомарные формулы. Если найти разные формулы не удалось, один из процессоров «засыпает» до тех пор, пока не будет отменено присвоение, приведшее к одинаковой работе двух процессоров. Если нашли подходящую формулу, то переходим к п. 3.3. Если ее нет, то переходим к п. 4.
3.3. Решаем систему уравнений вида Ц = а (/ = 1,...,«,-), унифицирующую список переменных и констант со списком констант. В случае, если эта система имеет решение, то переходим к п. 3.4. Если система решений не имеет, то понизить приоритет этого действия до 0 и переходим к п. 3.2.
3.4. Записываем результаты, полученные разными процессорами, и проверяем их на непротиворечивость следующим образом. Если процессоры одновременно присваивают одним и тем же переменным разные значения, то такие результаты считаются противоречивыми. Если результаты действий двух
4 Невозможно подобрать такой набор значений переменных, чтобы вывести пустой F-набор, так как в нем будет как минимум одна формула, в которой останутся переменные, которым будет невозможно присвоить значение. 5Первоначально t1,...,tni – список переменных из x1,..., xni . При последующих итерациях это спи переменных и констант, подставленных вместо переменных после процедуры унификации. процессоров не противоречат друг другу, то присвоение полученных значений переменных осуществляется в формулах обоих процессоров.
Алгоритм PHIAPTA (PartialHatchabilityInverseAntParallelTacticAlgorithm) выделения максимальной общей подформулы
Количество шагов выделения максимальной общей подформулы двух элементарных конъюнкций А{х) иА(у), при использовании алгоритма PHIAPTA, не менее 4 + 2s - 1 + / шагов. Доказательство. Нижняя оценка достигается в том случае, если одному из процессоров удается за один «прогон» не просто найти какую-то подформулу, а показать, что Л(у)полностью содержится в А\х), то есть является их максимальной общей подформулой.
Кроме того, нижняя оценка достигается в том случае, когда количество переменных равно наибольшему количеству аргументов в атомарной формуле и ответ получен при решении одной системы /уравнений.
На выполнение соответствующих пунктов алгоритма уходит в п. 1 - (5шагов на построение F-набора и З-яшагов на назначение приоритетов; в п. 2 - {3 - 1) шаг на копирование F-набора; 3 шагов на создание популяции процессоров;
3 шагов на назначение каждому процессору своего F-набора, своей начальной формулы с переменными; / шагов на решение системы / уравнений и Ушагов на проверку того, что получился пустой F-набор.
Теорема 4.3.2. (Верхняя оценка числа шагов работы алгоритма PHIAPTA.) Количество шагов выделения максимальной общей подформулы двух элементарных конъюнкций Aix) uAiy), при использовании алгоритма PHIAPTA, не превосходит Доказательство. В случае поиска наибольшей общей подформулы верхняя оценка будет достигнута, если А(у)не содержится полностью в А[х). Тогда каждому процессору придется перебрать все формулы из А(х) иЛ(у). Эта оценка превосходит верхнюю оценку числа шагов работы алгоритма IAPTA ровно на то количество шагов, которое требуется для хранения фрагментов и подсчета размеров этих фрагментов. На это требуется не более 23 шагов для каждого процессора на каждом шаге работы алгоритма. Итого имеем
В приложении В представлено решение следующей задачи с помощью алгоритма PHIAPTA.
Пусть имеется множество контурных изображений, составленных из отрезков прямых, задаваемых своими концами. Заданы два предиката V и L, определяемых так, как представлено на рис. 4.3.1.
Задан класс объектов 1 – класс контурных изображений «девять». Схематическое изображение эталонного объекта имеет вид, представлены на рисунке 4.3.2 (а).
Контурное изображение Рис. 4.3.2 (б). Контурное изображение «девять». «четыре». Описание класса задается следующей формулой: Al(xb...,x5)=V(xhx2,x3)&V(x2,x4,xl)&V(x2,x5,xl)& &V(x3,xhx4)&V(x4,x3,x2)&V(x4,x5,x3)&L(x4,x2,x5) Задан класс объектов 2 - класс контурных изображений «четыре». Схематическое изображение эталонного объекта имеет вид, представлено на рисунке 4.3.2 (б). Это изображение имеет описание: A2(yb...,y4)=V(yby3,y2)&V(yby4,y2)&V(y2,yby3)& &V(y3,y2,yi)&V(y3,y4,y2)&L(y3,yby4) Требуется найти максимальную общую подформулу этих двух классов. Так как при выделении максимальной общей подформулы двух заданных элементарных конъюнкций A(x) и A(y) требуется найти такую подформулу A (y ) формулы A(y), что имеет место следствие A x)=5 Зy A [y ), то первое, что необходимо сделать, чтобы решить поставленную задачу, это выбрать какую из двух формулA 1(x 1,...,x5) или A2(y 1,...,y4) взять за А{Х), а какую за А{у). Так как в полученных оценках числа шагов работы алгоритмов, основанных на обратном методе, в показателе степени стоят параметры правой части, то в качестве А(х) возьмем формулу, в которой больше атомарных формул. В нашем случае это А(хъ...,х5).
В работе получены следующие результаты: 1. Сформулирована и обоснована адаптация обратного метода Маслова для ( s доказательства выводимости формул вида 3(x1,...,xn) 8iDi{al,...,ak,xl,...,xn) доказательству выводимости которых сводятся многие задачи Искусственного Интеллекта, объекты исследования в которых характеризуются свойствами своих элементов и отношениями между этими элементами, а следовательно, допускающие формализацию средствами языка исчисления предикатов. 2. Разработан алгоритм IMA выводимости формул вида (8 3(xъ...,xn) & Di\ab...,ak,xb...,xn) основанный на разработанной адаптацииобратного метода. Доказаны асимптотические оценки числа шагов работы этого алгоритма. 3. Разработана модификацияIAPTA алгоритма IMA, использующая тактики муравьиных алгоритмов и параллельных вычислений. Доказаны асимптотические оценки числа шагов работы этого алгоритма. 4. Обоснована возможность применения обратного метода Маслова для решения задачи выведения максимальной общей подформулы. Сформулирован алгоритм PHIAPTA выделения максимальной общей с точностью до имен аргументовподформулы двух элементарных конъюнкций. Доказаны асимптотические оценки числа шагов работы этого алгоритма.
Кроме того, можно сформулировать следующие рекомендации по применению результатов работы в научных исследованиях: 1. Сформулированная конкретизация обратного метода Маслова является простым и понятным средством доказательства выводимости формул вида (8 3(x 1,...,xn) & Di\a1,...,ak,x1,...,xn) поэтому е можно применять для первоначального знакомства с обратным методом. 2. Построенные алгоритмы полностью готовы к программной реализации и могут быть применены для решения различных задач Искусственного Интеллекта в рамках логико-предметного подхода. В качестве основных перспектив дальнейшей разработки тематики можно указать построение модификаций предложенных алгоритмов для решения различных задач искусственного интеллекта, программную реализацию построенных алгоритмов, а также качественноесравнение полученного метода с существующими методами решения задач логико-предметного распознавания образов и теории выводимости, например, с методом резолюций. В результате диссертационного исследования были выполнены все поставленные задачи и достигнута цель работы.