न्यूनतम परिणाम के लिए एक मैट्रिक्स में संख्या कैसे जोड़ें?

Question

यह एक एल्गोरिदमिक/गणित समस्या से अधिक है लेकिन मैं सी ++ में एक समाधान को लागू करने की उम्मीद कर रहा हूं।

मान लीजिए मैं की तरह एक मैट्रिक्स है, इसलिए जहां डॉट्स पूर्णांकों प्रतिनिधित्व करते हैं:

W X Y Z 
A . . . . 
B . . . . 
C . . . . 
D . . . . 

मैं कम से कम परिणाम कैसे प्राप्त होते हैं अगर मैं प्रत्येक स्तंभ से सबसे ज्यादा एक नंबर पर है ऐसा है कि वहां से एक नंबर लेने के लिए किया था हर एक पंक्ति?

उदाहरण के लिए, मैं चुन सकते हैं AW BX CY DZ या AZ BX CY DW लेकिन नहीं AW BW CZ DZ

जानवर बल दृष्टिकोण n लेने के लिए प्रतीत होता है! गणना। क्या कोई तेज रास्ता है? आखिरकार मैं आकार ~ 60 के मैट्रिस में संख्या जोड़ना चाहता हूं।

इसके अलावा, सभी नंबरों को 0 से 256

Answer 1

तक होती है और अगर आप बल्कि यह अपने आप कोड नहीं चाहते हैं, तो आप हमेशा किसी और 'कड़ी मेहनत से काम करते हैं और तरह प्रकाशन इस्तेमाल कर सकते हैं। हास्केल में यह एक, मेरे पुराने लैपटॉप पर एक सेकंड के दो दशकों से भी कम समय में 60x60 यादृच्छिक मैट्रिक्स हल करता है। क्या एक महान एल्गोरिदम!

import Data.Algorithm.Munkres 
import Data.Array.Unboxed 
import Data.List (transpose) 

solve n matrix = 
    hungarianMethodInt (listArray ((1,1),(n,n)) $ concat $ transpose matrix)