अध्याय २ · खण्ड I · 18 मिनेट
खोजी र समस्या समाधान
मेसिनले आफूलाई थाहा नभएको उत्तर कसरी फेला पार्छ — ठमेलबाट भक्तपुर पुग्ने सरल समस्याबाट देखाइन्छ।
धेरै एआई समस्याहरू, मूलमा, खोजी समस्या हुन्। तपाईंसँग सुरुवात अवस्था छ। लक्ष्य अवस्था छ। एक अवस्थाबाट अर्को अवस्थामा पुर्याउने वैध चालहरूको सेट छ। प्रणालीको काम हो — सुरुवातदेखि लक्ष्यसम्म पुर्याउने चालहरूको क्रम, र सकभर उत्तम क्रम पत्ता लगाउनु।
यो विवरण अमूर्त सुनिन्छ। उदाहरण अमूर्त छैन। यो त्यही हो — पठाओले तपाईंको राइडरलाई ठमेलबाट भक्तपुरको तपाईंको घरसम्म कसरी पुर्याउँछ।
खोजीका चार शब्द
एल्गोरिथमतर्फ जानु अघि चार शब्द तय गरौं। यो अध्यायभर तिनै शब्द प्रयोग गरिनेछन्।
- अवस्था (State)। तपाईं कहाँ हुनुहुन्छ भन्ने स्न्यापसट। मार्गका लागि यो चोक हो। चेसका लागि बोर्डको अवस्था। सुडोकुका लागि आंशिक रूपमा भरिएको ग्रिड।
- कार्य (Action)। एउटा अवस्थाबाट अर्कोमा पुर्याउने वैध चाल। बाटो लिनु। प्यादा सार्नु। सेलमा अंक लेख्नु।
- लक्ष्य (Goal)। तपाईं पुग्न खोजेको अवस्था। भक्तपुर। चेकमेट। भरिएको ग्रिड।
- लागत (Cost)। एउटा कार्य कति महँगो छ। हिँडेको किलोमिटर। बितेको मिनेट। चालिएको चाल।
लगभग हरेक शास्त्रीय एआई समस्या यो ढाँचामा अटाउँछ। एक पटक तपाईंले समस्यालाई यी चार शब्दमा लेख्न सक्नुभयो भने त्यसमा कुनै न कुनै खोजी एल्गोरिथम लागू गर्न सकिन्छ।
नक्सा हिँड्ने दुई तरिका
कल्पना गर्नुहोस् — तपाईं ठमेलको चोकमा उभिएर तीन बाटा देख्दै हुनुहुन्छ। प्रत्येक बाटोले अर्को चोकमा पुर्याउँछ, जहाँ फेरि तीन बाटा छन्। केही पाइला अघि गएपछि सम्भावित बाटाहरूको संख्या विस्फोट हुन्छ। कुन बाटो हिँड्ने भनेर कसरी छान्ने?
दुई साधारण रणनीति छन्। दुवै थाहा पाउनुपर्छ, किनकि यिनै दुईको परिष्कृत रूप नै आधुनिक एल्गोरिथम हुन्।
ब्रेथ-फर्स्ट खोजी (BFS)। प्रत्येक बाटोमा एक पाइला चलिनुहोस्। त्यसपछि ती चोकहरूबाट निस्कने प्रत्येक बाटोमा एक पाइला। यसरी सुरुवातबिन्दु वरिपरि बढ्दो रिङमा नक्सा अन्वेषण गर्नुहोस्। सबैभन्दा थोरै पाइलामा पुग्ने लक्ष्य तपाईंले पाउनुहुन्छ — तर नक्सा ठूलो भयो भने तपाईंले अधुरो हिँडेको हरेक बाटो सम्झनुपर्ने हुन्छ।
डेप्थ-फर्स्ट खोजी (DFS)। एउटा बाटो रोज्नुहोस्, अन्तिमसम्म हिँड्नुहोस्। बाटो बन्द भयो भने फर्केर अर्को बाटो प्रयास गर्नुहोस्। तपाईं नक्सा लामो-पातला धागोमा अन्वेषण गर्नुहुन्छ। मेमोरी थोरै लाग्छ — हालको बाटो मात्र सम्झे पुग्छ — तर तपाईं घण्टौंसम्म डेड-एन्डमा हिँड्न सक्नुहुन्छ।
BFS धैर्यवान् र पूर्ण छ। DFS दृढ र भुलक्कड छ। काठमाडौंजस्तो शहरका लागि कुनै पनि एक्लै पर्याप्त छैन।
अन्धो खोजी किन पर्याप्त छैन
काठमाडौंमा झन्डै दसौं हजार सडक खण्ड छन्। भक्तपुर एउटा निश्चित चोक हो। ठमेलबाट अन्धो BFS ले पहिले एक किलोमिटर भित्रका सबै बाटा अन्वेषण गर्थ्यो, त्यसपछि दुई किलोमिटर भित्रका, त्यसपछि तीन भित्रका — पूर्व दिशा अर्थात् भक्तपुरतर्फ बहाव नदिईकन। यो सकिँदा-सकिँदै तपाईंको राइडर घरै पुगिसक्थ्यो।
समस्या यो हो — BFS र DFS लाई लक्ष्य कुन दिशामा छ थाहै हुँदैन। तिनले डाटा संरचनामा जुन क्रममा बाटा छन् त्यही क्रममा हिँड्छन्। एल्गोरिथमलाई भन्ने तरिका चाहिन्छ: भक्तपुर पूर्वमा छ। पूर्व जाने बाटा प्राथमिकतामा राख।
त्यो संकेतलाई हेरिस्टिक (heuristic) भनिन्छ। अर्को खण्ड त्यसैको बारेमा छ।
पठाओले वास्तवमा के गर्दैछ
साँझ ६ बजे नक्सालमा पठाओको राइडरले पाटनको गन्तव्यसहित एप खोल्दा, प्रणालीले ग्राफमा खोजी एल्गोरिथम चलाइरहेको हुन्छ। अवस्थाहरू चोक हुन्। कार्यहरू सडक खण्ड हुन्। लागत भनेको अपेक्षित यात्रा समय हो — विगतका ट्राफिक ढाँचा र हाल कुन बाटा जाम छन् भन्ने रियल-टाइम जानकारी समेत समावेश।
एल्गोरिथम BFS होइन। DFS होइन। यो A* को कुनै रूप हो — अर्को खण्डमा भेट्ने एल्गोरिथम — जुन सिङ्गापुरको सर्भरमा, मिलिसेकेन्डमा, उपत्यकाको हरेक सडकको ग्राफमा चलिरहेको हुन्छ। फर्केर आउने मार्ग “सबैभन्दा छोटो बाटो” होइन। यो “इन्जिनियरले छानेको लागत-कार्यअनुसार सबैभन्दा सस्तो बाटो” हो। लागत-कार्यले दूरीलाई जोड दियो भने तपाईं छोटो रुट पाउनुहुन्छ। समय जोड दियो भने छिटो। राइडरको आम्दानीलाई जोड दियो भने बेग्लै।
कुन लागत-कार्य प्रयोगमा छ भनेर थाहा पाउनु एआई-साक्षरताको अंश हो। मार्ग एक सटीक प्रश्नको जवाफ हो — र त्यो प्रश्न रोज्ने मानवीय निर्णय हो।
जब समस्या सडक नक्सा जस्तो देखिँदैन
शास्त्रीय एआईको चलाखी भनेको — समस्या नक्सा जस्तो नदेखिए पनि यसलाई खोजीको रूपमा फ्रेम गर्न सकिन्छ भनेर पहिचान गर्नु हो। तीन छोटा उदाहरण:
-
रुटिन/तालिका। विद्यालयको रुटिन एक खोजी समस्या हो। अवस्थाहरू आंशिक रुटिन हुन्। कार्यहरू “यो शिक्षकलाई यो पिरियडमा राख्” हुन्। लक्ष्य द्वन्द्व नभएको पूर्ण रुटिन हो। लागत प्रिन्सिपलले घटाउन चाहेको कुरा — उदाहरणका लागि शनिबार आउनुपर्ने शिक्षकको संख्या।
-
लजिस्टिक्स। दिनको डेलिभरी योजना बनाउने कम्पनी ड्राइभिङ समय न्यून बनाउने स्टपहरूको क्रम खोज्दैछ। अवस्था आंशिक मार्ग हुन्; कार्य “यो स्टप अर्को थप्” हो।
-
पजल सुल्झाउने। सुडोकु भर्ने, रुबिक्स क्युब मिलाउने, मेजबाट निस्कने बाटो खोज्ने — सबै बेग्लै अवस्था-स्थानसहितका खोजी समस्या।
समस्यालाई हाम्रा चार शब्दमा वर्णन गर्न सक्नुभयो भने — अवस्था, कार्य, लक्ष्य, लागत — त्यसमा आक्रमण गर्न कतै न कतै खोजी एल्गोरिथम छ।
आफ्नो बुझाइ जाँच्नुहोस्
छोटो जाँच
—ब्रेथ-फर्स्ट खोजी (BFS) र डेप्थ-फर्स्ट खोजी (DFS) मुख्यत: कुन कुरामा फरक हुन्छन्?
छोटो जाँच
—भरतपुरमा ३० वटा डेलिभरी स्टप घुम्ने सबैभन्दा सस्तो क्रम योजना गर्न खोज्ने लजिस्टिक्स कम्पनीका लागि कुन फ्रेमिङ सही हो?
अब के?
भाषा तय भयो। अर्को खण्ड शास्त्रीय एआई खोजीलाई व्यवहारिक बनाउने एउटै चलाखीबारे छ — हेरिस्टिक। हामी A* प्रयोग गरेर ठमेल-भक्तपुर मार्ग सही ढंगले योजना गर्नेछौं, र अनुमान धेरै आशावादी भयो भने के हुन्छ हेर्नेछौं।