icomit

Just another WordPress.com site

Cara Implementasi Algoritma Closest Pair Point Di Java

Setelah beberapa lama saya browsing tentang bagaimana sih cara penerapan algoritma closest pair point alias algoritma pencarian jarak terpendek dari kumpulan titik. saya mendapatkan beberapa sourcecode tingkat lanjut yang tentunya  bagi para programer pemula (seperti saya sendiri 🙂 hehe) yang tingkat pemahamannya masih dibawah standart menjadi semakin ‘MUMET’. kebanyakan para programer kelas atas menyelesaikan masalah closest pair point dengan cara algoritma tingkat lanjut seperti algoritma divide and conquer dan sebagainya… dan sebagainya…..

Okey, dari pada makin mumet7x, walaupun dengan literatur yang terbatas (2 dokumen ppt ditambah info dari wikipedia) saya mencoba menerapkan algoritma closest pair point dengan cara yang sederhana sehingga mudah dipahami walaupun konsekuensinya adalah ke-MANGKUS-an dari algoritma ini berkurang, :-). baiklah cukup basa-basinya, saya mulai pembahasannya mulai dari paragraf di bawah ini……

Algoritma closest pair point adalah suatu algoritma yang memecahkan persoalan untuk mencari jarak terdekat antara kumpulan titik dalam suatu bidang dua dimensi. Cara yang paling sederhana untuk memecahkan masalah ini adalah dengan membandingkan semua kemungkinan titik-titiknya untuk dicari jaraknya. Untuk menentukan jarak antar titik digunakan persamaan berikut.

Persamaan mencari jarak dua titik

Dimana x dan y adalah koordinat masing-masing titik yang diperbandingkan. Algoritma akan mencoba semua kemungkinan titik hingga didapatkan nilai d yang paling kecil. Berikut saya berikan contoh kasus bagaimana menentukan jarak terdekat dari beberapa titik dalam suatu bidang 2D.

Dari gambar di atas terdapat beberapa titik yang akan dicari jarak terdekatnya. Koordinat dari masing-masing titik adalah A(2,2),B(4,4),C(6,9),D(7,5),dan E(8,4). Berikut adalah psoudocode algoritma yang dapat menyelesaikan masalah tersebut.

Dari algoritma tersebut dapat kita lihat bahwa untuk menari nilai d(jarak) dilakukan dengan cara mencoba semua kemungkinan dengan mekanisme perulangan bersarang (dua ‘for’) sehingga kompleksitas algoritma ini adalah O(n2). Berikut adalah hasil implementasi algoritma closest pair point menggunakan bahasa pemrograman java.

public class ClosestPoints {
  private static void cPoint(int[]x,int[]y){
     double dMin= Math.sqrt((x[0]-x[1])*(x[0]-x[1])+((y[0]-y[1])*(y[0]-y[1])));
     double jarak;
     int x1 = 0,y1 = 0,x2 = 0,y2 = 0;
     for (int i = 0; i < y.length-1; i++) {
         for (int j = i+1; j < y.length; j++) {
             jarak=Math.sqrt((x[i]-x[j])*(x[i]-x[j])+((y[i]-y[j])*(y[i]-y[j])));
             if (jarak<dMin){
                dMin=jarak;
                x1=x[i];
                x2=x[j];
                y1=y[i];
                y2=y[j];
             }
          }
      }
      System.out.println("Jarak Terpendek = "+dMin+" di titik ("+x1+","+y1+") dengan ("+x2+","+y2+")");
   }
   public static void main(String[] args) {
      int[]titikX={2,4,6,7,8};
      int[]titikY={2,4,9,5,4};
      cPoint(titikX, titikY);
   }
}

Program di atas mencoba merepresentasikan suatu himpunan titik melalui dua buah array yaitu array titikX sebagai kumpulan koordinat X dan array titikY yang merupakan data-data sumbu Y. dua buah array ini akan diproses dalam method cPoint untuk dicari nilai jaraknya menggunakan persamaan jarak dua titik.

Dalam method cPanel pertama kali dilakukan inisialisasi nilai variable dMin yang didapat dengan cara memeasukkan nilai koordinat titik pertama dan kedua dalam persamaan jarak dua titik. Kemudian melalui mekanisme perulangan dicari nilai jarak yang lain, jika nilai jarak lebih kecil daripada nilai dMin maka nilai dMin akan diganti dengan nilai jarak tersebut. Proses ini akan terus berulang hingga semua kemungkinan sudah dicoba.

Berikut adalah hasil eksekusi program di atas.

Output program dari contoh di atas

Output memberikan informasi berapa jarak yang terpendek beserta dimana titik koordinat titik-titiknya.

Download artikel ini.

Advertisements

6 responses to “Cara Implementasi Algoritma Closest Pair Point Di Java

  1. Angga Ramadhan December 24, 2010 at 2:49 pm

    wew akhrnya muncul jg ni artikel
    thanks yow

  2. icomit December 24, 2010 at 4:20 pm

    Ok, silakan dipelajari….
    jika ada kesulitan mari kita diskusikan..

  3. AladinJember December 26, 2010 at 7:45 am

    alhamdulillah… ketemu rofi nang kene….
    tak copas materine… hohohoo…..

  4. icomit December 26, 2010 at 11:31 am

    copas sih bole2 aja.. asalkan juga dipelajari pokok2 bahasannya…

  5. wiidhiecyber January 12, 2011 at 12:24 pm

    makasih bos atas pencerahannya 🙂

  6. ewii April 17, 2011 at 6:38 am

    alhamdulillah bang, akhirnya aku mendapat kan petunjuk dari abang.
    ohh ya bang, aku maug tanya itu pendeklarasian variabelnya ditaruh mana bang?

    thanks bang 🙂

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: