Иван Братко - Программирование на языке Пролог для искусственного интеллекта Страница 42

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

trace

запускает полную трассировку всех целей, следующих за trace.

notrace

прекращает дальнейшее трассирование.

spy( P) (следи за P)

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

nospy( P)

прекращает "слежку" за P.

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

8.5. Эффективность

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

Традиционная архитектура вычислительных машин не очень хорошо приспособлена для реализации прологовского способа выполнения программ, предусматривающего достижение целей из некоторого списка. Поэтому ограниченность ресурсов по времени и пространству сказывается в Прологе, пожалуй, в большей степени, чем в большинстве других языков программирования. Вызовет ли это трудности в практических приложениях, зависит от задачи. Фактор времени практически не имеет значения, если пролог-программа, которую запускают по несколько раз в день, занимает 1 секунду процессорного времени, а соответствующая программа на каком-либо другом языке, скажем на Фортране, — 0.1 секунды. Разница в эффективности становится существенной, если эти две программы требуют 50 и 5 минут соответственно.

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

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

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

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

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

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

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

8.5.1. Повышение эффективности решения задачи о восьми ферзях

В качестве простого примера повышения эффективности давайте вернемся к задаче о восьми ферзях (см. рис. 4.7). В этой программе Y-координаты ферзей перебираются последовательно — для каждого ферзя пробуются числа от 1 до 8. Этот процесс был запрограммирован в виде цели

принадлежит( Y, [1, 2, 3, 4, 5, 6, 7, 8] )

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

принадлежит( Y, [1, 5, 2, 6, 3, 7, 4, 8] )

Это маленькое изменение уменьшит время, необходимое для нахождения первого решения, в 3-4 раза.

В следующем примере такая же простая идея, связанная с изменением порядка, превращает практически неприемлемую временную сложность в тривиальную.

8.5.2. Повышение эффективности программы раскраски карты

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

Пусть карта задана отношением соседства

соседи( Страна, Соседи)

где Соседи — список стран, граничащих со страной Страна. При помощи этого отношения карта Европы с 20-ю странами будет представлена (в алфавитном порядке) так:

соседи( австрия, [венгрия, запгермания, италия,

 лихтенштейн, чехословакия,

 швейцария, югославия]).

соседи( албания, [греция, югославия]).

соседи( андорра, [испания, франция]).

...

Решение представим в виде списка пар вида

Страна / Цвет

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

[австрия/C1, албания/C2, андорра/С3, ...]

Теперь определим предикат

цвета( СписЦветСтран)

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

цвета( []).

цвета( [Страна/Цвет | Остальные] ) :-

 цвета( Остальные),

 принадлежит( Цвет, [желтый, синий, красный, зеленый]),

 not( принадлежит( Страна1/Цвет, Остальные),

 сосед( Страна, Страна1) ).

сосед( Страна, Страна1) :-

 соседи( Страна, Соседи),

 принадлежит( Страна1, Соседи).

Здесь принадлежит( X, L) — как всегда, отношение принадлежности к списку. Для простых карт с небольшим числом стран такая программа будет работать. Что же касается Европы, то здесь результат проблематичен. Если считать, что мы располагаем встроенным предикатом setof, то можно попытаться раскрасить карту Европы следующим образом. Определим сначала вспомогательное отношение:

страна( С) :- соседи( С, _ ).

Тогда вопрос для раскраски карты Европы можно сформулировать так:

?- sеtоf( Стр/Цвет, страна( Стр), СписЦветСтран),

 цвета( СписЦветСтран).

Цель setof — построить "шаблон" списка СписЦветСтран, в котором в элементах вида страна/ цвет вместо цветов будут стоять неконкретизированные переменные. Предполагается, что после этого цель цвета конкретизирует их. Такая попытка скорее всего потерпит неудачу вследствие неэффективности работы программы.