Menemukan jalur pendek dan gemuk

Motivasi: Dalam algoritme maxflow jalur augmentasi standar, loop dalam membutuhkan jalur pencarian dari sumber untuk tenggelam dalam grafik tertimbang yang diarahkan. Secara teoritis, sudah diketahui umum bahwa agar algoritme itu bahkan berhenti ketika ada kapasitas tepi yang tidak rasional, kita perlu memberi batasan pada jalur yang kita temukan. Algoritma Edmonds-Karp, misalnya, memberitahu kita untuk menemukan jalur terpendek .

Secara empiris, telah diamati bahwa kita mungkin juga ingin menemukan jalur lemak (adakah istilah yang lebih baik untuk ini?). Misalnya, ketika menggunakan penskalaan kapasitas , kami menemukan jalur terpendek yang dapat menanggung setidaknya jumlah aliran. Tidak ada batasan berapa lama jalan itu bisa. Ketika kami tidak lagi menemukan jalur, kami mengurangi ϵ dan mengulanginya.$\epsilon$$\epsilon$

Saya tertarik untuk mengoptimalkan pilihan augmenting path untuk aplikasi max-flow yang sangat spesifik, dan saya ingin menjelajahi tradeoff antara jalur pendek dan gemuk. (Catatan: tidak perlu bagi saya untuk selalu memecahkan masalah. Saya paling tertarik untuk menemukan batas bawah terbesar pada aliran dalam jumlah waktu dinding terpendek.)

Pertanyaan: Apakah ada cara standar untuk menginterpolasi antara pendekatan jalur terpendek dan pendekatan peningkatan kapasitas? Yaitu, adakah algoritma untuk menemukan jalur yang pendek dan gemuk, di mana idealnya beberapa parameter akan mengontrol berapa panjang di jalur yang ingin kita tukar untuk kegemukan? Pada titik ekstrem, saya ingin dapat memulihkan jalur terpendek di satu sisi dan jalur gaya penskalaan kapasitas di ujung lainnya.

Dalam semangat komentar Anda tentang "cukup bagus tetapi belum tentu optimal," Saya menyajikan ide berikut ini tanpa jaminan optimal!

Untuk kelengkapan, berikut adalah pseudocode yang Anda maksudkan (Keterangan: algoritme yang ditautkan mengasumsikan bahwa kapasitas tepi adalah bilangan bulat antara 1 dan C dan bahwa nilai aliran dan kapasitas sisa merupakan bagian integral):

Scaling-Max-Flow (G, s, t, C) {
   foreach e ∈ E f (e) ← 0
   Δ ← kekuatan terkecil 2 lebih besar dari atau sama dengan C
   G_f ← grafik residual

   while (Δ ≥ 1) {
      G_f (Δ) ← Δ-residual graph
      while (ada tambahan jalur P di G_f (Δ)) {
         f ← ​​augment (f, C, P)
         perbarui G_f (Δ)
      }
      Δ ← Δ / 2
   }
   kembali f
}

$\epsilon$$\epsilon = \Delta$$\epsilon$

$0 \le \rho \le 1$$\rho$

Kemudian, setiap kali diberi nilai, kami juga mengambil rata-rata aritmatika tertimbang (saya harap itu istilah yang benar ..) antara 1 dan nilai saat ini. Itu adalah,$\epsilon$$\rho$

$\epsilon \leftarrow (\rho)\epsilon + (1-\rho)$

Untuk , kita berakhir dengan algoritma jalur terpendek murni; untuk , kita mendapatkan algoritma jalur paling gemuk murni; dan untuk kita mendapatkan sesuatu di antaranya. Khususnya, untuk beberapa nilai menengah, akan menyatu dengan lebih cepat, sehingga Anda akan mendapatkan lebih banyak jalur terpendek, dan lebih sedikit jalur paling gemuk.ρ = 1 0 < ρ < 1 ϵ ≤ $\rho = 0$$\rho = 1$$0 < \rho < 1$$\epsilon$$\le 1$