Программирование на языке Пролог для искусственного интеллекта
Шрифт:
Рис. 4.11. Программа 3 для задачи о восьми ферзях.
Процедура реш универсальна в том смысле, что ее можно использовать для решения задачи об N ферзях (на доске размером N×N). Нужно только правильно задеть области Dx, Dy и т.д.
Удобно автоматизировать получение этих областей. Для этого нам потребуется процедура
которая для двух заданных целых чисел N1 и N2 порождает список
Вот она:
Главную процедуру решение нужно соответствующим образом обобщить:
где N — это размер доски, а S — решение, представляемое в виде списка Y-координат N ферзей. Вот обобщенное отношение
Например, решение задачи о 12 ферзях будет получено с помощью:
4.5.4. Заключительные
Три решения задачи о восьми ферзях показывают, как к одной и той же задаче можно применять различные подходы. Мы варьировали также и представление данных. В одних случаях это представление было более экономным, в других — более наглядным и, до некоторой степени, избыточным. К недостаткам более экономного представления можно отнести то, что какая-то информация всякий раз, когда она требовалась, должна была перевычисляться.
В некоторых случаях основным шагом к решению было обобщение задачи. Как ни парадоксально, но при рассмотрении более общей задачи решение оказывалось проще сформулировать. Принцип такого обобщения — стандартный прием программирования, и его можно часто применять.
Из всех трех программ третья лучше всего показывает, как подходить к общей задаче построения структуры из заданного множества элементов при наличии ограничений.
Возникает естественный вопрос: " Какая из трех программ наиболее эффективна?" В этом отношение программа 2 значительно хуже двух других, а эти последние — одинаковы. Причина в том, что основанная на перестановках программа 2 строит все перестановки, тогда как две другие программы способны отбросить плохую перестановку не дожидаясь, пока она будет полностью построена. Программа 3 наиболее эффективна. Она избегает некоторых арифметических вычислений, результаты которых уже сразу заложены в избыточное представление доски, используемое этой программой.
4.7. Пусть поля доски представлены парами своих координат в виде
(а) Определите отношение
(b) Определите отношение
(с) Используя отношение
Резюме
Примеры, рассмотренные в данном разделе, иллюстрируют некоторые достоинства и характерные черты программирования на Прологе:
• Базу данных можно естественным образом представить в виде множества прологовских фактов.
• Такие механизмы Пролога, как вопросы и сопоставление, можно гибко использовать для получения информации из базы данных. Кроме этого можно использовать вспомогательные процедуры-утилиты, еще больше облегчающие взаимодействие с конкретной базой данных.