AI में खोज एल्गोरिदम: कदम-दर-कदम रास्ता ढूँढना

AI में खोज और अवस्था-आकाश

बहुत-सी समस्याएँ खोज से हल होती हैं: संभव कदमों को व्यवस्थित ढंग से आज़माना, जब तक लक्ष्य न मिले।

कंप्यूटर से खोज करवाने के लिए समस्या को अवस्था-आकाश (state space) की तरह लिखते हैं:

• अवस्था (state): एक स्थिति, जैसे भूल-भुलैया में रोबोट का खाना।
• प्रारंभिक अवस्था: जहाँ से शुरू करते हैं (S)।
• क्रियाएँ (actions): किसी अवस्था से संभव चालें (ऊपर, नीचे, दाएँ, बाएँ)।
• लक्ष्य-जाँच (goal test): जो बताए कि "पहुँच गए" (G)।
• पथ-लागत (path cost): रास्ते की कीमत, जैसे चालों की गिनती।

अवस्थाएँ और चालें मिलकर एक ग्राफ़ या खोज-वृक्ष (search tree) बनाती हैं। शुरू से लक्ष्य तक का रास्ता हल है; सबसे सस्ता हल इष्टतम (optimal) है।

खुलने का इंतज़ार कर रही अवस्थाओं की सूची को फ़्रंटियर (frontier) कहते हैं। किसी अवस्था को खोलने का मतलब है उसके पड़ोसी देखना और नए पड़ोसियों को फ़्रंटियर में डालना। अलग-अलग एल्गोरिदम बस यह तय करते हैं कि फ़्रंटियर से अगली अवस्था कौन-सी खुलेगी।

अंधी (अनसूचित) खोज: BFS और DFS

अंधी (uninformed) खोज को केवल समस्या के नियम पता होते हैं। लक्ष्य किस दिशा में है, यह उसे नहीं पता।

चौड़ाई-पहले खोज (BFS)

BFS स्तर-दर-स्तर खोलती है: पहले 1 चाल दूर की सारी अवस्थाएँ, फिर 2 चाल दूर की। इसका फ़्रंटियर एक कतार (queue) है: जो पहले आया, वह पहले खुला।

• पूर्ण (complete): हल हो तो ज़रूर मिलेगा।
• हर चाल की लागत बराबर हो तो इष्टतम: पहला मिला रास्ता ही सबसे छोटा।
• बहुत मेमोरी चाहिए, क्योंकि पूरा स्तर एक साथ याद रखना पड़ता है।

गहराई-पहले खोज (DFS)

DFS एक रास्ते पर गहरे जाती है और अटकने पर ही पीछे लौटती (backtrack) है। इसका फ़्रंटियर एक ढेर (stack) है: जो आख़िर में आया, वह पहले खुला।

• कम मेमोरी: बस मौजूदा रास्ता और उसकी शाखाएँ।
• इष्टतम नहीं: पहला रास्ता लंबा हो सकता है।
• बहुत गहरे या अंतहीन आकाश में भटक सकती है, जब तक गहराई की सीमा न हो।

दूसरी अंधी विधियाँ: एकसमान-लागत खोज (uniform-cost), जो अब तक के सबसे सस्ते रास्ते को खोलती है, और क्रमिक गहराई (iterative deepening), जो गहराई सीमा 1, 2, 3… के साथ बार-बार DFS चलाती है।

सूचित खोज: ह्यूरिस्टिक, लालची खोज और A*

ह्यूरिस्टिक (heuristic) h(n) एक तेज़, समझदार अनुमान है कि अवस्था n लक्ष्य से कितनी दूर है। ग्रिड में अच्छा अनुमान है मैनहट्टन दूरी: h = |x − x_G| + |y − y_G|। यह दीवारों को नज़रअंदाज़ करती है, इसलिए जल्दी निकलती है।

• लालची सर्वोत्तम-पहले खोज (greedy best-first) हमेशा सबसे छोटे h वाली अवस्था खोलती है। तेज़ है, पर दीवारें इसे धोखा दे सकती हैं और रास्ता हमेशा सबसे छोटा नहीं होता।
• A* खोज सबसे छोटे f = g + h वाली अवस्था खोलती है, जहाँ g शुरू से अब तक की असली लागत है। यह "कितना चल चुके" और "कितना बाक़ी लगता है" दोनों को तौलती है।

अगर ह्यूरिस्टिक स्वीकार्य (admissible) है, यानी असली दूरी से कभी ज़्यादा अनुमान नहीं लगाती, तो A* हमेशा सबसे छोटा रास्ता देता है। अनुमान जितना सच के क़रीब, A* उतनी कम अवस्थाएँ खोलता है।

सड़क नक्शे पर सीधी-रेखा दूरी और ग्रिड पर मैनहट्टन दूरी, दोनों स्वीकार्य हैं। h = 0 रखें तो A* एकसमान-लागत खोज बन जाता है।

जिन समस्याओं में समझदार खोज चाहिए: रास्ते, पहेलियाँ, खेल

रास्ते: नक्शे पर मार्ग, रोबोट की चाल, नेटवर्क रूटिंग। अवस्थाएँ जगहें हैं; लागत दूरी या समय। आम तौर पर A* चुना जाता है।

पहेलियाँ: 8-पज़ल, रूबिक क्यूब, सुडोकू, पानी के जग वाली पहेली। अवस्थाओं की संख्या बहुत तेज़ी से बढ़ती है (संयोजनात्मक विस्फोट), इसलिए अंधी खोज बहुत धीमी पड़ती है और ह्यूरिस्टिक चाहिए।

खेल: शतरंज या टिक-टैक-टो में दो खिलाड़ी बारी-बारी चलते हैं। खेल-वृक्ष (game tree) में मेरी चालें, फिर विरोधी के जवाब होते हैं। मिनीमैक्स (minimax) मानता है कि विरोधी अपनी सबसे अच्छी चाल चलेगा: मैं वह चाल चुनता हूँ जिसका सबसे बुरा नतीजा भी मेरे लिए सबसे अच्छा हो। अल्फ़ा-बीटा छँटाई उन शाखाओं को छोड़ देती है जो फ़ैसला नहीं बदल सकतीं। प्रोग्राम एक तय गहराई पर रुककर मूल्यांकन फलन (स्थिति का अनुमानित अंक) लगाते हैं।

आधा-आधा करके खोज: बाइनरी सर्च और द्विभाजन

कुछ खोजें भूल-भुलैया में नहीं, बल्कि क्रमबद्ध सूची या संख्या रेखा पर होती हैं। यहाँ हर कदम पर काम आधा हो जाता है।

• बाइनरी सर्च: क्रमबद्ध सूची के बीच वाले को देखो। लक्ष्य छोटा है तो बायाँ आधा, बड़ा है तो दायाँ आधा रखो। 1000 चीज़ों में अधिकतम 10 बार देखना पड़ता है, क्योंकि 2¹⁰ = 1024।
• द्विभाजन (bisection): a और b के बीच f(x) = 0 कहाँ है, यह ढूँढने के लिए (जब f(a), f(b) के चिह्न उलटे हों) बीच का बिंदु जाँचो और वह आधा रखो जहाँ चिह्न बदलता है। हर कदम पर त्रुटि आधी होती है। इससे वर्गमूल भी मिलता है: √2, x² − 2 = 0 का मूल है।

दोनों में समस्या की जानकारी (सूची क्रमबद्ध है, चिह्न बदलता है) से सब कुछ जाँचने से बचते हैं; यही ह्यूरिस्टिक का विचार है।

करके देखें

3D में: फ़्री प्ले में लक्ष्य से दूर एक छेद वाली लंबी दीवार बनाइए। अनुमान लगाइए: क्या A* अब भी BFS से कम खाने खोलेगा? दोनों चलाकर "खुले खाने" और "रास्ते की लंबाई" लिखिए।

घर पर: काग़ज़ पर 5 × 5 ग्रिड बनाइए, कोनों में S और G रखिए और 5 दीवारें रंगिए। किनारे पर एक कतार लिखते हुए BFS जिस क्रम में खाने खोलेगी, वे नंबर लिखिए। फिर हर खाने में G तक मैनहट्टन दूरी लिखकर A* से दोहराइए।

मुख्य सूत्र और परिभाषाएँ

• समस्या = प्रारंभिक अवस्था + क्रियाएँ + लक्ष्य-जाँच + पथ-लागत
• BFS फ़्रंटियर = कतार (FIFO); DFS फ़्रंटियर = ढेर (LIFO)
• मैनहट्टन दूरी: h = |x − xG| + |y − yG|
• A*: f(n) = g(n) + h(n); सबसे छोटा f पहले खोलो
• स्वीकार्य ह्यूरिस्टिक: h(n) ≤ लक्ष्य तक असली लागत → A* इष्टतम
• n चीज़ों में बाइनरी सर्च: अधिकतम ⌈log₂(n + 1)⌉ बार देखना

हल किए गए उदाहरण

आम गलतियाँ

• यह मानना कि DFS हमेशा सबसे छोटा रास्ता देती है। वह कोई रास्ता देती है, अक्सर लंबा; सबसे छोटा BFS (बराबर लागत) या A* (स्वीकार्य h) देते हैं।
• फ़्रंटियर उलझा देना: BFS में कतार (पहले आया, पहले गया), DFS में ढेर (आख़िर में आया, पहले गया)।
• ज़्यादा अनुमान लगाने वाली ह्यूरिस्टिक लेकर भी A* से सबसे छोटे रास्ते की उम्मीद करना। केवल स्वीकार्य ह्यूरिस्टिक ही यह गारंटी देती है।
• देखी हुई अवस्थाओं पर निशान न लगाना, जिससे खोज गोल-गोल घूमती रहती है और काम दोहराती है।