Bazı kısıtlamalar göz önüne alındığında, düğümlerin bir listesinin bağlanabileceğini doğrulamak için hangi algoritmayı kullanabilirim?

Question

Oyuncunun rastgele bir düğüm kümesi verildiği bir oyun yapıyorum ve düğümleri belirli bir sıraya yerleştirerek yapabilecekleri en uzun listeyi oluşturmaya çalışıyor. Her düğümün, listedeki bir sonraki düğümün yanında en az bir bağlantıyla eşleşmesi gereken kenarlarda sıfır veya daha fazla bağlantı vardır. Örneğin, bir düğüm bu gibi görünebilir:

    +--+ 
left connections A B right connections 
        B C 
        +--+ 

yukarıdaki düğümü (örnek düğüm), bu düğümlerin herhangi biriyle bağlantılı olabilir: o üç düğüm verilen

Yani

+--+ 
C | This node can connect to the right side of the example node (matches C) 
D | 
+--+ 

+--+ 
B K This node can connect to the left side of the example node (matches A) 
L A This node can connect to the right side of the example node (matches B) 
+--+ 

, oyuncu olabilir bunları bir listede eşleştirin:

Oyuncunun seçimlerini doğrulamam gerekiyor. Oyuncunun ilk başta doğru sırada düğümleri seçmesi gerekmez, ancak sonuçtaki son seçimler bitişik, doğrusal bir listeye bağlanabilmelidir.

Yani, bir dizi sıralanmamış düğüm (oyuncu seçimi) verildiğinde, düğümleri yukarıdaki gibi geçerli bir listeye yerleştirmem ya da oynatıcıya bir hata göstermem gerekiyor.

Doğrulamayı zorlayabilirim ama daha zarif bir çözüm bulmayı umuyordum.

Given a graph determine whether it has a path traversing all nodes 

tam the Hamiltonian problem geçerli:

Answer 1

karma up ve problem gibi görünebilir bazı Ön Hesaplamaları sonra. Bu konuyla ilgili araştırmaları okuyabilir veya grafiğinizin belirli yapısını analiz edebilirsiniz (bazı özel grafikler için basit çözümlere sahiptir), ancak genel olarak bildiğim en iyi çözüm üstel olur. Bununla birlikte, basit kaba kuvvet çözümünün tüm permütasyonlardan (n!) geçmesi ve uygun yol oluşturup oluşturmadığı kontrol edilir (*n). Bu yaklaşım, O(n*n!) asimptotik ile sonuçlanır. Etkin olarak, n'un alt saniye kontrolü için maksimum 12 olması ve n=15 için en kötü durumda kontrol edilmesi birkaç saat alacağı anlamına gelir.

hafif optimizasyon - daha da hızlı ortalama en kötü durumda birkaç saniye içinde n=13 kontrol etmek mümkün olacak ve böylece, O(n!) sürede sonuç kötü durumda - tedricen yolunu oluşturan ve her yeni verteksteki kontrol Bir çok yanlış yol erken aşamada kesilecek.

Daha ileri gidebilir ve dinamik programlamanın avantajlarından yararlanabilirsiniz. isProperPath[S][i] (S, düğümlerin alt kümesinin bir bit maskesidir, i bu alt kümenin bazı düğümüdür) S numaralı son düğümde i ile ilgili altküme düğümlerinin oluşturduğu yola karşılık gelen değeri tanımlayalım. Sonra sonra S az elemanları ile alt-gruplar için tüm değerler göre isProperPath[S][i] hesaplamak kolaydır:

isProperPath[S][i] = false; 
for (j in S) { 
    if (isProperPath[S\i][j] && hasConnection(j, i)) 
     isProperPath[S][i] = true; 
} 

tüm değerleri hesaplamak S artan büyüklük sırasına göre S ve i tüm çiftleri geçme ile. Ve cevabın, ve yalnızca A'un verilen tüm set ve i - düğümlerinden herhangi biri olması durumunda doğrudur.

Zaman karmaşıklığı orada 2^n*n değerlerdir ve önceki değerlere dayalı değerini hesaplamak için O(n) sürer uzay karmaşıklığı O(2^n*n) olduğunu O(2^n*n^2) olduğunu. Bu algoritma, 24'a kadar olan boyuttaki kümeleri, yaklaşık 400M bit veya 50Mb kullanarak alt saniye olarak kontrol etmeyi sağlar.