क्या कोई ज्ञात एल्गोरिदम ग्रिड में अंक के एक सेट को भरता है?

Question

मैंने इस खेल को Flow देखा, यह काफी रोचक लग रहा है।

प्रवाह बनाने के लिए पाइप के साथ मेल खाने वाले रंग कनेक्ट करें। सभी रंगों को हल करने के लिए सभी रंगों को जोड़ें, और पूरे बोर्ड को को कवर करें। लेकिन देखें, पाइप तोड़ देगा अगर वे पार या ओवरलैप हो जाएंगे।

जोड़े (x, y) का एक सेट को देखते हुए, पहेली को हल करने के लिए एक एल्गोरिथ्म है, अर्थात समूची ग्रिड में भरने (यह मानते हुए वहाँ एक समाधान है) कि मैं के बारे में पता नहीं कर रहा हूँ?

Answer 1

यह वैश्विक रूटिंग समस्या का एक बहुत विशिष्ट उदाहरण है। ग्लोबल रूटिंग वीएलएसआई सीएडी में एक अच्छी तरह से अध्ययन की गई समस्या है (जहां किसी को एकीकृत सर्किट में लाखों जाल रूट करने की आवश्यकता होती है)। समस्या एनपी-पूर्ण है और रनटाइम और गुणवत्ता के बीच आपको आवश्यक ट्रेडऑफ के आधार पर कई तरीकों से हल किया जा सकता है।

http://en.wikipedia.org/wiki/Routing_(electronic_design_automation)

कागज यहां विभिन्न तकनीकों के एक सर्वेक्षण देता है:: के बाद विकी एक अच्छा प्रारंभिक बिंदु है

http://dropzone.tamu.edu/~jhu/publications/HuIntegration01.pdf

मन में

भालू है कि संकेत दिया था मैं आम तौर पर एक हल करने का प्रयास आपके द्वारा बताई गई समस्या का कहीं अधिक जटिल संस्करण। कभी भी कम नहीं, गणितीय अवधारणाएं वही रहती हैं।