पीक खोज एल्गोरिदम

Question

मैंने हाल ही में एमआईटी के 6.006 व्याख्यान को देखना शुरू कर दिया और पहले व्याख्यान में प्रशिक्षक ने पीक-एल्गोरिदम प्रस्तुत किया।

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/MIT6_006F11_lec01.pdf

उसकी परिभाषाओं के अनुसार:

को देखते हुए एक सरणी [क, ख, ग, डी, ई, एफ, जी] जहां एजी नंबर दिए गए हैं, ख एक चोटी है अगर और केवल अगर < = बी और बी> = सी।

वह एक पुनरावर्ती दृष्टिकोण दिया:

if a[n/2] < a[n/2 -1] then look for a peak from a[1] ... a[n/2 -1] 
else if a[n/2] < a[n/2+1] then look for a peak from a[n/2+1] ... a[n] 
else a[n/2] is a peak 

उन्होंने कहा कि एल्गोरिथ्म टी (एन) = टी (एन/2) + ओ (1) = ओ (LGN)

में है उनके पीडीएफ उन्होंने एक पूर्ण उदाहरण भी दिया: [6,7,4,3,2,1,4,5]

दोनों 7 और 5 चोटियों हैं। लेकिन उपरोक्त एल्गोरिदम केवल 7 को चोटी के रूप में नहीं पाता है क्योंकि मध्य तत्व पहली शाखा को संतुष्ट करता है?

1. तो अगर हमें सभी चोटियों को ढूंढना था, तो क्या हम अभी भी पूरी सरणी के माध्यम से चलेंगे? क्या इसका मतलब सबसे खराब मामला होगा?

2. क्या उसकी परिभाषा का तात्पर्य है कि हमें केवल एक चोटी को खोजने की ज़रूरत है?

मुझे विश्वास है कि इस समस्या को एल्गोरिदम पुस्तक के रिवरस्ट के परिचय में अधिकतम और न्यूनतम तत्व ढूंढने के रूप में देखा जा सकता है।

Answer 1

हां, यह एल्गोरिदम केवल एक ही चोटी पाता है।

यदि आप सभी पाइक्स ढूंढना चाहते हैं तो आपको सभी तत्वों को जांचना होगा, इसलिए यह ओ (एन) होगा।

नोट: एक चोटी जरूरी नहीं है कि वह अधिकतम वैश्विक हो।

Answer 2

यह एल्गोरिदम binary search algorithm के समान दिखता है। बाइनरी खोज केवल क्रमबद्ध सरणी पर काम करती है, और यह शीर्ष खोज-खोज एल्गोरिदम ऐसा लगता है कि इसे किसी अन्य परिभाषा के साथ काम करना चाहिए: x[p]0 <= i < px[i] <= x[i + 1] और p <= i < x.sizex[i] >= x[i + 1] के लिए एक शिखर है। अगर हम निर्णय लेते हैं कि प्रश्न में परिभाषा गलत है, और यह सही है: सबकुछ ठीक है। और ऐसा लगता है कि यह गलत है, क्योंकि यह दूसरे मामले में कई चोटियों को देता है, तो आप सही हैं।

Answer 3

मैं सिर्फ कल इस पाठ्यक्रम शुरू किया, और समस्या कथन है:

समस्या: एक चोटी का पता लगाएं यदि वह मौजूद है (? यह हमेशा मौजूद है)

तो, क्या एल्गोरिथ्म करता है बस है कम से कम समय में, एक शीर्ष, उपलब्ध एक उपलब्ध खोजने की कोशिश कर रहा है।

यही कारण है कि इस एल्गोरिदम को केवल एक ही चोटी मिलती है।

Answer 4

मुझे कोई आश्वस्त नहीं है कि यह एल्गोरिदम एक दिलचस्प शिखर खोजने का सबसे अच्छा तरीका है। यह मध्य तत्व पर तुलना का पक्ष लेता है जो खोज को उप-दिशात्मक दिशा में चला सकता है और अंततः एल्गोरिदम हमेशा किनारों पर चोटी को खोजने में समाप्त होता है, न कि मध्य में। सरल उदाहरण

[1,2,3,4,5,6,7,8] => पीक होगा 8

[6,21,7,8,9,10,11,13 ] => पीक 13 होगा जबकि 21 की चोटी अधिक दिलचस्प है

सुनिश्चित करें कि एल्गोरिदम को चोटी को खोजने की गारंटी है क्योंकि यह उच्च दिशा में चलता है लेकिन जैसा कि मैंने उदाहरण में दिखाया है, शिखर दिलचस्प नहीं हो सकता है !