Permasalahan Dalam Algoritma

 PERMASALAHAN DALAM ALGORITMA

Geometric Problem

Geometric Problem berususan dengan benda-benda geometris seperti titik, garis, dan poligon. Orang Yunani kuno sangat tertatik untuk mengembangkan algoritma , untuk memecahkan berbagai masalah geometris, termasuk bangun sederhana seperi geometris bentuk segitiga, lingkaran dan lainnya dengan penguasaaan penandaan dan compas. Kemudian, selama sekitar 2000 tahun minat yang kuat dalam algoritma geometris menghilang, dan bangkit lagi di era komputer modern dengan penguasaan bit, byte, dan baik kecerdasan buatan. Tentu saja, saat ini orang banyak orang yang tertarik dengan algoritma geometrik dengan penerapan yang berbeda seperti komputer grafis, robotika, dan tomografi.

Masalah klasik dalam Geometric Problem :
• The Closest Pair Problem
Diberikan titik pada suatu bidang dan menemukan pasangan terdekatnya.
• Convex Hull Problem
Menemukan poligon cembung terkecil yang akan mencakup semua titik/nilai yang telah ditentukan.

The Closest Pair
Permasalahan closest pair adalah permasalahan umum yang kerap ditemui dalam konteks geometri ruang dan optimasi jarak. Dalam dunia sehari – hari juga banyak ditemui permasalahan semacam ini. Namun, seringkali kasus nyata memiliki batasan yang tinggi sehingga terkadang solusi dengan algoritma brute force tidak dapat menyelesaikan permasalahan dengan mangkus. Closest Pair merupakan salah satu permasalahan klasik dalam dunia matematika diskrit. Contohnya permasalahannya sebagai berikut : diberikan N buah titik yang terletak pada bidang planar 2-dimensi, tentukanlah dua buah titik yang memiliki jarak paling dekat.

Secara umum, permasalahan ini sering dikaitkan dengan permasalahan pada dunia sehari – hari. Contoh permasalahannya seperti proses pengambilan dua bahan baku oleh lengan robot pada pabrik mikroprosesor agar pergerakan lengan robot seminimal mungkin. Kurang lebih permasalahan ini dapat diselesaikan dengan algoritma brute force yang membutuhkan kompleksitas waktu O(N2 ). Untuk N yang besar (N > 100000), komputasi dengan algoritma brute force akan memakan waktu yang lama, bahkan dengan komputer paling cepat saat ini.

Convex Hull

Convex Hull adalah permasalahan di mana kita diminta untuk membentuk suatu curva yang mampu mengcover semua himpunan titik dengan jumlah garis yang paling minimal.
Jadi misalkan ada segerombol kambing di padang rumput, yang di asumsikan sebagai Covex Hull . Bagaimana cara kita untuk membuat kandang dengan bahan seminimal mungkin .
Jadi masalahnya ketika kita diminta menentukan himpunan titik yang membentuk convex hull itu sendiri dengan cara menulis program tersebut. Kompleksitas untuk menentukan himpunan convex hull adalah O(n3).