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

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

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

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

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

Упражнение

4.7. Предположим, что клетки шахматной доски представлены парами их коорди­нат в форме X/Y, где X и Y находятся з пределах 1-8.

а) Определите отношение iunp( Squarel, Square2), соответствующее ходу конем на шахматной доске. Предположим, что переменная Squarel всегда конкретизируется значениями координат некоторой клетки, a Square2 может оставаться не конкретизированной, например, следующим образом:

?- jump< 1/1, 5) . S = 3/2; 5 = 2/3; но


Глава 4. Использование структур; примеры программ



б) Определите отношение knightpath( Path), где Path - список клеток,
который представляет один из допустимых путей прохождения коня по
пустой шахматной доске.

в) Используя отношение knightpath, запишите вопрос для поиска любого пу­
ти движения коня, состоящего из четырех ходов от клетки 2/1 до противо­
положного края доски (Y = 8), который проходит через клетку 5/4 после
второго хода.

Резюме

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

• Любая база данных может быть естественным образом представлена как мно­
жество фактов Prolog.

• Механизмы запроса и согласования системы Prolog могут разнообразными способами применяться для выборки структурированной информации из базы данных. Кроме того, могут быть легко определены вспомогательные процедуры для дальнейшего упрощения взаимодействия с определенной базой данных.

• Абстрагирование данных может рассматриваться как метод программирова­ния, который позволяет упростить использование сложных структур данных и вносит свой вклад в обеспечение создания более понятных программ. В языке Prolog можно легко реализовать фундаментальные принципы абстрагирования данных.

• Такие абстрактные математические конструкции, как конечные автоматы,
часто можно непосредственно преобразовать в исполняемые определения
Prolog.

• Как показывает пример задачи с восемью ферзями, к решению одной и той же
проблемы можно подойти разными способами, определяя различные представ­
ления этой проблемы. Введение избыточности в представление часто позволя­
ет уменьшить объем вычислений. В этом проявляется один из компромиссов
между требованиями к пространству и времени.'

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



Часть I. Язык Prolog