Backjumping, CSP, книга AIMA

Question

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

Глава 5 Искусственного интеллекта, Современный подход, 3-е изд. p149-150 дает краткий пример того, как создать конфликт, заданный во время backjumping.

Пример касается раскраски Карта Австралии .

Цитата из проблемной части:

«Терминальный» сбой ветвипоиск всегда происходит, потому что домен переменной становится пустым;эта переменная имеет стандартный набор конфликтов.В нашем примере сбой SA, и его конфликтный набор (скажем) {WA, NT, Q}.Мы возвращаемся к Q, и Q поглощает набор конфликтов из SA (за исключением, конечно, самого Q) в свой собственный набор прямых конфликтов, который является {NT, NSW};новый набор конфликтов - {WA, NT, NSW}.То есть не существует решения от Q и далее, учитывая предыдущее назначение {WA, NT, NSW}.Поэтому мы возвращаемся к NT , самой последней из них.NT поглощает {WA, NT, NSW} - {NT} в своем собственном наборе прямых конфликтов {WA}, давая {WA, NSW} (как указано в предыдущем абзаце).Теперь алгоритм возвращает обратно к NSW , как мы и надеялись.

Я пытаюсь понять выделенные биты:

1. Возврат к NT.Каким образом / почему NT является самым последним?
2. .Почему?

Answer 1

Ответ на вопрос Q1 приведен в предыдущем абзаце, ключом является порядок принятия решения:

Рассмотрим снова частичное назначение {WA = красный, NSW = красный} (что из нашего предыдущего обсуждения, противоречиво).Предположим, что мы попробуем T = red затем и назначим NT, Q, V, SA.Мы знаем, что никакое присваивание не может работать для этих последних четырех переменных, поэтому в итоге у нас заканчиваются значения, чтобы попробовать NT.

NT является самым последним в том смысле, что оно является вершиной стека.в точке, где обсуждается этот пример.

Мы возвращаемся к NSW, так как это последнее решение, которое пересекается с установленным конфликтом.