अध्याय २ · खण्ड II · 14 मिनेट
एआईले समस्या समाधान
हेरिस्टिकले प्रणालीलाई अधिकांश खोजी-स्थान नछोडी समाधानसम्म कसरी पुर्याउँछ — र कहाँ चुक्छ।
ठमेलबाट भक्तपुर पुग्ने हरेक सम्भावित बाटो अन्धो खोजी गर्ने हो भने काम सकिन्छ, सकिन्छ, तर तपाईंको दालभातका लागि होइन। खोजीलाई व्यवहारमा उपयोगी बनाउने एउटै चलाखी छ, र त्यसलाई एउटै शब्दले बुझाइन्छ: हेरिस्टिक।
हेरिस्टिक छिटो, सस्तो, प्राय: गलत हुने अनुमान हो — लक्ष्य कति टाढा छ भन्ने। एल्गोरिथमले त्यो अनुमान प्रयोग गरेर कुन बाटो अघि बढ्ने निर्णय गर्छ। राम्रो हेरिस्टिकले असम्भव समस्यालाई हल हुने बनाउँछ। नराम्रो हेरिस्टिकले विश्वासका साथ गलत बाटो हिँडाउँछ।
सीधा-रेखाको हेरिस्टिक
उपत्यकाको नक्सा खोल्नुहोस्। ठमेलबाट पूर्व, भक्तपुरसम्म एउटा सीधा रेखा कोर्नुहोस्। त्यो रेखाको लम्बाइ — कौवा-उडान दूरी — तपाईंलाई अझै कति यात्रा बाँकी छ भन्ने हेरिस्टिक अनुमान हो।
यो वास्तविक दूरी होइन। वास्तविक दूरी लामो छ; बाटो बङ्ग्याउँछ, उक्लन्छ, र विमानस्थल वरिपरि घुम्छ। तर सीधा-रेखा दूरी उपयोगी अनुमान हो: जुन चोकको सीधा-रेखा दूरी कम छ, सायद, त्यो चोक सडक-दूरीमा पनि भक्तपुरको नजिक छ।
त्यो शब्द — सायद — ले सबै काम गरिरहेको छ। हेरिस्टिकलाई गलत हुने छुट छ। यसले अनियमित अनुमानले गर्ने भन्दा कम पटक मात्र गल्ती गरे पुग्छ।
एक अनुच्छेदमा A*
हेरिस्टिक-चालित सबैभन्दा प्रसिद्ध खोजी एल्गोरिथमको नाम A* हो (उच्चारण “ए-स्टार”)। हरेक चरणमा A* सोध्छ: अब कुन चोक अन्वेषण गर्ने? जवाफ हो — यो योगफल न्यून गराउने चोक:
(हालसम्म हिँडेको दूरी) + (बाँकी दूरीको हेरिस्टिक अनुमान)
पूरा विचार त्यति नै हो। यसले तपाईंलाई थाहा भएको कुरा — कति हिँड्नुभयो — र अनुमान — कति बाँकी छ — दुवैलाई जोड्छ। हेरिस्टिक राम्रो छ भने A* ले नक्साको थोरै भाग मात्र अन्वेषण गरेर उत्तम मार्ग फेला पार्छ। हेरिस्टिक एकदम सही छ भने A* सीधै लक्ष्यमा पुग्छ। हेरिस्टिक निरर्थक छ भने A* ढिलो BFS मा झर्छ।
तपाईंले प्रयोग गरेका सबै नेभिगेसन एप — गुगल म्याप्स, पठाओ, बाटो — A* वा त्यसको परिष्कृत संस्करण चलाइरहेका छन्।
उदाहरण: ठमेलदेखि भक्तपुरसम्म
अनौपचारिक रूपमा चलाऔं। ठमेलबाट A* ले तीन छिमेकी चोक हेर्छ — लैनचौर (उत्तर), नक्साल (पूर्व), र क्षेत्रपाटी (दक्षिण)।
- लैनचौर: २०० मि. हिँडियो, भक्तपुरको सीधा-रेखा दूरी १३.० किमि। कुल अनुमान: १३.२ किमि।
- नक्साल: २५० मि. हिँडियो, भक्तपुरको सीधा-रेखा दूरी १२.५ किमि। कुल अनुमान: १२.७५ किमि।
- क्षेत्रपाटी: ३०० मि. हिँडियो, भक्तपुरको सीधा-रेखा दूरी १३.४ किमि। कुल अनुमान: १३.७ किमि।
नक्साल जित्छ, त्यसैले A* ले अब नक्सालका छिमेकीहरू अन्वेषण गर्छ। प्रक्रिया दोहोरिन्छ। हरेक चरणमा एल्गोरिथमले न्यूनतम कुल-अनुमान भएको बाटो खोज्छ। हामी पूर्व लाग्दा सीधा-रेखा दूरी घट्दै जान्छ; दक्षिण वा पश्चिमका चोकहरूको अनुमान बढ्छ र चुपचाप छुट्छन्।
A* ले लैनचौर अन्वेषण गर्दैन, किनभने लैनचौर गलत दिशामा छ। यही नै पूरै फाइदा हो। अन्धो BFS ले लैनचौर पूरा अन्वेषण गरिसकेपछि मात्रै यो काम बेकार रहेछ भनेर थाहा पाउँथ्यो।
हेरिस्टिक कहाँ चुक्छ
हेरिस्टिक दुई तरिकामा गलत हुन सक्छ, र दुवैको परिणाम धेरै फरक छ।
आशावादी (कम अनुमान गर्ने)। हेरिस्टिकले लक्ष्यलाई वास्तविकभन्दा नजिक देखाउँछ। यो सुरक्षित हो: A* ले अझै पनि उत्तम मार्ग फेला पार्छ, केही धेरै चोक अन्वेषण गर्छ। सीधा-रेखा दूरी आशावादी हो — सडक सधैं कौवा-रेखाजति लामो वा बढी हुन्छ।
निराशावादी (बढी अनुमान गर्ने)। हेरिस्टिकले लक्ष्यलाई वास्तविकभन्दा टाढा देखाउँछ। यो खतरनाक हो: A* ले उत्तम मार्गलाई निराशाजनक ठानेर खराब बाटो छनोट गर्न सक्छ। एल्गोरिथमले एक जवाफ दिनेछ; तर त्यो उत्तम चाहिँ हुँदैन।
नेभिगेसनका लागि आशावादी हेरिस्टिक डिजाइन गर्न सजिलो छ (सीधा-रेखा एक उदाहरण)। अन्य समस्या — रुबिक्स क्युब, विद्यालय रुटिन — का लागि सूचनात्मक र प्रमाणित रूपले आशावादी हेरिस्टिक डिजाइन गर्ने काम अनुसन्धान करियर बन्न सक्छ।
जब संसार सडक नक्सा होइन
A* लाई नक्सामा कोरिएकोमा फरक पर्दैन। यो अवस्था, कार्य, लक्ष्य, र लागतमा व्यक्त गर्न मिल्ने जुनसुकै समस्यामा काम गर्छ। केही वास्तविक उदाहरण:
- वायुयानको मार्ग। अवस्था 3D आकाशमा बिन्दु हुन्; कार्य दिशा परिवर्तन; लागत इन्धन; हेरिस्टिक गन्तव्य विमानस्थलसम्मको ग्रेट-सर्कल दूरी।
- रोबोट गति योजना। बिर्गन्जको कारखानामा रोबोटले एक स्थानबाट अर्कोमा चीज नठोक्ने गरी हिँड्नुपर्छ। अवस्था जोइन्ट कोणहरू हुन्। कार्य साना गति। हेरिस्टिक जोइन्ट-स्पेसमा सीधा-रेखा दूरी।
- सफ्टवेयर प्रमेय प्रमाणन। अवस्था आंशिक प्रमाणहरू; कार्य निष्कर्ष चरण; हेरिस्टिक भनेको आंशिक प्रमाण थाहा भएको पूरा प्रमाणजस्तो कति देखिन्छ।
ढाँचा दोहोरिन्छ। चार शब्द परिभाषित गर्नुहोस्। उपयुक्त हेरिस्टिक खोज्नुहोस्। A* चलाउनुहोस्। काम सकियो।
सीमाहरू
A* शक्तिशाली छ, तर जादू होइन। दुई असफलता मोड बुझ्न जरुरी छ।
-
अवस्था-स्थान मेमोरीमा अटाउँदैन। चेसका अवस्था ब्रह्माण्डका परमाणुभन्दा बढी छन्। A* ले तिनको सानो अंश पनि भण्डारण गर्न सक्दैन। यस्ता समस्याका लागि बेग्लै एल्गोरिथम — मोन्टे कार्लो ट्री सर्च, डीप रिइन्फोर्समेन्ट लर्निङ — आविष्कार गरिए।
-
लागत-कार्य खोजी मध्येमा बदलिन्छ। ५:५५ बजे योजना गरिएको पठाओ मार्ग ६:०१ मा मैतीघरमा दुर्घटना भएर बाटो बन्द हुँदा अमान्य हुन्छ। वास्तविक प्रणालीहरूले निरन्तर, प्रति केही सेकेन्डमा, पुरानो जवाफ हटाएर पुनर्योजना गर्छन्।
यी सीमाले A* लाई अप्रचलित बनाउँदैनन्। यिनले A* कहिले र अरू केही कहिले प्रयोग गर्ने भन्ने बताउँछन्। दुवै तर्फको निर्णय एआई-साक्षरताको अंश हो।
आफ्नो बुझाइ जाँच्नुहोस्
छोटो जाँच
—खोजी एल्गोरिथममा हुने हेरिस्टिकले के दिन्छ?
अब के?
हामीले हेरिस्टिक प्रयोग गरेर निराशाजनक खोजीलाई सम्भव खोजीमा बदल्यौं। अर्को खण्डले गाह्रो काम थप्छ: तपाईंलाई हराउन सक्रिय रूपमा कोशिस गरिरहेको प्रतिद्वन्द्वी छ भने खोजी कसरी गर्ने। स्वागत छ — खेल खेल्ने एआईमा।