विवाह समस्या और धन वापसी मोड

बेकट्रैकिंग संपूर्ण समस्याओं को हल करने के लिए एक तंत्र है। आपको 1 स्वीकार्य विकल्प या सर्वश्रेष्ठ चुनने की अनुमति देता है।

रिटर्न मोड का सार इस प्रकार है। कार्यक्रम में "कांटे" अंक हैं - वे बिंदु जिन पर आपको व्यवहार में से एक ("विकल्प") चुनना होगा। भविष्य में, यह पता चल सकता है कि चुना गया विकल्प "असफल" है और आपको सड़क पर कांटे पर लौटने और कुछ अन्य विकल्प चुनने की आवश्यकता है।

बेकट्रैकिंग की ख़ासियत यह है कि प्रबंधन में एक रोलबैक है, साथ ही साथ डेटा भी। रोलबैक के दौरान, प्रोग्राम "सब कुछ भूल जाता है" जो कि एक असफल विकल्प चुनने के परिणामस्वरूप किया गया था - डेटा अपने पिछले मूल्यों को पुनर्स्थापित करता है, एक विकल्प चुनने के सभी परिणाम रद्द हो जाते हैं। रोलबैक के बाद, हम अगला विकल्प लेते हैं और सभी कार्यों को फिर से करते हैं। हम जांचते हैं कि कौन से विकल्प हमें स्वीकार्य हैं। यदि इस कांटे में सभी विकल्प असफल होते हैं, तो असफलता ओवरक फोर्क का प्रचार करती है।

बेकिंग प्रदान करता है:
- रोलबैक प्रबंधन;
- डेटा के अनुसार रोलबैक;
- विकल्प की सूची की गणना।

कोई रोलबैक क्रियाएँ नहीं हैं। उदाहरण: स्क्रीन, प्रिंटर इत्यादि पर मुद्रण

कांटों को स्थानीय लोगों में विभाजित किया जा सकता है (केवल उनके सबरूटीन में दिखाई देता है) और वैश्विक (यहां तक ​​कि सबरूटीन समाप्त हो गया है कांटा दिखाई देता है)।
इसलिए, प्रक्रिया में रोलबैक प्रविष्टि संभव है। प्रक्रिया पूरी तरह से बहाल है, सभी स्थानीय चर, उनके मूल्य और उनके मूल्यों का इतिहास बहाल किया गया है।

संगठन विकल्प:
- डेटा और कार्यों को विकल्प के रूप में चुना जा सकता है; (प्रक्रियात्मक लेबल की सरणी)

- विकल्पों की सूची: निर्धारित, गतिशील रूप से गणना, बिल्कुल भी संग्रहीत नहीं किया जा सकता है;

- विकल्पों के एक सेट का स्वत: पुन: निर्धारण।
भविष्यवाणी करें कि कौन सा विकल्प सफलता लाएगा। (भविष्यवाणी के लिए संसाधनों की आवश्यकता होती है।) लेकिन विकल्पों को छांटते हुए, हम अंततः परिणाम पर पहुंचेंगे।

- "विफलता" डिजाइन की अनुपस्थिति संभव है; (कांटा बिंदु स्थापित करने के लिए एक डिज़ाइन है या मौजूद नहीं है)

- रोलबैक संभव है: निकटतम कांटा, निर्दिष्ट सांख्यिकीय / गतिशील रूप से, वांछित कांटा का स्वचालित निर्धारण;
यदि आप सभी विकल्पों के माध्यम से गए, तो विफलता को ऊपर की ओर फैलाएं।
चरणों में वापस नहीं आने के लिए, लेकिन जो आप चाहते हैं वह आवश्यक है:
1. सभी कांटे को चिह्नित करें और वहां वापस रोल करें
2. कांटा को रोलबैक गतिशील रूप से निर्धारित किया जाता है।

- स्वचालित कांटा का पता लगाना।
कार्यक्रम के भीतर रोलबैक
रॉलबैक को रूटीन कहा जाता है
एक पूर्ण दिनचर्या के लिए रोलबैक।
यदि आप प्रक्रिया पूरी होने के बाद वापस कांटे पर जा सकते हैं, तो कांटा बाहरी है।
अपरिवर्तनीय कार्रवाई - रोलबैक के दौरान रद्द नहीं होने वाली क्रियाएं मौजूद हो सकती हैं।
- वापसी मोड को निष्क्रिय करना संभव है, गतिशील रूप से / सांख्यिकीय रूप से, पूरी तरह से / आंशिक रूप से;

- संदेश की विफलता के संकेत से जुड़ा हो सकता है, और कार्यक्रम विश्लेषण की संभावना।

ऐसी भाषाएं हैं जो उनके कार्यान्वयन में समर्थन का समर्थन करती हैं (प्रोलॉग, प्लनर)। इस लेख के भाग के रूप में, मैं उन भाषाओं में वापसी मोड के अनुकरण पर विचार करूंगा जो स्पष्ट रूप से इसका समर्थन नहीं करते हैं। इस लेख में, मैं लिस्टिंग लिखने के लिए एक पास्कल-जैसे छद्म कोड का उपयोग करूंगा, ताकि वाक्य रचना द्वारा विचलित न हो।

प्रक्रियात्मक रूप से उन्मुख भाषा में बैकट्रैकिंग का कार्यान्वयन।
इस दृष्टिकोण में, कांटों को पुनरावृत्ति, और लूप का उपयोग करके विकल्पों की गणना का अनुकरण किया जाता है।
procedure TryAlt(N:trazvilka; var uspeh:boolean);
begin
{ }
uspeh:=false;
repeat { }
if { } then begin { }
if { ( )} then
uspeh:=true
else begin
try(N+1;uspeh);{ }
if uspeh then
{ }
{ }
end;
end;
until uspeh or
end.

स्थिर विवाहों की चुनौती

मान लीजिए कि दो डिसऑइंट सेट ए और बी समान आकार के दिए गए हैं। यह एन जोड़े के एक सेट <a, b> को खोजने के लिए आवश्यक है - जैसे कि ए और बी से बी कुछ प्रतिबंधों को पूरा करते हैं। वितरण मानदंड कई हो सकते हैं। हम उनमें से एक पर विचार करेंगे, जिसे स्थिर विवाह का नियम कहा जाता है।
आज्ञा देना एक भीड़ हो पुरुषों और महिलाओं की भीड़ बी। प्रत्येक पुरुष और प्रत्येक महिला ने अपने पसंदीदा भागीदारों को संकेत दिया। यदि जोड़े इस तरह से बनते हैं कि एक पुरुष और एक महिला हैं जो पति और पत्नी हैं, लेकिन जो एक दूसरे को अपने वास्तविक जीवनसाथी पसंद करेंगे, तो यह वितरण अस्थिर होगा। यदि ऐसी कोई जोड़ी नहीं है, तो वितरण स्थिर है। यह ध्यान दिया जाना चाहिए कि जोड़े के वितरण के बाद भी वितरण की सूची अपरिवर्तित बनी हुई है।
एक समाधान खोजने में एक संभावित दिशा दो सेटों के सदस्यों के जोड़े को एक-एक करके वितरित करने की कोशिश करना है जब तक कि दोनों सेट समाप्त नहीं हो जाते। इस समस्या को हल करने के लिए, हम बैकट्रैकिंग योजना का उपयोग करते हैं, इसे सरलीकरण की दिशा में थोड़ा संशोधित करते हैं।

Procedure tryMan (m : man);
Var
R : rang;
Begin
If m < n then
For r := 1 to n do begin
r- m
If then begin
;
Try ( m);
;
End;
end;
else

end;

हम पुरुषों और महिलाओं की वरीयताओं को इंगित करते हुए दो मैट्रिस द्वारा प्रारंभिक डेटा का प्रतिनिधित्व करते हैं।
Var
womanForMan : array [1..n,1..n] of woman
manForWoman : array [1..n,1..n] of man
तदनुसार, महिलाफोरमैन [एम, आर] पुरुष मीटर की सूची में आर-वें स्थान पर एक महिला है। इसी तरह, मैनफ़ोरवुमन [डब्ल्यू, आर] एक ऐसा पुरुष है जो महिलाओं की सूची में आर-वें स्थान पर है।
परिणाम महिला सरणी द्वारा दर्शाया जाता है ताकि महिला [m] पुरुष m के पति को निरूपित करे। समरूपता के लिए, हम आदमी का परिचय देते हैं ताकि आदमी [w] आदमी w के पति को दर्शाता है। वास्तव में, पुरुष सरणी बेमानी है, क्योंकि इसमें पहले से ही महिला में निहित जानकारी शामिल है। विवाह के प्रस्तावित सेट की स्थिरता को निर्धारित करने के लिए पुरुष और महिला सरणियों में जानकारी की आवश्यकता है। चूँकि इस सेट का निर्माण कदम से कदम व्यक्तियों द्वारा किया जाता है और प्रत्येक प्रस्तावित विवाह के बाद स्थिरता की जाँच की जाती है, सभी घटकों को परिभाषित करने से पहले पुरुष और महिला सरणियों की आवश्यकता होती है। किन घटकों को पहले से परिभाषित किया गया है, इस पर नज़र रखने के लिए, हम बूलियन सरणियों का परिचय देते हैं:
सिंगलमैन, सिंगलवुमन: बूलियन की सरणी [1..n]
घटक की सच्चाई का अर्थ है कि संबंधित पुरुष (महिला) स्वतंत्र है।
उनकी मदद से, विधेय को सिंगलवूमन [डब्ल्यू] के संयोजन के रूप में स्पष्ट किया जा सकता है और विवाह स्थिर है, जहां शादी की भविष्यवाणी स्थिर होना अभी बाकी है।

अब मुख्य कार्य स्थिरता निर्धारण एल्गोरिदम को परिष्कृत करना है। ध्यान रखने वाली पहली विशेषता यह है कि, परिभाषा के अनुसार, स्थिरता रैंकों (यानी वरीयता सूची में स्थान) की तुलना करने से होती है। हालांकि, अब तक पहचाने गए आंकड़ों के हमारे संग्रह में पुरुषों और महिलाओं की सीधे सुलभ रैंक हैं। बेशक, इनकी गणना महिलाफोरमैन और मैनफोरवुमन के मूल्यों द्वारा की जा सकती है, लेकिन चूंकि स्थिरता गणना एक बहुत ही सामान्य ऑपरेशन है, इसलिए इस जानकारी तक अधिक सीधी पहुंच प्रदान करना उचित है। ऐसा करने के लिए, हम दो मैट्रिसेस पेश करते हैं,
आरएमडब्ल्यू: सरणी [पुरुष, महिला] रंग की;
आरडब्ल्यूएम: सरणी [महिला, पुरुष] रंग की;
इसके अलावा, rmw [m, w] पुरुषों की सूची में एक महिला w की रैंक के लिए खड़ा है, और rwm [w, m] महिला w की सूची में एक पुरुष मीटर की रैंक है। इन सहायक मैट्रिस के मूल्यों में परिवर्तन नहीं होता है और यह शुरुआत में महिलाफोरमैन और मैनफोर्सवुमन के मूल्यों द्वारा निर्धारित किया जा सकता है।
अब विधेय विवाह स्थिर है इसकी परिभाषा के ठीक बाद गणना की जा सकती है। मैं आपको याद दिलाता हूं कि हमें शादी की संभावना की जांच करने की आवश्यकता है, जहां डब्ल्यू = महिलाफोरमैन [एम, आर]। पहले, मान लीजिए कि इस तरह की शादी की अनुमति है, और फिर इस शादी की स्थिरता के साथ हस्तक्षेप का पता लगाने की कोशिश करें। इस तरह के दो हस्तक्षेप हो सकते हैं:
1) मी के अनुसार, w से अधिक रैंक वाली महिला pw हो सकती है, और जो खुद अपने पति को पसंद करती है;
2) w के अनुसार, m से अधिक रैंक वाला एक आदमी pm हो सकता है, और जो खुद अपनी पत्नी को w पसंद करता है
पहली तरह के हस्तक्षेप का पता लगाने के लिए, हम उन सभी महिलाओं के लिए रैंक rwm [pw, m] और rwm [pw, man [pw]] की तुलना करते हैं, जिन्हें m w पसंद करता है, अर्थात, सभी pw = womenFwman [m, i] के लिए ऐसा है कि i << आर। वास्तव में, सभी महिलाएं पहले से ही विवाहित हैं, क्योंकि यदि उनमें से किसी की भी शादी अभी तक नहीं हुई है, तो m ने उसे पहले चुना होगा। दूसरे प्रकार के हस्तक्षेप का पता लगाने के लिए, उन सभी उम्मीदवारों की जाँच करना आवश्यक है, जिन्हें w उनकी वर्तमान जोड़ी m, अर्थात, सभी पुरुषों pm = manForWoman [w, i], i <rwm [w, m] से पसंद करते हैं, पहले मामले के साथ सादृश्य द्वारा, हालांकि, यह आवश्यक है। विषय महिला [pm] के साथ तुलना को छोड़ना मत भूलना, जहाँ pm की अभी शादी नहीं हुई है। यह शाम <m की जाँच करके सुनिश्चित किया गया है, क्योंकि हम जानते हैं कि सभी पुरुष तक विवाहित हैं।

स्थिरता जांच प्रक्रिया का पूरा पाठ इस तरह दिखता है
Function stable(m, w, r : integer) : Boolean;
Var
Pw, pm, I, lim : integer;
S : Boolean;

Begin
I := 0; s := true;
Repeat
Inc(i);
If i<r then begin
Pw := womanForMan[m,i];
If not(singleWoman[pw]) then
S := rwm[pw,m] >rwmn[pw,man[pw]];
End;
Until (i=r) or (not(s));

I := ;0 lim := rwm[w,m];
Repeat
Inc(i);
If I < lim then begin
Pm := manForWoman[w,i];
If pm<m then
S := rmw[pm,w]>rmw[pm,woman[pm]
End;
Until (i=lim) or (nor(s));
End;


निष्कर्ष

यह एल्गोरिथ्म सभी संभव समाधान उत्पन्न करता है और इसे इस तरह से संशोधित किया जा सकता है जैसे कि पुरुषों के लिए या तो महिलाओं के लिए इष्टतम समाधान, या औसत। यह सब उस उद्देश्य पर निर्भर करता है जिसके लिए इस एल्गोरिथ्म का उपयोग किया जाता है।