Введение 4
0.1. Описание задачи
0.2. Используемый подход и методы решения . . . . . . . . . 5
0.3. Актуальность рассматриваемой задачи и другие подходы
к её решению
0.4. Реализация
1. Постановка задачи 11
1.1. Логико-предметный подход к решению задачи . . . . . . 11
1.2. Многоуровневое описание классов . . . . . . . . . . . . . 13
1.3. Неполная выводимость предикатных формул . . . . . . . 14
1.4. Самокорректирующаяся сеть . . . . . . . . . . . . . . . . 15
2. Описание решения поставленной задачи 17
2.1. Алгоритм полного перебора литералов и переменных . . 17
2.2. Алгоритм полного перебора литералов методом ветвей и
границ
2.3. Алгоритм проверки равенства предикатных формул с точностью до имен аргументов .
2.4. Оценки числа шагов работы алгоритмов . . . . . . . . . . 22
3. Сравнение и анализ результатов 26
3.1. Сравнение скорости работы алгоритмов выделения наибольшей общей подформулы . . . . . . . . . . . . . . . . 26
3.2. Анализ зависимости от структуры входных данных алгоритма перебора литералов методом ветвей и границ . . . 28
3.3. Анализ результатов времени работы самокорректирующейся сети
Заключение 34
Список литературы
Инструменты и средства математической логики [1, 2] довольно часто используются [3] при решении различных задач искусственного интеллекта. В частности, таких как распознавание образов. Примерами
подобных задач являются медицинская диагностика и выбор лечения (входными данными в этом случае являются состояние внутренних органов пациента и их текущий уровень и характер взаимодействия друг с другом), анализ рынка (входные данные представлены описанием состояния всех элементов рынка, таких как фирмы, предприятия, банки и т.п., и их относительная кооперация) или распознавание изображений (изображение и различные его характеристики являются входными данными в этом случае).
Рассматриваемые объекты часто представляют из себя множество составляющих его элементов, которые характеризуются своими свойствами и отношениями друг с другом. В этом случае удобно применение языка исчисления предикатов.
В [4] рассмотрены два подхода использующие инструменты математической логики для описания частей объектов и отношений между ними: язык логики высказываний и язык логики предикатов первого порядка. В этой работе было сказано, что язык логики высказываний может быть применен для решения вышеописанной задачи, но, т.к. логика высказываний довольно проста и не обладает достаточной выразительной мощью, то полученное описание классов объектов будет весьма громоздким (число пропозициональных переменных экспоненциально зависит от количества временных этапов, схем действий, объектов и арности произвольной схемы действий), что делает ее неприменимой для практического использования. Вместо этого используется язык предикатов первого порядка. Предикаты используются для описания свойств элементов объекта или отношения между элементами объекта. Их аргументами являются элементы объекта соответственно. Набор постоянных атомарных формул представляет собой описание объекта, точнее описанием класса объектов является дизъюнкция элементарных конъюнкций атомарных формул, истинная для объектов этого класса. При введеном описании можно решать данную задачу с помощью алгоритмов поиска логического вывода в исчислении предикатов, либо, используя алгоритмы, основанные на методе полного перебора.
Исходя из сравнительных результатов, можно сделать вывод, что для решения задач (3), (4) и (5) может быть успешна применена модель самокорректирующейся (логико-предикатной) сети. При создании описания для требуемых классов объектов эксперту в данной области стоит особое внимание обратить на структуру исходных данных. Как видно из результатов работы алгоритма полного перебора литералов методом ветвей и границ, структура данных может оказать серьезное влияние на временные характеристики работы всей сети. Так сто́ит, по возможности, использовать предикаты большей размерности при создании описаний, вводить большее количество различных предикатных символов. Также при выборе объектов в качестве аргументов для предикатов стоит учесть желательную неравномерность такого набора, например, в случае анализа рынка вполне естественна ситуация, когда некоторая часть предприятий фигурирует в гораздо большем количестве связей, по сравнению с другими.
Анализ времени работы блока распознавания показывает высокую эффективность для использования на практике, с учетом уже имеющегося многоуровнего описания классов. Тем не менее, время работы алгоритма выделения наибольшей общей подформулы имеет высокие асимптотические оценки. В дальнейшем возможно использование эвристического варианта рассматриваемого алгоритма, с вероятностной оценкой выводимости формул. Также требует дальнейшего исследования алгоритм проверки равенства формул с точностью до имен аргументов. Возможна классификация случаев ложноположительного результата работы и доработка алгоритма, исходя из полученных данных
