खोज, खेल-खेलना व तर्कसंगत अभिकर्ता

अभ्यास प्रश्न (8)

उत्तर खोलने से पहले प्रत्येक प्रश्न हल करें। हर व्याख्या सही विकल्प के साथ लुभावना गलत विकल्प भी बताती है, क्योंकि अंक वहीं जाते हैं।

1. ट्यूरिंग परीक्षण की तुलना में, तर्कसंगत अभिकर्ता फ्रेमिंग व्यापकतर कसौटी है क्योंकि:

   1. यह किसी भी अभिकर्ता पर लागू होती है जो प्रदर्शन-मापक अधिकतम करे, चाहे मानव-सदृश वार्तालाप प्रासंगिक हो या न हो
   2. यह अभिकर्ता को पाठ-वार्तालाप परीक्षण पास करने की माँग करती है
   3. यह केवल शतरंज-खेलने वाले प्रोग्रामों पर लागू होती है
   4. यह हर प्रकार से ट्यूरिंग परीक्षण के समान है
   उत्तर देखें

   उत्तर: A — यह किसी भी अभिकर्ता पर लागू होती है जो प्रदर्शन-मापक अधिकतम करे, चाहे मानव-सदृश वार्तालाप प्रासंगिक हो या न हो

   थर्मोस्टैट या स्व-चालित कार तर्कसंगत अभिकर्ता हो सकते हैं बिना कभी मानव-सदृश वार्तालाप की आवश्यकता के, यही ठीक वह कारण है कि यह कसौटी ट्यूरिंग परीक्षण की वार्तालाप-फ्रेमिंग से कहीं अधिक व्यापक रूप से लागू होती है।

2. 'मान्य' अनुमानी h(n) का अर्थ है:

   1. यह लक्ष्य तक वास्तविक शेष लागत को कभी अत्यधिक-आकलित नहीं करती
   2. यह वास्तविक शेष लागत को सदा अत्यधिक-आकलित करती है
   3. यह लक्ष्य-अवस्था को पूर्णतः नज़रअंदाज़ करती है
   4. यह सदा ठीक शून्य है
   उत्तर देखें

   उत्तर: A — यह लक्ष्य तक वास्तविक शेष लागत को कभी अत्यधिक-आकलित नहीं करती

   मान्यता (h(n) ≤ वास्तविक शेष लागत, सदा) ठीक वही शर्त है जो A* को इष्टतम गारंटी देने हेतु चाहिए, क्योंकि यह खोज को किसी बुरे पथ के विषय में कभी झूठा आशावादी होने से रोकती है।

3. मिन-मैक्स खोज में, MIN खिलाड़ी वह चाल चुनता है जो इस ओर ले जाती है:

   1. न्यूनतम मान वाली संतति
   2. सर्वाधिक मान वाली संतति
   3. यादृच्छिक रूप से चुनी संतति
   4. बिल्कुल कोई संतति नहीं
   उत्तर देखें

   उत्तर: A — न्यूनतम मान वाली संतति

   MIN को उस विरोधी के रूप में प्रतिरूपित किया जाता है जो सदा MAX के अंतिम परिणाम को न्यूनतम करने खेलता है, अतः MIN सदा वह चाल चुनता है जो अपनी संतति में न्यूनतम मान की ओर ले जाए।

4. सादे मिन-मैक्स की तुलना में, अल्फ़ा-बीटा छंटाई का सर्वोत्तम वर्णन है:

   1. सिद्ध रूप से अप्रासंगिक शाखाएँ छोड़कर, तेज़ी से, ठीक वही चाल लौटाना
   2. समय बचाने हेतु भिन्न, सन्निकट चाल लौटाना
   3. केवल एकल-खिलाड़ी खेलों में प्रयोग करने योग्य
   4. विरोधी की चालों को पूर्णतः नज़रअंदाज़ करना
   उत्तर देखें

   उत्तर: A — सिद्ध रूप से अप्रासंगिक शाखाएँ छोड़कर, तेज़ी से, ठीक वही चाल लौटाना

   वही मूल्यांकन-फलन व गहराई देखते हुए अल्फ़ा-बीटा की छाँटी शाखाएँ अंतिम निर्णय हेतु सिद्ध रूप से अप्रासंगिक हैं, अतः यह सदा ठीक वही लौटाती है जो सादा मिन-मैक्स देता, बस तेज़ी से गणित।

5. वास्तविक शतरंज इंजन खेल के वास्तविक अंत तक पूरा खेल-वृक्ष मुख्यतः इसलिए नहीं खोज सकते:

   1. अवस्था-समष्टि संपूर्ण खोज हेतु बहुत विशाल है, अतः इसके बजाय गहराई-सीमित खोज व मूल्यांकन-फलन प्रयोग किया जाता है
   2. शतरंज में कोई अंतिम अवस्था बिल्कुल नहीं है
   3. शतरंज पर मिन-मैक्स लागू नहीं किया जा सकता
   4. शतरंज में अल्फ़ा-बीटा छंटाई अवैध है
   उत्तर देखें

   उत्तर: A — अवस्था-समष्टि संपूर्ण खोज हेतु बहुत विशाल है, अतः इसके बजाय गहराई-सीमित खोज व मूल्यांकन-फलन प्रयोग किया जाता है

   शतरंज का शाखन-गुणक व खेल-लंबाई संपूर्ण खोज को गणनात्मक रूप से असंभव बनाते हैं, अतः इंजन केवल परिबद्ध गहराई खोजते हैं व वास्तविक खेल-समापक अवस्था तक खोजने के बजाय मूल्यांकन-फलन से अ-अंतिम स्थितियों का मूल्य आकलित करते हैं।

6. सूचित (अनुमानी) खोज की तुलना में असूचित (अंधी) खोज के विषय में निम्नलिखित में कौन सत्य हैं? (एक से अधिक विकल्प सही हो सकते हैं।)

   1. असूचित खोज केवल समस्या की संरचना प्रयोग करती है, शेष लागत के आकलन का नहीं
   2. चौड़ाई-प्रथम खोज मानक असूचित खोज कलनविधि है
   3. A* मानक असूचित खोज कलनविधि है
   4. सूचित खोज अगले किस नोड को विस्तारित करना है यह मार्गदर्शित करने हेतु अनुमानी प्रयोग कर सकती है
   उत्तर देखें

   उत्तर: A — असूचित खोज केवल समस्या की संरचना प्रयोग करती है, शेष लागत के आकलन का नहीं; B — चौड़ाई-प्रथम खोज मानक असूचित खोज कलनविधि है; D — सूचित खोज अगले किस नोड को विस्तारित करना है यह मार्गदर्शित करने हेतु अनुमानी प्रयोग कर सकती है

   A* सूचित खोज का मानक उदाहरण है, f(n) = g(n) + h(n) प्रयोग करते हुए; BFS असूचित का मानक उदाहरण है, बिना किसी लागत-आकलन के केवल वृक्ष की उथला-पहले संरचना प्रयोग करते हुए।

7. A* खोज में, फलन f(n) = g(n) + h(n) का नाम बताइए, जहाँ g(n) अब तक की वास्तविक लागत है व h(n) आकलित शेष लागत है।

   संख्यात्मक उत्तर — मान टाइप करें।

   उत्तर देखें

   उत्तर: evaluation function

   f(n) A* का मूल्यांकन-फलन है, अब तक की ज्ञात लागत को शेष का आकलन जोड़ते हुए — जब h मान्य हो, यही संयोजन ठीक वही है जो A* को इष्टतम पथ खोजने की गारंटी देता है।

8. A* की तुलना में, लोभी सर्वोत्तम-प्रथम खोज अगले किस नोड को विस्तारित करना है यह तय करती है इससे:

   1. केवल अनुमानी आकलन h(n) से, अब तक हुई वास्तविक लागत को नज़रअंदाज़ करते हुए
   2. केवल g(n), अब तक की वास्तविक लागत
   3. बिल्कुल कोई सूचना नहीं
   4. यादृच्छिक सिक्का-उछाल
   उत्तर देखें

   उत्तर: A — केवल अनुमानी आकलन h(n) से, अब तक हुई वास्तविक लागत को नज़रअंदाज़ करते हुए

   लोभी सर्वोत्तम-प्रथम खोज उस नोड को विस्तारित करती है जो केवल h(n) से लक्ष्य के निकटतम दिखे, जो उसे कम आकलन पर पर उच्च वास्तविक लागत वाले पथ में भटका सकता है — ठीक वही कमी जिसे ठीक करने हेतु A* का f(n) = g(n) + h(n) अभिकल्पित है।