Московский Государственный Технический Университет

имени Н.Э.Баумана

Кафедра САПР


Искусственный интеллект в САПР

Федорук В.Г.

Введение

Возможность и эффективность применения ЭВМ для решения тех или иных задач проектирования непосредственно связаны со степенью математической формализации этих задач. Наибольший успех достигнут для тех объектов и задач проектирования, для которых найдены адекватные ММ, развиты эффективные вычислительные процедуры, доказана их разрешимость, определены ограничения. В САПР это, в первую очередь, относится к задачам анализа и параметрической оптимизации.

В то же время многие задачи проектирования (например, подавляющее большинство задач структурного синтеза) плохо поддаются автоматизации, решаются вручную, эвристически на основе опыта и интуиции разработчика. При этом качество получаемых решений определяющим образом зависит от творческих способностей человека. Такие задачи принято называть плохоформализуемыми, к ним относятся: 1) задачи, не имеющие точно выраженной математической постановки (в терминах АП - задачи, не имеющие конструктивной ММ) и/или 2) задачи, решение которых алгоритмическими методами невозможно или неэффективно. Наряду с поиском и разработкой формальных подходов к решению таких задач перспективным является использование методов и средств искусственного интеллекта.

Искусственный интеллект (ИИ) - это (применительно к проблематике АП) научная дисциплина, развивающая теорию и средства решения на ЭВМ плохоформализуемых задач на основе оперирования неформальными знаниями человека.

Кроме перечисленных выше плохоформализуемые задачи обычно обладают следующими особенностями:

Плохоформализуемые задачи - это чаще всего задачи в нечисловой форме (см. Приложение).

Работы в области ИИ ведутся по нескольким тесно связанным друг с другом направлениям: автоматическое доказательство теорем, распознавание образов и сцен, обработка естественного языка, автоматическое программирование, планирование целесообразного поведения роботов, консультирующие экспертные системы и др. Теоретические и практические результаты, достигнутые в каждом из этих разделов ИИ, находят или могут найти приложение в САПР.

В зависимости от масштабности той роли, которую призваны играть методы и средства ИИ в решении задач проектирования, условно можно выделить 3 уровня интеллектуализации САПР. На первом уровне средства ИИ используются лишь в качестве компонент отдельных подсистем САПР, где они используются для решения подзадач, решений которых формальными методами неэффективно или невозможно. Второй уровень предусматривает наличие в САПР, построенных на традиционных принципах, подсистем (проектирующих или обслуживающих), полностью организованных в соответствии с методологией ИИ. Третий уровень интеллектуальности достигается при построении САПР целиком на организационных принципах систем ИИ с использованием как формальных так и эвристических процедур проектирования.

Пример. Иллюстрацией первого уровня интеллектуальности могут служить подсистемы трассировки печатных плат, в которых 90...95% межсоединений трассируются формальными методами, а для размещения в автоматическом режиме остальных используются эвристические приемы. Ко второму уровню может быть отнесена САПР жидкостных расходомеров, в которой для выбора физических принципов действия расходомеров используется подсистема структурного синтеза, воплощающая в себе методы ИИ. К средствам построения САПР третьего уровня интеллектуальности относится мониторная подсистема INTERLOG, служащая средством интеграции независимых программных комплексов в единую САПР и основанная на идеологии ИИ.

Представление знаний

Основным объектом изучения и манипулирования в ИИ являются знания - не определяемое формально понятие, в которое обычно включается совокупность сведений, используемых человеком при решении конкретных задач. Особенностями, отличающими знания от данных являются:

Пример. В системе знаний инженера последовательность символов ТИТАН имеет однозначный смысл "конструкционный материал" (свойство интерпретируемости). Это понятие, с одной стороны, включает в себя титаны различных марок, а, с другой, само является элементом более широкого понятия "материалы, используемые в технике" (свойство структурированности). С каждым конструкционным материалом связываются такие его свойства как плотность, модуль упругости, коэффициент Пуассона и др., при этом значение модуля упругости, например, непосредственно влияет на напряжения и деформации, возникающие в конструкциях (свойство связности). Отсутствие численного значения какого-либо атрибута для конструкционного материала служит стимулом к его поиску в справочнике или проведению физического эксперимента (свойство активности).
Та же последовательность символов, выступая в качестве данного, обретает свой смысл только в контексте использующей ее процедуры и может иметь смысл "город в Мурманской области" или "название хоккейной команды".

Следует отметить, что четкой границы между данными развитой структуры и знаниями нет.

Знания об объектах и явлениях принято делить на синтаксические, семантические и прагматические. Первые описывают структуру объектов и явлений, вторые - информацию, связанную с их значением и их смыслом, а третьи описывают объекты и явления с точки зрения решаемой задачи.

Пример. Синтаксические знания об электронном усилителе включают в себя сведения о возможных структурных схемах таких усилителей, состоящих из каскадов различных типов, объединенных разнообразными связями. Семантические знания - это знания о назначениях отдельных каскадов (согласование по входу - выходу, предварительное усиление, поворот фазы сигнала и т.п.) и принципах их функционирования. В прагматические знания разработчика усилителей входят знания, позволяющие по ТЗ выбрать структурную схему усилителя и принципиальные электрические схемы отдельных каскадов, рассчитать значения внутренних параметров и т.п. Прагматические знания наладчика усилителя состоят из знаний о способах поиска и устранения неисправностей.

Центральное место в системах ИИ любого назначения занимает база знаний (БЗ) - вместилище всей совокупности знаний, относящихся к решаемой задаче. Важной проблемой при создании БЗ является выбор наиболее адекватного с точки зрения указанных выше особенностей способа представления знаний. Различают декларативную и процедурную формы представлений знаний. Форма представления знаний совокупностью программ называется процедурной. Представление знаний в виде набора утверждений об объектах предметной области и отношениях между ними называется декларативным. При использовании этой формы представления в системах ИИ подразумевается, что их интеллектуальность достигается за счет наличия небольшого числа универсальных процедур работы со знаниями, а их специализация на конкретную предметную область обеспечивается наполнением утверждениями, характеризующими эту область. Этим достигается независимость друг от друга предметных знании и знаний о методах решения задач, что гарантирует их гибкость и легкую модифицируемость. Однако, для некоторых понятий использование декларативного представления невозможно или неэкономично. В связи о этим на практике чаще всего используют смешанные представления, сочетающие в себе оба подхода.

Важными с т.з. представления являются понятия экстенсионал и интенсионал знаний. Под экстенсионалом некоторого понятия подразумевается множество конкретных фактов, соответствующих данному понятию. Интенсионал определяется как правило, либо порождающее множество фактов, составляющих экстенсионал, либо проверяющее принадлежность некоторого факта к экстенсионалу.

Пример. Экстенсионалом понятия "числа Фибоначчи" является бесконечное множество целых чисел 1,1,2,3,5,8,... , интенсионалом - следующее правило порождения:
С1=1, С2=1, Сkk-1k-2 для k = 3,4.... .

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

В соответствии с указанными двумя способами представления знаний в БЗ выделяют две части - интенсиональную и экстенсиональную, реализуемую как база данных. Для представления знаний в БЗ используются формализмы, носящие название моделей представления знаний, и соответствующий инструмент - языки представления знаний.

Примечание. Модели и языки представления знаний можно рассматривать как результат эволюционного развития и усложнения моделей данных и языков их описания и манипулирования.

Используемые в настоящее время модели представления знаний условно классифицируют на 3 типа: логические, сетевые модели и продукционные системы (см. рис. 1). К первым относят обычно исчисление предикатов первого порядка и формальные продукционные системы, ко вторым - семантические сети и фреймовые модели. Однако, как правило, возможности указанных моделей каждой в отдельности оказываются недостаточными для представления всей необходимой совокупности знаний, поэтому в реальных системах ИИ используются комбинированные представления - чаще всего логические и сетевые модели встраиваются в продукционные системы.


Рис. 1. Классификация моделей представления знаний

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

Пример. Пусть необходимо представить знания о чрезвычайно упрощенной предметной области "проектирование башен". Башня представляет собой сооружение из крыши и поддерживающего ее ствола. Крыша может быть призматической высотой 4 м или плоской высотой 1 м. Ствол башни может состоять из 1, 2 или 3 блоков одинаковой формы. Цилиндрические блоки имеют высоту 5 м и 3 м, а блоки в виде параллелепипеда - 4 м и 2 м. Все башни в нашей предметной области должны иметь громоотвод и сигнальный маяк на крыше.
Основной задачей, решаемой в этой предметной области, является создание проекта башни заданной высоты.

Семантические сети (СС)

В основе моделей представления знаний этого типа лежит сеть (ориентированный граф), вершины которого соответствуют понятиям предметной области, а дуги - отношениям между парами понятий. Отметим, что в отличие от ИППП все отношения предметной области здесь должны быть приведены к бинарным.


Рис. 2. Пример эктенсиональной семантической сети

Пример. На рис. 2. представлен фрагмент СС, описывающей башню из нашего примера, состоящую из крыши призматической формы и ствола из двух цилиндрических блоков высотой по 3 и 5. Дуги, помеченные символами ISA, соответствуют отношению "быть элементом множества" (is a - быть одним из), а дуги, помеченные AKO - отношению "быть подмножеством" (a kind of).

В зависимости от характера (типа) отношений, приписываемых дугам, различают три типа сетей: функциональные сети, сценарии и собственно СС.

Функциональная сеть представляет собой двудольный граф, все множество вершин которого распадается на два непересекающихся подмножества, таких, что в любом из этих подмножеств нет двух вершин, соединенных дугой. В функциональных сетях вершины одного из подмножеств трактуются, обычно, как процедуры (функции), а вершины другого подмножества - как аргументы и результаты этих процедур. Основной задачей на сетях этого типа является задача определения последовательности выполнения процедур, обеспечивающей достижение требуемых результатов по заданному набору аргументов. Математически эта задача формулируется как задача назначения ориентации дугам от вершин-аргументов к вершинам-результатам, через необходимое число допустимых вершин-процедур.

Сценарии представляют собой однородные сети, дуги которых моделируют отношения нестрогого порядка (временные, причинно-следственные, родовидовые и т.п.).

В собственно СС не фиксируются строго ни типы вершин, ни дуг, т.е., как это видно из примера, вершины СС могут иметь различные интерпретации, а дуги - соответствовать отношениям различных типов. СС принято делить на простые и иерархические.

СС, представленная в примере, относится к простым. В иерархических СС вершины могут иметь собственную сложную структуру, представляемую, в свою очередь, семантической сетью, называемой в данном случае подсетью (пространством). В иерархических СС между пространствами устанавливается отношение видимости - как правило, из пространств более высокого иерархического уровня информация, содержащаяся в пространствах, лежащих ниже, недоступна (невидима). Введение иерархии на СС позволяет декомпозировать решаемые задачи на подзадачи и тем самым бороться с их сложностью.

Пример. СС, содержащая знания об электронном усилителе, может иметь два уровня иерархии. На верхнем в качестве базовых вершин будут выступать вершины, соответствующие отдельным каскадам усилителя, на нижнем каждый каскад может быть раскрыт сетью, описывающей, в частности, принципиальную электрическую схему этого каскада.

Рассмотренная в примере с башней СС носит название экстенсиональной (ЭСС), поскольку описывает факты о башне конкретной конструкции. Знания же об абстрактной башне (т.е. о всех возможных конструкциях башен в нашем примере) представляются в интенсионалной СС (ИСС), как это показано на рис 3, через общие понятия и отношения между ними. СС рассмотренных двух типов составляют соответственно экстенсиональную и интенсиональную части БЗ.


Рис. 3. Пример интенсиональной семантической сети

Отношения предметной области, явно представленные в СС, носят название базовых. Кроме них в СС используются так называемые виртуальные отношения, включаемые в интенсиональную часть БЗ на основе СС. Виртуальными отношениями обычно являются дополнительные средства, позволяющие по мере надобности конструировать необходимые факты. Эти отношения реализуются:

  1. в виде процедур, вычисляющих значение функций или предикатов (ИССС рис. 3 содержит явные ссылки на одну из таких процедур - процедуру вычисления высот, высота ствола и башни в ЭСС рис. 2 рассчитаны с привлечением именно этой процедуры);
  2. путем использования свойств симметричности, рефлексивности, транзитивности базовых отношений (например, транзитивность отношения "находится - на" позволяет из фактов "крыша находится на стволе", "ствол состоит из блока-1 и блока-2", "блок-1 находится на блоке-2" вывести новый факт "крыша находится на блоке-2");
  3. в виде правил продукционных систем, как это будет рассмотрено ниже.

Основными режимами в функционировании БЗ на основе СС являются её пополнение и информационно-поисковый. Расширение экстенсиональной части БЗ реализуется на основе сведений, заключенных в ИСС, с широким привлечением виртуальных отношений. Так ЭСС рис. 2 могла быть сгенерирована из ИСС рис. 3 по запросу пользователя, содержащему сведения ТЗ на башню. При этом направленный перебор вариантов конструкций, расчет ее параметров реализуется виртуальными отношениями и встроенными механизмами БЗ.

В организации информационно-поискового режима важную роль играют ISA- и АКО-отношения, выражающие таксономию понятий и позволяющие сосредоточить информацию, одинаковую для всех без исключения элементов некоторого множества в вершине, соответствующей понятию-множеству, а не во многих вершинах-элементах. При обращении за этой информацией к вершине-элементу встроенный механизм наследования передаст ее от вершины-множества. Так, при обращении с запросом в ЭСС рис. 2 о том, какие конструктивные элементы имеет спроектированная башня-1, будет получен ответ "громоотвод и сигнальный маяк", поскольку их должны иметь все башни в нашей предметной области.

Наличие в СС явных ассоциативных связей между понятиями (выраженных в виде ISA - и АКО-отношений) составляет основное достоинство СС как модели представления знаний, однако наиболее полно это достоинство проявляется при использовании СС совместно с продукционными системами.

Фреймовые модели представления знаний

Их можно рассматривать как специальную разновидность СС, используемую для представления хорошо структурированных предметных областей, т.е. областей с четко выделенной понятийной структурой. В качестве вершин таких сетей используется агрегат, представляющий собой по возможности наиболее полное формализованное описание понятий (или, как говорят, "стереотипной ситуации"). Такой агрегат называется фреймом.

В простом случае фрейм может быть представлен в виде следующей конструкции:

имя_фрейма:ISA-_или_АКО-ссылка
         (описание_слота#1;
                 .     .     .
          описание_слота#N) .
Здесь слот является основной единицей информации и идентифицирует структурные элементы понятия.

Слот в свою очередь состоит из ряда ячеек и имеет следующую структуру:

имя_слота(ЗНАЧЕНИЕ:значение_слота;
          ТИП:тип_значения_слота;
          УМОЛЧАНИЕ:значение_по_умолчанию;
          ДЕМОНЫ:имена_процедур-демонов;
          СЛУГИ:имена_процедур-слуг)

Обязательными в структуре слота являются только ячейки ЗНАЧЕНИЕ и ТИП, обеспечивающие интерпретируемость и структурированность в представлении знаний. Фрейм, все слоты которые характеризуются только значением и типом, полностью аналогичен структуре (struct) языка C. Для адресации к структурным единицам фрейма используется конкатенация символов имя_фрейма.имя_слота.имя_ячейки. Для отображения во фреймовом представлении свойств связности и активности знаний служат три последние ячейки слота. Ячейка УМОЛЧАНИЕ содержит стандартное ("стереотипное", предполагаемое, ожидаемое) значение слота, что дает возможность манипулировать фреймами в недоопределенных ситуациях, когда отсутствует конкретная информация о целом ряде аспектов объекта или явления. С помощью ячеек ДЕМОНЫ и СЛУГИ задаются имена присоединенных к фрейму процедур.

Присоединенные процедуры в зависимости от способа вызова делятся на две группы. Процедуры-демоны включаются в работу автоматически (без явного на то указания) при выполнении некоторого условия. Чаще всего таким условием является изменение значения слота, в этом случае процедура-демон может проверить допустимость нового значения (например, не противоречит ли оно уже имеющимся сведениям в других слотах фрейма) или осуществить корректировку в других слотах информации, связанной со значением данного слота и т.п.

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

Интенсиональную часть фреймовых БЗ составляют фреймы-прототипы с присоединенными к ним процедурами, при этом, как правило, фреймы объединяются в сеть с помощью слотов типа ссылка согласно отношениям, существующим между реализуемыми фреймами понятиями, и ISA- и АКО-связей. Фрейм - прототип представляет собой готовую структуру, которая при том или ином заполнении слотов значениями превращается в описание конкретного факта.

Пример. Фрагмент интенсиональной части БЗ на основе фреймов для рассматриваемого нами примера с башней может иметь следующий вид:

башни: сооружения
   (крыша
       (ЗНАЧЕНИЕ: крыши;
        ТИП: ссылка);

    ствол
       (ЗНАЧЕНИЕ: стволы;
        ТИП: ссылка;
        СЛУГИ: расч_кол_бл);

    высота 
       (ЗНАЧЕНИЕ: <>; 
        ТИП: положит. действ. число;
        ДЕМОНЫ: расч_высоты);

    имеет
       (ЗНАЧЕНИЕ: громоотвод, маяк;
        ТИП: текст);

    цвет
       (ЗНАЧЕНИЕ: <>;
        ТИП: множество {красный, . . . , фиолетовый};
        УМОЛЧАНИЕ: желтый) )

Здесь в виде фрейма представлено понятие "абстрактная башня" (иначе, все башни в нашей предметной области). Понятие "башня" выступает в качестве подмножества по отношению к понятию "строительные сооружения", на что указывает АКО-ссылка на фрейм сооружения. Слоты крыша и ствол имеют тип ссылки, т.е. их значениями выступают ссылки на другие фреймы-прототипы. Процедура-слуга расч_кол_бл при явном запросе к ней может после заполнения значения слота выдать в качестве результата своей работы количество блоков ствола башни. Для этого ей потребуется перейти по ссылке к фрейму ствола. Процедура-демон расч_высоты в слоте высота обеспечивает расчет значения высоты башни при условии: а) есть обращение к ячейке ЗНАЧЕНИЕ этого слота и б) она пуста. Заполненность значения слота имеет указывает на то, что его значение присуще всем без исключения башням.

Экстенсиональную часть БЗ составляет сеть фреймов-примеров (конкретных фреймов), создаваемая путем полной или частичной конкретизации фреймов-прототипов значениями слотов (необязательной является конкретизация слотов, имеющих значения "по умолчанию").

Пример. Сгенерированный на основе фрейма-прототипа башни конкретный фрейм башня_1 может быть представлен в экстенсиональной части БЗ следующим образом:

башня_1: башни
   (крыша
       (ЗНАЧЕНИЕ: крыша_1;
        ТИП: ссылка);

    ствол
       (ЗНАЧЕНИЕ: ствол_1;
        ТИП: ссылка) ;

    высота
       (ЗНАЧЕНИЕ: 12;
	ТИП: положит. действ. число;
	ДЕМОНЫ: расч_высоты);

    цвет
       (ЗНАЧЕНИЕ: <>;
	ТИП: множество {красный, ..., фиолетовый};
	УМОЛЧАНИЕ: желтый) )

В этом фрейме установлена ISA-ссылка на фрейм-прототип башни и отсутствует слот имеет. Второе обстоятельство обусловлено тем, что содержимое этого слота одинаково для всех фреймов-примеров башен в нашей предметной области и поэтому он в фрейм-пример не копируется. При запросе к слоту имеет фрейма башня_1 будет автоматически включен встроенный механизм наследования понятий, который осуществит навигацию вверх по ISA- и АКО-связям и доставит необходимое значение слота.

Для реализации присоединенных процедур и организации вычислений на фреймах в основном используются следующие три подхода:

  1. пользователь сам пишет соответствующие процедуры на каком-либо языке программирования, используя базовый набор подпрограмм доступа к ячейкам фреймов;
  2. выделяется ограниченный набор допустимых фреймов, для которых однократно создаются специфические процедуры (такой подход возможен только для БЗ узкой ориентации);
  3. включение в интенсиональную часть БЗ наряду с предметными "вычислительных" фреймов, реализующих, например, алгебраические операции (фрейм-сложение, фрейм-вычитание и т.п.) или вычисление значений предикатов (фрейм-И, фрейм-ИЛИ, кванторные фреймы и др.).
В последнем случае, например, присоединенная процедура может быть представлена как сценарий из вычислительных фреймов.

Основной операцией на фреймах является операция поиска по образцу. Образец представляет собой отдельный фрейм, в котором конкретизированы не все, а лишь некоторые значения слотов. В задачу поиска входит обнаружение в БЗ фрейма (или фреймов) с совладающими значениями слотов и возврат значений для неконкретизированных слотов фрейма-образца. В более сложных вариантах может ставиться задача поиска подсети фреймов или поиска при наложенных ограничениях на значения слотов.

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

Примечание. Необходимо отметить, что сам термин "фрейм" (frame - рамка) и соответствующая формализация были введены специалистами в области ИИ, однако подразумеваемая под этим термином концепция широко использовалась задолго до этого в программировании, где она получила название абстрактного типа данных.

Продукционные системы (ПС)

Под ПС будем понимать систему <W, P, I>, состоящую из трех компонент, где W - рабочая память, содержащая информацию, характеризующую текущее состояние предметной области, P -множество продукций вида ЕСЛИ условие, ТО следствие, применимых к W; I - интерпретатор (решатель), управляющий применением продукций. Общая постановка задач при использовании ПС - даны начальное W0 и конечное Wk состояния рабочей памяти, необходимо найти путь (пути) из W0 в Wk, реализуемый последовательностью применения продукций из P.

Рабочая память W в простейшем варианте представляет собой информационную структуру, описывающую факты предметной области и организованную наиболее удобным для этого способом (здесь можно использовать любые структуры данных, известные в программировании). W в таком виде представляет собой экстенсиональную часть БЗ, используемой в ПС. В сложных предметных областях W реализуется на основе рассмотренных выше моделей знаний, при этом чаще всего используются фреймовое представление и СС.

Множество продукций P составляет основу интенсиональной части БЗ. Основное достоинство ПС как раз состоит в том, что с помощью продукций наиболее адекватно отражаются механизмы принятия решений человеком, основанные, как показывают результаты психологических исследований, на правилах типа "причина-следствие", "посылка-заключение", "условие-действие". Левая часть продукции (ЕСЛИ ...) представляет собой заданное в декларативной форме условие ее применимости, выраженное в виде объединенных связками И, ИЛИ, НЕ требований к элементам W. Оценка условий применимости продукций осуществляется интерпретатором. Правая часть продукции (ТО...) может иметь декларативную или процедурную форму и задает изменения, которые необходимо выполнить в случае истинности условия в левой части. Если правая часть продукции задана в декларативной форме, то предписываемые ею изменения в W (удаление, модификация, добавление элементов) реализуются интерпретатором. В альтернативной форме правой части подразумевается наличие ассоциированной с продукцией процедуры, непосредственно выполняющей в W все необходимые изменения. В ПС, W которых организуется с использованием представлений на основе фреймов или СС, целесообразным является представление и самих продукций в рамках этих формализмов (в виде специальных фреймов-продукций и фрагментов СС) - этим достигается единообразие в организации компонентов ПС.

Примечание. Структуры ЕСЛИ..., ТО..., обе части которых реализуются процедурно, называются модулями, управляемыми образцами. ПС, рабочая память которых организована в виде линейной последовательности символов некоторого алфавита, а продукции задают правила преобразования (подстановки) этих последовательностей, называются формальными ПС.

Задачей интерпретатора в ПС является построение цепочки продукций (вывода), переводящих W из начального в конечное состояниt, при этом на вывод могут накладываться различные ограничения, такие, например, как минимизация его длины или требуемых ресурсов. Алгоритм работы интерпретатора может быть представлен последовательностью следующих шагов:

  1. сопоставление левых частей продукций (всех или только активного их подмножества) с текущим состоянием W (всей или только активной ее части);
  2. разрешение возможного конфликта путем выбора из набора применимых в текущий момент продукций только одной (наиболее "полезной" с т. з. решаемой задачи);
  3. реализация (непосредственно интерпретатором или через вызов процедуры) всех изменений в W, предписанных правой частью продукции;
  4. проверка условий достижимости конечного состояния W.

Пример. ПС для рассматриваемой нами предметной области с башнями может быть реализована следующим образом.
Поскольку предметная область проста, то W можно реализовать в виде линейного списка троек (объект атрибут значение). Начальное состояние W в такой форме показано ниже:
	(крыша форма призма)
	(крыша форма плоск.)
	(призма высота 4)
	(плоск. высота 1)
	(блок форма цилиндр)
	(блок форма паралл.)
	(цилиндр высота 5)
	(цилиндр высота 3)
	(паралл. высота 4)
	(паралл. высота 2)
Целью использования ПС в этом примере пусть будет проектирование башни любой высоты, тогда конечное состояние W должно содержать тройку (башня высота X), где Х - обозначение переменной (т. е. высота проектируемой башни в данном случае для нас безразлична).
В число необходимых продукций будут входить следующие (прописными латинскими буквами обозначены переменные, принимающие конкретные значения в результате сопоставления):
ЕСЛИ НЕ (ствол X Y) И (блок форма F) И (F высота H),
	ТО ДОБАВИТЬ [(ствол кол_бл. 1), (ствол высота H)]
ЕСЛИ НЕ (ствол X Y) И (блок форма F) И (F высота H1) И (F высота H2),
	ТО ДОБАВИТЬ [(ствол кол_бл. 2), (ствол высота H1+H2)]
ЕСЛИ НЕ (башня X Y) И (крыша форма F) И (F высота H1) И (ствол  высота H2),
	ТО ДОБАВИТЬ (башня высота H1+H2)
Представленные продукции для простейшей безвозвратной стратегии работы интерпретатора с выбором первой подходящей продукции не могут быть использованы для проектирования башни заданной высоты. Для того чтобы достичь такой возможности, необходимо расширить набор продукций, включив в них удаление из W троек, или использовать интерпретатор с более сложным механизмом управления.

Достоинства ПС как модели представления знаний составляют:

  1. модульность знаний, заключенных в продукциях, что обеспечивает широкие возможности их независимой модификации;
  2. высокая степень декларативности, что освобождает от необходимости программирования процедур обработки;
  3. асинхронность, недетерминизм, параллельность в применении продукций.
Недостатками являются:
  1. относительно низкая эффективность, связанная с необходимостью сопоставления левых частей большого количества продукций с объемной W (в реальных ПС на это расходуется 90-98% времени);
  2. сложность контроля правильности функционирования.

Все рассмотренные выше модели представления знаний имеют приблизительно одинаковую универсальность. Выбор наиболее подходящей модели определяется лишь удобством перехода от неформальных знаний той или иной предметной области к их формальному представлению в рамках модели. Для задач проектирования в технике предпочтительным является сочетание ПС с фреймовыми моделями, что связано с наличием в научных и технических знаниях четко выделенной и математизированной понятийной структуры.

Интерпретатор в ПС

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

  1. направление поиска;
  2. режим использования продукций;
  3. способ разрешения конфликтов между продукциями;
  4. метод поиска.

В зависимости от направления, в котором используются продукции интерпретатором, различают прямой (иначе говорят поиск от данных), обратный (или поиск от цели) и комбинированный поиск. При прямом поиске интерпретатор оценивает на рабочей памяти условие, содержащееся в левой части продукции, и осуществляет изменения, предписанные ее правой частью. Этот вид поиска рассмотрен в предыдущем параграфе. При обратном поиске интерпретатор пытается построить цепочку вывода от цели (от конечного состояния рабочей памяти), для этого он подыскивает продукцию, правая часть которой совпадает с целью, и проверяет, удовлетворяется ли на начальном состоянии рабочей памяти ее левая часть. Если да, то поиск решения считается завершенным, если нет, то условие левой части продукции рассматривается как новая цель, которую необходимо вывести, используя продукции в обратном направлении. Комбинированный поиск подразумевает построение цепочки вывода одновременно с двух сторон. Выбор направления поиска при реализации интерпретатора определяется спецификой предметной области и решаемых в ней задач.

Интерпретатор ПС может реализовывать два режима обработки продукций: безвозвратный и пробный. В безвозвратном режиме связанные с применением продукции изменения рабочей памяти происходят необратимо, т.е. в интерпретаторе отсутствуют средства, позволяющие вернуть рабочую память в состояние, предшествующее применению продукции. Данный режим применим на практике, если только интерпретатор располагает информацией, позволяющей обоснованно выбрать продукцию (причем эта информация должна иметь локальный характер, а не глобальный - иначе цепочка вывода, а с ней и само решение, будет известна заранее). Безвозвратный режим возможен также в случаях, когда применение какой-либо одной продукции не исключает затем применения остальных.

В пробном режиме интерпретатор имеет возможность испытать продукцию из конфликтного набора (т.е. набора продукций, применяемых на текущем шаге работы) и в случае неудачи в выводе вернуться к текущей ситуации. Здесь различают режим с возвращением и режим поиска на графе. В первом при построении цепочки вывода устанавливаются точки возврата, к которым может возвращаться интерпретатор при возникновении трудностей в нахождении решения. При этом восстанавливается состояние рабочей памяти, соответствующее точке возврата, а вся информация о более поздних изменениях теряется. При поиске на графе также предусмотрен возврат для испытания иных применимых продукций, однако вся информация о проделанной работе сохраняется, что дает возможность интерпретатору отслеживать одновременно несколько конкурирующих линий вывода. Реализация пробных режимов работы интерпретатора требует существенного его усложнения, в частности, включения в его состав специальной памяти состояний для хранения протоколов его работы.

Примечание. Примеры работы продукционных систем в безвозвратном режиме и режиме с возвращением будут даны в следующем параграфе.

Решающее влияние на эффективность поиска решения в ПС оказывают процедуры разрешения конфликтов среди продукций, применимых к рабочей памяти в текущем цикле работы интерпретатора. Для выбора единственной продукции из конфликтного набора используются процедуры универсального характера, дополненные эвристиками предметной области. Для управления разрешением конфликтов в универсальных процедурах используются

  1. упорядочение продукций,
  2. упорядочение данных в рабочей памяти,
  3. специальные случаи условий продукций,
  4. информация о предыстории применения продукций.

В первом случае эксперт при заполнении БЗ должен, исходя из относительной "полезности" каждой продукции, приписать ей приоритет или связать ее отношением предпочтительности с рядом других продукций. Тогда при разрешении конфликта выбирается продукция из набора, имеющая высший приоритет или наиболее предпочтительная по отношению к другим. В подходе, основанном на упорядочивании данных, как правило, выбирается к исполнению продукция, условие которой удовлетворяется на наиболее "молодых" элементах рабочей памяти. В процедурах специального случая предпочтение обычно отдается продукциям с наиболее "жестким" условием. Процедуры, использующие информацию о предыстории работы интерпретатора, требуют от эксперта определения отношения порядка над подмножествами продукций (например, в виде сети предшествования).

Режим работы интерпретатора в совокупности с процедурами разрешения конфликта составляет стратегию управления. Стратегии управления, в которых информация о предпочтительности продукций из конфликтного набора не доступна (не используется), носят название неинформированных.

Методы поиска решений в ПС

Задачу построения цепочки вывода в ПС принято трактовать как задачу поиска в пространстве, элементами которого являются все возможные состояния рабочей памяти. Объектом поиска является последовательность продукций, определяющая путь из начального в конечное (целевое) состояния.

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

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

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

Алгоритм этого вида поиска для нахождения одного какого-либо решения кратко может быть представлен в следующем виде:

  1. поместить в очередь корневую (начальную) вершину;
  2. выбрать из очереди вершину и раскрыть ее (если очередь пуста, то целевая вершина недостижима);
  3. если среди дочерних вершин есть целевая, то конец;
  4. поместить список дочерних вершин в конец очереди и перейти к п. 2.

Алгоритм поиска в глубину выбирает вершины для раскрытия в порядке, обратном их порождению:

  1. поместить в стек корневую (начальную) вершину;
  2. выбрать из стека первую вершину и раскрыть ее (если стек пуст, то целевая вершина недостижима);
  3. если в списке дочерних вершин есть целевая, то конец;
  4. список дочерних вершин поместить в стек и перейти к п. 2.

Пример. Рассмотрим простую формальную продукционную систему, начальное состояние рабочей памяти которой обозначим А, а конечное - Р. Множество продукций составляют следующие:

Р1: А->ВР7: D->HP13: F->N
P2: A->CP8: D->IP14: G->O
P3: A->DP9: E->JP15: G->P
P4: B->EP10: E->KP16: H->Q
P5: B->FP11: E->LP17: I->R
P6: C->GP12: F->MP18: I->S
Где прописные латинские буквы A...S обозначают состояние рабочей памяти в целом, а не отдельных ее элементов. Запись вида x->y есть сокращение формулы ЕСЛИ x, ТО y.

Дерево поиска для рассматриваемой системы продукций приведено на рисунке, его вершины помечены состояниями рабочей памяти, а дуги - имена продукций. Метод поиска в ширину осуществляет раскрытие вершин по ярусам сверху-вниз, а внутри яруса - слева-направо (в нашем примере в "алфавитном" порядке от А до Р). Последовательность применения продукций для порождения дочерних состояний соответствует порядку их нумерации - от Р1 до Р18.

Порядок раскрытия вершин методом поиска в глубину таков: A, B, E, J, K, L, F, M, N, C, G, O, P, а последовательность применения продукций - Р1, Р2, Р3, Р4, Р5, Р9, Р10, Р11, Р12, Р13, Р6, Р14, Р15.

В рассмотренном примере дерево имеет конечный размер, что гарантирует окончание поиска любым методом за конечное время. Однако в реальных задачах дерево поиска, как правило, бесконечно, в связи с чем приходится искусственно ограничивать глубину поиска некоторым числом ярусов. Для задач, требующих поиска всех возможных решений (отыскание всех целевых вершин дерева) оба метода требуют одинаковых временных затрат, однако затраты памяти для метода поиска в глубину могут быть значительно ниже, поскольку он допускает работу интерпретатора в режиме с возвращением.

Для методов поиска в глубину и ширину характерен экспоненциальный рост затрат времени от числа ярусов дерева поиска, что неизбежно ведет к проблеме комбинаторного взрыва, накладывающей жесткие ограничения на глубину поиска и, следовательно, на допустимую длину цепочек вывода. Одним из возможных путей преодоления этого затруднения является, как уже указывалось, использование информированных стратегий управления, осуществляющих выбор малого количества "перспективных" продукций из конфликтного набора и тем самым сужающих дерево поиска, "фокусируя" его в направлении целевой вершины. В некоторых задачах для выбора направления поиска удается построить оценочную функцию, косвенным образом в числовой форме характеризующую расстояние от текущей вершины до целевой. Подобные методы поиска, использующие сведения о специфике предметной области, называются эвристическими, а совокупность знаний о методах решения задач той или иной предметной области составляют метазнания ПС, т.е. знания более высокого уровня, чем предметные.

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

Методы решения сложных задач

Сложные задачи поиска решения характеризуются, в первую очередь, большим размером пространства состояний, что ограничивает использование для них рассмотренных выше методов. Проблема размерности решается, как правило, путем

Одним из методов разбиения пространства является метод сведения задач к подзадачам. Чтобы пояснить его суть, вернемся к примеру с башнями.

Пример. Используем систему продукций для конструирования башни, представленную в конце предыдущего параграфа, в обратном направлении (от цели). На рис. 4 упрощенно представлен фрагмент дерева поиска для этой задачи, здесь вершины помечены именами объектов, фигурирующих в продукциях, меняющих состояние рабочей памяти, а ветви - именами самих этих продукций.


Рис. 4. Пример И/ИЛИ-дерева

В дереве поиска выделены вершины двух типов: вершины типа И (исходящие из них ветви на рис. объединены дугой) и вершины типа ИЛИ (это все остальные вершины). Различие между ними заключается в том, что для достижения цели, заключенной в вершине типа И, обязательным условием является удовлетворение всех ее подцелей, заключенных в ее дочерних вершинах, в то время как для достижения цели в вершине ИЛИ достаточно удовлетворить любую из подцелей. В нашем примере вершина башня является вершиной типа И, поскольку для получения проекта башни необходимо спроектировать ее крышу и ствол. А вершина крыша - это вершина типа ИЛИ, т.к. в нашей предметной области крыша может быть призматической или плоской соответствующей высоты. Дерево поиска, включающее в себя только вершины типа И и типа ИЛИ, называется И/ИЛИ-деревом.

Примечание. Дерево поиска на представленном выше рисунке является И/ИЛИ-деревом, для приведения его к этому виду в него дополнительно были введены фиктивные вершины ствол_1, ствол_2 и ствол_3.

Наличие в дереве поиска вершин типа И обеспечивает декомпозицию задачи поиска решения на ряд подзадач (по количеству дочерних вершин), каждая из которых в некоторых случаях может решаться независимо. Во многих ситуациях это ведет к уменьшению перебора, т.к. каждая подзадача решается не на всем пространстве состояний, а только на ограниченном его подпространстве. Для решения подзадач могут использоваться любые из рассмотренных выше методов поиска.

Для рассматриваемого примера, в частности, и для задач структурного синтеза, в общем, характерно взаимодействие подзадач, которое проявляется в том, что результат решения одной подзадачи влияет на процесс решения остальных. Так, при проектировании башни высотой 12 м выбор крыши призматической формы (4 м) задает поиск конструкции ствола высотой только 8 м.

Важную роль при организации взаимодействия подзадач в процессе поиска общего решения играют ограничения (подобные рассмотренному в предыдущем абзаце), повышающие степень определенности в постановке подзадач и уменьшающие тем самым количество вариантов перебора. Это обстоятельство используется в методе, основанном на принципе наименьших свершений. Метод организует параллельное решение подзадач, чередуя распространение ограничений от одной подзадачи к другим и активизацию той подзадачи, накопившиеся ограничения для которой позволяют сделать достаточно определенный выбор. Решение подзадачи приостанавливается, если для ее эффективного продолжения не хватает информации.

Разбиения пространства поиска на подпространства можно добиться не только путем сведения задачи к подзадачам, но и основываясь на свойстве факторизуемости. Пространство состояний называется факторизованным, если оно разбивается на непересекающиеся подпространства частичными (не полностью построенными) решениями. В таких пространствах существует возможность на ранних этапах поиска, когда только начинает формироваться решение, по его предварительному виду исключить из поиска подпространства, которые заведомо не могут содержать полное решение и тем самым понизить сложность задачи.

Второй подход к решению проблемы размерности основан на введении в рассмотрение кроме "подробного" конкретного пространства состояний еще ряда иерархически организованных пространств, получающихся из конкретного и друг из друга путем удаления несущественных для соответствующего уровня абстракции деталей. Решение задачи начинается с поиска в пространстве верхнего уровня (это пространство имеет минимальную размерность), найденное решение уточняется затем в пространствах, лежащих ниже, пока не будет построено полное решение в конкретном пространстве. При этом движение по уровням носит, как правило, итеративный характер, что подразумевает возврат на более высокие уровни для пересмотра плана решения в случае некорректности этого плана.

Кроме большой размерности пространства состояний сложность задачи поиска решений может характеризоваться также неполнотой исходных данных. Неполнота исходных данных типична для задач синтеза описаний технических объектов, поскольку сведений, содержащихся в ТЗ, как правило, недостаточно для однозначного решения задачи. В качестве способа борьбы с неполнотой исходных данных в ПС наряду с рассмотренным выше принципом наименьших свершений используются правдоподобные рассуждения. Рассуждения (вывод) называются правдоподобными, если они основываются на истинных фактах и предположениях, истинность которых в рамках известных ПС сведений доказать невозможно.

Необходимость в предположениях возникает всякий раз, когда интерпретатору для продолжения поиска решения становится необходимой дополнительная информация. В этом случае интерпретатор подбирает продукцию, большинство условий левой части которой удовлетворяется на текущем состоянии рабочей памяти, а остальные - не противоречат ей. Далее он делает предположение о выполнимости недостающих условий и пытается обосновать эти предположения, соотнеся их с имеющимися в его распоряжении знаниями. Если опровергнуть предположения не удается, то поиск решения продолжается применением рассматриваемой продукции. Однако в ходе решения может возникнуть новая информация, противоречащая данным предположениям, тогда интерпретатор должен вернуться к точке принятия предположений и пересмотреть их, сделав новый выбор. Поскольку каждое принятое предположение ведет поиск в отдельную часть пространства состояний, то методы поиска, базирующиеся на правдоподобных рассуждениях, называются методами поиска в альтернативных пространствах.

Методы поиска решений при неточных знаниях

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

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

Для базы знаний диагностирующих ПС характерны продукции вида

ЕСЛИ свидетельство, ТО гипотеза ,
где в качестве гипотезы выступает одна из возможных причин неисправности, а свидетельство - это доступное к наблюдению проявление этой неисправности. Причем в общем случае каждая неисправность имеет несколько проявлений и, наоборот, одно и то же проявление может свидетельствовать в пользу нескольких причин. Эта неоднозначность и обусловливает неточность используемых продукций. Основной задачей интерпретатора в таких ПС является выбор наиболее обоснованной свидетельствами гипотезы (гипотез) из ряда возможных.

В основе теоретико-вероятностного подхода к решению этой задачи лежит использование формулы Байеса:

Р(Н|Е) = Р(Е|Н)·(Р(Н)/Р(Е)) ,
где Н - гипотеза, Е - свидетельство, Р(Н) - априорная (безусловная) вероятность гипотезы (вероятность наличия данной неисправности в любом наугад выбранном экземпляре технического объекта), Р(Н|Е) - апостериорная (условная) вероятность гипотезы при наличии свидетельства, Р(Е|Н) - вероятность проявления свидетельства при справедливости гипотезы, Р(Е) - вероятность наличия свидетельства независимо от истинности или ложности гипотезы.

Последняя вероятность определяется как

Р(Е) = Р(Е|Н)·Р(Н) + Р(Е|~Н)·Р(~Н),  Р(~Н) = 1 - Р(Н),
где ~Н означает ложность гипотезы (отсутствие данной неисправности).

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

Р(Н|Еn, Еn-1, ..., Е1) = Р(Еn|Н)·(Р(Н| Еn-1, ..., Е1)/Р(Еn)),
n - количество свидетельств. После вычисления апостериорных вероятностей всех гипотез и их упорядочения интерпретатор имеет возможность выбрать одну или несколько в качестве решения задачи поиска причины неисправности.

В некоторых случаях при решении задачи диагностики информация о свидетельствах также носит вероятностный характер, что обусловлено не полной уверенностью пользователя ПС, поставляющего ей исходные данные, в наблюдаемых проявлениях неисправностей. Пусть Р(Е|R) - это заданная пользователем вероятность наблюдения в исследуемом объекте свидетельства Е, т.е. Р(Е|R) выражает степень уверенности пользователя в присутствии Е для объекта. Тогда вероятность истинности гипотезы Н при заданной определяется следующим образом:

Р(Н|R) = Р(Н|Е)·Р(Е|R) + Р(Н|~Е)·(1 - Р(Е|R)).

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

Эмпирические подходы не имеют строгого обоснования, однако хорошо зарекомендовали себя на практике. В рамках одного из таких подходов всем данным рабочей памяти и всем продукциям приписываются коэффициенты определенности (КО). КО для данных указываются пользователем в ответ на запрос ПС из диапазона действительных чисел -1 ... 1, где 1 соответствует полной уверенности пользователя в истинности его ответа, -1 - его полной уверенности в обратном, 0 - незнание пользователем ответа. КО для продукций задаются экспертом на этапе формирования БЗ из диапазона 0 ... 1, где 1 означает абсолютную уверенность эксперта в надежности продукции.

На основе КО данных рабочей памяти и КО продукций осуществляется расчет КО заключений, содержащихся в правой части продукций и добавляемых в рабочую память в ходе поиска решения. Для этого используется следующая формула:

КО(заключение) = КО(условие) · КО(продукция).

Условие продукции представляет собой, как уже говорилось выше, объединенные логическими связками И, ИЛИ, НЕ требования к элементам рабочей памяти, в связи с чем возникает задача вычисления КО условия продукции, исходя из КО соответствующих данных. Для ее решения обычно используются соотношения, подобные принятым в нечеткой логике, а именно:

КО(x И y) = min(КО(x), КО(y)),
КО(x ИЛИ y) = max(КО(x), КО(y)),
КО(НЕ x) = -КО(x).

Приложение

Задачами в нечисловой форме занимается дискретная математика. Вам должны быть знакомы ее основные понятия и объекты: множества, графы, грамматики и т.п. Сейчас же остановимся на понятии сложности решения задач дискретной математики (а это, как правило, комбинаторные задачи).

Алгоритм - эффективная процедура, однозначно приводящая к результату. С точки зрения практики алгоритм - это программа, критерий алгоритмичности процесса - возможность его запрограммировать.

Требования к алгоритмам (рассмотрим неформально) перечислены ниже.

  1. Алгоритм работает с данными (входными, выходными, промежуточными), он применяется к исходным данным и выдает результаты. Данные - это объекты, которые четко определены и отличимы (как друг от друга, так и от "необъектов"). Нам понятны такие данные, как числа, вектора, матрицы, формулы. Сложнее с рисунком (хотя бы того же графа). Но такие объекты, как "хорошая книга" или "симпатичная девушка" должны быть описаны (переведены) как данные с помощью других, более подходящих объектов. Заметим, что человек легко справляется с этими понятиями.
  2. Данные требуют для своего размещения памяти (однородной и дискретной), которая может быть бесконечной (лучше - неограниченной).
  3. Алгоритм состоит из отдельных элементарных шагов или действий. Каждый шаг может иметь дело с данными фиксированной длины (это удобно для оценки времени работы алгоритма) или переменной.
  4. Последовательность шагов детерминирована (после каждого шага указывается, что делать дальше).
  5. Алгоритм должен быть результативен - должен останавливаться после конечного числа шагов с указанием того, что считать результатом. Всякий, кто заявляет, что он изобрел алгоритм решения какой-либо задачи, должен показать, что алгоритм остановится за конечное число шагов и дает результат для любых исходных данных из их области допустимых значений. Замечание: общего метода проверки сходимости для любого алгоритма и любых исходных данных не существует.
  6. Следует различать: а), б), в) конечны, кроме памяти, которая входит в механизм.

Для теоретического исследования свойств алгоритмов принято использовать абстрактное устройство, называемое машиной Тьюринга. Различают два типа таких устройств: детерминированная машина Тьюринга (ДТМ) и недетерминированная машина Тьюринга (НДТМ).

ДТМ умеет выполнять "обычные" операции: +, -, *, /, ИЛИ, ЧИТАТЬ, ПИСАТЬ, ЕСЛИ, ПОВТОРЯТЬ. В конкретный момент времени ДТМ может выполнять только одно действие и находится в строго определенном состоянии. НДТМ имеет кроме операций ДТМ еще операцию ВЫБОР{M}, которая создает столько копий текущего состояния, сколько элементов в множестве М. НДТМ останавливается, когда одна из копий достигнет инструкции КОНЕЦ. Например, задача разрешимости логического выражения Е(q1, q2, q3, ..., qn) может быть решена на НДТМ с помощью следующего простого алгоритма

for (i=1; i<(n+1); i++) {
  qi = ВЫБОР {0, 1};
  };
if ( Е(q1, q2, q3, ..., qn) ) {
  успех; КОНЕЦ;
  }
 else {
  неудача;
  };
НДТМ позволяет легко записывать алгоритмы перебора.

Сложность алгоритма - выраженная в виде функции от размерности входных данных верхняя граница числа шагов, необходимых для получения результата. Сложность алгоритмов принято обозначать как O(f(n)), где n - размерность входных данных например, запись вида O(1) или O(c) говорит о том, что количество шагов алгоритма не зависит от размерности данных и постоянно. Такими алгоритмами являются следующие:

1+2+3+...+n = (n*(n+1))/2 ,
12+22+32...+n2 = (n*(n+1)*(2n+1))/6 .

Сложность задачи - сложность наилучшего алгоритма, известного для ее решения.

Самые лучшие - линейные алгоритмы [O(n)] и линейные задачи. Примерами таких задач являются проверка планарности графов, поиск Эйлерова цикла на графе из n ребер.

Задачи класса P имеют полиномиальную сложность. Например:

Но таких задач, к сожалению, мало.

Задачи класса E - задачи, экспоненциальные по природе: О(fn) - где f - const или полином. В этот класс попадают задачи, для которых число ожидаемых ответов уже само по себе экспоненциально, например: найти все подмножества некоторого множества.

На практике встречается много задач, которые не могут быть отнесены ни к одному из рассмотренных классов - для них количество решений не экспоненциально, но не разработаны и полиномиальные алгоритмы.

Задачи класса NP (недетерминированные полиномиальные задачи) - задачи, которые можно решить за полиномиальное время на НДТМ.

Оказывается, что различные задачи класса NP на самом деле эквивалентны.

Определение 1. Задача Q сводится к задаче R тогда и только тогда, когда для всякого решения r задачи R существует функция g(r), которую можно вычислить полиномиально и которая является решением задачи Q.

Определение 2. Если одновременно задача Q сводится к задаче R, и R сводится к Q, то Q и R - эквивалентны.

NP-сложная задача - задача, к которой сводима любая задача из класса NP. NP-сложная задача необязательно принадлежит классу NP! Кстати (теорема Кука), задача разрешимости логического выражения является NP-сложной.

NP-полная задача - задача, являющаяся NP-сложной и попадающая в класс NP.