Apakah algoritma Dijkstra merupakan solusi yang tepat untuk masalah rute sinyal ini?

Saya sedang dalam proses mengembangkan manajemen sinyal dan modul routing untuk sistem audiovisual terintegrasi dan saya merancang itu dengan maksud menjadi sefleksibel mungkin di berbagai jaringan distribusi sinyal. Tujuan modul ini adalah untuk menangani perutean di sejumlah pengalih matriks yang ditumpuk ¹ dan menangani konversi format yang diperlukan.

Solusi terbaik yang saya jelajahi pada saat ini adalah memetakan jaringan ke grafik dengan simpul diskrit untuk setiap jenis sinyal yang didukung oleh switchers dan yang kemudian bergabung melalui node yang mewakili prosesor video yang menangani konversi format.

Contoh grafik

Warna mewakili format sinyal. Round node adalah switchers, source, atau sink. Node persegi adalah prosesor video yang melakukan konversi format.

Dari sana saya dapat menggunakan implementasi algoritma Dijkstra untuk mengidentifikasi jalur yang harus dibentuk untuk mendapatkan input X ke output Y. Ini harus memungkinkan data tentang konfigurasi input / output dari semua switcher dan prosesor untuk dilewatkan dalam dan modulnya beradaptasi.

Apakah ini solusi yang tepat atau apakah ada pendekatan alternatif yang mungkin perlu diselidiki?

_{¹ alias 'crossbar switch', router video dengan input M x output yang mendukung koneksi satu-ke-banyak. Setiap perangkat fisik dapat menangani berbagai format sinyal dan mungkin atau mungkin tidak dapat melakukan konversi format apa pun.}

sunting: Seperti yang disebutkan oleh Péter Török, grafik tidak harus berupa pohon, diagram adalah contoh sederhana untuk menggambarkan ide tersebut. Ketika diimplementasikan di jalur nyata 'dunia nyata' mungkin ada yang menawarkan berbagai tingkat definisi (DVI> VGA> komponen> komposit) yang saya rencanakan untuk wakili dengan bobot tepi.

sunting 2: Berikut adalah contoh yang sedikit lebih komprehensif dengan direktivitas yang ditunjukkan dan menunjukkan jaringan yang terdiri dari dua jenis sinyal. Contoh awal telah dimodifikasi sedikit sehingga setiap input dan output pada suatu perangkat didefinisikan sebagai simpul diskrit karena ini akan memberikan data yang diperlukan untuk mengontrol pemilihan / pemilihan input matriks. Contoh 2 - dua jenis sinyal, switchers bertumpuk

design algorithms Kim Burgess
sumber

Apakah Anda ingin bobot tepi menjadi multiplikasi?

Peter Taylor

Aditif Teori yang menyatakan hal ini akan memungkinkan untuk didefinisikan sedemikian rupa sehingga semakin tinggi definisi jalur sinyal, semakin rendah bobotnya. Tepian yang menghubungkan node yang melakukan konversi format kemudian akan diberi bobot lebih tinggi dari yang ditugaskan ke tepi yang menghubungkan node non-konversi. Ini akan merutekan sinyal dalam format asli jika memungkinkan, hanya melibatkan konversi format (dan degradasi sinyal terkait dan pemanfaatan peralatan) bila perlu.

Kim Burgess

@PeterTaylor: Apakah penting jika mereka multiplikasi? Mereka memiliki semantik yang sama persis sebagai aditif (asalkan mereka positif) dengan menerapkan logaritma. Atau apakah ada sesuatu yang lebih rumit di belakangnya?

herby

@herby, poin bagus, tidak memikirkan itu. hang head in malu

Peter Taylor

Jawaban:

Ini adalah pohon, Dijkstra adalah O ( n ^ 2 ) berlebihan. Pencarian sepele O ( n ) pertama kali sudah cukup.

EDIT: Mulai BFS di setiap simpul dengan derajat setidaknya dua.

EDIT2: Karena grafik tidak dijamin menjadi pohon, gunakan Dijkstra, jika Anda ingin sedikit mengoptimalkan, Anda dapat terlebih dahulu "strip" grafik semua simpul derajat satu (bagi mereka, jalannya sepele), termasuk yang yang kebetulan memperoleh gelar satu karena menelanjangi tetangga mereka, dan melakukan Dijkstra pada yang lain (yang sebenarnya merupakan bagian "non-pohon").

Plus, saya akan mengatakan Anda ingin jalur dari setiap node ke yang lain, bukan? Algoritma Dijsktra hanya melakukan jalur dari satu ke yang lainnya. Mungkin melakukan algoritma Floyd-Warshall pada sisa stripped. Tentu saja, jika topologi sangat dinamis, yang terbaik adalah melakukan (stripping dan) Dijkstra, ad hoc.

herba
sumber

Saya percaya grafik yang ditampilkan di atas adalah contoh sederhana (ified) dan dalam kehidupan nyata mungkin sering ada beberapa jalur alternatif antara dua node (format), yaitu Anda tidak dapat mengandalkan grafik yang selalu menjadi pohon.

Péter Török

Diimplementasikan dengan tepat, algoritma Dijkstra akan menjadi O ( n ) juga, meskipun lebih rumit dan masih berlebihan.

Peter Taylor

@ PéterTörök: Kalau begitu, ya. Hanya penanya yang tahu pasti. Tetapi ketika itu adalah pohon, bfs sudah cukup (dan mati sederhana).

herby

@PeterTaylor: Menarik. Sumber apa saja?

herby

@ PéterTörök benar. Lihat pertanyaan yang diedit.

Kim Burgess

Anda mungkin dapat menggunakan A * (bentuk yang lebih umum dari algoritma Dijkstra) untuk mencari grafik yang dimaksud. Anda menyebutkan biaya bobot dalam komentar Anda:

Aditif Teori yang menyatakan hal ini akan memungkinkan untuk didefinisikan sedemikian rupa sehingga semakin tinggi definisi jalur sinyal, semakin rendah bobotnya. Tepian yang menghubungkan node yang melakukan konversi format kemudian akan diberi bobot lebih tinggi dari yang ditugaskan ke tepi yang menghubungkan node non-konversi. Ini akan merutekan sinyal dalam format asli jika memungkinkan, hanya melibatkan konversi format (dan degradasi sinyal terkait dan pemanfaatan peralatan) bila perlu

Jika saya memahaminya dengan benar, Anda ingin menemukan jalur jalur biaya terendah dari awal hingga tujuan. Jika Anda memberikan setiap node biaya aktual dan taksiran (heuristik) ke tujuan (yang diterima dan konsisten), maka A * dijamin untuk memberikan solusi optimal. Ini mungkin terlalu banyak, tergantung pada seberapa baik saya memahami masalah Anda.

jdt141
sumber

+1: Selain itu, IIRC, heuristik harus selalu memperkirakan biaya yang lebih buruk daripada biaya sebenarnya agar dapat menjamin jalur yang optimal. Dalam kasus terburuk, jika Anda tidak bisa mendapatkan heuristik dengan benar, cukup kembalikan 0 dari heuristik dan Anda punya algoritma dijkstra.

Steven Evers