12
यहाँ एक दिलचस्प समस्या यह है कि मैं एक प्रोग्रामिंग प्रतियोगिता में सामना करना पड़ा है:का पता लगाने जब आव्यूह गुणन संभव है
समस्या बयान:n मैट्रिक्स के आयामों को देखते हुए, यह निर्धारित करता है, तो वहां मौजूद एक आदेश ऐसी है कि मैट्रिक्स हो सकता है गुणा किया हुआ। यदि कोई मौजूद है, परिणामी मैट्रिक्स के आकार (आयामों का उत्पाद) प्रिंट करें।
मेरे टिप्पणियों: इस एन पी-सम्पूर्ण Hamiltonian पथ समस्या को कम कर देता है अगर आप एक शीर्ष के रूप में प्रत्येक मैट्रिक्स पर विचार करने और मैट्रिक्स कि गुणा किया जा सकता जो निर्देश दिया किनारे आकर्षित। मैंने समस्या को मजबूती से मजबूर कर हल किया लेकिन यह स्पष्ट रूप से बहुत धीमा है। मैं सोच रहा था कि समस्या के इस विशेष उदाहरण के लिए कोई चालाक अनुकूलन है या नहीं।
सभी कुशलतापूर्वक सुलभ (और जांच योग्य) समस्याएं एनपी-पूर्ण समस्याओं को कम करती हैं। यह एनपी-पूर्ण समस्या से आपकी समस्या में कमी है जो परेशान होना चाहिए। – aelguindy
@ElKamina के रूप में, यह एक यूलेरियन निशान समस्या है, मेरा जवाब भी देखें [यहां] (http://stackoverflow.com/a/9046177/1011995)। –