Algoritma Tepat untuk masalah pelabelan tepi dalam DAG

Saya menerapkan beberapa bagian sistem yang memerlukan bantuan. Karena itu saya membingkainya sebagai masalah grafik untuk menjadikannya domain independen.

Masalah: Kami diberi grafik asiklik langsung $G=(V,E)$ . Tanpa kehilangan umum menganggap bahwa memiliki tepat satu sumber vertex dan tepat satu wastafel titik ; biarkan menyatakan himpunan semua jalur diarahkan dari ke di . Kami juga diberi satu set simpul . Masalahnya adalah untuk menetapkan bobot bilangan bulat non-negatif ke tepi , sehingga setiap dua jalur dalam memiliki bobot yang sama jika dan hanya jika mereka mengandung subset simpul yang sama dalam $G$ $s$ $t$ $P$ $s$ $t$ $G$ $R \subseteq V$ $G$ $P$ $R$ . (Berat jalan adalah jumlah dari bobot ujungnya.) Kisaran bobot jalan di harus sekecil mungkin. $P$

Saat ini pendekatan saya tampaknya tidak efisien; Saya hanya mencari beberapa referensi literatur atau wawasan yang bagus. Apa pun yang sebaliknya juga dihargai.

Sunting: Apakah ada bukti kekerasan untuk masalah ini? Apakah penomoran kompak selalu ada?

ds.algorithms reference-request co.combinatorics graph-algorithms directed-acyclic-graph pengguna5153
sumber

mohon klarifikasi "Kisaran bobot jalur di P harus optimal." Apakah bobot hanya bilangan bulat? Apakah kita diperbolehkan bobot negatif? Apakah optimal berarti "rentang sekecil mungkin" atau apakah itu berarti sesuatu yang lain?

Artem Kaznatcheev

saya telah mengedit pertanyaan. terima kasih atas komentar Anda. bobot harus bilangan bulat non-negatif dan kisarannya harus sekecil mungkin.

user5153

Strategi sederhana untuk menghasilkan solusi yang valid adalah dengan menetapkan kekuatan dua yang berbeda untuk masing-masing simpul v dalam R, menggunakan angka itu sebagai bobot semua tepi yang masuk ke v, dan menetapkan bobot nol untuk semua tepi yang tersisa. Jelas, ini mungkin tidak optimal, tetapi setidaknya memberikan batas atas pada kisaran yang dibutuhkan. Apakah ini merupakan perbaikan untuk membuat tepi yang berbeda melalui titik yang sama dalam R memiliki bobot yang berbeda satu sama lain, atau dapatkah Anda menyederhanakan masalah dengan membuat bobot berjalan dengan simpul daripada tepi?

David Eppstein

Jawaban BTW @ DavidEppstein menunjukkan bahwa berat total maksimum lintasan adalah

. Ini ketat untuk konstanta. Sebagai contoh, Anda dapat mengambil grafik

dan

O (2^{| R |})

$O(2^{|R|})$

G = (V, E)

$G = (V, E)$

V = [n] \cup {s, t}

$V = [n] \cup \{s, t\}$

. Biarkan juga

. Ada

jalur berbeda pada

, dan karena setiap jalur memiliki bobot bilangan bulat non-negatif, setidaknya satu harus memiliki bobot setidaknya

E = {(i, j) : i < j} \cup {(s, 1), (n, t), (s, t)}

$E = \{(i, j): i<j\} \cup \{(s, 1), (n, t), (s, t)\}$

R = [n]

$R = [n]$

2^{n}

$2^n$

R

$R$

2^{n} - 1

$2^n -1$

Sasho Nikolov

tentu, saya maksudkan ketat dalam kasus terburuk (saya benar-benar menulis bahwa dalam versi pertama dari komentar ini yang hilang). pikir akan lebih baik untuk terlebih dahulu menjabarkan beberapa batasan absolut, karena belum ada yang mengatasi masalah optimisasi.

Sasho Nikolov

Saya belum pernah mendengar masalah ini persis dalam literatur [mungkin orang lain memiliki] namun sebagai "masalah terdekat" menurut saya pohon spanning minimum akan memiliki sifat yang berguna untuk menyelesaikan masalah Anda. misalnya mungkin menghasilkan dua pohon rentang minimum mulai dari simpul sumber & simpul sinkronisasi, dan menyebarkannya ke luar sampai menyentuh, dll. mungkin menyelesaikan masalah atau memberikan jawaban yang dekat. sebelum ada yang menyanggah saya tentang hal ini di sini, tolong mengerti saya memperluas ide MST yang akan dihasilkan mulai dari titik tertentu [biasanya dimulai dari tepi terpendek di seluruh grafik]. jika tidak berhasil saya akan penasaran karena alasan itu.

vzn
sumber

Maaf, tapi saya tidak melihat relevansi jawaban ini untuk pertanyaan ini.

David Eppstein

mungkin Anda punya ide yang lebih baik tentang apa yang dia bicarakan? apakah masuk akal bagi Anda seperti yang dinyatakan?

vzn

Dia perlu menetapkan bobot ke tepi. Bagaimana menghitung MST akan membantu itu?

Nicholas Mancuso

ok saat membacanya, & tanpa ada orang lain yang mengusulkan jawaban, sepertinya masalahnya dapat dikonversi menjadi dua bagian - (1) menetapkan bobot berdasarkan kriteria / batasan, (2) menemukan jalur terpendek berdasarkan bobot tersebut. sepertinya MST bisa berguna pada (2). atau mungkin tidak! (mis. mungkin 1/2 sangat erat)

vzn

Tidak. Pohon spanning minimum hanya untuk grafik tidak terarah; grafik input diarahkan. Selain itu, pohon spanning minimum hanya terkait secara dangkal dengan jalur terpendek.

Jeffε

Algoritma Tepat untuk masalah pelabelan tepi dalam DAG

Jawaban: