Шектеулерді шешу алгоритмдерінде алдын ала қарау әдістері

Кіріспе

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

Шектілік қанағаттану

Жалпы шектеуді қанағаттандыру мәселесінде әрбір айнымалы домендегі бір мән қабылдай алады. Сондықтан, кері іздеу алгоритмі айнымалыны іле-келе таңдайды және оның барлық мүмкін мәндерін тексереді; әр мән үшін алгоритм рекурсивті шақырылады. Алға қарау, белгілі бір айнымалыны таңдаудың салдарына баға беру үшін немесе оған берілетін мәндердің тәртібін анықтау үшін қолданылады.

Алға қарай қарау әдістері

Алдын ала тексеру – өзгергішке нақты тапсырманың әсерін бағалаудың қарапайым әдісі. Ағымдағы жарым-жартылай шешім мен бағалауға ұсынылған тапсырманы ескере отырып, ол басқа өзгергіштің тұрақты мән қабылдауы мүмкін емесе, оны тексереді. Яғни, ол ең алдымен қарастырылып отырған өзгергіштің уақытша мәнімен қазіргі жарым-жартылай шешімді кеңейтеді, содан кейін әлі тағайындалмаған әрбір басқа өзгергішті қарастырып, кеңейтілген жарым-жартылай шешіммен сәйкес келетін бағалаудың бар-жоғын тексереді. Жалпы алғанда, алдын ала тексеру кеңейтілген тапсырмаға сәйкес келетін мәндерді анықтайды. Доғалық тұрақтылыққа негізделген алдын ала қарау әдісі көбірек уақытты қажет етеді, бірақ жақсы нәтижелер беруі мүмкін. Атап айтқанда, жаңа өзгергіштің мәнімен кеңейтілген жарым-жартылай шешімді ескере отырып, ол барлық тағайындалмаған өзгергіштер үшін доғалық тұрақтылықты қамтамасыз етеді. Басқаша айтқанда, тағайындалмаған әрбір өзгергіш үшін басқа өзгергішке сәйкес келмейтін мәндер алынып тасталады. Алдын ала тексеру мен доғалық тұрақтылықтың арасындағы айырмашылық – біріншісі бір уақытта тек бір тағайындалмаған өзгергішті тұрақтылыққа тексерсе, екіншісі өзара тұрақтылық үшін тағайындалмаған өзгергіштердің жұптарын да тексереді. Қиындықтарға қанағаттандыру мәселелерін шешу үшін алдын ала қарауды пайдаланудың ең көп таралған тәсілі – доғалық тұрақтылықты сақтау (MAC) алгоритмі. Доғалық тұрақтылықты қолданатын тағы екі әдіс – толық және ішінара алдын ала қарау. Олар доғалық тұрақтылықты қамтамасыз етеді, бірақ әрбір өзгергіштер жұбы үшін емес. Атап айтқанда, толық алдын ала қарау тағайындалмаған әрбір өзгергіштер жұбын қарастырып, олардың арасында доғалық тұрақтылықты қамтамасыз етеді. Бұл жаһандық доғалық тұрақтылықты қамтамасыз етуден өзгеше, онда кейбір өзгергіштерді бірнеше рет қайта қарастыру қажет болуы мүмкін. Керісінше, толық алдын ала қарау бір өзгергіштер жұбы арасында доғалық тұрақтылықты күштеп орындағаннан кейін, бұл жұп енді қарастырылмайды. Ішінара алдын ала қарау ұқсас, бірақ өзгергіштердің белгілі бір реті қарастырылады және доғалық тұрақтылық әрбір жұп үшін бір рет ғана күштеп орындалады. Доғалық тұрақтылыққа негізделген алдын ала қарау жол тұрақтылығымен және жалпы i тұрақтылығымен немесе қатынастық доғалық тұрақтылықпен де жұмыс істеуі үшін кеңейтілуі мүмкін.

The simpler technique for evaluating the effect of a specific assignment to a variable is called forward checking. Given the current partial solution and a candidate assignment to evaluate, it checks whether another variable can take a consistent value. In other words, it first extends the current partial solution with the tentative value for the considered variable; it then considers every other variable that is still unassigned, and checks whether there exists an evaluation of that is consistent with the extended partial solution. More generally, forward checking determines the values for that are consistent with the extended assignment. A look ahead technique that may be more time consuming but may produce better results is based on arc consistency. Namely, given a partial solution extended with a value for a new variable, it enforces arc consistency for all unassigned variables. In other words, for any unassigned variables, the values that cannot consistently be extended to another variable are removed. The difference between forward checking and arc consistency is that the former only checks a single unassigned variable at time for consistency, while the second also checks pairs of unassigned variables for mutual consistency. The most common way of using look ahead for solving constraint satisfaction problems is the maintaining arc consistency (MAC) algorithm. Two other methods involving arc consistency are full and partial look ahead. They enforce arc consistency, but not for every pair of variables. In particular, full look considers every pair of unassigned variables , and enforces arc consistency between them. This is different than enforcing global arc consistency, which may possibly require a pair of variables to be reconsidered more than once. Instead, once full look ahead has enforced arc consistency between a pair of variables, the pair is not considered any more. Partial look ahead is similar, but a given order of variables is considered, and arc consistency is only enforced once for every pair with
Look ahead based on arc consistency can also be extended to work with path consistency and general i consistency or relational arc consistency.