9.5. Контрольные вопросы и упражнения

1. Дайте определение монотонных и немонотонных логик.

2. Что такое модальные логики?

3. Перечислите классы модальных логик.

4. Какие существуют способы автоматизации нечетких рассуждений?

10. Представление задач в пространстве состояний

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

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

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

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

Пример. Преобразовать алгебраическое выражение:

(АВ + СD) / BC  A/C + D/B.

В качестве состояний в этой задаче должны выступать алгебраические выражения, но нужно также выбрать форму описания состояния. Можно использовать двоичные деревья, в которых неконцевые вершины – алгебраические операции, а концевые вершины – постоянные или переменные (символы А, В, С, D, которые появляются в выражении). Законы алгебраических преобразований – это операторы в пространстве состояний. Применение этих законов приведет к преобразованию этого описания в другие описания, например, в описание состояния АВ/BС + CD/BC:

и далее в состояние A/C + D/B:

Можно использовать другую форму представления для этой задачи – линейную строку: / + * AB * CD * BC. Так как все операции двуместные, то по этой строке можно восстановить дерево. Таким образом, в задаче необходимо преобразовать исходную линейную строку в строку + / AC / DB.

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

Таблица 8

Операторные функции в пространстве состояний

Входное описание	Выходное описание
Si1	Sj1
Si2	Sj2
…	…

Для больших задач представление в виде таблицы становится практически непригодным, поэтому в общем случае операторы – это вычисления, преобразующие одни описания в другие. Для описания состояния в форме строки имеется удобный способ представления операторных вычислений – правила переписывания, которые имеют вид: S_i  S_j (строка S_i может быть преобразована в строку S_j).

Например, правило переписывания может иметь вид: A$  B$, где А – первый символ некоторой строки, который заменяется на В, $ – произвольная строка.

Представление правил в виде правил переписывания не ограничивается строковыми описаниями состояний. Рассмотрим другую форму правил переписывания на примере.

Пример. «Игра в восемь» – восемь пронумерованных фишек расположены в клетках таблицы 33. Одна клетка всегда пустая, на нее можно передвинуть одну из соседних с ней фишку. Нужно перевести некоторое начальное состояние в целевое (упорядоченное).

Пусть начальное состояние имеет вид:

2	1	6
4		8
7	5	3

Целевое состояние:

1	2	3
4	5	6
7	8

Правила переписывания для этой игры.

Описание множества состояний: x_i  {1,2,…,8}, x_i  x_j (ij).

х1	х2	х3
х4		х5
х6	х7	х8

Для фиксированного расположения пустой клетки возможно 8! расположений фишек 1... 8. Всего состояний 9*8! = 9! = 362880.

Правила переписывания:

и т.д. Например:

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

Существуют следующие стандартные задачи поиска:

1. Найти по заданным начальному и конечному состояниям путь на графе.

2. Усложнение первой задачи – дугам приписывается стоимость (стоимость применения соответствующего оператора) и нужно найти путь из начального состояния в конечное, имеющий минимальную стоимость.

3. Найти путь из начального состояния в любое состояние задачи.

Граф может быть задан как явно, так и неявно. При явном задании все вершины должны быть перечислены, например, в таблице. Такое задание графа практически неприемлемо для больших графов, а для бесконечных графов – невозможно.

При неявном способе задания графа определяется некоторое конечное множество {S_i} вершин (начальные вершины) и оператор Г, который применением к некоторой вершине дает все ее дочерние вершины и стоимости дуг.

Неявному заданию графа соответствует еще один способ представления пространства состояний – недетерминированная программа:

где х, у – произвольные совокупности данных; Г(у) – сыновья вершины у; ВЫБОР – выбор одной из вершин из множества Г(у).

П ример. Представление «Игры в восемь» с помощью недетерминированной программы.

Если в результате получено целевое состояние – успех, если нет, то возврат.