Механизм отсечений алгоритм и пример на прологе(Cuting and Backtracking)

Привет, мой друг, тебе интересно узнать все про механизм отсечений, тогда с вдохновением прочти до конца. Для того чтобы лучше понимать что такое механизм отсечений, cuting and backtracking , настоятельно рекомендую прочитать все из категории Представление и использование знаний.

Механизм отсечений и отката(mechanism of Cuting and Backtracking) ПроЛога.Отличия ПроЛога от алгоритмичесих языков программирования.

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

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

Процесс решения задачи с использованием механизма отсечений и отката может быть описан следующим образом:

1. Инициализация: задание начального состояния задачи и подготовка всех необходимых данных.

2. Поиск: перебор всех возможных вариантов решения задачи путем последовательного выбора вариантов для каждого решаемого параметра.

3. Проверка: проверка каждого выбранного варианта на соответствие заданным условиям и ограничениям.

4. Отсечение: если выбранный вариант не удовлетворяет заданным условиям, то он отбрасывается, и поиск продолжается с предыдущего шага.

5. Откат: возвращение на предыдущий шаг и выбор следующего варианта, если текущий вариант не привел к решению.

6. Решение: получение решения задачи, когда перебор всех вариантов привел к выбору оптимального решения.

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

Способность выдавать несколько решений

Отличительной способностью ПроЛога является то, что при поиске решений на ПроЛоге выдается целый список подходящих значений. Поэтому, в ПроЛоге один предикат может быть представлен целым набором правил, каждое из которых может выдавать ответ. Пример. Пусть есть следующее описание предиката “число_больше”:

число_больше(А,3):-А<3.

число_больше(А,5):-А<5.

число_больше(А,8):-А<8.

Тогда вызов решателя ПроЛога

Goal число_больше(4,Больше).

Выдаст ответы: Больше = 5, 8.

Другими словами, согласно правилам в предикате “число_больше” больше числа 4 есть два числа 5 и 8. Здесь видно, что набор правил работает как структура ветвления case в алгоритмических языках. Предикаты которые могут выдавать несколько значений называются неопределенными (nondeterm). Предикаты, которые выдают только одно значение, называются определенными (determ). Кроме неопределенных предикатов в ПроЛоге еще используют механизм неопределенности факты. Пример.

иметь(долги, плохо).

иметь(квартира, хорошо).

иметь(дети, хорошо).

Тогда вызов решателя ПроЛога

Goal иметь(Что,хорошо).

Ответ будет: Что = квартира, дети

Откат (Backtracking)

Теперь введем понятие отката (Backtracking). Откат – это попытка ПроЛога найти следующий вариант решения задачи. Откат вызывается неудачей в некотором месте программы, что приводит ПроЛог к попытке найти следующее решение. Откатывание идет до места, где возможно вычислить другое решение. При этом все связанные переменные, которые были связаны ниже точки, где возможен другой вариант решения, освобождаются. При вызове решателя ПроЛога, откат создается самим ПроЛогом для выдачи всех значений решения. Пример.

database - знания

иметь(string, string)

predicates

показать(string)

clauses

показать(Как):-

% здесь переменная Что будет каждый раз освобождаться и

% связываться с новым значением

               иметь(Что,Как),

               nl,write(Что," иметь ",Как).

Goal

% загрузим знания с фактами иметь() из файла знания.txt

               consult("знания.txt",знания),

% вызовем предикат выдающий несколько вариантов ответа

               показать(хорошо).

Ответы ПроЛога:

               квартира иметь хорошо

               дети иметь хорошо

Отсечение (Cut)

Теперь введем понятие отсечения. Об этом говорит сайт https://intellect.icu . Отсечением в ПроЛоге называется механизм, который запрещает перебор правил данного предиката находящихся ниже текущего правила и запрещает механизм отката. Отсечение обозначается знаком “!”. Пример. Если переписать предыдущий предикат “число_болше” как:

число_больше(А,3):-А<3,

               !.

число_больше(А,5):-А<5,

               !.

число_больше(А,8):-А<8,

               !.

Тогда вызов решателя ПроЛога

Goal число_больше(4,Больше).

Выдаст ответ: Больше = 5.

Это происходит потому, что в каждом правиле предиката, после проверки на больше, идет оператор отсечения "!", что запрещает ПроЛогу последующий откат и поиск других вариантов ответа.

Пример использования механизма отката и отсечений.

Механизм отката и отсечений можно рассмотреть на следующем примере. Допустим у нас есть список значений, в котором нужно найти некое значение и выдать стоящее перед ним значение. Так как ПроЛог это логический язык, то поставленная задача решается с помощью создания набора правил:

1. При переборе списка, если текущий элемент не является искомым значением, то делаем перебор далее.
2. При переборе списка, если текущий элемент является искомым значением, то прекратим перебор и вернемся на предыдущий элемент.
3. Если предыдущие правила не сработали, то выдать текущий элемент как предыдущее значение.

Описание на языке ПроЛог предиката выполняющего эти правила будет такое:

1. найти_пред_значение(Значение,[Элемент|Список], Предыдущее):-

               not(Значение=Элемент),

               !, % отсечение перебора правил предиката, расположенных ниже

               найти_пред_значение(Значение,Список,Предыдущее),

               !.

2. найти_пред_значение(Значение,[Значение|_],_):-

               !,% отсечение перебора правил предиката, расположенных ниже

fail.

3. найти_пред_значение(_,[Предыдущее|_],Предыдущее):- !.

Зная, что в ПроЛоге можно использовать порядок расположения правил как способ выбора последовательности обхода правил, и зная действие механизма отсечений, можно переставить правила 1 и 2 местами и убрать проверку на несовпадение. Тогда получим следующее описание предиката:

domains

Номер = integer

НСписок = Номер*

predicates

найти_пред_значение(Номер Значение, НСписок, Номер Предыдущее)

clauses

найти_пред_значение(Значение,[Значение|_],_):-

               !,% отсечение перебора правил предиката, расположенных ниже

               fail.

найти_пред_значение(Значение,[_|Список], Предыдущее):-

               найти_пред_значение(Значение,Список,Предыдущее),

               !.% отсечение выдачи других ответов

найти_пред_значение(_,[Предыдущее|_],Предыдущее):-

               !.% отсечение выдачи других ответов

Полученное описание состоит из трех правил и выполняет следующие действия. Первое правило сравнивает текущий элемент с искомым значением, и если они равны, то происходит а) отсечение правил предиката расположенных ниже от участия в поиске, б) вызывается неудача, что приводит к останову рекурсии. Второе правило делает перебор всех элементов списка с помощью вызова самой себя, то есть вызывает рекурсию. При этом, в правиле до вызова рекурсии нет отсечений, и если вызов рекурсии будет неуспешным, то управление перейдет на правило предиката, расположенное ниже. Если вызов рекурсии будет успешен, то вызывается отсечение ("!"), а потом выход из предиката. Третье правило выдает текущий элемент как предыдущее значение, которое стоит перед искомым значением, вызывает отсечение и выход из предиката. Действие предиката рассмотри на примере. Дадим решателю ПроЛога строку:

Goal найти_пред_значение(3,[1,2,4,3,5,2],Предыдущее).

ПроЛог делает первый вызов предиката:

1. Правило 1 не срабатывает: 3 не равно 1. Переход на второе правило:
2. Правило 2 вызывает рекурсию найти_пред_значение(3,[2,4,3,5,2],Предыдущее):
   1. Правило 1 не срабатывает: 3 не равно 2. Переход на второе правило:
   2. Правило 2 вызывает рекурсию найти_пред_значение(3,[4,3,5,2],Предыдущее):
      1. Правило 1 не сработает: 3 не равно 4. Переход на второе правило:
      2. Правило 2 вызывает рекурсию: найти_пред_значение(3,[3,5,2],Предыдущее):
         1. Первое правило сработает: 3=3. и выполняется: отсечение правил предиката ниже и неудача. Что приводит в выходу из рекурсии с результатом неудачи.
      3. Продолжение правила 2. Неудача вызова рекурсии со списком [3,5,2] приводит к неудаче второго правила на данном уровне. ПроЛог переходит на третье правило.
      4. Правило 3. Здесь список = [4,3,5,2]. Происходят действия: Предыдущее унифицируется с 4, выход с отсечением других возможных решений.
      5. Продолжение правила 2. Рекурсия возвращает удачное значение Предыдущее =4. Происходит выход с отсечением других возможных решений.
   3. Продолжение правила 2. Рекурсия возвращает удачное значение Предыдущее =4. Происходит выход с отсечением других возможных решений.
3. Продолжение правила 2. Рекурсия возвращает удачное значение Предыдущее =4. Происходит выход с отсечением других возможных решений.

Ответ ПроЛога Предыдущее = 4.

Теперь посмотрим что будет, если убрать отсечение во втором правиле:

domains

Номер = integer

НСписок = Номер*

predicates

% обявляем что предикат неопределенный

nondeterm найти_пред_значение(Номер Значение, НСписок, Номер Предыдущее)

clauses

найти_пред_значение(Значение,[Значение|_],_):-

               !,% отсечение перебора правил предиката, расположенных ниже

               fail.

найти_пред_значение(Значение,[_|Список], Предыдущее):-

% в этом правиле нет ни одного отсечения

% что указывает на возможность отката в это место

% для выбора следующего варианта ответа

               найти_пред_значение(Значение,Список,Предыдущее).

найти_пред_значение(_,[Предыдущее|_],Предыдущее):-

               !.% отсечение выдачи других ответов

То ПроЛог уже выдаст несколько результатов:

Предыдущее = 4, 2, 1.

Это становится возможным, так как включается механизм отката ПроЛога и во втором правиле появляется возможность выдать ответ на каждом шаге рекурсии.

Пролог (Prolog) относится к логическим языкам программирования и отличается от алгоритмических языков программирования, таких как C++, Java или Python, следующими особенностями:

1. Декларативный подход: в Прологе программист описывает логические отношения между объектами, а не последовательность шагов для достижения цели. Это означает, что программа на Прологе описывает, что должно быть выполнено, а не как это должно быть сделано.

2. Использование базы знаний: Пролог работает с базой знаний, состоящей из фактов и правил, описывающих свойства объектов и их отношения друг с другом.

3. Логическое вывод: Пролог использует механизм логического вывода для нахождения решения задачи. Это означает, что программа на Прологе не явно задает последовательность действий, а выполняет поиск решения, используя базу знаний и логические правила.

4. Рекурсия: Пролог часто использует рекурсию для реализации итеративных процессов.

5. Сопоставление с образцом: Пролог позволяет сопоставлять объекты с шаблонами (образцами) для поиска соответствия.

6. Неизменяемость данных: в Прологе данные являются неизменяемыми, что означает, что после того, как они были определены, они не могут быть изменены.

7. Ограничения: Пролог поддерживает ограничения (constraints), что позволяет задавать ограничения на значения переменных в программе.

В целом, Пролог отличается от алгоритмических языков программирования тем, что позволяет описывать отношения между объектами, а не последовательность действий для достижения цели. Это делает Пролог особенно полезным для задач, связанных с искусственным интеллектом, базами знаний и логическим выводом. Однако Пролог не так удобен для написания процедурных алгоритмов, как алгоритмические языки программирования.

Если я не полностью рассказал про механизм отсечений? Напиши в комментариях Надеюсь, что теперь ты понял что такое механизм отсечений, cuting and backtracking и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Представление и использование знаний