Saya memiliki satu set bilangan bulat. Saya ingin menemukan peningkatan berikutnya terpanjang dari set yang menggunakan pemrograman dinamis.
215
Saya memiliki satu set bilangan bulat. Saya ingin menemukan peningkatan berikutnya terpanjang dari set yang menggunakan pemrograman dinamis.
Jawaban:
OK, saya akan menjelaskan dulu solusi paling sederhana yaitu O (N ^ 2), di mana N adalah ukuran koleksi. Ada juga solusi O (N log N), yang akan saya jelaskan juga. Lihat di sini untuk itu di bagian Algoritma yang efisien.
Saya akan menganggap indeks array dari 0 hingga N - 1. Jadi mari kita definisikan
DP[i]
sebagai panjang dari LIS (terpanjang meningkatkan urutan) yang berakhir pada elemen dengan indeksi
. Untuk menghitungDP[i]
kita melihat semua indeksj < i
dan memeriksa apakahDP[j] + 1 > DP[i]
danarray[j] < array[i]
(kita ingin itu meningkat). Jika ini benar, kami dapat memperbarui untuk saat iniDP[i]
. Untuk menemukan global optimal untuk array, Anda dapat mengambil nilai maksimum dariDP[0...N - 1]
.Saya menggunakan array
prev
untuk nanti bisa menemukan urutan sebenarnya tidak hanya panjangnya. Cukup kembali secara rekursif daribestEnd
dalam satu lingkaran menggunakanprev[bestEnd]
. The-1
nilai adalah tanda untuk berhenti.OK, sekarang untuk
O(N log N)
solusi yang lebih efisien :Membiarkan
S[pos]
didefinisikan sebagai bilangan bulat terkecil yang mengakhiri peningkatan panjang urutanpos
. Sekarang beralih melalui setiap integerX
dari set input dan lakukan hal berikut:Jika
X
> elemen terakhir masukS
, maka tambahkanX
ke akhirS
. Ini penting artinya kami telah menemukan yang terbesar baruLIS
.Jika tidak, temukan elemen terkecil di
S
, yaitu>=
dariX
, dan ubah keX
. KarenaS
diurutkan kapan saja, elemen dapat ditemukan menggunakan pencarian biner dilog(N)
.Total runtime -
N
integer dan pencarian biner untuk masing-masingnya - N * log (N) = O (N log N)Sekarang mari kita lakukan contoh nyata:
Koleksi bilangan bulat:
2 6 3 4 1 2 9 5 8
Langkah:
Jadi panjang LIS adalah
5
(ukuran S).Untuk merekonstruksi yang sebenarnya
LIS
kita akan kembali menggunakan array induk. Membiarkanparent[i]
menjadi pendahulu elemen dengan indeksi
diLIS
akhir di elemen dengan indeksi
.Untuk mempermudah, kita bisa tetap menggunakan array
S
, bukan bilangan bulat sebenarnya, tetapi indeks (posisi) mereka di set. Kami tidak menyimpan{1, 2, 4, 5, 8}
, tetapi menyimpan{4, 5, 3, 7, 8}
.Itu adalah input [4] = 1 , input [5] = 2 , input [3] = 4 , input [7] = 5 , input [8] = 8 .
Jika kami memperbarui array induk dengan benar, LIS yang sebenarnya adalah:
Sekarang untuk hal yang penting - bagaimana kita memperbarui array induk? Ada dua opsi:
Jika
X
> elemen terakhirS
, makaparent[indexX] = indexLastElement
. Ini berarti induk dari elemen terbaru adalah elemen terakhir. Kami hanya melanjutkanX
sampai akhirS
.Kalau tidak, cari indeks elemen terkecil di
S
, yaitu>=
dariX
, dan ubah keX
. Di siniparent[indexX] = S[index - 1]
.sumber
DP[j] + 1 == DP[i]
ituDP[i]
tidak akan menjadi lebih baik denganDP[i] = DP[j] + 1
. Kami berusaha mengoptimalkanDP[i]
.[1,2,5,8]
, 4 muncul sebelum 1 dalam array, bagaimana LIS[1,2,4,5,8]
?[2,3,4,5,8]
. Baca dengan cermat -S
arrayDOES NOT
mewakili urutan aktual.Let S[pos] be defined as the smallest integer that ends an increasing sequence of length pos.
Penjelasan Petar Minchev membantu menjernihkan hal-hal bagi saya, tetapi sulit bagi saya untuk menguraikan semua itu, jadi saya membuat implementasi Python dengan nama variabel yang terlalu deskriptif dan banyak komentar. Saya melakukan solusi rekursif naif, solusi O (n ^ 2), dan solusi O (n log n).
Saya harap ini membantu menjernihkan algoritme!
Solusi Rekursif
Solusi Pemrograman Dinamis O (n ^ 2)
Solusi Pemrograman Dinamis O (n log n)
sumber
bisect
. Untuk mendemonstrasikan bagaimana suatu algoritma bekerja dan karakteristik kinerjanya, saya mencoba untuk menjaga hal-hal se primitif mungkin.Berbicara tentang solusi DP, saya menemukan mengejutkan bahwa tidak ada yang menyebutkan fakta bahwa LIS dapat direduksi menjadi LCS . Yang perlu Anda lakukan adalah mengurutkan salinan dari urutan asli, menghapus semua duplikat dan melakukan LCS mereka. Dalam pseudocode itu adalah:
Dan implementasi penuh ditulis dalam Go. Anda tidak perlu mempertahankan seluruh matriks n ^ 2 DP jika Anda tidak perlu merekonstruksi solusinya.
sumber
Implementasi C ++ berikut ini juga menyertakan beberapa kode yang membangun peningkatan terpanjang aktual yang sebenarnya menggunakan sebuah array bernama
prev
.Implementasi tanpa tumpukan hanya membalikkan vektor
sumber
Berikut adalah tiga langkah mengevaluasi masalah dari sudut pandang pemrograman dinamis:
Jika kita ambil sebagai contoh urutan {0, 8, 2, 3, 7, 9}, pada indeks:
Berikut kode C ++ 11 yang berfungsi:
sumber
Berikut ini adalah implementasi Scala dari algoritma O (n ^ 2):
sumber
Inilah implementasi JAWA O (n ^ 2) yang lain. Tidak ada rekursi / memoisasi untuk menghasilkan selanjutnya yang sebenarnya. Hanya larik string yang menyimpan LIS aktual di setiap tahap dan larik untuk menyimpan panjang LIS untuk setiap elemen. Sangat mudah. Lihat:
Kode beraksi: http://ideone.com/sBiOQx
sumber
Ini dapat diselesaikan dalam O (n ^ 2) menggunakan Pemrograman Dinamis. Kode python untuk hal yang sama akan seperti: -
Untuk input:
5 19 5 81 50 28 29 1 83 23
output akan menjadi:
[1, 2, 1, 3, 3, 3, 4, 1, 5, 3] 5
List_index daftar output adalah list_index dari daftar input. Nilai pada list_index dalam daftar output menunjukkan panjang terpanjang meningkat berikutnya untuk list_index itu.
sumber
di sini adalah implementasi java O (nlogn)
sumber
Ini adalah implementasi Java dalam O (n ^ 2). Saya hanya tidak menggunakan Pencarian Biner untuk menemukan elemen terkecil dalam S, yaitu> = daripada X. Saya hanya menggunakan untuk loop. Menggunakan Binary Search akan membuat kompleksitas di O (n logn)
sumber
checkout kode di java untuk penambahan yang paling lama dengan elemen array
http://ideone.com/Nd2eba
sumber
Ini dapat diselesaikan dalam O (n ^ 2) menggunakan pemrograman dinamis.
Memproses elemen input secara berurutan dan memelihara daftar tupel untuk setiap elemen. Setiap tuple (A, B), untuk elemen yang akan saya tunjukkan, A = panjang sub-urutan terpanjang yang berakhir pada i dan B = indeks pendahulu daftar [i] dalam sub-urutan terpanjang yang meningkat yang berakhir pada daftar [i ]
Mulai dari elemen 1, daftar tuple untuk elemen 1 adalah [(1,0)] untuk elemen i, pindai daftar 0..i dan temukan daftar elemen [k] sedemikian rupa sehingga daftar [k] <daftar [i] , nilai A untuk elemen i, Ai akan menjadi Ak + 1 dan Bi akan menjadi k. Jika ada beberapa elemen seperti itu, tambahkan mereka ke daftar tupel untuk elemen i.
Pada akhirnya, temukan semua elemen dengan nilai maksimal A (panjang LIS yang berakhir pada elemen) dan mundur menggunakan tupel untuk mendapatkan daftar.
Saya telah membagikan kode yang sama di http://www.edufyme.com/code/?id=66f041e16a60928b05a7e228a89c3799
sumber
O (n ^ 2) implementasi java:
sumber
walaupun ada cara dimana Anda dapat menyelesaikan ini dalam waktu O (nlogn) (ini diselesaikan dalam waktu O (n ^ 2)) tetapi masih dengan cara ini memberikan pendekatan pemrograman dinamis yang juga baik.
sumber
Berikut ini adalah solusi Leetcode saya menggunakan Pencarian Biner: ->
sumber
Solusi LIS paling sederhana dalam C ++ dengan kompleksitas waktu O (nlog (n))
OUTPUT:
4
sumber
Sub selanjutnya yang Meningkat Terlama (Jawa)
sumber
Saya telah mengimplementasikan LIS di java menggunakan Dynamic Programming and Memoization. Seiring dengan kode saya telah melakukan perhitungan kompleksitas yaitu mengapa itu adalah O (n Log (base2) n). Karena saya merasa penjelasan teoretis atau logis itu baik tetapi demonstrasi praktis selalu lebih baik untuk dipahami.
Sementara saya menjalankan kode di atas -
sumber