Menemukan siklus negatif untuk algoritme pembatalan siklus

Saya menerapkan algoritme pembatalan siklus untuk menemukan solusi optimal untuk masalah aliran biaya minimum. Dengan menemukan dan menghilangkan siklus biaya negatif dalam jaringan residual, total biaya diturunkan di setiap putaran. Untuk menemukan siklus negatif saya menggunakan algoritma bellman-ford.

Masalah saya adalah: Bellman-ford hanya menemukan siklus yang dapat dijangkau dari sumbernya, tetapi saya juga perlu menemukan siklus yang tidak dapat dijangkau.

Contoh: Di jaringan berikut, kami sudah menerapkan aliran maksimum. Tepi membuatnya sangat mahal. Dalam jaringan residual, kami memiliki siklus biaya negatif dengan kapasitas . Menghapus itu, akan memberi kita solusi yang lebih murah menggunakan tepi dan , tapi kita tidak dapat mencapai itu dari sumber . $(A, B)$ $1$ $(A, C)$ $(C, T)$ $S$

Label: Aliran / Kapasitas, Biaya

masukkan deskripsi gambar di sini

Tentu saja, saya bisa menjalankan Bellman-ford berulang kali dengan setiap node sebagai sumber, tetapi itu tidak terdengar seperti solusi yang baik. Saya agak bingung karena semua kertas yang saya baca sepertinya melewati langkah ini.

Dapatkah Anda memberi tahu saya, bagaimana cara menggunakan bellman-ford untuk menemukan setiap siklus negatif (dapat dicapai atau tidak)? Dan jika tidak memungkinkan, algoritma lain apa yang Anda usulkan?

algorithms graph-theory shortest-path network-flow Patrick Schmidt
sumber

Jika sebuah siklus tidak dapat dicapai melalui sumber, bagaimana bisa mempengaruhi aliran total?

Nicholas Mancuso

Itu tidak akan mempengaruhi nilai aliran tetapi total biaya. Lihat contoh baru.

Patrick Schmidt

Saya pikir Anda harus menjalankan Bellman-Ford dari wastafel, bukan? Jika Anda menemukan aliran maksimum, , maka di bawah grafik residual tidak akan ada jalur dari ke . Oleh karena itu, Bellman-Ford harus dijalankan pada dengan .

f

$f$

G_{f}

$G_f$

s

$s$

t

$t$

G_{f}

$G_f$

t

$t$

Nicholas Mancuso

Jawaban:

Untuk memperluas komentar saya, ingatlah, algoritma ini untuk menemukan Min-Cost-Flow bergantung pada fakta itu $f$ maksimal. Dengan pertama menjalankan Ford-Fulkerson untuk menemukan $f$ dan jaringan residual yang dihasilkan $G_f$ , biaya $f$ kemudian dikurangi dengan menemukan siklus negatif di $G_f$ . Yaitu, dengan menemukan siklus negatif di $G_f$ kami tidak mengubah jumlah aliran, $f$ , tetapi hanya biaya.

Sekarang dengan menjalankan Bellman-Ford dari $t$ di $G_f$ kita dapat melacak mundur pada tepi yang memiliki aliran non-negatif (menurut definisi $G_f$ ). Jika siklus berbatasan dengan setiap tepi di jalur ini, maka kita dapat "mentransfer" sejumlah aliran ke tepi lain dalam siklus. Dengan kata lain, kami menjaga aliran-net untuk beberapa siklus yang sama, tetapi dapat mengubah biaya.

Perhatikan siklus yang tidak dapat dijangkau dari $t$ harus memiliki aliran nol. Kalau tidak, kita akan memiliki kontradiksi di $f$ menjadi maksimal.

^{Saya minta maaf atas "tangan bergelombang" penjelasan ini. Saya akan mencoba menjadi lebih formal ketika saya punya waktu malam ini.}

Nicholas Mancuso
sumber

Terima kasih, kalimat terakhir Anda membuatnya jelas. Jadi, sudah cukup untuk berurusan dengan siklus yang dapat dijangkau

T

$T$ .

Patrick Schmidt

Saran saya: Anda harus memulai algoritme dari T, untuk menemukan siklus negatif di jaringan residu Anda. Hasilnya harus sama, tetapi kemudian Anda dapat mencapai lingkaran

Sven Jung
sumber

Ini berfungsi untuk grafik ini, tetapi Anda dapat memiliki siklus negatif yang tidak terhubung ke S atau T. Saya menduga bahwa OP menginginkan solusi yang berfungsi secara umum.

Peter Shor

ya, secara umum Anda tidak dapat menemukan setiap siklus negatif, tetapi OP ingin meningkatkan Jaringan residualnya dengan memeriksa biayanya. Maka lingkaran negatif yang tidak terjangkau tidak masalah

Sven Jung

Saya ingin menggunakan ini untuk mendapatkan aliran biaya minimum. Jadi pertanyaan baru adalah: Apakah cukup untuk menghilangkan setiap siklus yang dapat dijangkau dari wastafel

T

$T$ (Di jaringan residual). Saat ini saya tidak dapat menemukan contoh balasan

Patrick Schmidt

Anda dapat melihat aliran yang berasal dari

S

$S$ dan pergi ke

T

$T$ , atau membalikkan setiap tepi dan melihatnya sebagai sumber dari

T

$T$ dan pergi ke

S

$S$ . Jika menghilangkan setiap siklus yang dapat dijangkau dari sumbernya

S

$S$ tidak bekerja, lalu hilangkan setiap siklus yang bisa dicapai dari wastafel

T

$T$ tidak akan bekerja Sumber dan wastafel berperilaku simetris.

Peter Shor

tentu saja sama jika Anda membalik setiap sisi dan mulai dari T, karena tidak ada yang berubah. Tetapi mengapa tidak mulai dari T tanpa membalikkan tepinya? Maka Anda harus menemukan siklus negatif yang dapat dijangkau, jika ada. Pertanyaannya adalah, apakah siklus negatif yang tidak dapat dijangkau benar-benar tidak penting

Sven Jung

Saya pikir itu tidak cukup untuk menjalankan Bellman-Ford dari T atau S. Pertimbangkan satu contoh di mana ada satu sisi dari S ke T dan satu siklus biaya negatif tidak dapat dicapai dari S atau T.

Salah satu solusinya adalah menambahkan auxiliary S 'dan menambahkan edge dari S' ke vertex lain dengan biaya 0. Kemudian jalankan Bellman-Ford dari S '. Dengan cara ini, semua siklus negatif dapat dicapai dari S '.

Selain itu, Anda tidak benar-benar perlu menambahkan titik bantu S dalam implementasi Anda. Inisialisasi saja d (v) = 0 untuk sembarang simpul v.

Lihat bagaimana Boost Graph Library menerapkannya.

Hongjie Chen
sumber