Algoritma yang menemukan jumlah jalur sederhana dari ke di

34

Can anyone menyarankan saya algoritma waktu linear yang mengambil sebagai masukan diarahkan asiklik grafik dan dua simpul dan dan kembali jumlah jalur sederhana dari ke di . Saya memiliki algoritma di mana saya akan menjalankan DFS (Depth First Search) tetapi jika DFS menemukan maka tidak akan mengubah warna (dari putih menjadi abu-abu) dari salah satu node yang ada di jalur sehingga jika ini adalah subpath dari jalur lain maka DFS juga akan melalui subpath ini lagi. Sebagai contoh pertimbangkan daftar adjacency di mana kita perlu menemukan jumlah path dari p ke v .G=(V,E)ststG
tstpv

poszorsvsrryyvvwzwz
Di sini DFS akan mulai dengan p dan kemudian katakanlah ia pergi ke pz karena tidak menemukan v DFS akan berjalan secara normal. Sekarang kedua path adalah psryv karena ia bertemu v kita tidak akan mengubah warna simpul s,r,y,v ke grey. Lalu path pov karena warna v masih putih. Lalu path posryv karena warna s putih dan sama dengan path poryv.Juga counter dipertahankan yang bertambah ketika v ditemui.

Apakah algoritme saya benar? jika tidak, modifikasi apa yang diperlukan untuk membuatnya benar atau pendekatan lain akan sangat dihargai.

Catatan : Di sini saya telah mempertimbangkan algoritma DFS yang diberikan dalam buku "Pengantar algoritma oleh Cormen" di mana ia mewarnai node sesuai dengan statusnya. Jadi jika node belum dikunjungi, belum dieksplorasi dan dieksplorasi maka warnanya akan menjadi putih, abu-abu dan hitam masing-masing. Semua hal lain adalah standar.

Saurabh
sumber
4
Perhatikan bahwa semua jalur dalam grafik asiklik terarah harus sederhana (berdasarkan asiklik ).
Noldorin

Jawaban:

37

Implementasi Anda saat ini akan menghitung jumlah jalur yang benar dalam DAG. Namun, dengan tidak menandai jalur, ini akan membutuhkan waktu yang eksponensial. Misalnya, dalam ilustrasi di bawah ini, setiap tahap DAG meningkatkan jumlah total lintasan dengan kelipatan 3. Pertumbuhan eksponensial ini dapat ditangani dengan pemrograman dinamis.

dag

Menghitung jumlah jalur - dalam DAG diberikan oleh pengulangan, st

Paths(u)={1if u=t(u,v)EPaths(v)otherwise.

Modifikasi sederhana DFS akan menghitung ini diberikan sebagai

def dfs(u, t):
    if u == t:
        return 1
    else:
        if not u.npaths:
            # assume sum returns 0 if u has no children
            u.npaths = sum(dfs(c, t) for c in u.children)
        return u.npaths

Tidaklah sulit untuk melihat bahwa setiap sisi dilihat hanya satu kali saja, karenanya merupakan runtime dari .O(V+E)

Nicholas Mancuso
sumber
Saya mengerti algoritme Anda dan dapat dibuat sedikit lebih efisien dengan menggunakan pemrograman dinamis karena panggilan rekursif yang sama dipanggil berkali-kali sehingga lebih baik untuk menghemat. Benar ??
Saurabh
1
@SaurabhHota, menggunakan pemrograman dinamis. Pertama kali simpul ditemui, itu menghitung jumlah lintasan yang harus . Ini disimpan di u.npaths. Setiap panggilan selanjutnya ke tidak akan menghitung ulang jumlah jalurnya, tetapi cukup mengembalikan jalur Anda. utu
Nicholas Mancuso
1
Untuk grafik seperti itu, bukankah jawabannya hanya m ^ n di mana m adalah jumlah node dalam kolom (3 di sini) dan n adalah jumlah kolom tidak termasuk s, t (4 di sini). output adalah 3 ^ 4 = 81 untuk grafik contoh.
saadtaame
@saadtaame, tentu; Namun, maksud saya adalah hanya menampilkan peningkatan eksponensial saat "panjang" grafik tumbuh. Tentu saja untuk grafik yang sangat terstruktur itu Anda dapat menghitung dalam bentuk tertutup sementara algoritma yang tercantum berfungsi untuk semua grafik.
Nicholas Mancuso
3
Waktu berjalan mengasumsikan bahwa Anda dapat melakukan penambahan yang diperlukan dalam waktu konstan, tetapi angka yang ditambahkan dapat memiliki bit dalam kasus terburuk. Jika Anda menginginkan jumlah jalur yang tepat , waktu berjalan (menghitung operasi bit) sebenarnya . O(V+E)Θ(V)O(VE)
JeffE
15

Anda hanya perlu memperhatikan bahwa jumlah jalur dari satu simpul ke simpul target adalah jumlah dari jumlah jalur dari anak-anaknya ke target. Anda tahu bahwa algoritma ini akan selalu berhenti karena grafik Anda tidak memiliki siklus.

Sekarang, jika Anda menyimpan jumlah jalur dari satu node ke target saat Anda mengunjungi node, kompleksitas waktu menjadi linear dalam jumlah simpul dan memori linear dalam jumlah node.

molyss
sumber
0

Jumlah jalur antara dua simpul dalam DAG dapat ditemukan menggunakan representasi matriks adjacency.

Misalkan A adalah matriks adjacency dari G. Mengambil kekuatan Kth dari A setelah menambahkan matriks identitas ke dalamnya, memberikan jumlah lintasan panjang <= K.

Karena panjang maks dari setiap jalur sederhana dalam DAG adalah | V | -1, menghitung daya | V | -1 akan memberikan jumlah jalur antara semua pasangan simpul.

Menghitung | V | -1 th kekuatan dapat dilakukan dengan melakukan muliplications log (| V | -1) masing-masing TC: | V | ^ 2.

Vivek Anand Sampath
sumber
Pertanyaannya meminta algoritma waktu linier. Algoritma Anda lebih lambat dari itu.
DW
@Vivek dapatkah Anda menyebutkan referensi untuk teorema dalam jawaban Anda?
Hamideh