Pilihan online murah dengan perbandingan berbobot

Misalkan kita ingin menemukan elemen terkecil dari himpunan , yang elemennya diindeks dari ke . Kami tidak memiliki akses ke nilai-nilai elemen ini, tetapi kami dapat membandingkan dua elemen untuk melihat mana yang lebih kecil. Untuk setiap indeks dan , ada terkait biaya untuk membandingkan th dan th unsur . Matriks biaya lengkap diberikan kepada kami sebelumnya. $S$ $1$ $n$ $S$ $i$ $j$ $C_{i,j}$ $i$ $j$ $S$ $C_{i,j}$

Hal ini juga diketahui bahwa perbandingan yang perlu dan cukup untuk menemukan elemen terkecil dari . Namun, karena setiap perbandingan mungkin memiliki biaya yang berbeda, kami juga ingin menjaga agar biaya total perbandingan sekecil mungkin. $n-1$ $S$

Apakah ada algoritma online yang menemukan urutan perbandingan biaya total kecil yang menemukan elemen terkecil ? $S$ Tidak ada algoritma online yang menemukan rangkaian perbandingan dengan total biaya minimum , bahkan ketika , tetapi mungkin ada algoritma online dengan rasio persaingan kecil. $n=3$

Secara khusus, apakah memungkinkan algoritma online untuk melakukan lebih dari perbandingan membantu? Apakah lebih baik membuat beberapa perbandingan murah "ekstra" daripada beberapa perbandingan mahal? $n-1$

Saya terutama tertarik pada kasus , di mana adalah metrik diskrit atas himpunan , dan , untuk semua . Sebuah optimal algoritma online masih mungkin dalam pengaturan ini. $C_{i,j} = 4^{d(i,j)}$ $d$ $S$ $0 \le d(i,j) \le k$ $i,j$

Setiap referensi untuk masalah serupa dihargai. Saya tidak mencari seseorang untuk menyelesaikan masalah saya (walaupun beberapa ide dapat membantu dan dihargai). Saya hanya ingin tahu apakah masalah ini diketahui. (Saya tidak dapat menemukan apa pun.)

cc.complexity-theory ds.algorithms reference-request online-algorithms George
sumber

Tunggu, sekarang saya bingung. Jika Anda mengetahui nilai dan biaya perbandingan berpasangan sebelumnya, meminimalkan total biaya perbandingan setara dengan menghitung arboresensi biaya minimum dalam grafik yang diarahkan langsung asiklik. Tetapi jika Anda tidak tahu nilainya, tetapi hanya menemukan pesanan mereka dengan benar-benar melakukan perbandingan, tidak ada strategi online yang selalu menemukan elemen terkecil menggunakan perbandingan biaya total minimum; lawan yang cerdik dapat memaksa Anda untuk membuang uang. Versi apa yang Anda minati?

Jeffε

Ok, mungkin saya tidak membuat pertanyaan saya cukup jelas. Nilai tidak diketahui dan "diungkapkan" oleh perbandingan (tidak benar-benar, katakan perbandingan hanya mengembalikan jika suatu objek lebih besar, sama atau lebih kecil dari yang lain). Jadi saya tertarik dengan versi kedua. Btw tidak pernah mendengar tentang penghematan biaya minimum. Setidaknya saya belajar sesuatu yang baru.

George

Anda harus mengedit pertanyaan Anda untuk membuat titik ini eksplisit. Untuk menjawab pertanyaan singkat Anda: Saya tidak tahu apakah masalahnya sudah diketahui, tetapi melakukan rangkaian perbandingan online yang optimal bukanlah NP-complete, karena itu tidak mungkin (kecuali ). Yang terbaik yang bisa Anda harapkan adalah rasio persaingan kecil.

n = 2

$n=2$

Jeffε

Diedit untuk kejelasan (saya harap) dan untuk menekankan bahwa ini adalah pertanyaan algoritma online . Harap periksa bahwa saya belum terlalu mengacaukan pernyataan masalah!

Jeffε

Ini jauh lebih baik! Terima kasih banyak. Saya juga menambahkan bahwa jarak antara dua objek dibatasi di atas oleh beberapa integer k.

George

Jawaban:

Analisis kasus brute-force mengungkapkan bahwa rasio kompetitif optimal untuk kasus khusus , tanpa batasan lain pada matriks biaya, adalah rasio emas . Dengan demikian, tidak ada algoritma online yang dapat mencapai rasio kompetitif lebih baik dari . $n=3$ $\phi = (\sqrt{5}+1)/2$ $\phi$

Misalkan , , dan . $C_{1,2}=0$ $C_{1,3}=1$ $C_{2,3}=\phi$

Tanpa kehilangan keumuman, algoritma dimulai dengan membandingkan dengan , dengan biaya nol. $S_1$ $S_2$
Musuh menyatakan . $S_1 > S_2$
Jika algoritma membandingkan ke : $S_1$ $S_3$
- Musuh menyatakan . $S_1 > S_3$
- Algoritma harus membandingkan dan . $S_2$ $S_3$
- Musuh menyatakan , jadi adalah minimum. $S_2 < S_3$ $S_2$
- Total biaya perbandingan algoritma adalah . $1+\phi$
- Musuh mengungkapkan urutan total . $S_2 < S_3 < S_1$
- Total biaya perbandingan optimal ( dan ) adalah . $S_1>S_2$ $S_2<S_3$ $\phi$
Jika algoritme membandingkan dengan : $S_2$ $S_3$
- Musuh menyatakan , jadi adalah minimum. $S_3 > S_2$ $S_2$
- Total biaya perbandingan algoritma adalah . $\phi$
- Musuh mengungkapkan urutan total . $S_2 < S_1 < S_3$
- Total biaya perbandingan optimal ( dan ) adalah . $S_1>S_2$ $S_1<S_3$ $1$
Dalam kedua kasus tersebut, perbandingan algoritma menghabiskan faktor lebih dari set perbandingan optimal untuk total order yang terungkap. $\frac{1+\phi}{\phi} = \frac{\phi}{1} = \phi$

Secara umum, rasio kompetitif adalah , di mana berada tiga biaya perbandingan. (Ada lebih banyak kasus untuk dipertimbangkan di sini, karena ada algoritma optimal yang tidak melakukan perbandingan termurah terlebih dahulu, tetapi analisis kasus masih elementer.) Perhitungan yang membosankan menyiratkan bahwa ekspresi dimaksimalkan ketika , , dan . $\min\{\frac{a+c}{a+b} , \frac{a+b+c}{a+c}\}$ $a\le b\le c$ $\min\{\frac{a+c}{a+b} , \frac{a+b+c}{a+c}\}$ $a=0$ $b=1$ $c=\phi$

Khususnya, jika , algoritma terbaik mungkin dapat dipaksa untuk melakukan ketiga perbandingan. $\frac{a+c}{a+b} > \frac{a+b+c}{a+c}$

Jeffε
sumber

Itu adalah langkah pertama yang sangat bagus! Terima kasih atas minat Anda pada masalah saya (tampaknya Anda bahkan lebih tertarik daripada saya :))

George

Pengamatan yang bagus. Sebagai catatan, analisis ini mengasumsikan algoritma deterministik kecuali saya salah.

Tsuyoshi Ito

Ya itu betul. Algoritma acak mungkin lebih baik (dengan harapan, melawan musuh yang tidak sadar).

Jeffε

-3

Sebuah awal adalah:

Urutkan semua elemen dari matriks biaya Anda C
Lakukan perbandingan biaya terendah terlebih dahulu, menempatkan pecundang di set NOPE
Untuk setiap perbandingan biaya selanjutnya, jika salah satu dari kedua elemen berada di NOPE, jangan lakukan perbandingan
Anda harus terus berjalan sampai semua kecuali satu elemen dalam NOPE, yang merupakan perbandingan n-1.

Apakah ini algoritma yang layak? Bergantung pada biaya relatif penyortiran C vs melakukan perbandingan di S:

Untuk setiap item yang Anda evaluasi, jika ada perbandingan yang lebih murah daripada yang saat ini dilakukan, itu sudah dilakukan, dan item saat ini memenangkan perbandingan itu
Biaya == n ^ 2 perbandingan numerik untuk mengurutkan C, ditambah perbandingan n-1 S

-t.

Tristan Reid
sumber

Ya, ini adalah satu algoritma serakah yang jelas. Tidak, biaya adalah jumlah dari biaya masing-masing perbandingan yang dilakukan oleh algoritma, seperti yang diberikan oleh matriks .

C_{i, j}

$C_{i,j}$

Jeffε

Terima kasih! Saya sudah memikirkan pendekatan serakah yang jelas ini (yang akan saya gunakan jika tidak ada yang lebih baik muncul). Masalahnya adalah apakah ia memberikan jaminan pada rasio kompetitif.

George

@ Jeffe - ya, biayanya adalah perbandingan n-1 dengan biaya yang terkait, tetapi juga biaya pengurutan matriks biaya

Tristan Reid

@ George B. - Jika biaya pengurutan C relatif murah, saya tidak berpikir ada algoritma yang lebih baik untuk melakukan ini. Algoritma ini akan selalu melakukan perbandingan persis n-1, tidak pernah 1 lebih atau 1 kurang. Perbandingan yang dilakukan akan selalu menjadi yang termurah n-1. Saya pikir keserakahan itu baik ...

Tristan Reid

Tidak, itu tidak selalu menjadi yang termurah. Sebagai contoh, misalkan A> B> C dan = 1, = 2 dan = 1. Jika Anda pertama kali membandingkan dan lalu membandingkan ke total biaya akan menjadi 4 ^ 1 + 4 ^ 2 = 20, sedangkan jika Anda pertama kali membandingkan ke dan kemudian ke biaya akan menjadi 4 ^ 1 + 4 ^ 1 = 8, jadi algoritma serakah seperti itu tidak akan bekerja disini. Dan ya, menyortir C tidak menjadi masalah.

d_{(} A, B)

$d_(A,B)$

d_{(} A, C)

$d_(A,C)$

d_{(} B, C)

$d_(B,C)$

A

$A$

B

$B$

A

$A$

C

$C$

B

$B$

C

$C$

A

$A$

B

$B$

George