मुझे समझने में कठिनाई हो रही है कि कैसे कुछ आविष्कार के साथ प्रेरण, एल्गोरिदम की शुद्धता साबित करने के लिए उपयोग किया जा सकता है। अर्थात्, आविष्कार कैसे पाया जाता है, और विशेष रूप से बाइनरी खोज के लिए उपयोग की जाने वाली अपरिवर्तनीय परिकल्पना कब होती है? मैं अभी तक एक सहज प्रतिक्रिया प्राप्त करने में सक्षम नहीं हूं, इसलिए मैं उम्मीद कर रहा था कि कोई इस विषय पर कुछ प्रकाश डाल सकता है।हम प्रेरण से कैसे साबित कर सकते हैं कि बाइनरी खोज सही है?
मान लेते हैं कि द्विआधारी खोज परिभाषित किया गया है चलो इस तरह:
def binary_search(a,b,e,x):
n = e-b
if n==0: return None
m = b + int(n/2)
if x<a[m]: return binary_search(a,b,m,x)
if x>a[m]: return binary_search(a,m+1,e,x)
return m
जहां
समारोह के लक्ष्य को मैं वापस जाने के लिए जहां एक [i] == एक्स अगर वहाँ मैं इस तरह के एक मूल्य है, अन्यथा लौट कोई नहीं है खोज कर रहे हैं है।
binary_search शून्य आकार की एक सीमा के लिए काम करता है:
मानते हैं कि binary_search 0 से n तक किसी भी आकार के तत्वों की एक श्रृंखला के लिए काम करता है, तो बाइनरी खोज आकार n + 1 के तत्वों की एक श्रृंखला के लिए काम करती है।
सबूत:
क्योंकि सरणी सॉर्ट हो जाता है, अगर एक्स < एक [एम], तो x < एक सब k> मीटर के लिए [k]। इसका मतलब है कि हमें केवल सीमा [बी, एम) खोजना होगा। सीमा [बी, एम) रेंज [बी, ई) की तुलना में जरूरी है, और हमने माना है कि बाइनरी खोज एन + 1 से छोटे आकार की सभी श्रेणियों के लिए काम करती है, इसलिए यह [बी, एम) के लिए काम करेगी।
यदि x> a [m], तो समान तर्क लागू होता है।
यदि x == a [m], तो फ़ंक्शन एम वापस करेगा, जो सही है।
/** Return an index of x in a.
* Requires: a is sorted in ascending order, and x is found in the array a
* somewhere between indices left and right.
*/
int binsrch(int x, int[] a, int left, int right) {
while (true) {
int m = (left+right)/2;
if (x == a[m]) return m;
if (x < a[m])
r = m−1;
else
l = m+1;
}
}
कुंजी अवलोकन है कि binsrch एक विभाजन और जीत फैशन में काम करता है, जो अपने आप ही तर्क है कि कर रहे हैं "छोटे" किसी तरह पर फोन है।
चलो पी (एन) इस बात का दावा करें कि binsrch इनपुट के लिए सही तरीके से काम करता है जहां दाएं-बाएं = n। अगर हम साबित कर सकते हैं कि पी (एन) सभी एन के लिए सच है, तो हम जानते हैं कि बिंस्रच सभी संभावित तर्कों पर काम करता है।
बेस केस। मामले में जहां n = 0, हम बाएं = दाएं = मीटर जानते हैं। चूंकि हमने माना है कि फ़ंक्शन केवल तभी कॉल किया जाएगा जब x बाएं और दाएं के बीच पाया जाता है, यह मामला होना चाहिए कि x = a [m], और इसलिए फ़ंक्शन एम लौटाएगा, सरणी में x की अनुक्रमणिका होगी।
अपरिवर्तनीय चरण। हम मानते हैं कि binsrch तब तक काम करता है जब तक बाएं-दाएं ≤ के। हमारा लक्ष्य साबित करना है कि यह एक इनपुट पर काम करता है जहां बाएं-दाएं = के + 1. तीन मामले हैं, जहां x = a [m], जहां x < एक [m] और जहां x> a [m]।
Case x = a[m]. Clearly the function works correctly.
Case x < a[m]. We know because the array is sorted that x must be found between a[left] and a[m-1]. The n for the recursive call is n = m − 1 − left = ⌊(left+right)/2⌋ − 1 − left. (Note that ⌊x⌋ is the floor of x, which rounds it down toward negative infinity.) If left+right is odd, then n = (left + right − 1)/2 − 1 − left = (right − left)/2 − 1, which is definitely smaller than right−left. If left+right is even then n = (left + right)/2 − 1 − left = (right−left)/2, which is also smaller than k + 1 = right−left because right−left = k + 1 > 0. So the recursive call must be to a range of a that is between 0 and k cells, and must be correct by our induction hypothesis.
Case x > a[m]. This is more or less symmetrical to the previous case. We need to show that r − (m + 1) ≤ right − left. We have r − (m + 1) − l = right − ⌊(left + right)/2⌋ − 1. If right+left is even, this is (right−left)/2 − 1, which is less than right−left. If right+left is odd, this is right− (left + right − 1)/2 − 1 = (right−left)/2 − 1/2, which is also less than right−left. Therefore, the recursive call is to a smaller range of the array and can be assumed to work correctly by the induction hypothesis.
क्योंकि सभी मामलों आगमनात्मक कदम काम करता है में, हम उस binsrch (और इसके पुनरावृत्ति संस्करण) निष्कर्ष निकाल सकते हैं सही हैं!
ध्यान दें कि अगर हमने एक्स> ए [एम] मामले को कोड करने में गलती की है, और एम + 1 (आसान करने के लिए!) के बजाए एम को पास किया गया है, तो हमने जो प्रमाण बनाया है, वह उस मामले में विफल हो गया होगा । और वास्तव में, एल्गोरिदम एक अनंत लूप में जा सकता है जब दाएं = बाएं + 1. यह सावधानीपूर्वक अपरिवर्तनीय तर्क का मूल्य दिखाता है।
संदर्भ: http://www.cs.cornell.edu/Courses/cs211/2006sp/Lectures/L06-Induction/binary_search.html
आपको लगता है कि साबित करना चाहिए द्विआधारी खोज के प्रत्येक चरण के बाद arr[first] <= element <= arr[last]
इस से और समाप्ति आप निष्कर्ष निकाल सकते हैं कि एक बार द्विआधारी खोज समाप्त हो जाता है arr[first] == element == arr[last]
मान लें कि क्रमबद्ध सरणी a[0...n] है। बाइनरी खोज इस सरणी को में विभाजित करके तीन टुकड़े, मध्यम तत्व m, बाएं हिस्से का सभी भाग <= m (चूंकि सरणी धारणा द्वारा क्रमबद्ध है) और सही भाग जिसमें से सभी तत्व >=m (फिर, क्योंकि सरणी धारणा द्वारा क्रमबद्ध है)।
invariant कैसे तैयार करें?
आइए पहले सोचें कि बाइनरी खोज कैसे काम करती है। यदि कुंजी (आइटम की खोज की जा रही है) k है तो मैं इसे मध्यम तत्व m से तुलना करता हूं।
तो k = m, मैं अपने मद (अधिक कुछ भी नहीं करना)
हैं k < mतो मैं निश्चित रूप से पता है कि ka में दिखाई देता है, उसके दाईं ओर भाग में दिखेंगे नहीं कर सकते हैं पाया है सरणी क्योंकि सरणी के उस हिस्से के सभी तत्व >= m > k हैं। तो यह सरणी के बाएं हिस्से के भीतर दिखाई देना चाहिए (यदि यह करता है)।
यदि k > mतो मुझे निश्चित रूप से पता है .....।
तो, क्या कर सकते हैं हम गारंटी इस तरह के एक पुनरावर्ती गणना के प्रत्येक चरण पर? प्रत्येक चरण में हम दो सूचकांक i, j की पहचान कर सकते हैं और दावा कर सकते हैं कि "अगर ka[0...n] का एक तत्व है तो यह i, j" के बीच में दिखाई देना चाहिए।यह अपरिवर्तनीय क्योंकि यह सभी पुनरावर्ती चरणों के लिए रखती है, और प्रत्येक चरण के साथ आप इस श्रेणी i, j निचोड़ जब तक आप अपने आइटम मिल गया है या इस श्रृंखला खाली हो जाता है (रेंज गैर खाली जब i < j है)।
प्रेरण कैसे काम करता है?
i = 0, j = n लेने के लिए । Invariant trivially रखती है।
अपरिवर्तनीय चरण के लिए, कुछ रिकर्सिव चरण p जहां i = i_p & j = j_p के लिए इनवेरिएंट धारण करता है। और फिर आपको साबित करना होगा कि अगले रिकर्सिव चरण के लिए, i, j अपडेट किया जाता है जैसे कि इनवेरिएंट अभी भी है। यह वह जगह है जहां आपको ऊपर चरण 2) और 3) में तर्कों का उपयोग करना होगा।
श्रेणी i, j सख्ती से घट रही है, इसलिए गणना को समाप्त करना होगा।
क्या मुझे कुछ याद आया?