शक्तिशाली एल्गोरिदम

Question

लागू करने के लिए बहुत जटिल हैं वैध उपयोगिता के कुछ एल्गोरिदम क्या हैं जो कार्यान्वित करने के लिए बहुत जटिल हैं?

मुझे स्पष्ट होने दें: मैं वर्तमान एसिम्प्टोटिक इष्टतम मैट्रिक्स गुणा एल्गोरिदम जैसे एल्गोरिदम की तलाश नहीं कर रहा हूं, जो कार्यान्वित करने के लिए उचित है लेकिन एक निरंतर है जो इसे अभ्यास में बेकार बनाता है। मैं एल्गोरिदम की तलाश में हूं जो व्यावहारिक रूप से व्यावहारिक मूल्य हो सकता है, लेकिन कोड करना मुश्किल है कि उन्हें कभी लागू नहीं किया गया है, केवल अत्यंत कृत्रिम सेटिंग्स में लागू किया गया है, या केवल उल्लेखनीय विशेष उद्देश्य अनुप्रयोगों के लिए लागू किया गया है।

भी असीमित-से-लागू एल्गोरिदम का स्वागत है जिसमें अच्छा एसिम्प्टोटिक्स है लेकिन संभवतः खराब वास्तविक प्रदर्शन होगा।

Answer 1

मुझे यकीन नहीं है कि मैं जानता हूं कि आप क्या पूछ रहे हैं, लेकिन मानक एनपी अधूरा गणना बहुत मुश्किल है, जहां तक ​​मुझे पता है, और उनके पास कई तरीकों से असली दुनिया का मूल्य है, उदाहरण के लिए डेटा के लिए सबसे कुशल मार्गों की गणना करना ट्रांसमिशन, या सर्किट बोर्ड काटने, या बिजली ग्रिड के लिए रूटिंग शक्ति ... संभावनाएं सेना हैं।

Answer 2

मुझे नहीं लगता कि व्यावहारिक उपयोग के साथ कोई एल्गोरिदम है जिसमें कभी कोडित नहीं किया गया है, लेकिन कोड के लिए बहुत मुश्किल हैं।

एल्गोरिदम का एक उदाहरण जो असम्बद्ध रूप से इष्टतम है, लेकिन कोड के लिए बहुत मुश्किल है Chazelle's O(n) polygon triangulation algorithm। स्कीनियाना (द एल्गोरिदम डिजाइन मैनुअल के लेखक) के अनुसार, "[ए] एल्गोरिदम लागू करने के लिए काफी निराशाजनक है।"

सामान्य रूप से, त्रिभुज और अन्य कम्प्यूटेशनल ज्यामिति एल्गोरिदम (जैसे 3 डी उत्तल हॉल, और वोरोनोई आरेख) लागू करने के लिए त्वरित मुश्किल हो सकते हैं। फ्लोटिंग पॉइंट त्रुटियों को संभालने के लिए बहुत सी चाल कम हो जाती है।

Answer 3

हम तो कुछ गणितीय प्रमाणों ऐसे हेल के सबूत या केपलर के अनुमान के रूप में विशेष मामलों की एक बहुत बड़ी संख्या हो सकती है समानता कर सकते हैं "कठिन" "मुश्किल" के साथ: http://en.wikipedia.org/wiki/Kepler_conjecture

दृष्टिकोण के बाद Fejes ने सुझाव दिया टॉथ (1 9 53), थॉमस हेल्स, मिशिगन विश्वविद्यालय में, ने निर्धारित किया कि की अधिकतम घनत्व चर के साथ एक समारोह को कम करने के द्वारा पाया जा सकता है। 1992 में, उसके स्नातक छात्र शमूएल फर्ग्यूसन द्वारा सहायता प्रदान की, वह करने के लिए एक अनुसंधान कार्यक्रम शुरू कर व्यवस्थित रैखिक प्रोग्रामिंग विधियों लागू एक कम से अधिक का एक सेट में से हर एक के लिए इस समारोह के मूल्य पर बाध्य खोजने के लिए गोलाकारों की विभिन्न विन्यास। तो एक लोअर बाउंड (समारोह मूल्य के लिए) इन विन्यास कि अधिक से अधिक घन पास पैकिंग व्यवस्था के लिए समारोह के मूल्य से था में से हर एक के लिए पाया जा सकता है, तो केपलर अनुमान साबित कर दिया की जाएगी। सभी मामलों के लिए निचली सीमाएं खोजने के लिए लगभग 100,000 रैखिक प्रोग्रामिंग समस्याओं को हल करने में शामिल है।

जब 1996 में अपने परियोजना की प्रगति पेश, हेल्स ने कहा कि अंत दृष्टि में था, लेकिन यह पूरा करने के लिए ले सकता है "एक या दो साल"।अगस्त 1 99 8 में हेल्स ने घोषणा की कि सबूत पूरा हो गया था। उस चरण में में 250 पृष्ठों के नोट्स और 3 कंप्यूटर प्रोग्राम के गीगाबाइट, डेटा और परिणाम शामिल थे।

Answer 4

बाधाओं से एक वातावरण के माध्यम से एक रोबोट ले जाने के The Piano Mover's Problem गणितीय परिभाषित और ज्ञात asymptotic जटिलता के साथ एल्गोरिदम के साथ हल किया जा सकता है।

It is amazing that such algorithms exist; हालांकि, यह भी दुर्भाग्यपूर्ण है कि वे लागू करने के लिए बेहद चुनौतीपूर्ण हैं और अधिकतर अनुप्रयोगों के लिए पर्याप्त कुशल नहीं हैं।

रोबोट गति योजना पर हर नए शोध कैनी के रोडमैप एल्गोरिथ्म का उल्लेख है, वहीं यह संदेह है कि यह कभी लागू किया गया है:

no general implementation of Canny's algorithm वर्तमान में मौजूद नहीं है।