Algoritma yang efisien untuk mengambil penutupan transitif dari grafik asiklik diarahkan

14

Saya mencoba untuk memecahkan masalah grafik (ini bukan untuk pekerjaan rumah, hanya untuk melatih keterampilan saya). DAG diberikan, di mana V adalah himpunan simpul dan E tepi. Grafik diwakili sebagai daftar adjacency, jadi A v adalah himpunan yang berisi semua koneksi v . Tugas saya adalah untuk menemukan yang simpul dicapai dari setiap sudut v V . Solusi yang saya gunakan memiliki kompleksitas O ( V 3 )G(V,E)VEAvvvVO(V3), dengan penutupan transitif, tetapi saya membaca bahwa di blog bisa lebih cepat, meskipun tidak mengungkapkan caranya. Adakah yang bisa memberitahu saya cara lain (dengan kompleksitas yang lebih baik) untuk memecahkan masalah penutupan transitif dalam DAG?

Rontogiannis Aristofanis
sumber
Namun, saran saya adalah untuk menjaga . tetapi coba lakukan untuk mengurangi jumlah perbandingan secara rata-rata. Artinya, tebak dan tambahkan aturan sederhana ke algoritme Anda. Anda dapat menggunakan perkalian matriks - tetapi jika Anda menggunakannya untuk grafik kecil - maka itu hanya berantakan dan pada kenyataannya dalam praktiknya metode Anda lebih baik. O(|V|3)
AJed
@AJed Dalam masalah khusus ini, akan melebihi batas waktu. O(V3)
Rontogiannis Aristofanis
2
@RondogiannisAristophanes Ketika Anda mengatakan batas waktu, apakah maksud Anda bahwa ini merupakan masalah dalam beberapa tantangan pemrograman / algoritma seperti topcoder, dll? Jika demikian, dan jika Anda yakin telah menerapkan solusi , Anda mungkin ingin melihat masalahnya lagi. Mungkin ada beberapa properti tersembunyi lainnya yang mungkin menyederhanakan hal-hal, atau mungkin ada cara yang lebih baik untuk mengekspresikan masalah sehingga penutupan transitif tidak diperlukan. Karena penutupan transitif sama sulitnya dengan perkalian matriks. Baca student.cs.uwaterloo.ca/~cs466/Old_courses/F08/…O(V3)
Paresh

Jawaban:

8

Fakta bahwa grafik kita asiklik membuat masalah ini lebih sederhana.

Sortasi topologi dapat memberi kita urutan simpul sehingga, jika i < j , maka tidak ada tepi dari v j kembali ke v i . Kami telah membuat daftar simpul sedemikian rupa sehingga semua ujung masuk "maju" dalam daftar kami.v1,v2,,vni<jvjvi

(diedit untuk memperbaiki analisis dan memberikan algoritma yang sedikit lebih cepat)

Sekarang kita kembali ke daftar ini, mulai dari titik terakhir . v n 's penutupan transitif hanya sendiri. Juga tambahkan v n ke penutupan transitif setiap simpul dengan tepi ke v n .vnvnvnvn

Untuk setiap vertex , pergi dari ujung ke belakang, pertama-tama tambahkan v i ke penutupan transitifnya sendiri, kemudian tambahkan semua yang ada di penutupan transitif v i ke penutupan transitif semua simpul dengan ujung ke v i .vivivivi

Waktu berjalan adalah dalam kasus terburuk, dengan n jumlah simpul dan m O ( n 2 ) jumlah tepi. Sortasi topologis membutuhkan waktu O ( n + m ) . Kemudian kita melakukan pekerjaan O ( m n ) yang lain di backward pass: Ketika kita mundur daftar, untuk setiap edge, kita harus menambahkan hingga nO(n+m+nm)=O(n3)nmO(n2)O(n+m)O(mn)n simpul untuk penutupan transitif seseorang.

n=64iiijcjci

n>64

OO(n3)

usul
sumber
1
Anda mungkin bisa menggunakan representasi daftar tertaut untuk set dan mereka akhirnya akan berbagi ekor bersama.
Kyle Butt