न्यूनतम अतिरिक्त-श्रृंखला एक्सपोनेंटिएशन

Question

मुझे पता है कि यह एनपी-पूर्ण साबित हुआ है, और यह ठीक है। मैं वर्तमान में इसे शाखा और बाध्यता से हल कर रहा हूं जहां मैंने गुणाओं की संख्या पर प्रारंभिक ऊपरी सीमा निर्धारित की है, यह सामान्य बाइनरी वर्ग/गुणा एल्गोरिदम ले जाएगा, और यह सही उत्तर देता है, लेकिन मैं दौड़ने से संतुष्ट नहीं हूं समय (200 के आसपास संख्याओं के लिए कई सेकंड लग सकते हैं)। यह एक एनपी-पूर्ण समस्या है, मैं कुछ भी शानदार नहीं होने की उम्मीद कर रहा हूं; लेकिन वास्तविक समय को कुछ हद तक नियंत्रण में लाने के लिए अक्सर चालें होती हैं।

क्या अभ्यास में ऐसा करने के तेज़ तरीके हैं? यदि ऐसा है, तो वो क्या हैं?

Answer 1

यह Knuth वॉल 2 सेमिन्यूमेरिकल एल्गोरिदम में खंड 4.6.3 "शक्तियों का मूल्यांकन" जैसा दिखता है। यह विभिन्न दृष्टिकोण देने के लिए काफी विस्तार से जाता है, जो शाखा और बाध्य से बहुत तेज दिखता है लेकिन सभी बिल्कुल सही समाधान प्रदान नहीं करते हैं।

नूथ थियोरम एफ के बाद चर्चा में कहता है कि वह एल (1 9 1) = 11 साबित करने के लिए बैकट्रैक खोज का उपयोग करता है, इसलिए मुझे संदेह है कि आपको इसके लिए संक्षिप्त जवाब मिलेगा। वह बैकट्रैक सर्च की धारा 7.2.2 में स्पष्टीकरण को रोकता है, जो मुझे अभी भी अप्रकाशित लगता है, हालांकि http://www-cs-faculty.stanford.edu/~uno/programs.html पर इस पर काम का निशान है।

Answer 2

मेटाएरियसिक्स एल्गोरिदम बहुत बेहतर होगा। वे तब्बू खोज, आनुवंशिक एल्गोरिथम, सिमुलेटेड एनिलिंग ...

वहाँ freebooks और software वहाँ की एक जोड़ी है शामिल हैं।