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

Таким образом, мы видим, что для полного представления задачи в пространстве состояний необходимо задать:

а) форму описания состояний и, в частности, описание начального состояния;

б) множество операторов и их воздействий на описания состояний;

в) свойства описания целевого состояния.

Пространство состояний полезно представлять себе в виде направленного графа.

3.4.3. Запись в виде графа.

Граф состоит из множества (не обязательно конечного) вершин. Некоторые пары вершин соединены с помощью дуг, и эти дуги направлены от одного члена этой пары к другому. Такие графы носят название направленных графов. Если некоторая дуга направлена от вершины ni к вершине nj, то говорят, что вершина nj является дочерней для вершины ni, а вершина ni является родительской вершиной для nj. Может оказаться, что наши две вершины будут дочерними друг для друга; в этом случае пара направленных дуг называется иногда ребром графа. В случае, когда граф используется для представления пространства состояний, с его вершинами связывают описание состояний, а с его дугами - операторы.

Последовательность вершин ni1,ni2, .,nik., в которой каждая вершина nij дочерняя для ni,j-1, j=2,k, называется путем длины k от вершины ni1, к вершине nik. Если существует путь, ведущий от вершины ni к вершине nj, то вершину nj называют достижимой из вершины ni или потомком вершины ni . В этом случае вершина ni называется также предком для вершины nj. Видно, что проблема нахождения последовательности операторов, преобразующих одно состояние в другое, эквивалентна задаче поиска пути на графе.

Список литературы:

1). И. Братко. Программирование на языке Пролог для искусственного интеллекта М.: Мир, 1990.

2). Г. Долин. Что такое ЭС.- Компьютер Пресс, 1992/2.

3). Д. Р. Малпасс. Реляционный язык Пролог и его применение.

4). Д. Н. Марселлус. Программирование экспертных систем на Турбо Прологе М.: Финансы и статистика, 1994.

5). К. Нейлор. Как построить свою экспертную систему М.: Энергоатомиздат, 1991.

6). Н. Д. Нильсон. Искусственный интеллект. Методы поиска решений М.: Мир, 1973.

7). В. О. Сафонов. Экспертные системы - интеллектуальные помощники специалистов С.-Пб: Санкт-Петербургская организация общества “Знания” России, 1992.

8). К. Таунсенд, Д. Фохт. Проектирование и программная реализация экспертных систем на персональных ЭВМ.- М.: Финансы и статистика, 1990.

9). В. Н. Убейко. Экспертные системы М.: МАИ, 1992.

10). Д. Уотермен. Руководство по экспертным системам М.: Мир, 1980.

11). Д. Элти, М. Кумбс. Экспертные системы: концепции и примеры М.: Финансы и статистика, 1987.