Материал: Волченков Логическое программирование язык пролог 2015

На рис. 9.6,в представлен фрагмент дерева игры после построения вершины P9, имеющей оценку 0. При этом α(P2) = 1, а β(M6) = 0. Так как α(P2) > β(M6), то строить другие дочерние вершины для вершины M6 не имеет смысла. Вершина M6 бесперспективна и отсекается.

Рис. 9.6. Фрагменты дерева абстрактной игры в процессе применения алгоритма АЛЬФА/БЕТА-отсечения

Во многих случаях использование АЛЬФА/БЕТА-отсечения позволяет примерно в 2 раза увеличить глубину дерева игры при сохранении примерно того же числа вершин.

Взаключение отмечу, что впервые на языке Пролог алгоритм АЛЬФА/БЕТА-отсечения был реализован У.Уилсоном, а описан в уже упоминавшейся выше книге Л. Стерлинг и Э. Шапиро [7]. Применение Пролога для реализации игровых алгоритмов также

хорошо представлено и в книге И. Братко «Алгоритмы искусственного интеллекта на языке Пролог» [9].

Вкниге И. Братко хорошо изложен материал и о другой возможности использования Пролога в искусственном интеллекте – о реализации на этом языке основных идей построения экспертных систем. Ограниченность объёма настоящего пособия вынуждает автора призвать читателей к самостоятельному изучению этого материала.

136

Лекция 10

Пролог и системы искусственного интеллекта (продолжение)

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

Пролог со своими механизмами автоматического возврата (backtracking) и сопоставления образцов (pattern-matching) лишь имити-

рует «недетерминированность». Но эта имитация реализована в Прологе красиво и эффективно. Именно в этом смысле к искусственному интеллекту автор отнёс и другие задачи, рассмотренные в данной лекции. Это известная «задача о коммивояжёре» и весьма близкая к сфере деятельности известного сыщика Шерлока Холмса почти криминалистическая задача «об обитателях пяти домов».

1.Задача распознавания изображений тел с плоскими гранями

Пусть имеется исходная «картинка». Это плоское изображение, на котором компьютер «видит» многоугольники, точнее односвязные области, ограниченные замкнутыми ломаными линиями. Каждая область заполнена одним цветом. На рис. 10.1 – пример указанного изображения.

Рис. 10.1. Пример исходного изображения двух тел

137

«Видны» 10 односвязных областей, закрашенных разными цветами: один треугольник, 6 четырёхугольников, два шестиугольника и одна область с «дырой».

Ещё одна область на картинке – это фон, для простоты также закрашенный одним цветом.

Очевидно, что никакого искусственного интеллекта не нужно для автоматического преобразования картинки, представленной на рис. 10.1, в так назы-

ваемое контурное изображение,

показанное на рис. 10.2.

Рис. 10.2. Пример контурного изображения

После указанного преобразования можно считать, что компьютер «знает» уже не только о существовании на изображении, помимо фона, десяти гипотетических граней каких-то тел. Компьютеру уже также «известно» о существовании 29 рёбер – отрезков, находящихся либо между двумя гранями, либо между одной гранью и фоном. (Рис. 10.3).

Рис. 10.3. Нумерация ребер и граней контурного изображения

138

Следующая задача – построение контурного описания изображения.

Контурное описание изображения – это список описаний всех рёбер. В этом списке сначала должны быть представлены все рёбра, находящиеся на границе между фоном и «не фоном» при движении по часовой стрелке от какой-нибудь произвольно выбранной точки на этой границе (например, точки 0 на рис. 10.3). Остальные рёбра могут располагаться в списке произвольно.

Договоримся ещё об одном. Пусть описание каждого ребра – это структура с тремя аргументами. Функтор структуры – это вид ребра; 1-й аргумент структуры – это область, находящаяся слева от ребра; 2-й аргумент – это область, находящаяся справа от ребра, 3- й аргумент – это тип ребра.

Для простоты будем считать, что рёбра бывают всего трёх видов: «положительные» (рис. 10.4,а), «отрицательные» (рис. 10.4,б)

и «вертикальные» (рис. 10.4,в). Будем обозначать вид ребра так: pr, nr, vr.

Рис. 10.4. Три вида ребер контурного изображения

Типы ребер (всего их четыре) следующие:

выпуклое ребро (грани слева и справа от ребра образуют выпуклую поверхность); вогнутое ребро (грани слева и справа от ребра образуют вогнутую поверхность);

ребро типа «down» (если при обходе по контуру изображения по часовой стрелке движение по данному ребру происходит сверху вниз);

ребро типа «up» (если при обходе по контуру изображения по часовой стрелке движение по данному ребру происходит снизу вверх).

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

139

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

Итак, после предварительной обработки на вход «интеллектуального» распознавателя поступают данные следующего вида:

Код 10.1

patrecdata((R1;R2;R3;R4;R5;R6;R7;R8;R9;R10),

(pr(фон, R2, E1), nr(R2, фон, E2), vr(фон, R5, E3), pr(фон, R7, E4), nr(R7, фон, E5), vr(R8, фон, E6), pr(R8, фон, E7), nr(фон, R5, E8), vr(R6, фон, E9), pr(R6, фон, E10), nr(фон, R4, E11), pr(R3, фон, E12), nr(фон, R1, E13), vr(фон, R1, E14), nr(R1, R2, E15),

nr(R10, R9, E28), pr(R10, R8, E29))).

Данные представлены в виде факта Пролога patrecdata/2, первый аргумент которого – это совокупность граней (R1; …; R10), второй аргумент – это последовательность рёбер. Ri – переменная, обозначающая грань ( i-ю односвязную область на картинке). Все эти 10 переменных объединены в единую структуру данных с функтором «;» Ej – переменная, обозначающая тип j-го ребра.

Решение задачи распознавания в данном случае должно выдать следующий результат:

R1 = B1 : левая_грань,

R2 = B1 : горизонтальная_грань,

R3 = B1 : правая_грань,

R4 = B1 : левая_грань,

R5 = B2 : левая_грань,

R6 = B1 : правая_грань,

140