Solusi sains dan teknologi -- Menemukan jalur terpendek antara dua simpul dalam grafik adalah tugas umum dalam ilmu komputer dan ada beberapa solusi yang sangat bagus untuk itu.Algoritma Dijkstra adalah algoritma yang paling terkenal dan pasti salah satu algoritma paling intuitif untuk menemukan jalur terpendek.Ini sebenarnya lebih dari sekedar menemukan jalan terpendek dari A ke B - ia menemukan jalur terpendek dari A ke setiap titik.Algoritma naïve berjalan pada waktu \ (O (n ^ 3) \), dan Anda bisa mendapatkan waktu sebaik \ (O (n \ log nv) \) (di mana n adalah jumlah simpul dan v jumlah tepi ).
Solusi sains dan teknologi -- Ada juga banyak algoritma efisien lainnya.Berikut ini bukan algoritma yang efisien.Dr.Anstee menunjukkan fakta lucu pada kelas aljabar linear saya istilah terakhir: jika \ (A \) adalah matriks kedekatan untuk grafik, maka \ (A ^ 2 \) adalah matriks jarak 2 koneksi, yaitu ada 1 pada posisi \ ((i, j) \) jika vertek \ (i ^ \ text {th} \) terhubung ke verteks yang terhubung ke verteks \ (j ^ \ text {th} \).Sebagai contoh, pertimbangkan sp yang dihasilkan secara acak iniMatikan matriks konektivitas: \ (A = \ begin {bmatrix} {\ color {gray} 0} & {\ color {gray} 0} & 1 & {\ color {gray} 0} & {\ color {gray} 0} & { \ color {gray} 0} & {\ color {gray} 0} & {\ color {gray} 0} & {\ color {gray} 0} & {\ color {gray} 0} & 1 & {\ color {gray} 0} \ \ {\ color {gray} 0} & 1 & {\ color {gray} 0} & {\ color {gray} 0} & 1 & {\ color {gray} 0} & 1 & {\ color {gray} 0} & { \ color {gray} 0} & {\ color {gray} 0} & {\ color {gray} 0} & {\ color {gray} 0} \\ {\ color {gray} 0} & {\ color {gray } 0} & {\ color {gray} 0} & {\ color {gray} 0} & {\ color {gray} 0} & {\ color {gray} 0} & {\ color {gray} 0} & 1 & { \ color {gray} 0} & {\ color {gray} 0} & {\ color {gray} 0} & {\ color {gray} 0} \\ {\ color {gray} 0} & {\ color {gray } 0} & 1 & {\ color {gray} 0} & {\ color {gray} 0} & 1 & {\ color {gray} 0} & 1 & {\ color {gray} 0} & {\ color {gray} 0} & { \ color {gray} 0} & {\ color {gray} 0} \\ {\ color {gray} 0} & {\ color {gray} 0} & {\ color {gray} 0} & {\ color {gray } 0} & 1 & {\ color {gray} 0} & {\ color {gray} 0} & {\ color {gray} 0} & {\ color {gray} 0} & {\ color {gray} 0} & { \ color {gray} 0} & {\ color {gray} 0} \\ {\ color {gray} 0} & {\ color {gray} 0} & 1 & {\ color {gray} 0} & {\ color {gray } 0} & {\ color {gray} 0} & {\ color {gray} 0} & {\ color {gray} 0} & {\ color {gray} 0} & 1 & {\ color {gray} 0} & {\ color {gray} 0} \\ {\ color {gray} 0} & {\ color {gray} 0} & {\ color {gray} 0} & 1 & 1 & {\ color {gray} 0} & {\ color {gray} 0} & {\ color {gray} 0} & 1 & 1 & {\ color {gray} 0} & {\ color {gray} 0} \\ {\ color {grey} 0} & {\ color {gray} 0} & {\ color {gray} 0} & {\ color {gray} 0} & {\ color {gray} 0} & {\ color {gray} 0} & {\ color {gray} 0} & 1 & {\ color {gray} 0} & {\ color {gray} 0} & {\ color {gray} 0} & {\ color {gray} 0} \\ {\ color {grey} 0} & {\ color {gray} 0} & {\ color {gray} 0} & {\ color {gray} 0} & {\ color {gray} 0} & {\ color {gray} 0} & 1 & {& warna {kelabu} 0} & {\ color {gray} 0} & {\ color {gray} 0} & {\ color {gray} 0} \\ {\ color {gray} 0} & 1 & {\ color {grey} 0} & {\ color {gray} 0} & {\ color {gray} 0} & {\ color {gray} 0} & {\ color {gray} 0} & {\ color {gray} 0} & {\ color {gray} 0} & {\ color {gray} 0} & {\ color {gray} 0} & 1 \\ {\ color {gray} 0} & {\ color {gray} 0} & {\ color {gray} 0} & {\ color {gray} 0} & {\ color {gray} 0} & {\ color {gray} 0} warna {kelabu} 0} & {\ color {gray} 0} & {\ color {gray} 0} & {\ color {gray} 0} & {\ color {gray} 0} & {\ color {gray} 0 } & {\ color {gray} 0} & {\ color {gray} 0} & 1 & {\ color {gray} 0} \\ \ end {bmatrix} \) Inilah visualisasi grafik untuk matriks ini (dibuat dengan graphviz, a alat command-line super berguna): Sayangnya, vertex 1 tidak terhubung dengan apapun (pergilah memeriksa kolom pertama sendiri!) sehingga tidak tergambar.
Solusi sains dan teknologi -- Sekarang perhatikan kedekatan jarak-2 (a 2 menunjukkan ada dua jalur antara simpul dengan panjang 2, dan juga untuk 3): \ (A ^ 2 = \ begin {bmatrix} {\ color {gray} 0} & {\ warna {kelabu} 0} & {\ color {gray} 0} & {\ color {gray} 0} & {\ color {gray} 0} & {\ color {gray} 0} & {\ color {gray} 0 } & {\ color {gray} 0} & {\ color {gray} 0} & {\ color {gray} 0} & {\ color {gray} 0} & {\ color {gray} 0} \\ {\ warna {abu} 0} & 2 & {\ color {gray} 0} & {\ color {gray} 0} & 1 & {\ color {gray} 0} & 1 & {\ color {gray} 0} & {\ color {gray} 0 } & {\ color {gray} 0} & {\ color {gray} 0} & 1 \\ {\ color {gray} 0} & {\ color {gray} 0} & 3 & {\ color {gray} 0} & { \ color {gray} 0} & 1 & {\ color {gray} 0} & 1 & {\ color {gray} 0} & 1 & 1 & {\ color {gray} 0} \\ {\ color {gray} 0} & {\ color {gray } 0} & {\ color {gray} 0} & 1 & 1 & {\ color {gray} 0} & {\ color {gray} 0} & {\ color {gray} 0} & 1 & {\ color {gray} 0} & { \ color {gray} 0} \\ {\ color {gray} 0} & 1 & {\ color {gray} 0} & 1 & 3 & {\ color {gray} 0} & 1 & {\ color {gray} 0} & 1 & 1 & {\ color {abu-abu } 0} & {\ color {gray} 0} \\ {\ color {gray} 0} & {\ color {gray} 0} & 1 & {\ color {gray} 0} &{\ color {gray} 0} & 1 & {\ color {gray} 0} & 1 & {\ color {gray} 0} & {\ color {gray} 0} & {\ color {gray} 0} & {\ color {abu-abu } 0} \\ {\ color {gray} 0} & 1 & {\ color {gray} 0} & {\ color {gray} 0} & 1 & {\ color {gray} 0} & 2 & 1 & {\ color {gray} 0} & {\ color {gray} 0} & {\ color {gray} 0} & {\ color {gray} 0} \\ {\ color {gray} 0} & {\ color {gray} 0} & 1 & {\ color { abu} 0} & {\ color {gray} 0} & 1 & 1 & 4 & {\ color {gray} 0} & {\ color {gray} 0} & {\ color {gray} 0} & {\ color {gray} 0} \ \ {\ color {gray} 0} & {\ color {gray} 0} & {\ color {gray} 0} & 1 & 1 & {\ color {gray} 0} & {\ color {gray} 0} & {\ color { abu} 0} & 1 & 1 & {\ color {gray} 0} & {\ color {gray} 0} \\ {\ color {gray} 0} & {\ color {gray} 0} & 1 & 1 & {\ color {gray} 0} & {\ color {gray} 0} & {\ color {gray} 0} & 1 & 2 & {\ color {gray} 0} & {\ color {gray} 0} \\ {\ color {gray} 0} & {\ color {grey} 0} & 1 & {\ color {gray} 0} & {\ color {gray} 0} & {\ color {gray} 0} & {\ color {gray} 0} & {\ color {gray} 0} & {\ color {gray} 0} & {\ color {gray} 0} & 2 & {\ color {gray} 0} \\ {color {gray} 0} & 1 & {\ color {gray} 0} & {\ color {grey} 0} & {\ color {gray} 0} & {\ color {gray} 0} & {\ color {gray} 0} & {\ color {gray} 0} & {\ color {gray} 0} & {\ color {gray} 0} & {\ color {gray} 0} & 1 \ end {bmatrix} \) Dan vis kamualization.Ini adalah grafik yang sama seperti sebelumnya, tapi tepi merah muda menunjukkan ada jalur panjang 2 di antara dua simpul: Sekarang kita memiliki awal dari sebuah algoritma.Untuk menemukan jalur terpendek dari \ (v_i \) ke \ (v_j \) Kita hanya perlu menemukan paling sedikit \ (d \ in \ mathbb {N} \) sehingga matriks \ (A ^ d \) memiliki non Sel zero berada pada posisi (i, j).Dengan kata lain, kita harus menyelesaikan persamaan ini: \, (\ n \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ sebuah jenis persamaan Diophantine, yang umumnya tidak dapat diselesaikan secara aljabar.
Solusi sains dan teknologi -- Jadi saya mengusulkan sedikit kekuatan kasar: def ShortestPath (Matrix A, int i, int j): d = 0; sementara (A ^ d) [i, j] ≠ 0: d; kembali d; Sekarang, satu-satunya alasan mengapa algoritma ini memiliki harapan untuk bersaing adalah Matrik dapat dikalikan dan diekskalkan dengan cepat.Perkalian Matriks Efisien merupakan bidang penelitian yang aktif.Anehnya, ada algoritma yang bisa mengalikan matriks lebih cepat dari waktu \ (O (n ^ 3) \).Pada saat penulisan, catatan adalah \ (O (n ^ {2.37}) \) waktu terburuk.Namun, kita tidak akan banyak mengalikan matriks.
Solusi sains dan teknologi -- Kami akan exponentiating mereka.Jika matriks dapat didiagonalisasi, eksponensiasi sepele.Kita hanya perlu mengubah basis ke dalam ruang eigen dari matriks, yang mensyaratkan penghitungan vektor eigen dan nilai eigen dari mat riks.Untungnya, jika grafik tidak diarahkan, kita dijamin dapat menemukan basis ortonormal dari vektor eigen.
Solusi sains dan teknologi -- Karena ini adalah matriks kedekatan, saya tidak tahu pasti apa arti vektor eigen dan nilai eigen, tapi tampaknya sangat jelek.Berikut adalah nilai eigen dari matriks di atas: \ (\ lambda \ in \ {-2.223, -1.948, -1.320, -0.671, -0.358, \\ \, \, \, \, \, \, \, \, \, \, \, \, \, \, 0, 0, 0.322, 1, 1.126, 1.664, 2.408, \} \\\) Yang sangat menarik adalah bahwa 0 adalah nilai eigen yang berulang.Mudah sekali menemukan vektor eigen pertama untuk \ (\ lambda = 0 \) dengan tangan (ingat verteks 1 tidak membuat potongannya), tapi yang kedua agak sulit.Membiarkan's memilih dua simpul (katakanlah simpul 2 dan 4) dan coba algoritma ini dengan Octave: oktaf: 44> (U * D * V) (2,4) ans = 0 oktaf: 45> (U * D ^ 2 * V) (2,4) ans = 0 oktaf: 46> (U * D ^ 3 * V) (2,4) ans = 0 oktaf: 47> (U * D ^ 4 * V) (2,4) ans = 1 oktaf: 48> int8 (U * D ^ 4 * V) ans = 0 0 0 0 0 0 0 0 0 0 0 0 0 7 0 1 6 0 5 1 1 1 0 3 0 0 13 1 1 5 1 8 1 5 5 0 0 1 1 4 6 0 1 0 4 5 0 0 0 6 1 6 14 0 6 1 6 7 0 1 0 0 5 0 0 3 1 6 0 1 1 0 0 5 1 1 6 1 7 6 1 1 0 1 0 1 8 0 1 6 6 19 0 1 1 0 0 1 1 4 6 0 1 0 4 5 0 0 0 1 5 5 7 1 1 1 5 8 1 0 0 0 5 0 0 1 0 1 0 1 5 0 0 3 0 0 1 0 1 0 0 0 0 2 Cantik.
Solusi sains dan teknologi -- Kita melihat jalur terdekat seharusnya panjang 4, dan jika Anda menggulirkan kembali ke grafik, itulah yang kita amati.Atau ini dia lagi: Yap.Jalannya adalah: V4-V8-V5-V3-V2, yang memiliki 4 sisi di dalamnya.Keren.
Solusi sains dan teknologi -- Berhasil.Jadi, apa kompleksitas waktu itu.Kami: Menghasilkan basis vektor eigen: \ (O (n ^ 2) \) Keluarkan setiap nilai eigen: \ (O (1) \).Semacam.
Solusi sains dan teknologi -- Kalikan beberapa matriks: \ (O (n ^ {2.37 \ ldots}) \)Ulangi dua langkah di atas beberapa kali.Berapa kali.Tidak ada jalur terpendek yang bisa melebihi panjang \ (n \) (jumlah simpul), dengan asumsi grafik terhubung (grafik ironisnya tidak.Vertex 1 menyebabkan masalah lagi.) Secara keseluruhan, kita memiliki \ (O ( n ^ {1 2.37 \ ldots}) \) algoritma terburuk, yang jauh lebih buruk daripada Dijkstra's.
Solusi sains dan teknologi -- Baiklah.Algoritma ini paling tidak menyenangkan.
Tidak ada komentar:
Posting Komentar