Cтраница 1
Бэктрекинг на таком дереве реализуется применением соответствующего обратного перехода в свободной группе сдвигов. В программной реализации такие обратные переходы реализуются обратными указателями. [1]
Назначение бэктрекинга состоит в обеспечении обхода дерева вывода со всеми возможными вариантами означивания переменных. Тем не менее иногда это существенно замедляет вычисления. Для компенсации подобных ограничений в Пролог были введены конструкции процедурного типа. Это так называемые нелогические примитивы, содержащие управляющую информацию относительно того, как должен выполняться поиск. [2]
Режим бэктрекинга реализуется следующим образом. Если М, обрабатывая элемент d, применил команду ах - v a, то это означает, что Л, обрабатывая d, в соответствующий момент ничего не добавляет к следу 5 ( d), применяет команду ах - а и начинает процедуру обратного прохождения. При этом в следе s ( d) уничтожается крайний элемент а. Этот элемент d, и является результатом процедуры бэктрэкинга. [3]
Применение бэктрекинга при поиске в альтернативных мирах будет приводить к излишней неэффективности, так как все неудачи, возникшие при поиске в одном направлении, не запоминаются при переходе к поиску в Другом направлении. Та же самая причина неудачи может заново обнаруживаться и на новом направлении. [4]
В случае бэктрекинга, обусловленного некоторым вызовом tempstatus, статусная строка уничтожается. [5]
Применение механизма бэктрекинга при поиске в альтернативных мирах будет приводить к излишней неэффективности, так как все неудачи, возникшие при поиске в одном направлении, не запоминаются при переходе к поиску в другом направлении. Та же самая причина неудачи может заново обнаруживаться и на новом направлении. [6]
Хронологический возврат ( бэктрекинг) представляет собой один из подходов к реализации процедуры поиска. В нем неудача при поиске приводит к возврату, при котором сначала удаляются все действия и выводы, сделанные после последней точки выбора, а затем продолжается работа над другой альтернативой, имеющейся в этой точке. Поскольку в процедуре возврата используется правило последним вошел - первым вышел, то память для хранения множества активных в данное время убеждений может быть выполнена в виде стека, или магазинной памяти. Хронологический возврат оказывается часто без нужды малоэффективным, поскольку все неудачи, встретившиеся на некотором пути поиска, забываются, как только этот путь отбрасывается. Независящие от пути поиска общие причины неудач впоследствии повторно скажутся на других путях поиска. [7]
Таким образом, традиционный бэктрекинг отбрасывает слишком много информации. [8]
Этот процесс называется бэктрекингом. [9]
Таким образом, механизм традиционного бэктрекинга отбрасывает слишком много информации. Осуществлять возврат целесообразно не к состоянию, непосредственно предшествующему данному, а к тому состоянию, которое является причиной возникновения неудачи. В используемых нами терминах причиной неудач являются предположения, т.е. недоказуемые утверждения. Поэтому при обнаружении неудачи необходимо возвращаться в состояние, где это предположение было сделано, и испытывать другое предположение. [10]
Если такая пара имеется, то сразу начинается режим бэктрекинга в состоянии а, если такой пары нет, то продолжается режим прямых прохождений. [11]
Заметим, что при стандартном моделировании стека при помощи бэктрекинга ( перевод М3 в УИ4) необходимо запоминать в элементах среды состояния прямых переходов и состояния, заносимые в стек. В стек заносятся два состояния аг и а3, соответствующие возврату по левой и по правой дуге. [12]
Специальный предикат отсечения () используется в Прологе для управления бэктрекингом. Отсечение как цель удовлетворяется немедленно. Поскольку бэктрекинг на этих переменных не выполняется, механизм Пролога отбрасывает все альтернативные сопоставления. [13]
Преобразователь А работает в двух режимах: прямое прохождение элементов и бэктрекинг. При этом в элементах структуры JZ) конструируются следы, характеризующие историю прохождения элементов преобразователем А. Если а, равно ( а, г) из 01 X Z, то М, в 1 - й раз находясь в d, выполнил команду ах - - а, СТЕК ( 2), запоминающую пару ( d, z) в верхней части стека. [14]
Другими словами, отсечение ограничивает распространение аргументов для подбора новых значений возврата ( бэктрекинга) из-за неудачи. Отсечение применяется также для ускорения вычислений путем отбрасывания избыточных ветвей вычислений. [15]