Saya memiliki satu set besar jaringan linear dan saya ingin menemukan dua ujung dari masing-masing jaringan yang paling jauh satu sama lain di sepanjang jaringan (pada gambar di bawah, itu akan menjadi D ke K). Solusi brute force untuk masalah ini adalah menghitung jalur terpendek di sepanjang jaringan untuk setiap pasangan asal, tetapi saya memiliki ratusan jaringan dengan ribuan ujung, sehingga menghitung setiap jalur yang mungkin cukup berat.
Apakah ada cara optimal untuk menghitung ini tanpa menggunakan brute force? Bisakah saya mengecualikan beberapa poin berdasarkan beberapa aturan pintar?
EDIT: Saya telah menambahkan ilustrasi jalur terpanjang yang disebutkan oleh @Alex Tereshenkov untuk memperjelas pertanyaan saya. Jalur hitam adalah hasil dari algoritma jalur terpanjang (jalur terpanjang tanpa mengulangi semua simpul). Dalam kasus saya, bayangkan Anda memasuki jaringan dari salah satu surat dan Anda harus pergi ke surat lain secepat mungkin. Dua surat mana yang paling sulit untuk diikuti?
Jawaban:
Saya pikir Anda mungkin mencari Diameter Grafik jaringan Anda. Ada beberapa pertanyaan tentang stackexchange yang menyebutkan topik ini, misalnya:
Sebagian besar algoritma menyarankan untuk menghitung "all-pair shortest paths" terlebih dahulu dan memilih yang terpanjang dari itu, tetapi saya menemukan posting blog oleh Koushik Narayanan yang menyarankan pendekatan alternatif yang mungkin lebih optimal (saya tidak memeriksa), yang beralih ke setiap simpul dan menemukan pasangannya yang paling jauh:
sumber
Menurut halaman Wikipedia masalah jalan terpanjang , masalah ini
Jika Anda bekerja dengan (atau dapat mewakili grafik Anda sebagai DAG ), maka
networkx
paket Python akan membiarkan Anda menghitungnya. Cari fungsinyadag_longest_path
.Kecuali jika saya kehilangan sesuatu, Anda harus menghitung panjang antara node grafik dan mengurutkannya yang, sayangnya, hanya akan bekerja dalam waktu linier , yaitu tidak ada algoritma yang efisien untuk ini.
sumber