एक निर्देशित एसाइक्लिक ग्राफ को ग्रिड/मैट्रिक्स

Question

पर मैप करने के तरीके मेरे पास कई हजार वर्टेक्स और किनारों वाला एक डीएजी है।

मैं एल्गोरिदम की तलाश में हूं जो ग्रिड पॉइंट्स पर कशेरुक को सबसे अधिक मानवीय अनुकूल/सौंदर्यशास्त्र में रख सकता है। मेरा झुकाव यह है कि सबसे अच्छा लेआउट कम से कम लंबाई की लंबाई के साथ लेआउट के समान होगा।

क्या आप मुझे न्यूनतम लंबाई के लेआउट लेआउट के लिए कुशल एल्गोरिदम के लिए इंगित कर सकते हैं, या अन्य एल्गोरिदम जो इस समस्या से निपटने में मेरी मदद कर सकते हैं?

यहाँ एक बहुत ही भोली एल्गोरिथ्म से उत्पादन का हिस्सा है:

Answer 1

मैं बहुत यकीन है कि यह एक खुला समस्या है कर रहा हूँ ("graph drawing")।

• किनारों एक शीर्ष से आ रही (अधिकतम)
• बढ़त क्रॉसिंग की संख्या के बीच कोण (कम से कम)

आप एक उपयोग करने में सक्षम हो सकता है: एक जोड़े को अन्य बातों के आप अनुकूलित करने पर विचार करना चाह सकते हैं जेनेटिक एल्गोरिदम या metaheuristic के कुछ अन्य प्रकार, लेकिन मुझे नहीं पता कि परिणाम कितने अच्छे होंगे।