Bagaimana cara menggunakan algoritme serakah untuk menemukan urutan non-menurun paling dekat dengan yang diberikan?

20

Anda diberi n bilangan bulat semuanya antara dan . Di bawah setiap bilangan bulat Anda harus menulis bilangan bulat antara dan dengan persyaratan bahwa membentuk urutan yang tidak menurun. Tentukan penyimpangan urutan seperti itu menjadi . Desain algoritma yang menemukan b_i dengan deviasi minimum dalam runtime O (n \ sqrt [4] {l}) . 0 l a i b i 0 l b i max ( | a 1 - b 1 | , , | a n - b n | ) b i O ( n 4 a1,,an0laibi0lbimax(|a1b1|,,|anbn|)biO(nl4)

Jujur saya tidak tahu sama sekali bagaimana bahkan mulai menyelesaikan pertanyaan ini. Sepertinya pertanyaan pemrograman dinamis bagi saya, tetapi profesor mengatakan bahwa ini harus diselesaikan dengan menggunakan algoritma serakah. Akan sangat dihargai jika seseorang dapat mengarahkan saya ke arah yang benar dengan memberikan sedikit petunjuk.

Aden Dong
sumber

Jawaban:

9

Mari kita mulai dengan pengamatan berikut:

Biarkan max menunjukkan maksimum urutan a1,...,an , dan biarkan min menunjukkan minimumnya. Jika a1=max , maka memilih b1=b2=...=bn=(max+min)/2 adalah optimal.

Mengapa demikian? Ya, karena urutan dimulai dengan maksimum, baik kita memilih besar, dan menderita penyimpangan besar dari minimum urutan (karena setiap berikutnya harus lebih besar atau sama dengan ), atau kita memilih kecil dan menderita dari deviasi ke . Rata-rata meminimalkan deviasi maksimal.b i b 1 b 1 m a xb1bib1b1max

Kita sekarang dapat mencoba menggeneralisasi pengamatan ini untuk digunakan pada urutan umum . Sebagai contoh, kita dapat mempartisi urutan apa pun menjadi urutan, sehingga masing-masing dimulai dengan maksimum urutan berikutnya.a1,...,an

Contoh: dipartisi menjadi , , dan .( 2 ) ( 6 , 4 , 1 , 5 , 2 ) ( 8 , 7 , 5 , 1 )(2,6,4,1,5,2,8,7,5,1)(2)(6,4,1,5,2)(8,7,5,1)

Dengan diberikannya partisi ini, sekarang kita dapat menyelesaikan setiap ini secara terpisah, dan mendapatkan penugasan dari , yang bagaimanapun dapat melanggar kondisi yang tidak menurun. Ini dapat diperbaiki tanpa kehilangan optimalitas.bi

Perhatikan bahwa urutan terakhir selalu berisi maksimum dari seluruh urutan (jika tidak, akan ada urutan berikutnya setelahnya). Biarkan menjadi nilai yang kami tetapkan untuk sesudahnya. Sekarang, untuk mencapai non-penurunan di , kita mulai dari belakang di dan bekerja terus ke depan. Jika lebih besar dari , kami cukup menetapkan . Jika lebih kecil, kami menyimpannya. Kemudian, kita lanjutkan dengan membandingkan dengan dan seterusnya. Perhatikan bahwa menurunkan apa pun ke nilaiw 1 , w 2 , . . . , W k k w 1 , . . . , w k w k w k - 1 w k w k - 1 : = w k w k - 2 w k - 1 w i w i + 1 w i w i + 1maxw1,w2,...,wkkw1,...,wkwkwk1wkwk1:=wkwk2wk1wiwi+1tidak pernah meningkatkan deviasi, karena nilai pepatium pada baris berikutnya yang ditentukan dengan selalu lebih rendah dari maksimum pada baris berikutnya yang ditetapkan dengan .wiwi+1

Algoritma ini seharusnya benar, saya pikir. Mengenai waktu berjalan, langkah kuncinya adalah menghitung peningkatan maksimum untuk urutan berikutnya, yang mungkin dilakukan dalam ? Tidak yakin dari mana berkontribusi.lO(n)l

Syzygy
sumber
2

Saya akan berpikir keras di sini hanya bekerja melalui petunjuk yang Anda berikan. Mari kita pergi ke petunjuk asli mengatakan bahwa adalah apa yang harus Anda coba terlebih dahulu. Saya dapat memikirkan algoritma serakah yang memiliki waktu itu.O(nl)

Bagian dari kompleksitas waktu berarti Anda dapat menyimpan daftar hitungan setiap kemunculan setiap nilai . Itu, hanya membuat set yang melacak jumlah setiap dalam set. Anda dapat membuat daftar awal dengan memindai urutan input satu kali.l0..lCount=C0,,Cll

Anda dapat memindai daftar ini di untuk mendapatkan nilai maksimum dan minimum. Jika Anda mengisi seluruh daftar dengan titik tengah ini, varian Anda hanya akan menjadi perbedaan dari nilai ini dan maks / mnt. Ini pada dasarnya adalah skenario terburuk Anda, sebut saja .O(l)bbw

Jadi kerjakan ke dari kiri. Anda berdua dapat menjatuhkan elemen ini dari dan mendapatkan min / maks dari di . Sekarang kita bisa serakah. Kami tidak memilih karena itu memaksa seluruh daftar yang tersisa (untuk memenuhi persyaratan yang tidak menurun) dan dengan demikian meningkatkan varians. Nilai minimum yang dapat kita pilih adalah . Jika berada dalam rentang yang dapat diterima, kami memilihnya, jika di bawah kisaran daripada menggunakan minimum. Ini meminimalkan varians pada mengingat kendala yang diketahui.biCountb[i+1]b[n]O(l)bi>bwb[i1]aibi

Ini hanya sebuah ide, mungkin saya beruntung dan itu menunjukkan Anda ke arah yang benar. Algoritma ini mungkin tidak berfungsi (hanya untuk beberapa tes sederhana saya), tetapi cocok dengan petunjuk yang diberikan, jadi mungkin ini membantu. Jika benar mudah untuk melihat bahwa bagian pasti dapat diturunkan ke , bahkan lebih jauh lagi, saya tidak yakin.O(l)O(logl)

edA-qa mort-ora-y
sumber
2

Ini adalah solusi profesor, yang ia sebut "reduksi": Untuk setiap dari hingga , cobalah untuk membangun solusi jika kita tahu bahwa deviasinya kurang dari atau sama dengan . Pertama yang solusi dapat ditemukan adalah deviasi minimum. Kami dapat menemukan solusi mengingat penyimpangan dalam waktu . Jadi waktu berjalan adalah . Kemudian, alih-alih menggunakan pencarian linear, kita dapat menggunakan pencarian biner untuk menentukan penyimpangan terkecil yang memungkinkan solusinya. Ini mengurangi waktu berjalan ke , yang memenuhi persyaratan .i0liiO(n)O(nl)O(nlogl)O(nl4)

Aden Dong
sumber
4
Jadi adalah tipuan ... Tapi saya lebih tertarik dengan "Kita bisa menemukan solusi mengingat penyimpangan dalam O (n) waktu" .. bagaimana itubukanbagian yang menarik? O(nl4)
jmad
@jmad Mengingat , untuk setiap j , mengambil b j sebagai nilai terendah yang setidaknya sama besarnya dengan semua sebelumnya b k , dan yang tidak lebih dari i jauh dari sebuah j . Jika kita tidak dapat menemukan nilai seperti itu, apa artinya? Ini berarti bahwa sebelumnya b t lebih dari i lebih besar dari sebuah j . Jadi sebelumnya sebuah t lebih dariijbjbkiajbtiajat lebih besar dari sebuah j . Jadi nilai saya tidak mungkin. Jika Anda melewati n2iajinnilai tanpa macet seperti ini, Anda telah menemukan solusi untuk tanpa mundur, dalam waktu O ( n ) . iO(n)
jwg
O (n log l) akan menjadi petunjuk kuat bahwa Anda perlu melakukan beberapa pencarian biner pada rentang 0 hingga l.
gnasher729
0

Saya pikir ini harus bisa dilakukan di O (n).

Ambil masalah yang sama: Mengingat , 1 ≤ i ≤ n, dan d ≥ 0, menemukan b i di non-urutan seperti itu | a i - b i | d untuk semua i, atau menunjukkan bahwa itu tidak mungkin. Ini dapat dilakukan di O (n), dan menggunakan pencarian biner masalah asli diselesaikan dalam O (n log l).aibi|aibi|d

Sekarang jika ada saya ≤ j sehingga a_i - a_j> 2d, maka tidak ada solusi (karena ).biaid,bjaj+d<ai2d+d=aidbi

Tetapi jika a_i - a_j ≤ 2d untuk semua saya ≤ j maka saya pikir solusi akan selalu ditemukan. Jadi yang harus kita lakukan adalah mencari m = max (a_i - a_j) untuk semua i ≤ j, dan pilih d = floor ((m + 1) / 2). Maksimum itu dapat ditemukan di O (n).

gnasher729
sumber
Ide yang menarik! Saya percaya sesuatu seperti ini mungkin berhasil, tetapi sepertinya ada celah besar di akhir jawaban Anda dan saya kesulitan mengisi detailnya. Apakah Anda memiliki bukti bahwa jika untuk semua i j maka solusi selalu ada? Lebih penting lagi, bagaimana kita menemukannya? Pertanyaan aslinya mengatakan kita harus menemukan b i . Bahkan jika kita berasumsi ada solusi, saya mengalami kesulitan melihat bagaimana menemukan b i yang sesuai . Dapatkah Anda menguraikan itu? aiaj2dijbibi
DW