कुछ इनपुट देखते हुए, जिसमें बाएं और दाएं प्रतीक होते हैं, आउटपुट चेन जो इनपुट को लिंक करते हैं।डोमिनोज़ मिलान एल्गोरिदम
डोमिनोज़ होने के लिए इनपुट की कल्पना करें, जिसे आप क्षैतिज पर फ़्लिप नहीं कर सकते हैं और उन्हें एक साथ श्रृंखला की आवश्यकता है। बड़ी परिपत्र श्रृंखलाएं बनाना (अगर आप वास्तविक डोमिनोज़ के साथ शारीरिक रूप से ऐसा नहीं कर सकते हैं) को अनदेखा करें, छोटे परिपत्र श्रृंखलाओं पर प्राथमिकता दी जाती है जिन्हें श्रृंखलाओं पर प्राथमिकता दी जाती है जहां प्रारंभ और अंत मेल नहीं खाता है।
अधिक परिपत्र श्रृंखलाओं के साथ आउटपुट (चाहे कितने या श्रृंखला की लंबाई) हम जो खोज रहे हैं। उदाहरण के लिए, 3 गोलाकार श्रृंखलाओं का उत्पादन 1 बड़ी श्रृंखला और एक बचे हुए एकल डोमिनोज़ से बेहतर है।
क्या कोई मुझे सही दिशा में इंगित कर सकता है? यह किस समस्या का समूह है और यह हल करने के लिए मौजूदा एल्गोरिदम हैं?
उदाहरण (आउटपुट गलत हो सकता है!):
in[0]=(A,B)
in[1]=(B,C)
in[2]=(C,A)
out[0]=(0,1,2)
in[0]=(A,B)
in[1]=(B,A)
in[2]=(C,D)
in[3]=(D,C)
out[0]=(0,1)
out[1]=(2,3)
in[0]=(A,B)
in[1]=(B,A)
in[2]=(C,D)
in[3]=(E,F)
out[0]=(0,1)
out[1]=(2)
out[2]=(3)
in[0]=(A,B)
in[1]=(B,A)
in[2]=(C,D)
in[3]=(D,E)
out[0]=(0,1)
out[1]=(2,3)
in[0]=(A,B)
in[1]=(B,C)
in[2]=(C,D)
out[0]=(0,1,2)
@Lieven सुधार के लिए धन्यवाद। – zaf
इसका जिक्र नहीं है लेकिन मुझे इसका जवाब पता होना चाहिए। मैं खुद ग्राफ के संदर्भ में सोच रहा था लेकिन यह एक ऐसा क्षेत्र है जहां मेरे कौशल में गंभीरता से कमी है। Http://www.amazon.co.uk/Algorithm-Design-Manual-Steven-Skiena/dp/1848000693/ref=sr_1_1?s=books&ie=UTF8&qid=1301312087&sr=1-1 पढ़कर स्वयं को बेहतर बनाने की कोशिश कर रहा हूं। यदि आप, मेरे जैसे, मेरे पास पर्याप्त गणितीय पृष्ठभूमि नहीं है, तो मैं अत्यधिक अनुशंसा कर सकता हूं। –
@ लिवन अरे! मेरे पास एक मजबूत गणितीय पृष्ठभूमि है। मैंने अभी पर्याप्त डोमिनोज़ नहीं खेला है :) – zaf