Цель 2 преимущества логического программирования 4
жүктеу/скачать 36,6 Kb.
|
- Бұл бет үшін навигация:
- Избыточные решения.
Порядок целей.Порядок целей более существен, чем порядок предложений. Порядок целей имеет решающее значение при определении последовательности действий в программе на Прологе. Причина, по которой порядок целей в предложении влияет на порядок решений, отличается от причины, по которой порядок правил в процедуре влияет на порядок решений. Изменение порядка правил не изменяет дерево поиска, которое используется при решении данной цели. Просто обход дерева производится в ином порядке. Изменение порядка целей приводит к изменению дерева поиска. Порядок целей определяет дерево поиска. По этой причине порядок целей влияет на количество проверок, выполняемых программой при решении. Существенен не порядок правил, а порядок целей. Программа будет завершающейся, если первый аргумент цели – полный список. Цели, у которых первый аргумент – неполный список приводят к бесконечным вычислениям. Избыточные решения.При построении программ на Прологе следует обратить внимание на важную характеристику программы, не имеющую аналогов в логическом программировании, - отсутствие избыточных решений. Значением логической программы является множество выводимых из программы основных целей. Здесь не существенно, выводится ли цель единственным образом или существует несколько различных выводов; однако это существенно в Прологе, поскольку от этого зависит эффективность поиска решений. Каждый возможный вывод означает дополнительную ветвь в дереве поиска, чем больше дерево поиска, тем дольше продолжается вычисление. В общем случае желательно сохранить размер дерева поиска по возможности минимальным. Наличие избыточных решений из-за возвратов может вызвать в предельном случае экспоненциальный рост времени работы программы. При решении конъюнкции n целей, каждая из которых имеет одно избыточное решение, в случае возвратов может быть порождено 2n решений, что приводит к изменению оценки времени работы программы от полиноминальной (или даже линейной) к экспоненциальной. Одна из причин появления избыточных решений в программах на Прологе состоит в наличии различных правил, пригодных для одного и того же случая. Другая причина, приводящая к избыточным решениям, состоит в рассмотрении слишком большого числа специальных случаев. Иногда подобное рассмотрение мотивируется стремлением к эффективности. Для исключения избыточных решений можно добавить дополнительный факт, что позволит сократить рекурсивные вычисления, когда существует аргумент – пустой список. Каждое предложение должно применяться лишь к спискам с ненулевым вторым аргументом. жүктеу/скачать 36,6 Kb. Достарыңызбен бөлісу:
|