Yönlendirilmiş bir asiklik grafiğin bir grid/matrise eşlenmesiyle ilgili yollar

Question

Binlerce köşe ve kenarlı DAG'ım var.

Vertex'leri ızgara noktalarında en insan dostu/estetik bir şekilde konumlandırabilen algoritmalar arıyorum. Önsezim, en güzel düzenin kenar uzunluklarının minimum toplamı ile düzende benzer olması.

Bu tür minimum kenar uzunluğu düzenleri toplamı veya bu sorunu çözmemde yardımcı olabilecek başka algoritmalar için verimli algoritmalara işaret edebilir misiniz?

İşte çok naif algoritma gelen çıktının parçası:

Answer 1

Bu açık bir problemdir eminim ("graph drawing"). (Maksimize) kenar geçişlerini

sayısı bir tepe gelen kenarları arasındaki

• Açı

Bir kullanmak mümkün olabilir (minimize): Birkaç diğer şeyler optimize düşünebilirsiniz genetik algoritma veya başka bir çeşit metaheuristic, ama sonuçların ne kadar iyi olacağını bilmiyorum.