GEOMETRY
PROBLEMS
Geometry problem adalah yang
berhubungan dengan objek geometri seperti: titik garis dll. di dalam analisis
algoritma masalah geometry ini di selesaikan menggunakan komputasi(komputer)
adapun algoritma penyelesaian yang digunakan didalam geometri probelm dalam
komputasi di sini kami bahas hanya dua:
1. Closest pair problem
2. Convex hull problem
1. Closest pair probelm
Permasalahan closest pair
merupakan salah satu permasalahan klasik
dalam dunia matematika
diskrit. Secara singkat, deskripsi
permasalahan adalah sebagai berikut: diberikan N buah titik yang
terletak pada bidang planar 2 dimensi,
tentukanlah dua buah titik yang memiliki jarak paling dekat.
. Kita asumsikan bahwa titik pada pertanyaan ditetapkan dalam bentuk
standar dengan Koordinat Cartesius (x, y) dan bahwa jarak antara dua titik Pi
= (xi, yi) dan Pj = (xj, yj) adalah jarak Euclidean standar.
Pendekatan
brute force untuk menyelesaikan masalah ini mengarah pada algoritma: menghitung
jarak antara setiap pasangan titik yang berbeda dan menemukan pasangan dengan
jarak terdekat.Tentu saja, kita tidak ingin menghitung jarak antara pasangan
titik yang sama dua kali. Supaya tidak melakukan hal itu, kita menganggap hanya
ada pasangan titik titik (Pi, Pj) dimana i < j.
Algoritma BruteForceClosestPoint(P)
for
i ß i to n – 1 do
d ß sqrt sqrt adalah
fungsi akar kuadrat
if d < dmin
dmin ß d; index1 ß i; index2 ß j
operasi dasar algoritma
akan menguadratkan angka tersebut. Berapa kali hal ini dilaksanakan dapat
dihitung sebagai berikut:
penyelesaian dengan algoritma divide and
conquer
tidak sesederhana algoritma brute force. Penyelesaian
dengan divide and conquer membutuhkan pencapaian sebuah lemma yang bergantung
pada strategi penyelesaian itu sendiri. Lemma inilah yang menjadi kunci
optimasi. Pada konsepnya, penyelesaian menggunakan algoritma divide and conquer
dapat diabstraksikan melalui pseudocode berikut:
function findClosestPair(left , right) : real
if
(right = left) return 0
else
l = findClosestPair(left , (left +
right) / 2)
r = findClosestPair((left + right) / 2
+ 1 , right)
mid = conquer(left , right)
return min(l,r,mid)
2. Convex hull problem
Definisi suatu
himpunan titik (berhingga atau tak terhingga) pada bidang disebut cembung jika
untuk setiap dua titik P dan Q pada himpunan, seluruh ruas garis dari
P dan Q berada didalam himpunan tersebut.
Convex Hull
dari himpunan n titik pada bidang
adalah polygon cembung terkecil yang mencakup seluruhnya (baik didalam maupun
pada batasnya).
memecahkan
masalah convex-hull dalam kerangka Brute-Force
Brute force
search adalah cara yang sangat mudah diimplementasikan untuk memecahkan masalah
karena brute force search selalu mencari
solusi dari seluruh kemungkinan yang ada. tetapi tidak efisien yang
didasarkan pada pengamatan berikut ini mengenai segmen garis bata dari convex
hull: segmen garis yang menghubungkan dua titik Pi dan Pj dari satu himpunan N titik merupakan bagian dari
batas convex-hull-nya jika dan hanya jika semua titik lain pada himpunan
terletak pada sisi yang sama dari garis lurus melalui kedua titik ini. Akan
tetapi pemecahan masalah menggunakan metode brute force biasanya memerlukan
sumber yang banyak baik waktu dan memori dan kebutuhan tersebut makin membesar
dengan cepat sejalan dengan banyaknya permasalahan yang ingin diselesaikan
Beberapa
bukti mendasar dari geometri analitik dibutuhkan untuk mengimplementasikan
algoritma ini. Pertama, garis lurus melalui dua (x1,y2) (y1,x2) dalam
bidang koordinat dapat didevenisikan dengan persamaan
Pemecahan
Masalah Convex Hull dengan Algoritma Divide and Conquer
Pada
penyelesaian masalah pencarian Convex Hull dengan menggunakan algoritma Divide
and Conquer, hal ini dapat dipandang sebagai generalisasi dari algoritma
pengurutan merge sort. Berikut ini merupakan garis besar gambaran dari
algoritmanya:
·
Lakukan
pengurutan p1, p2, ... pN dalam koordinat X à|S|
·
Buat
partisi himpunan titik-titik tersebut menjadi 2 himpunan A dan B, dimana A
terdiri dari setengah jumlah dari |S| dan titik dengan koordinat X yang
terendah dan B terdiri dari setengah dari jumlah |S| dan titik dengan koordinat
X terbesar
·
Secara
rekursif lakukan penghitungan terhadap HA = conv(A) dan HB = conv(B)
·
Gabungkan
(merge) kedua hull tersebut menjadi convex hull, H, dengan menghitung dan
mencari upper dan lower hull (tangents) untuk HA dan HB. Setiap titik searah
jarum jam untuk himpunan yang berada di sebelah kanan, dan berlawanan arah
jarum jam pada himpunan yang berada di sebelah kiri. dengan mengabaikan semua
titik yang berada diantara dua buah tangen ini
Sumber:
E-Book [Anany Levitin]-Intro_2_Design&Analysis_Algorithms
Tidak ada komentar:
Posting Komentar