Look-ahead (backtracking)
बैकट्रैकिंग एल्गोरिदम में, आगे देखें एक उप-प्रक्रिया के लिए सामान्य शब्द है जो अपने मूल्यों में से एक का मूल्यांकन करने के लिए एक शाखा चर चुनने के प्रभावों का पूर्वानुमान लगाने का प्रयास करता है। आगे देखने के दो मुख्य उद्देश्य अगले मूल्यांकन के लिए एक चर का चयन करना और उसे निर्धारित करने के लिए मूल्यों का क्रम चुनना है। बाधा संतुष्टि एक सामान्य बाधा संतुष्टि समस्या में, प्रत्येक चर एक क्षेत्र में एक मूल्य ले सकता है। एक बैकट्रैकिंग एल्गोरिथ्म इसलिए पुनरावृत्त रूप से एक चर चुनता है और इसके प्रत्येक संभावित मूल्यों का परीक्षण करता है; प्रत्येक मूल्य के लिए एल्गोरिथ्म पुनरावर्ती रूप से चलाया जाता है। आगे देखें का उपयोग मूल्यांकन करने के लिए दिए गए चर को चुनने के प्रभावों की जांच करने या इसे देने के लिए मूल्यों का क्रम तय करने के लिए किया जाता है। एक चर के लिए एक विशिष्ट कार्य के प्रभाव का मूल्यांकन करने के लिए सरल तकनीक को आगे की जाँच कहा जाता है। वर्तमान आंशिक समाधान और मूल्यांकन करने के लिए एक उम्मीदवार असाइनमेंट को देखते हुए, यह जांचता है कि क्या कोई अन्य चर एक सुसंगत मूल्य ले सकता है। दूसरे शब्दों में, यह पहले माने गए चर के लिए अस्थायी मूल्य के साथ वर्तमान आंशिक समाधान का विस्तार करता है; फिर यह हर दूसरे चर पर विचार करता है जो अभी भी असंबद्ध है, और जाँच करता है कि क्या इसका कोई मूल्यांकन मौजूद है जो विस्तारित आंशिक समाधान के अनुरूप है। अधिक आम तौर पर, आगे की जाँच उन मूल्यों को निर्धारित करती है जो विस्तारित कार्य के अनुरूप हैं। एक आगे देखने की तकनीक जो अधिक समय लेने वाली हो सकती है लेकिन बेहतर परिणाम दे सकती है, चाप की स्थिरता पर आधारित है। अर्थात्, एक नए चर के लिए एक मूल्य के साथ विस्तारित आंशिक समाधान को देखते हुए, यह सभी असंबद्ध चर के लिए चाप स्थिरता को लागू करता है। दूसरे शब्दों में, किसी भी असाइन किए गए चर के लिए, उन मूल्यों को हटा दिया जाता है जिन्हें लगातार किसी अन्य चर तक नहीं बढ़ाया जा सकता है। फॉरवर्ड चेकिंग और आर्क कंसिस्टेंसी के बीच का अंतर यह है कि पहला केवल कंसिस्टेंसी के लिए समय पर एक एकल असाइन किए गए चर की जांच करता है, जबकि दूसरा आपसी कंसिस्टेंसी के लिए असाइन किए गए चर के जोड़े की भी जांच करता है। बाधा संतुष्टि समस्याओं को हल करने के लिए लुक-फॉरवर्ड का उपयोग करने का सबसे आम तरीका आर्क-कंसिस्टेंसी (MAC) एल्गोरिदम को बनाए रखना है। चाप स्थिरता से जुड़े दो अन्य तरीके हैं पूर्ण और आंशिक रूप से आगे देखें। वे चाप स्थिरता को लागू करते हैं, लेकिन चर की हर जोड़ी के लिए नहीं। विशेष रूप से, पूर्ण रूप असंबद्ध चर की प्रत्येक जोड़ी पर विचार करता है, और उनके बीच चाप स्थिरता को लागू करता है। यह वैश्विक चाप स्थिरता को लागू करने से अलग है, जिसके लिए संभवतः चर की एक जोड़ी पर एक से अधिक बार पुनर्विचार करने की आवश्यकता हो सकती है। इसके बजाय, एक बार जब आगे की पूरी नज़र से चर की एक जोड़ी के बीच चाप स्थिरता लागू हो जाती है, तो जोड़ी को अब और नहीं माना जाता है। आगे आंशिक रूप से देखना समान है, लेकिन चर के दिए गए क्रम पर विचार किया जाता है, और चाप की स्थिरता प्रत्येक जोड़ी के लिए केवल एक बार लागू की जाती है। चाप स्थिरता के आधार पर आगे देखें पथ स्थिरता और सामान्य आई-स्थिरता या संबंधपरक चाप स्थिरता के साथ काम करने के लिए भी बढ़ाया जा सकता है। आगे देखने का उपयोग आगे देखने के परिणामों का उपयोग मूल्यांकन करने के लिए अगले चर और इस चर को देने के लिए मूल्यों का क्रम तय करने के लिए किया जाता है। विशेष रूप से, किसी भी असंबद्ध चर और मूल्य के लिए, आगे देखें उस चर को उस मूल्य पर स्थापित करने के प्रभावों का अनुमान लगाता है। अगले चर का चयन और इसे देने के लिए अगले मूल्य का चयन पूरक है, जिसमें मूल्य को आम तौर पर इस तरह से चुना जाता है कि एक समाधान (यदि कोई हो) जितनी जल्दी हो सके पाया जाता है, जबकि अगले चर को आम तौर पर इस तरह से चुना जाता है कि असंतोष (यदि वर्तमान आंशिक समाधान असंतोषजनक है) जितनी जल्दी हो सके साबित हो जाता है। मूल्यांकन के लिए अगले चर का चयन विशेष रूप से महत्वपूर्ण है, क्योंकि यह चलने के समय में घातीय अंतर पैदा कर सकता है। जितनी जल्दी हो सके असंतोषजनक साबित करने के लिए, सौंपे जाने के बाद कुछ विकल्प छोड़ने वाले चर पसंदीदा हैं। इस विचार को केवल परिवर्तनीय/मूल्य जोड़े की संतोषजनकता या असंतोषजनकता की जांच करके लागू किया जा सकता है। विशेष रूप से, अगला चर जो चुना जाता है वह वह है जिसमें न्यूनतम संख्या में मान होते हैं जो वर्तमान आंशिक समाधान के अनुरूप होते हैं। बदले में, स्थिरता का मूल्यांकन केवल आंशिक स्थिरता की जांच करके, या ऊपर चर्चा की गई किसी भी मानी गई लुक फॉरवर्ड तकनीक का उपयोग करके किया जा सकता है। एक चर को अस्थायी रूप से निर्धारित करने के लिए मूल्यों को क्रमबद्ध करने के लिए निम्नलिखित तीन तरीके हैंः न्यूनतम-संघर्षः पसंदीदा मूल्य वे हैं जो असंबद्ध चर के क्षेत्र से कम से कम कुल मूल्यों को हटाते हैं जैसा कि आगे देखते हुए मूल्यांकन किया जाता है; अधिकतम-क्षेत्र-आकारः पसंदीदा मूल्य वे हैं जो असंबद्ध चर के लिए सबसे छोटे क्षेत्र में मूल्यों की संख्या को अधिकतम करते हैं, जैसा कि आगे देखते हुए मूल्यांकन किया जाता है; समाधान का अनुमान लगाएंः पसंदीदा मूल्य वे हैं जो समाधानों की अधिकतम संख्या का उत्पादन करते हैं, जैसा कि इस धारणा को आगे देखते हुए मूल्यांकन किया जाता है कि असंबद्ध चर के क्षेत्र में बचे सभी मूल्य एक दूसरे के अनुरूप हैं; दूसरे शब्दों में, मूल्य के लिए वरीयता आगे देखने के परिणामस्वरूप सभी क्षेत्र के आकार को गुणा करके प्राप्त की जाती है। प्रयोगों ने साबित किया कि ये तकनीकें बड़ी समस्याओं, विशेष रूप से लघु-संघर्षों के लिए उपयोगी हैं। यादृच्छिककरण का उपयोग कभी-कभी एक चर या मूल्य चुनने के लिए भी किया जाता है। उदाहरण के लिए, यदि किसी माप के अनुसार दो चरों को समान रूप से पसंद किया जाता है, तो चयन यादृच्छिक रूप से किया जा सकता है। संदर्भ बाधा प्रोग्रामिंग खोज एल्गोरिदम