पाइथन

में अधिकतम वजन/न्यूनतम लागत द्विपक्षीय मिलान कोड मैं द्विपक्षीय ग्राफ में अधिकतम वजन/न्यूनतम लागत मिलान के लिए पायथन कोड खोज रहा हूं। मैं नेटवर्कएक्स में सामान्य केस अधिकतम वजन मिलान कोड का उपयोग कर रहा हूं, लेकिन मुझे अपनी जरूरतों के लिए बहुत धीमी गति मिल रही है। यह संभवतः दोनों तथ्यों के कारण है कि सामान्य एल्गोरिदम धीमा है, और तथ्य यह है कि नेटवर्कएक्स समाधान पूरी तरह से पायथन में लागू किया गया है। आदर्श रूप से, मैं द्विपक्षीय मिलान समस्या के लिए कुछ पायथन कोड ढूंढना चाहता हूं जो कुछ सी/सी ++ कोड को लपेटता है, लेकिन अभी, नेटवर्कएक्स कार्यान्वयन से कुछ भी तेज़ होगा।पाइथन

स्रोत

2010-12-13 nomad

यदि आपके मन में कोई विशेष छद्म कोड है? क्या आप एक अजगर इनपुट/आउटपुट उदाहरण प्रदान कर सकते हैं? – kevpie

इसी तरह के प्रश्न http://stackoverflow.com/questions/4075669/hglish-algorithm-in-python – Ante

@ केवीपी मैं लगभग किसी भी इंटरफ़ेस के लिए खुला हूं। अधिकतम वजन समस्या, स्वयं अच्छी तरह से परिभाषित है (उदाहरण के लिए विकिपीडिया पर http://en.wikipedia.org/wiki/Matching_(graph_theory)#Maximum_matchings_in_bipartite_graphs) इसलिए मैं इसे फिर से परिभाषित करने की जगह बर्बाद नहीं करना चाहता था। इनपुट एक ग्राफ या यहां तक कि केवल एक वजन मैट्रिक्स होगा, और आउटपुट द्विपक्षीय शिखर के बीच एक मिलान होगा। – nomad

कुछ और जांच के बाद, मुझे निम्नलिखित दो मॉड्यूल विशेष रूप से सहायक (http://pypi.python.org/pypi/pyLAPJV/0.3 और http://pypi.python.org/pypi/hungarian) मिला है। वे पाइथन बाइंडिंग के साथ सी ++ में कार्यान्वित एल्गोरिदम दोनों हैं, और नेटवर्कएक्स मिलान कार्यान्वयन से बहुत तेज दौड़ते हैं। हालांकि, pyLAPJV कार्यान्वयन मेरी आवश्यकताओं के लिए थोड़ा सा फिकल लगता है और अच्छी तरह से भारित किनारों को अच्छी तरह से संभाल नहीं करता है। हंगेरी मॉड्यूल (हालांकि पीलापाजेवी एल्गोरिदम की तुलना में धीमी गति से धीमा) डेटा आकार पर नेटवर्कएक्स कार्यान्वयन की तुलना में तीव्रता के लगभग 3 ऑर्डर चलाता है, जिसका मैं वर्तमान में काम कर रहा हूं। मैं कुनीगामी द्वारा सुझाए गए कोड पर एक और नज़र डालने जा रहा हूं, क्योंकि मुझे विश्वास है कि शेडस्किन काफी हद तक तेजी से कार्यान्वयन देने के लिए काफी आसानी से चलाया जा सकता है।

स्रोत

2010-12-14 05:35:10 nomad

यह भी सुनिश्चित नहीं है कि आप यही चाहते हैं, लेकिन यह होपक्रॉफ्ट-कार्प द्विपक्षीय ग्राफ मिलान एल्गोरिदम का एक अजगर कार्यान्वयन है। यदि नहीं, तो यह शायद आपके लिए एक अच्छी शुरुआत जगह हो सकता है।

Hopcroft-Karp Bipartite Matching

स्रोत

2010-12-13 09:51:28

लिंक निको के लिए धन्यवाद। हालांकि, अधिकतम मिलान समस्या अधिकतम वजन मिलान समस्या से अधिक है; यह भाग लेने वाले शिखरों की अधिकतम संख्या को ढूंढने से चिंतित है, आंत वजन नहीं लेता है। – nomad

कम से कम वजन द्विपक्षीय मिलान हंगेरी एल्गोरिथ्म (wikipedia) द्वारा हल किया जा सकता है। विकिपीडिया में लिंक python कार्यान्वयन से लिंक है। मुझे यकीन नहीं है कि यह आपके द्वारा वर्णित कोड से तेज़ है, हालांकि।

स्रोत

2010-12-13 11:22:50 kunigami

धन्यवाद कुनीगामी, मैं इसे देख लूंगा और यह कैसे करता है यह जांचें। – nomad

क्या आपने हंगेरियन एल्गोरिदम के कार्यान्वयन की कोशिश की है, जिसे मंक्रेस या कुह्न-मंक्रेस एल्गोरिदम भी कहा जाता है?

scipy.optimize.linear_sum_assignment

स्रोत

2017-02-01 22:29:04