Saya mencoba menerapkan mekanisme pencarian jalur yang lebih cepat dalam game yang sedang saya kerjakan untuk grafik simpul yang terhubung. Node dikelompokkan menjadi dua jenis, "Jaringan" dan "Router".
Dalam gambar ini, lingkaran biru mewakili router dan jaringan persegi panjang abu-abu.
Setiap jaringan menyimpan daftar router mana yang terhubung dengannya, dan sebaliknya. Router tidak dapat terhubung langsung ke router lain, dan jaringan tidak dapat terhubung langsung ke jaringan lain.
Jaringan mencantumkan router mana yang terhubung
Router melakukan hal yang sama
Saya perlu mendapatkan algoritma yang akan memetakan jalur, diukur dalam jumlah jaringan yang dilintasi, untuk setiap kemungkinan jaringan sumber dan tujuan tidak termasuk jalur di mana sumber dan tujuan adalah jaringan yang sama. Saya punya satu saat ini, namun sangat lambat, membutuhkan waktu sekitar dua detik untuk memetakan jalur, yang menjadi sangat terlihat oleh semua pemain yang terhubung.
Algoritme saat ini adalah pencarian brute-force yang mendalam (dilakukan bersama-sama dalam waktu sekitar satu jam agar caching jalur berfungsi) yang mengembalikan array jaringan sesuai urutan yang dilaluinya, yang menjelaskan mengapa ini sangat lambat. Apakah ada algoritma yang lebih efisien?
Sebagai catatan tambahan, meskipun contoh grafik ini memiliki empat jaringan, grafik dalam praktiknya memiliki 55 jaringan dan sekitar 20 router yang digunakan. Jalur yang tidak memungkinkan juga dapat terjadi, dan juga sewaktu-waktu topografi grafik jaringan/router dapat berubah, sehingga memerlukan cache jalur untuk dibangun kembali.
Pendekatan/algoritma apa yang mungkin memberikan hasil terbaik untuk jenis grafik ini?
