Cтраница 2
Этот процесс ( возврата на несколько шагов назад) называется откатом назад или бэктрекингом. [16]
Переход в это состояние осуществляется, если в первом поле метки элемента в последовательности-следе, не прерываемой бэктрекингом, встречаются два одинаковых управляющих состояния. Таким образом, А ограничивает число посещений одного и того же элемента в режиме прямых прохождений, не прерываемых возвратами. [17]
Таким образом, конкретные результаты из теорем 8.2 и 8.3 получаются при конкретном выборе информационной среды и конкретной реализации бэктрекинга. Наиболее интересен случай информационных сред, для которых полугруппа сдвигов является группой, так как для таких сред возможна реализация бэктрекинга умножением на обратные элементы полугруппы сдвигов. В частности, справедлива следующая теорема. [18]
В английской литературе подобные операторы называют бэктр е-кинговыми, а методы вычислений, основанные на возвращениях в предыдущие элементы обработки - бэктрекингом. [19]
Если прологовские программы имеют операционную семантику, программы на Дейталоге - чисто декларативные, при интерпретации программ на Прологе используется нисходящая схема, основанная на резолюци-онной стратегии, поиске сначала вглубь и бэктрекинге Для конструирования деревьев доказательства. Базовая схема интерпретации Дейталога - восходящая. [20]
В одних методах применяется поиск сначала вширь, в других - поиск сначала вглубь. Последние используют бэктрекинг ( слева - направо), и лишь некоторые из них - более сложные эвристические подходы. [21]
В теореме 8.1 доказано, что детерминированные стековые читающие преобразователи транслируемы в класс локально-конечных бэктрекинговых итеративных алгоритмов. В случае групп бэктрекинг реализуется явно, через обратные переходы. Поэтому, учитывая вышесказанное и теорему 9.6, получаем необходимое утверждение. [22]
Недетерминированные программы допускают стандартную трансляцию в детерминированные программы. Это осуществляется программной реализацией бэктрекинга - метода, позволяющего возвращаться в начало пути, приведшего к тупикам. Таким образом, вводя недетерминированные конструкции и имея соответствующее программное обеспечение для их реализации, программист получает гибкий алгоритмический аппарат, освобождающий его от утомительной громоздкости, характерной для многих детерминированных описаний. Подобные недетерминированные конструкции введены в ряд языков искусственного интеллекта. Наиболее известный из них язык PLANAR. Пятый довод является, пожалуй, самым убедительным для практического программиста. [23]
Эффективность этого метода определяется возможностью использовать безвозвратную стратегию. В тех случаях, когда решение задачи не может быть получено без механизма бэктрекинга, применяются более сложные методы. Метод нисходящего уточнения применим в том случае, когда все задачи не могут быть сведены к фиксированному набору подзадач, однако существует фиксированная упорядоченность понятий области и фиксированный частичный порядок между подзадачами. В случае, если подзадачи взаимозависимы, т.е. для решения некоторой подзадачи может требоваться информация, получаемая другой подзадачей, и подзадачи не могут быть упорядочены, целесообразно применять принцип наименьших свершений. [24]
Таким образом, преобразователь А динамически накапливает информацию, позволяющую избегать повторных вычислений. Формирование метки в элементе среды показано на рис. 8.5, где пунктиром обозначен режим бэктрекинга, сплошной линией - режим прямых прохождений, при котором происходит накапливание информации в первом поле. [25]
Метки преобразователя Л имеют два поля. Первое поле предназначено для меток следов, характеризующих историю прямого прохождения элемента, второе поле предназначено для анализа бэктрекинга. [26]
Таким образом, конкретные результаты из теорем 8.2 и 8.3 получаются при конкретном выборе информационной среды и конкретной реализации бэктрекинга. Наиболее интересен случай информационных сред, для которых полугруппа сдвигов является группой, так как для таких сред возможна реализация бэктрекинга умножением на обратные элементы полугруппы сдвигов. В частности, справедлива следующая теорема. [27]
Механизм Пролога представляет собой некоторую Пролог-систему, способную выполнять цели языка Пролог. Хотя мы и не намерены при связывании изменять базовое поведение механизма Пролога ( поиск по стратегии сначала вглубь, унификация, бэктрекинг), однако в этом механизме могли быть расширены некоторые средства с целью их адаптации к среде конкретной системы баз данных. [28]
Специальный предикат отсечения () используется в Прологе для управления бэктрекингом. Отсечение как цель удовлетворяется немедленно. Поскольку бэктрекинг на этих переменных не выполняется, механизм Пролога отбрасывает все альтернативные сопоставления. [29]
Множество кортежей возвращается целиком. При этом кортежи помещаются в резидентную в оперативной памяти базу данных Пролога, после чего работа механизма Пролога возобновляется с первого кортежа множества. При бэктрекинге механизм Пролога обнаружит следующий кортеж, удовлетворяющий заданной цели, уже в основной памяти. Следовательно, в этом случае сопоставление и бэктрекинг на предикатах базы данных находятся под управленем механизма Пролога. [30]