प्रोलॉग में डिफ़ॉल्ट गहराई-पहली खोज योजना पर चौड़ाई का उपयोग करने का सामान्य विचार क्या है?प्रोलॉग में ब्रेडथ-फर्स्ट
अनंत शाखाएं नहीं ले रहे हैं?
क्या प्रोलॉग में पहली बार चौड़ाई का उपयोग करने का कोई सामान्य तरीका है? मैं चारों ओर घूम रहा हूं और मुझे नौसिखिए के लिए बहुत उपयोगी जानकारी नहीं मिली है।
चौड़ाई का लाभ यह है कि आपको सभी समाधान मिलेंगे। गहराई से पहले आप एक अनंत शाखा में फंस सकते हैं।
नुकसान यह है कि चौड़ाई पहले बहुत सारी मेमोरी का उपयोग करती है, इसलिए इसे आम तौर पर निष्पादन के लिए उपयोग नहीं किया जाता है।
यदि आप इसका उपयोग करना चाहते हैं तो आपको इसे किसी प्रकार की कतार के साथ स्पष्ट रूप से कार्यान्वित करने की आवश्यकता होगी।
संपादित करें: यदि आप अधिक स्मृति का उपयोग किए बिना चौड़ाई-पहली खोज के फायदे चाहते हैं तो आप पुनरावृत्ति गहराई का उपयोग कर सकते हैं। यह गहराई से पहली गहराई वाली खोज है, जिसे आप लगातार बढ़ाते हैं। इससे कुछ डुप्लिकेट गणना होती है, लेकिन यदि आपकी खोज स्थान में ब्रांचिंग के बिना लंबे रैखिक फैले नहीं हैं तो यह डुप्लिकेशंस छोटा है।
कुछ ऐसा है जो मुझे "एजेंडा खोज" के रूप में जानना है। पेड़ (डेटा, संबंध, नियम, ...) की यात्रा करते समय आप आगे क्या करना है इसके बारे में एक "एजेंडा" (एक सूची) बनाए रखते हैं। जब आप नोड दर्ज करते हैं तो आप अपने बच्चों को एजेंडा पर डाल देते हैं, और फिर एजेंडा के पहले तत्व के साथ जारी रखें, जिसे आप पॉप करते हैं। इस तरह, यदि आप एजेंडा के अंत में नई चीजें डालते हैं, तो आपको पहले चौड़ाई मिलती है। यदि आप उन्हें एजेंडा के सामने रखते हैं, तो आपको गहराई मिलती है।
प्रोलॉग के साथ कार्यान्वित करना आसान है।
संपादित करें: मैं यहां एक कार्यान्वयन संकेत भी दे सकता हूं। यह एजेंडा खोज एल्गोरिदम का एक बहुत ही बुनियादी कार्यान्वयन है।
agenda_search([N|T],Mode):-
doWithNode(N), % do whatever you do the searching for
getNodeChildren(N,C),
(Mode=bf -> % bf or df (depth-first)
append(T,C,A);
append(C,T,A)),
agenda_search(A,Mode).
यह बाहरी विधेय doWithNode कि कार्रवाई आप प्रत्येक नोड के साथ प्रदर्शन करना चाहते हैं के लिए खड़ा है पर निर्भर करता है (उदाहरण के लिए, एक खोज पद के लिए नोड डेटा की तुलना asf नोड सामग्री को क्रमानुसार।)। और getNodeChildren जो दिए गए नोड के बच्चों को C पर सूचीबद्ध करेगा (यानी यह भविष्य वास्तव में पेड़ की संरचना जानता है और बाल नोड कैसे ढूंढें)। बेशक doWithNode भविष्यवाणी के लिए अपनी नौकरी करने के लिए अतिरिक्त पैरामीटर की आवश्यकता हो सकती है, जो agenda_search की तर्क सूची में भी दिखाई देगी।
आप इस तरह यह आह्वान कर सकते हैं:
agenda_search([RootNode], bf) % for breadth-first search
और
agenda_search([RootNode], df) % for depth-first search
मैं भी एजेंडे खोज on this web page की व्याख्या का एक सा मिल गया है। एजेंडा खोज के साथ अच्छी बात यह है कि आप आसानी से दो प्रकार के डीएफ और बीएफ के बीच स्विच कर सकते हैं और परिणामों के साथ खेल सकते हैं। एल्गोरिदम काफी अच्छी तरह से व्यवहार किया गया है, एजेंडा के रूप में, नोड्स अभी भी अन्वेषण करने के लिए, केवल किसी भी समय (तथाकथित फ्रिंज) पेड़ में नोड्स के एक छोटे से कम (छोटे या कम) छोटे अंश को कैप्चर करता है।
agenda_search के लिए कोड ठीक काम करना चाहिए। दक्षता के लिए आप किसी अन्य डेटास्ट्रक्चर का उपयोग करने पर विचार करना चाहेंगे; वास्तव में, चौड़ाई-पहले मोड में नोड्स (टी) की पूरी सूची को संलग्न (टी, सी, ए) द्वारा पार किया जाएगा। उदाहरण के लिए आप एसआईसीस्टस से लाइब्रेरी (कतार) मॉड्यूल का उपयोग कर सकते हैं। ब्रेड-फर्स्ट सर्च तब निम्नानुसार दिखाई देगी (प्रारंभ/1 भविष्यवाणी द्वारा पैरामीटर द्वारा उत्तराधिकारी एस/2 और लक्ष्य अनुमानित लक्ष्य/1)। नोट, मैंने लूप जांच भी जोड़ा है।
bfs(Res) :- start(Start), empty_queue(EQ),
queue_append(EQ,[e(Start,[])],Q1),
bfs1(Q1,Res).
bfs1(Queue,Res) :- queue_cons(e(Next,Path),NQ,Queue),
bfs2(Next,Path,NQ,Res).
bfs2(H,Path,_NQ,Res) :- goal(H), reverse([H|Path],Res).
bfs2(H,Path,NQ,Res) :-
findall(e(Succ,[H|Path]),
(s(H,Succ),\+ member(Succ,Path)),AllSuccs),
queue_append(NQ,AllSuccs,NewQueue),
bfs1(NewQueue,Res).
(। आप भी आजमा सकते हैं और की जगह/एक बेहतर आंकड़ा संरचना द्वारा पथ घटक के पूरक हैं, जैसे, AVL-वृक्ष) हल करने के लिए एक उदाहरण समस्या होगा:
start(env(0,0)). s(env(X,Y),env(X1,Y)) :- X1 is X+1. s(env(X,Y),env(X,Y1)) :- Y1 is Y+1. goal(env(3,3)).
आप भी कर सकते हैं कतार को प्राथमिकता कतार से प्रतिस्थापित करें, और एक ह्युरिस्टिक फ़ंक्शन का उपयोग करके प्राथमिकता की गणना करें। फिर आपको ए * खोज मिलती है (जो गहराई-पहले, चौड़ाई-पहले, सर्वोत्तम-प्रथम, ... का अनुकरण कर सकती है।)। ब्राट्को की पुस्तक (आर्टिफिशियल इंटेलिजेंस के लिए तर्क प्रोग्रामिंग) इस सामग्री को पढ़ने के लिए अच्छा स्रोत होना चाहिए।
इसके अलावा, चौड़ाई पहले सबसे कम पथ/पथ पाएंगे। –