प्रोल में प्राइमा क्रैस्कल समस्या

यह विषय प्राइमा-क्रैस्कल समस्या ( "लालची एल्गोरिथ्म" ) और प्रोलॉग भाषा में इसके समाधान पर चर्चा करेगा।

शुरू हो जाओ!


कार्य: इसमें एक समतल देश और n शहर दिए गए हैं। सभी शहरों को टेलीफोन से जोड़ना आवश्यक है ताकि टेलीफोन लाइनों की कुल लंबाई न्यूनतम हो।

कार्य का स्पष्टीकरण। कार्य टेलीफोन संचार के बारे में है, अर्थात तात्पर्य संचार की संवेदनशीलता: यदि i-th शहर को j-th से जोड़ा गया है, और k-th के साथ j-th शहर को जोड़ा गया है। यह भी समझा जाता है कि टेलीफोन लाइनें केवल टेलीफोन एक्सचेंज में ही चल सकती हैं, न कि साफ-सुथरे क्षेत्र में। अंत में, न्यूनता की आवश्यकता (एक साथ संक्रामकता के साथ) का मतलब है कि वांछित समाधान में कोई चक्र नहीं होगा।

ग्राफ सिद्धांत के संदर्भ में, प्राइमा-क्रैस्कल समस्या इस प्रकार है:
एन कोने के साथ एक ग्राफ दिया गया है; पसलियों की लंबाई दी गई है। न्यूनतम लंबाई का एक फैले हुए वृक्ष का पता लगाएं।
जैसा कि आप जानते हैं, n कोने वाले पेड़ में n-1 किनारे होते हैं। यह पता चला है कि प्रत्येक किनारे को लालच से चुना जाना चाहिए (जब तक कि कोई चक्र न हो)।

प्राइमा-क्रैस्कल एल्गोरिथ्म का संक्षिप्त विवरण: लूप एन -1 बार में, ऐसा करें: "सबसे कम रिब का चयन करें जो अभी तक चयनित नहीं है, बशर्ते कि वे पहले से चुने गए लोगों के साथ लूप न बनाएं"।
इस तरह से चुने गए किनारे वांछित पेड़ बनाते हैं।

समस्या को हल करने के लिए, एक ग्राफ बनाया जाएगा, किनारों और कोने की सूची के रूप में प्रस्तुत किया जाएगा।

फैले हुए पेड़ खोज एल्गोरिदम को निम्नलिखित चरणों में विभाजित किया जा सकता है:

• उनकी लंबाई के बढ़ते क्रम में किनारों की सूची को क्रमबद्ध करें;
• "लालची" एल्गोरिथ्म लागू करें और किनारों की एक सूची प्राप्त करें;
• जाँच करें कि किनारों की सूची एक फैले हुए पेड़ है।

लालची एल्गोरिथ्म निम्नानुसार काम करता है: एक किनारे का चयन करना आवश्यक है जिसे अभी तक न्यूनतम लंबाई का चयन नहीं किया गया है (किनारे को अन्य चयनित किनारों के साथ एक चक्र नहीं बनाना चाहिए)।

अब, SWI- प्रोलॉग पर परिणामी एल्गोरिदम का कार्यान्वयन :

%
launch:-
write_ln(':'), read(X),
write_ln(' :'), read(Y),
city(X,Y,Z),
write_ln(' :'),
write(Z).

launch:-
write_ln(' ').

%
%
%Z1 - ,
%Y-
%Z2 -
minimum([],Z,Z):- !.

minimum([[X1,X2,_]|Y],Z1,Z2):-
not(search(X1,X2,Z1,[X1])),!,
minimum(Y,[[X1,X2]|Z1],Z2).

minimum([_|Y],Z1,Z2):- minimum(Y,Z1,Z2). %

% 1 2
% - 7.
%, Y - , Z - ( ).
search(X1,X2,Y,_):- member([X1,X2],Y).

search(X1,X2,Y,_):- member([X2,X1],Y).

search(X1,X2,Y,Z):- member([X1,X3],Y),
not(member(X3,Z)), search(X3,X2,Y,[X3|Z]).

search(X1,X2,Y,Z):- member([X3,X1],Y),
not(member(X3,Z)), search(X3,X2,Y,[X3|Z]).

% ( )
%
% L1 - , X - , L2 -
ins(X,[],[X]).

ins([X1,X2,R1],[[Y1,Y2,R2]|L],[[X1,X2,R1]|[[Y1,Y2,R2]|L]]):- R1<R2,!.
ins(X,[Y|L1],[Y|L2]):- ins(X,L1,L2).

%
%
%L - ,Y1 - , Y3 - .
sortrast([],Y,Y). sortrast([X|L],Y1,Y3):- ins(X,Y1,Y2), sortrast(L,Y2,Y3).

% .
%
%Z - X - , Y - ,
city([X|L],Y,Z):- sortrast(Y,[],Y1), minimum(Y1,[],Z), all(X,L,Z).

%
%
% x -, Z - L -
all(_,[],_).
all(X,[Y|L],Z):- search(X,Y,Z,[X]),!,all(X,L,Z).

निम्नलिखित विधेयकों को कार्यक्रम में लागू किया गया था:
• लॉन्च - स्क्रीन पर जानकारी प्रदर्शित करने के लिए उपयोग किया जाता है। उदाहरण के लिए, शहरों की सूची और उनके बीच बिखराव।
• Sortrast (L1, L2, L3) - सम्मिलित विधि का उपयोग करके L1 सूची को सॉर्ट करें, जहां L2 वर्तमान सूची है, L3 परिणाम है।
• ity (एक्स, वाई, जेड) - टेलीफोन लाइनों द्वारा शहरों का कनेक्शन, जहां एक्स - शहरों की सूची, वाई - दूरी की सूची, जेड - परिणाम।
• खोज (एक्स 1, एक्स 2, वाई, जेड ) - मार्ग एक्स 1 से वर्टेक्स एक्स 2 तक के मार्ग की खोज को लागू करता है, जहां वाई किनारों की सूची है, जेड कोने की सूची है (जो पारित हो गए हैं)।
• सभी (एक्स, वाई, जेड) - शहरों के फोन कवरेज की जांच करता है। जहाँ X पहला शहर है, L अन्य शहरों की सूची है, Z टेलीफोन लाइनों की सूची है।
• ins (X, L1, L2) - विधेय तत्व को L1 (किनारों की क्रमबद्ध सूची) में X सम्मिलित करता है। L2 का परिणाम है।
• न्यूनतम (वाई, जेड 1, जेड 2) - न्यूनतम (लंबाई में) कनेक्शन खोजने के लिए एक विधेय। जहां Y किनारों की सूची है, Z1 चयनित किनारों है, Z2 परिणाम है।

कार्यक्रम के परिणाम: