Bir DAG'ın en uzun yolunu bulmak için, 2 algoritmanın farkındayım: Algo 1: topolojik sıralama yapın + sort ~ veya ~ algo 2 sonucu dinamik programlama kullanın: tümünü sıralayın DFS'yi DFS kullanarak yollar ve en uzun kayıt. DFS ile tüm yolları saymak, algo 1'den daha karmaşık bir yapıya sahip gibi görünüyor. Bu doğru mu?DAG'ın en uzun yolu DAG
İkinci seçeneğiniz yanlış: DFS grafiğiniz ağaç veya orman olmadığı sürece olası tüm yolları araştırmaz ve köklerden başlarsınız. Bildiğim ikinci algoritma, ağırlıkları reddetmek ve en kısa yolu bulmaktır, ancak # 1 olarak listelediğiniz top sort + DP algorithm'dan biraz daha yavaştır.
Tamam, DFS'yi yeniden başlatma ile kastediyorum. Önceki DFS geçişlerinde ziyaret edilmeyen herhangi bir köşe noktası. Bu tüm DAG'ı keşfedecek. Topo sort + DP'den daha hızlı olmamalı mı? – Frank
@Frank DFS, ziyaret edilmeyen köşe noktalarından yeniden başlatıldığında tüm yolları araştırmayacaktır. A -> B-> C 'grafiğini düşünün; DFS'yi B'den başlatırsınız, C'ye gidin ve durun; daha sonra A'dan başlayarak B'ye gidin ve tekrar durun, çünkü zaten C'yi ziyaret ettiniz. DFS'nin, B-C ve A-B'nin bulduğu her iki yol da uzunluk 1'dir; A-B-C'nin en uzun yolu 2'dir. – dasblinkenlight
Neden B'den başlıyorsunuz? DFS'yi kaynaklardan başlatmalısınız. – Frank
Numaralandırma "DFS" kullanarak bir DAG tüm yollar:
def enumerate_dag(g):
def enumerate_r(n, paths, visited, a_path = []):
a_path += [n]
visited[n] = 1
if not g[n]:
paths += [list(a_path)]
else:
for nn in g[n]:
enumerate_r(nn, paths, visited, list(a_path))
paths, N = [], len(g)
visited = np.zeros((N), dtype='int32')
for root in range(N):
if visited[root]: continue
enumerate_r(root, paths, visited, [])
return paths
Bu koda çift elmaslı bir grafik geçmeyi denediniz mi? En uzun yolu kaçırma şansının 50/50 olduğu anlaşılıyor. – dasblinkenlight
Sadece denedim: [[1,2], [3], [3], [4], [5,6], [7], [7], [8], [9], [ ]]. 4 yol alırım: [[0, 1, 3, 4, 5, 7, 8, 9], [0, 1, 3, 4, 6, 7, 8, 9], [0, 2, 3, 4 , 5, 7, 8, 9], [0, 2, 3, 4, 6, 7, 8, 9]], ki doğru cevabı olduğuna inanıyorum. Anlattığım kadarıyla (diğer birçok testten), bu algoritma bir DAG içindeki yolları doğru olarak numaralandırır. Topo sort, DFS'nin çok benzer bir kullanımına dayanmaktadır. Kaynaklarda başlat/yeniden başlatmanız koşuluyla, DFS, her kaynaktan erişilebilen nodları * tüm * okuyacaktır, dolayısıyla yukarıdaki kod * tamamen * DAG'yi araştırır, hiçbir köşe kaçırılmaz. – Frank
Kodunuzda 'ziyaret edilen' kullanımını yanlış anlamıştım: siz onu ayarlayın, ancak geçişe devam edip etmemeniz gerektiğine karar vermek için kullanmayın. Bu, DFS (http://en.wikipedia.org/wiki/Depth-first_search) adı verilen bir şey değildir, çünkü DFS tamamen araştırılmış olan düğümleri ziyaret etmez. DFS ile kodunuz arasındaki en büyük fark, kodunuzun büyük ölçüde verimsiz olmasıdır. Ne demek istediğimi görmek için aynı elmas desenini elli kez tekrarlamayı deneyin: programınız tüm 2^50'lerin yollarını keşfedecek ve keşfedilecek çok yol var. – dasblinkenlight
yok DFS gerekli. Algoritma: DAG G. Her yay bütün düğümler işlendikten zaman
for each node with no predecessor :
for each of his leaving arcs, E=1.
for each node whose predecessors have all been visited :
for each of his leaving arcs, E=max(E(entering arcs))+1.
MAX_PATH kenarları içinde yüksek E bir değişken E tutar alır.
Doğru cevap budur; https://en.wikipedia.org/wiki/Longest_path_problem#Acyclic_graphs_and_critical_paths sayfasına bakın. –
[CS.SE] ile ilgili: [Bir DAG'de iki köşe arasındaki en kısa ve en uzun yolları bulma (http://cs.stackexchange.com/q/11295/11177) – Palec