Қайту алгоритмдеріндегі кері секіру техникасы

Кіріспе

Артқа қарай іздеу алгоритмдерінде іздеу кеңістігін қысқартатын техника бар. Артқа қарай іздеу алгоритмдерінде артқа секіру – іздеу кеңістігін қысқартып, тиімділікті арттыратын техника. Артқа іздеу әрқашан бір айнымалының барлық мәндері тексерілгеннен кейін іздеу ағашында бір деңгей жоғары көтеріледі, ал артқа секіру бірнеше деңгейге көтерілуі мүмкін. Осы мақалада айнымалыларды бағалаудың белгілі бір реті қолданылады, бірақ динамикалық бағалау ретіне де осы принциптер қатысты.

Анықтама

Кері іздеу кез келген шешімді таба алмай, бір айнымалының барлық мәндерін сынаған кезде, ол бұрын тағайындалған айнымалылардың соңғысын қайта қарастырады, оның мәнін өзгертеді немесе басқа мәндер сыналмаса, одан әрі кері іздеуге көшеді. Егер ағымдағы ішінара тапсырма болса және -ның барлық мәндері шешім табылмағаннан кейін сыналған болса, кері іздеу -ны кеңейтетін шешім жоқ деген қорытындыға келеді. Алгоритм содан кейін "жоғары қарай" -ға көтеріледі, мүмкін болса, -ның мәнін өзгертеді, әйтпесе тағы да кері іздейді. Ішінара тапсырманың толық болуы әрқашан -ның ешқандай мәні шешімге алып келмейтінін дәлелдеу үшін қажет емес. Атап айтқанда, ішінара тапсырманың префиксі де сол қасиетке ие болуы мүмкін, яғни, индексі бар, онда -ның қандай мәні болса да, оны шешімге дейін кеңейту мүмкін емес. Егер алгоритм осы фактіні дәлелдей алса, ол әдеттегідей қайта қарастырудың орнына үшін басқа мәнді тікелей қарастыра алады. Мысалы, егер -қа берілген ағымдағы тапсырма -ның барлық мүмкін мәндерімен сәтсіз болса, кері іздеу -ға қайта оралып, оған жаңа мән беруге тырысады. Кері іздеудің орнына, алгоритм қосымша талдау жасайды, , және бағалауларының ешқандай шешімнің бөлігі еместігін дәлелдейді. Нәтижесінде, -ның ағымдағы бағалауы ешқандай шешімнің бөлігі емес, ал алгоритм тікелей -ға кері секіріп, оған жаңа мән береді. Кері секіру алгоритмінің тиімділігі оның қаншалықты жоғары секіре алуына байланысты. Идеалды жағдайда, алгоритм -тан -ға дейін секіруге мүмкін болады, егер -ға берілген ағымдағы тапсырманы ешқандай мәнмен шешімге дейін кеңейту мүмкін болмаса. Мұндай жағдайда, бұл секіру "қауіпсіз секіру" деп аталады. Секірудің қауіпсіздігін анықтау әрқашан мүмкін емес, өйткені қауіпсіз секірулер шешімдер жиынтығымен анықталады, ал алгоритм осы жиынды табуға тырысады. Іс жүзінде, кері секіру алгоритмдері қауіпсіз екенін тиімді дәлелдей алатын ең төменгі индексті пайдаланады. Әртүрлі алгоритмдер секірудің қауіпсіздігін анықтау үшін әртүрлі әдістерді қолданады. Бұл әдістердің құны әртүрлі, бірақ іздеу ағашының бөліктерін өткізіп тастау арқылы іздеу көлемін азайту үшін жоғарырақ қауіпсіз секіруді табудың жоғары құнымен сауда жасауға болады.

Whenever backtracking has tried all values for a variable without finding any solution, it reconsiders the last of the previously assigned variables, changing its value or further backtracking if no other values are to be tried. If is the current partial assignment and all values for have been tried without finding a solution, backtracking concludes that no solution extending
exists. The algorithm then "goes up" to , changing 's value if possible, backtracking again otherwise. The partial assignment is not always necessary in full to prove that no value of leads to a solution. In particular, a prefix of the partial assignment may have the same property, that is, there exists an index such that cannot be extended to form a solution with whatever value for If the algorithm can prove this fact, it can directly consider a different value for instead of reconsidering as it would normally do. An example in which the current assignment to has been unsuccessfully tried with every possible value of Backtracking goes back to , trying to assign it a new value. Instead of backtracking, the algorithm makes some further elaboration, proving that the evaluations , , and are not part of any solution. As a result, the current evaluation of is not part of any solution, and the algorithm can directly backjump to , trying a new value for it. The efficiency of a backjumping algorithm depends on how high it is able to backjump. Ideally, the algorithm could jump from to whichever variable is such that the current assignment to cannot be extended to form a solution with any value of If this is the case, is called a safe jump. Establishing whether a jump is safe is not always feasible, as safe jumps are defined in terms of the set of solutions, which is what the algorithm is trying to find. In practice, backjumping algorithms use the lowest index they can efficiently prove to be a safe jump. Different algorithms use different methods for determining whether a jump is safe. These methods have different cost, but a higher cost of finding a higher safe jump may be traded off a reduced amount of search due to skipping parts of the search tree.

Жапырақ түйіндерінде кері секіру

Артқа секірудің мүмкін болатын ең қарапайым жағдайы – айнымалының барлық мәндері қосымша тармақталусыз сәйкес емес деп дәлелденген кезде. Шешім табу процесінде, ішінара бағалау тағайындалған айнымалыларды қамтитын барлық шектеулерді қанағаттандырса ғана сәйкес келеді, әйтпесе сәйкес емес болады. Тұрақты ішінара шешімді толық шешімге кеңейту мүмкін болмауы мүмкін, себебі тағайындалмаған кейбір айнымалылар басқа шектеулерді бұзбай тағайындалмауы керек. Белгілі бір айнымалының барлық мәндері ағымдағы ішінара шешіммен сәйкес келмейтін жағдайды «жапырақ тұйық» деп атайды. Бұл айнымалы іздеу ағашының жапырағы болған кезде ғана болады (бұл мақаланың суреттерінде тек жапырақтары бар түйіндерге сәйкес келеді). Джон Гасшнигтің артқа секіру алгоритмі тек жапырақ тұйықтарында ғана артқа секіреді. Яғни, ол кері жолмен жұмыс істеуді тек барлық мүмкін мәндер тексерілгенде және басқа айнымалыға тармақталу қажеттілігі тумағанда ғана қолданады. Қауіпсіз секіруді әр мән үшін , -қа сәйкес келмейтін ең қысқа префиксін бағалау арқылы табуға болады. Басқаша айтқанда, егер -ның мүмкін мәні болса, алгоритм келесі бағалаулардың сәйкестігін тексереді:

Бағалаулар сәйкес келмейтін ең кішкентай индекс (тізімдегі ең төменгі орны) егер -ның жалғыз мүмкін мәні болса, қауіпсіз секіру болады. Әрбір айнымалы әдетте бірнеше мән қабылдай алатындықтан, әрбір мән үшін тексеруден шығатын ең үлкен индекс қауіпсіз секіру болып табылады және Джон Гасшниг алгоритмінің секіретін нүктесі болып табылады. Іс жүзінде алгоритм жоғарыда көрсетілген бағалауларды -ның сәйкестігін тексерумен бірге бір уақытта тексеруі мүмкін.

Ішкі тораптарда кері секіру

Алдыңғы алгоритм өзгермелінің мәні ағымдағы ішінара шешіммен үйлесімсіз екені одан әрі тармақталмастан көрсетілгенде ғана кері секіреді. Яғни, ол іздеу ағашындағы жапырақ түйіндерінде ғана кері секіруге рұқсат береді. Іздеу ағашының ішкі түйіні – бұл бұрынғыларымен үйлесімді айнымалыға берілген мән. Егер осы мәнді кеңейтетін шешім болмаса, алдыңғы алгоритм әрқашан кері қайтады: мұндай жағдайда кері секіру жасалмайды. Ішкі түйіндерде жапырақ түйіндері сияқты кері секіру мүмкін емес. Шындығында, егер кейбір бағалаулар тармақталуды қажет етсе, олардың ағымдағы мәнге сәйкес келетінін білдіреді. Осылайша, соңғы айнымалының осы мәндерімен үйлесімсіз префикс іздеу сәтті болмайды. Мұндай жағдайларда, бағалаудың ағымдағы жартылай бағалаумен шешімнің бөлігі еместігін рекурсивті іздеу анықтайды. Атап айтқанда, алгоритм «біледі» бұл нүктеден бастап шешім жоқ екенін, өйткені ол шешім тапқаннан кейін тоқтамай, кері қайтады. Бұл кері қайтару – ішінара шешімнің үйлесімсіз екенін дәлелдеген бірнеше тұйықтардың нәтижесі. Әрі қарай кері секіру үшін алгоритм шешім табудың мүмкін болмауы осы тұйықтарға байланысты екенін ескеруі керек. Атап айтқанда, қауіпсіз секірулер – бұл осы тұйықтарды әлі де үйлесімсіз ішінара шешімдер деп санайтын префикстердің индекстері. Мысалда, алгоритм барлық мүмкін мәндерін сынағаннан кейін үш үйлесімсіздік нүктесіне байланысты кері қайтады. Екінші нүкте оның ішінара бағалауынан алынған мәндері алынса да үйлесімсіз болып қалады (айнымалының мәндері оның ұрпақтарында екенін ескеріңіз). Басқа үйлесімсіз бағалаулар да , , және алынса да өзгермейді. Алгоритм барлық үйлесімсіздіктерді сақтайтын ең төменгі айнымалы болғандықтан , дейін кері секіре алады. -ның жаңа мәні сыналып жатыр. Басқаша айтқанда, -ның барлық мәндері сыналғаннан кейін, алгоритм егер -ның ағымдағы шындық бағалауы, -ның ұрпақтары болып табылатын жапырақ түйіндеріндегі -ның барлық шындық бағалауларымен үйлесімсіз болса, бұрынғы айнымалыға кері секіре алады.

The previous algorithm only backjumps when the values of a variable can be shown inconsistent with the current partial solution without further branching. In other words, it allows for a backjump only at leaf nodes in the search tree. An internal node of the search tree represents an assignment of a variable that is consistent with the previous ones. If no solution extends this assignment, the previous algorithm always backtracks: no backjump is done in this case. Backjumping at internal nodes cannot be done as for leaf nodes. Indeed, if some evaluations of required branching, it is because they are consistent with the current assignment. As a result, searching for a prefix that is inconsistent with these values of the last variable does not succeed. In such cases, what proved an evaluation not to be part of a solution with the current partial evaluation is the recursive search. In particular, the algorithm "knows" that no solution exists from this point on because it comes back to this node instead of stopping after having found a solution. This return is due to a number of dead ends, points where the algorithm has proved a partial solution inconsistent. In order to further backjump, the algorithm has to take into account that the impossibility of finding solutions is due to these dead ends. In particular, the safe jumps are indexes of prefixes that still make these dead ends to be inconsistent partial solutions. In this example, the algorithm come back to , after trying all its possible values, because of the three crossed points of inconsistency. The second point remains inconsistent even if the values of and are removed from its partial evaluation (note that the values of a variable are in its children) The other inconsistent evaluations remains so even without , , and The algorithm can backjump to since this is the lowest variables that maintains all inconsistencies. A new value for will be tried. In other words, when all values of have been tried, the algorithm can backjump to a previous variable provided that the current truth evaluation of is inconsistent with all the truth evaluations of in the leaf nodes that are descendants of the node .

Жайлатулар

, суб-ағашындағы түйіндердің көп болу мүмкіндігіне байланысты, оның суб-ағашына кірген кезде, қауіпсіз кері секіру үшін қажетті ақпарат жиналады. Қауіпсіз секіруді табу екі мәселені қарастыру арқылы жеңілдетіледі. Біріншісі, алгоритмге қауіпсіз секіру қажет, бірақ ол ең жоғары қауіпсіз секірудің орнына басқа секірумен де жұмыс істей алады. Екінші жеңілдету – кері секіру арқылы өткізілген суб-ағаш түйіндерін кері секіруді іздеу кезінде елеуге болмайды. Нақтырақ айтқанда, түйіннен түйінге дейін кері секіру арқылы өткізілген барлық түйіндер , және олардың басқа да суб-ағаштары тамырланған суб-ағаш үшін маңызсыз. Шындығында, егер алгоритм түйіннен жол арқылы төменге түсіп, кері қайтқанда кері секіру жасаса, онда ол тікелей түйінден түйінге өте алатын еді. Кері секіру түйіндер арасындағы түйіндер тамырланған суб-ағаш үшін маңызсыз екенін көрсетеді. Басқаша айтқанда, кері секіру іздеу ағашының бір бөлігіне бару қателік болғанын білдіреді. Сондықтан, іздеу ағашының бұл бөлігін оның ата-бабаларының бірінен немесе өзінен кері секіруді қарастырғанда елеуге болады. Бұл фактіні пайдаланып, әр түйінде бұрын тағайындалған айнымалылар жиынтығын жинауға болады, олардың мәні тамырланған суб-ағашта шешімнің жоқ екенін дәлелдеуге жеткілікті. Бұл жиын алгоритм орындалған кезде құрылады. Түйінден кері қайтарылғанда, бұл жиын түйіннің айнымалысын алып тастайды және кері қайту немесе кері секірудің мақсатты жиынтығына қосылады. Кері секіруден өткізілген түйіндер ешқашан кері қайтарылмайтындықтан, олардың жиынтығы автоматты түрде елеуге алынбайды.

График негізінде кері секіру

Графқа негізделген кері секірудің мағынасы – жапырақ түйіндерінде белгіленген айнымалылармен шектеуде болатын айнымалыларды тексеру арқылы қауіпсіз секіруді табу болып табылады. Әрбір жапырақ түйінінде және онда белгіленген әрбір индекс айнымалысы үшін, сол айнымалысымен шектесетін, оған тең немесе кіші индекстерді қауіпсіз секіруді табу үшін пайдалануға болады. Атап айтқанда, белгілі бір айнымалының барлық мәндері тексерілген кезде, бұл жиын сол айнымалылардың қандай бағалаулары астындағы тармақта шешім табу мүмкін еместігін дәлелдейтін индекстерін қамтиды. Осының нәтижесінде алгоритм осы жиынның ең жоғары индексіне кері секіруге мүмкіндік алады. Кері секіру арқылы өткізілген түйіндерді одан әрі кері секіруді қарастырғанда назардан тыс қалдыруға болады, бұл мүмкіндік келесі алгоритммен пайдаланылады. Жапырақ түйінінен кері қайтарылғанда, онымен шектесетін айнымалылар жиынтығы құрылып, оның ата-анасына немесе кері секіру жағдайында ата-бабасына "қайтарылады". Әрбір ішкі түйінде айнымалылар жиынтығы сақталады. Оның балаларының немесе ұрпақтарының бірінен айнымалылар жиынтығы алынған сайын, олардың айнымалылары сақталатын жиынтыққа қосылады. Түйінден кері қайтарылғанда немесе кері секіргенде, түйіннің айнымалысы осы жиынтықтан алынып тасталады, ал жиынтық кері қайтарылудың немесе кері секірудің бағытындағы түйінге жіберіледі. Бұл алгоритмнің жұмыс істеу себебі – түйінде сақталатын жиын осы түйіннің ұрпағы болып табылатын жапырақтарда қанағаттандырылмаушылықты дәлелдеуге қатысты барлық айнымалыларды жинайды. Айырмалылар жиынтығы тек түйіндерден кері қайтарылғанда ғана жіберілетіндіктен, кері секіру арқылы өткізілген түйіндерде жиналған жиынтықтар автоматты түрде елемеледі.

Конфликтке негізделген кері секіру (конфликтке бағытталған кері секіру (cbj))

Кейде үлкен кері секірулерге қол жеткізе алатын, одан да жетілдірілген кері секіру алгоритмі, бір шектеуде екі айнымалының ортақ болуын тексеруге ғана емес, сонымен қатар бұл шектеудің шын мәнінде қайшылыққа себеп болған-болмағанын анықтауға негізделген. Атап айтқанда, бұл алгоритм әрбір жапырақ түйінінде бұзылған шектеулердің біреуін жинақтайды. Әрбір түйінде жапырақтарда жиналған шектеулердің бірінде кездесетін айнымалының ең жоғары индексі қауіпсіз секіру болып табылады. Жапырақта таңдалған бұзылған шектеу нәтижелі секірудің қауіпсіздігіне әсер етпесе де, ең жоғары индексті шектеулерді таңдау секірудің биіктігін арттырады. Сондықтан, қақтығысқа негізделген кері секіру алгоритмі шектеулерді осылай реттейді: төменгі индексті айнымалыларға қатысты шектеулер жоғары индексті айнымалыларға қатысты шектеулерге басымдық беріледі. Формальды түрде, егер бір шектеудегі айнымалының ең жоғары индексі, бірақ екінші шектеуде болмаса, төмен болса, онда ол шектеуге басымдық беріледі. Басқаша айтқанда, ортақ айнымалыларды ескермегенде, барлық төменгі индекстері бар шектеуге басымдық беріледі. Жапырақ түйінінде алгоритм жапырақта соңғы бағаланған айнымалымен қайшылық тудыратын ең төменгі индексті таңдайды. Бұл бағалау кезінде бұзылған шектеулердің арасынан ең басым шектеу таңдалып, оның барлық индекстері жинақталады. Осылайша, алгоритм айнымалыға қайтып келгенде, ең төменгі жиналған индекс қауіпсіз секіруді анықтайды. Іс жүзінде, бұл алгоритмді барлық индекстерді бір жиынға жинау арқылы жеңілдетуге болады, әрбір мән үшін жеке жиын жасаудың орнына. Атап айтқанда, алгоритм әрбір түйінде өзінің ұрпақтарынан келген, кері секіру арқылы өтпелген жиынтықтарды жинақтайды. Бұл түйінден кері қайтарылғанда, жиынтықтан түйіннің айнымалысы алынып тасталады және кері қайту немесе кері секірудің бағытына жинақталады. Қақтығысқа бағытталған кері секіруді Патрик Проссер 1993 жылғы мақаласында шектеулерді қанағаттандыру мәселелері үшін ұсынған.