Выделение наибольшей общей подформулы предикатных формул для решения ряда задач искусственного интеллекта

В задачах искусственного ителлекта, в которых объект представлен как множество составляющих его элементов и характеризуется свойствами этих элементов и отношениями между ними, язык исчисления предикатов является адекватным для описания объектов и классов объектов. Так. формализованные задачи оказываются NP-полными или NP-трудными. Примером такой NP-трудной задачи является задача анализа сложного объекта, представленного как множество его элементов и описываемого набором атомарных формул с предикатами, задающими свойства этих элементов и отношения между ними. Для решения данных задач рассматривается задача выделения наибольшей общей с точностью до имен переменных подформулы двух элементарных конъюнкций атомарных предикатных формул. Выделение таких подформул позволяет свести задачу распознавания объекта к серии аналогичных задач с меньшей длиной исходных данных за счeт построения многоуровневого описания классов, существенно уменьшающего показатель степени в экспоненциальной оценке числа шагов решения NP-трудной задачи проверки принадлежности объекта этому классу. Приводится алгоритм выделения наибольшей общей с точностью до имен переменных подформулы двух элементарных конъюнкций. Доказываются оценки числа шагов его работы. Анализируется время применения его реализации в зависимости от структуры исходных данных. Анализ числа шагов работы алгоритма показывает, что предложенный алгоритм может быть успешно применен для уменьшения вычислительной сложности многих задач искусственного интеллекта, формализуемых средствами исчисления предикатов. Приводятся результаты численных экспериментов, показывающих влияние структуры исходных данных на время работы алгоритма. Так, например, при увеличении количества аргументов у предикатов значительно снижается время работы за счeт уменьшения глубины рекурсии. Также существенное влияние оказывает количество различных предикатных символов, участвующих в записи формулы. При больших исходных данных особенно заметна эффективность предложенного алгоритма, отсекающего «ветви», заведомо не приводящие к успеху. Сильное влияние на время работы алгоритма оказывает распределение переменных в качестве аргументов предикатов. Результаты показывают значительное снижение числа шагов работы алгоритма при неравномерном распределении переменных. В процессе работы описанного алгоритма возникает задача проверки совпадения с точностью до имен переменных (изоморфизма) двух элементарных конъюнкций. Решение этой задачи имеет наибольшую вычислительную сложность среди прочих шагов алгоритма. Предложен полиномиальный алгоритм проверки изоморфизма предикатных формул, правильность работы которого превышает 99,5%. Алгоритм не является абсолютно точным. Доказано, что если он даeт отрицательный ответ, то формулы не изоморфны. Если алгоритм дает положительный ответ, то результаты численных экспериментов в 99,5% случаев показали изоморфность формул. Библиогр. 14 назв. Табл. 2.