Tags


Ringkasan Pembahasan Soal Radar
Pasti ada penempatan radar-radar optimal di mana semua radar berada di titik dengan nilai y yang sama (segaris). Pada penempatan ini, pesawat dengan T yang berbeda ataupun V yang berbeda pasti akan terdeteksi di waktu yang berbeda. Contoh saja, kita bisa mengambil y bilangan irrasional, misalnya PI.
Oleh karena itu, kita bisa mengelompokkan pesawat-pesawat berdasarkan T dan V (yang T dan V nya sama diberi nomor yangsama).
Misal ada 3 pesawat dengan T dan V berturut-turut (dari kiri ke kanan):
(a) T = 5, V = 2
(b) T = 3, V = 2
(c) T = 5, V = 2
Pesawat (a) bisa kita beri nomor 1, (b) bisa kita beri nomor 2, (c) karena sama dengan (a) kita beri nomor 1. Kasus ini bisa dikodekan sebagai:
1 2 1
Misal r adalah radar. Kita bisa menempatkan r seperti berikut ini sehingga semua pesawat pasti terdeteksi:
1 r 2 1
Ketika pesawat-pesawat bernomor 1 melewati sisi radar, kedua pesawat dapat terdeteksi (sekali lagi ingat, pesawat-pesawat yangdinomori berbeda akan melewati samping radar di waktu yang berbeda). Begitu pula ketika satu-satunya pesawat bernomor 2melewati sisi radar ia akan terdeteksi.
Ilustrasi:
1 r . 1 (ketika pesawat-pesawat bernomor 1 melewati sisi-sisi radar)
. r 2 .  (ketika pesawat-pesawat bernomor 2 melewati sisi-sisi radar)
Sekarang kita coba meletakkan radar-radar sesedikit mungkin. Pada solusi optimal, tidak akan ada dua atau lebih pesawat bernomor sama terletak di sebelah kiri radar paling kiri. Mengapa? Karena hal ini akan mengakibatkan pesawat bernomor tersebut yangberposisi paling kiri tidak terdeteksi radar. Perhatikan contoh berikut.
[1] 1 r …
Pada kasus tersebut, pesawat yang diberi kurung siku tidak dapat terdeteksi. Perhatikan kasus berikut juga untuk lebih jelasnya:
1 2 1 r …
Pada saat pesawat-pesawat bernomor 1 melewati samping radar r, kasus sebelumnya terjadi ([1] 1 r …).
Nah, perhatikan bahwa jika radar paling kiri bisa diletakkan di antara pesawat ke-i dan ke-(i + 1) dari kiri maupun di antara pesawat dengan urutan ke-j dan ke-(j + 1), dan i > j, pasti ada solusi yang lebih atau setidaknya sama optimal dengan peletakkan radar di antara pesawat ke-i dan ke-(i + 1) dibanding di antara j dan (j + 1).
Mengapa? Asumsikan ada solusi optimal di mana radar terkiri diletakkan di antara j dan (j + 1). Geser radar tersebut ke posisi antara i dan (i + 1), maka semua pesawat tetap dapat terdeteksi.
Oleh karena itu, letakkan radar terkiri di posisi sekanan mungkin yang masih valid (tidak ada dua atau lebih pesawat bernomor sama terletak di sebelah kirinya). Lalu hapus semua pesawat yang bisa ia deteksi baik di kiri maupun di kanan. Lalu kita peroleh subproblem yang sama persis (cari peletakan radar terkiri lagi), bisa rekursi. Misal solusi optimal untuk subproblem ini adalah S’, maka solusi untukproblem kita adalah S’ + 1 (tambah 1 karena kita sudah meletakkan sebuah radar di posisi paling kiri).
Dengan solusi berdasar pada teknik greedy ini, jika diimplementasikan dengan tepat akan diperoleh algoritma dengan kompleksitasO(n lg n).
Advertisements