Pemesanan topologi positif

45

Misalkan saya memiliki grafik asiklik terarah dengan bobot bilangan real pada simpulnya. Saya ingin menemukan pemesanan topologi DAG di mana, untuk setiap awalan pemesanan topologis, jumlah bobot adalah non-negatif. Atau jika Anda lebih suka terminologi teoretis pesanan, saya memiliki urutan parsial tertimbang dan saya ingin ekstensi linier sehingga setiap awalan memiliki bobot non-negatif. Apa yang diketahui tentang masalah ini? Apakah NP-lengkap atau dipecahkan dalam waktu polinomial?

ds.algorithms directed-acyclic-graph partial-order David Eppstein
sumber

4

Coba algoritma serakah pada grafik ini: 1 -> 2 -> 3, 1 -> 4 -> 5, bobot titik adalah 1: +2, 2: -2, 3: +3, 4: -1 , 5: -2. Algoritma serakah akan mulai dengan v1, lalu pilih v4, dan kemudian macet. Urutan yang benar adalah v1, v2, v3, v4, v5.

Robin Kothari

2

"beberapa masalah jarak Frechet yang telah dilihat JeffE dan yang lainnya" - abstraksi yang bagus! Untuk keuntungan orang lain, inilah satu versi: Misalkan Anda diberi grafik bidang berbobot tepi G, dan dua simpul s dan di sisi luar. Anda ingin mengubah satu jalur batas dari s ke t ke yang lain dengan urutan gerakan elementer. Setiap gerakan menggantikan jalur saat ini dengan perbedaan simetrisnya dengan beberapa batas wajah. Seberapa cepat kita dapat menemukan urutan mve yang meminimalkan panjang maksimum dari jalur yang berevolusi?

Jeffε

3

Tsuyoshi, maaf soal itu, aku mencoba untuk menambahkan baris baru sambil berkomentar dan itu membuat komentarku terputus. Jadi idenya adalah, Anda memiliki tali yang diikat erat di pergelangan tangan Anda dan Anda ingin tahu apakah Anda bisa melepaskannya. Pergelangan tangan Anda direpresentasikan sebagai jaring poligon, sel-sel yang merupakan elemen dari urutan parsial (lebih dekat ke string sebelumnya, lebih dekat ke off nanti dalam urutan). Berat sel adalah perbedaan panjang antara batas dalam dan luarnya.

David Eppstein

1

@ David: Terima kasih atas penjelasannya. Kali ini saya bisa mengerti bagaimana ini terkait dengan pertanyaan saat ini, dan itu menarik!

Tsuyoshi Ito

3

Pengamatan yang tidak begitu berguna tetapi menyenangkan: Masalah ini setara dengan masalah urutan mesin tunggal dengan tenggat waktu dan kendala prioritas di mana waktu pemrosesan setiap pekerjaan bisa negatif . Dengan waktu pemrosesan yang tidak negatif, masalah ini ada di P (Lawler dan Mooer 1969 jstor.org/stable/2628367 ), dan jika ada solusi, maka ada solusi yang tidak tergantung pada waktu pemrosesan. Ini jelas rusak jika beberapa pekerjaan memiliki waktu pemrosesan negatif.

Tsuyoshi Ito

18

Masalah ini tampaknya sangat mirip dengan SEQUENCING TO MINIMIZE BIAYA KUMULATIF MAKSIMUM, masalah [SS7] di Garey & Johnson . Yakni:

$T$ $\prec$ $T$ $c(t) \in Z$ $t \in T$ $c(t) < 0$ $K \in Z$

$\sigma$ $T$ $t \in T$ $t'$ $\sigma(t') \leq \sigma(t)$ $K$

$K$ $c(t) \in \{-1,0,1\}$ $t \in T$

mhum
sumber

7

K = 0

$K=0$

c

$c$

- K

$-K$

K

$K$

c

$c$

- 1

$-1$

@ mhum: Saya sedang mengerjakan laporan teknis tentang hasil terkait dan ingin mengutip Anda. Maukah Anda memberi saya nama asli Anda? Jika Anda mau, Anda dapat mengirim email kepada saya, atau hanya tinggal ...

domotorp

9

Nah, jawaban saya adalah pertanyaan saya dari mana ternyata jika Anda bisa menyelesaikan masalah ini di P, Anda juga bisa memecahkan masalah terbuka lainnya: Urutan topologis positif, ambil 3

Sunting: Masalah ini juga ternyata merupakan NP-complete, jadi masalah Anda sudah NP-complete jika DAG Anda hanya memiliki dua level, yaitu jika tidak ada jalur yang diarahkan dengan dua tepi.

domotorp
sumber

3

Jika saya memahami masalah dengan benar, saya pikir bahwa prioritas masalah mesin penjadwalan dibatasi untuk meminimalkan jumlah waktu penyelesaian tertimbang (1 | prec | \ sum wc) dapat dikurangi menjadi masalah yang Anda minati. Dalam masalah 1 | prec | \ sum wc kami memiliki n pekerjaan, masing-masing dengan bobot non-negatif dan waktu pemrosesan, poset pada pekerjaan dan kami ingin perpanjangan linier pekerjaan sehingga jumlah tertimbang waktu penyelesaian pekerjaan adalah diminimalkan. Masalahnya adalah NP-lengkap meskipun kami mengasumsikan bahwa waktu pemrosesan setiap pekerjaan sama dengan 1. Apakah masuk akal?

monaldo
sumber

Itu pasti kemungkinan yang menarik. Tetapi bagaimana Anda melakukan reduksi sedemikian rupa sehingga kriteria optimasi (meminimalkan jumlah waktu penyelesaian) ditransformasikan menjadi kendala (awalan non-negatif)?

David Eppstein

Saya tidak tahu hasil kelengkapan NP ini dari masalah penjadwalan, tapi saya pikir itu mengacu pada masalah keputusan memutuskan apakah ada ekstensi linear sehingga jumlah tertimbang waktu penyelesaian pekerjaan paling banyak K, oleh karena itu saya tidak berpikir perbedaan antara kriteria optimasi dan kendala adalah penting di sini. Namun, saya belum mengerti bagaimana merepresentasikan kendala pada jumlah waktu penyelesaian yang tertimbang dalam masalah saat ini.

Tsuyoshi Ito

Saya pikir pengurangan itu tidak semudah yang saya kira di awal. Saya tidak yakin lagi dengan jawaban saya.

monaldo

Saya baru menyadari kesalahan dalam komentar saya sebelumnya. Ketika saya mempostingnya, saya berpikir bahwa mewakili batasan pada jumlah tidak tertimbang itu mudah (karena itu penekanan pada bobot ), tetapi itu sepenuhnya salah.

Tsuyoshi Ito

2

Bagaimana jika kita selalu mengambil elemen maksimal (dalam urutan parsial) dengan bobot paling sedikit. Setelah kami menghabiskan elemen, kami mengembalikannya dalam urutan terbalik sebagai output.

Daniel Martin
sumber

Masalahnya invarian di bawah transformasi membalik urutan parsial dan meniadakan semua bobot. Jadi saya tidak melihat bagaimana ini bisa berbeda dari algoritma ke depan-serakah Robin K memberikan contoh balasan dalam komentar.

David Eppstein

Tetapi metode ini berfungsi untuk contohnya: pertama, simpul 5 akan dipilih, kemudian simpul 4, kemudian 3, 2, dan akhirnya 1. Jadi urutan terakhir adalah 1, 2, 3, 4, 5. Sebenarnya, saya tidak Sulit untuk membuktikan bahwa metode ini berhasil. Misalkan Anda memiliki solusi yang tidak memiliki elemen maksimal (wastafel) dari berat minimum di posisi terakhir. Kemudian Anda dapat menemukan solusi lain yang memang memiliki properti ini, cukup dengan mengubah posisi elemen seperti itu untuk bertahan, dan mempertahankan sisanya seperti apa adanya. Lanjutkan dengan induksi pada apa yang tersisa, dan Anda mendapatkan bukti formal.

Daniel Martin

Ya ... itu tidak berhasil ... 1 -> 2 -> 3, 1 -> 4 dengan bobot 4, -7, 6, 3 masing-masing.

Daniel Martin

1

Masalah ini mengingatkan saya pada banyak pohon keputusan. Saya akan mempertimbangkan jenis solusi ini, yang mencoba untuk selalu memilih jalan yang paling menjanjikan, tetapi dengan melihat keseluruhan subgraph:

Mulai dari node sink, bekerja menuju sumber, satu tingkat pada satu waktu. Saat Anda melakukan ini, beri bobot pada setiap sisi. Bobot ini harus mewakili jumlah minimum yang harus Anda "bayar" atau Anda akan "mendapatkan" dengan melintasi subgraph mulai dari titik titik simpul ke. Misalkan kita berada pada level i + 1 dan kita bergerak ke level i. Inilah yang akan saya lakukan untuk menetapkan bobot untuk ujung yang menunjuk ke simpul level i:

edge_weight = pointing_node_weight.
Temukan tepi mulai dari "titik menunjuk" dengan berat maksimum. Biarkan bobot ini menjadi next_edge_weight.
edge_weight + = next_edge_weight

Kemudian, buat pesanan sebagai berikut:

Biarkan S menjadi batas pencarian, yaitu set node untuk memilih dari selanjutnya.
Pilih simpul agar (node_weight + maksimum_edge_weight) dimaksimalkan.
Hapus simpul dari grafik dan S. Tambahkan simpul "anak-anak" ke S.
Jika grafik tidak kosong, lanjutkan ke langkah 1.
Berhenti.

Idenya adalah untuk melintasi subgraph yang akan memberi keuntungan sebanyak mungkin terlebih dahulu, agar dapat menanggung biaya subgraph bobot negatif nanti.

chazisop
sumber

Pemesanan topologi positif

Jawaban: