при рассмотрении более общей задачи решение оказывалось проще сформулировать. Принцип такого обобщения - стандартный прием программирования, и его можно часто применять.
Из всех трех программ третья лучше всего показывает, как подходить к общей задаче построения структуры из заданного множества элементов при наличии ограничений.
Возникает естественный вопрос: ' Какая из трех программ наиболее эффективна?' В этом отношение программа 2 значительно хуже двух других, а эти последние - одинаковы. Причина в том, что основанная на перестановках программа 2 строит все перестановки, тогда как две другие программы способны отбросить плохую перестановку не дожидаясь, пока она будет полностью построена. Программа 3 наиболее эффективна. Она избегает некоторых арифметических вычислений, результаты которых уже сразу заложены в избыточное представление доски, используемое этой программой.
Упражнение
4. 7. Пусть поля доски представлены парами своих координат в виде X/Y, где как X, так и Y принимают значения от 1 до 8.
(а) Определите отношение ходконя( Поле1, Поле2), соответствующее ходу коня на шахматной доске. Считайте, что Поле1 имеет всегда конкретизированные координаты, в то время, как координаты поля Поле2 могут и не быть конкретизированы. Например:
?- ходконя( 1/1, S).
S = 3/2;
S = 2/3;
no (нет)
(b) Определите отношение путьконя( Путь), где Путь - список полей, представляющих соответствующую правилам игры последовательность ходов коня по пустой доске.
(с) Используя отношение путьконя, напишите вопрос для нахождения любого пути, состоящего из 4-х ходов, и начинающегося с поля 2/1, а заканчивающегося на противоположном крае доски (Y= 8). Этот путь должен еще проходить после второго хода через поле 5/4.
Посмотреть ответ
Резюме
Примеры, рассмотренные в данном разделе, иллюстрируют некоторые достоинства и характерные черты программирования на Прологе:
Базу данных можно естественным образом представить в виде множества прологовских фактов.
Такие механизмы Пролога, как вопросы и сопоставление, можно гибко использовать для получения информации из базы данных. Кроме этого можно использовать вспомогательные процедуры-утилиты, еще больше облегчающие взаимодействие с конкретной базой данных.
Часто легко можно осуществить перевод абстрактных математических конструкций, таких как автоматы, на язык определений Пролога, готовых к выполнению.
Как это было в случае восьми ферзей, многие задачи допускают различные подходы, связанные с разными представлениями этих задач. Часто внесение избыточности в представление экономит вычисления. Происходит как бы проигрыш в рабочем пространстве, но выигрыш во времени.
Часто основным шагом на пути к решению оказывается обобщение задачи. Парадоксально, но рассмотрение более общей задачи позволяет облегчить формулировку решения.
Назад | Содержание
