Saturday, 26 April 2014

Algoritma Kruskal

18:02 Posted by Unknown No comments
Algoritma Kruskal adalah algoritma untuk mencari pohon merentang minimum secara langsung didasarkan pada algoritma MST (Minimum Spanning Tree) umum. Pada algoritma Kruskal sisi-sisi di dalam graf diurut terlebih dahulu berdasarkan bobotnya dari kecil ke besar. Sisi yang dimasukkan ke dalam himpunan T adalah sisi graf G sedemikian sehingga T adalah pohon. Pada keadaan awal, sisi-sisi sudah diurut berdasarkan bobot membentuk hutan (forest). Hutan tersebut dinamakan hutan merentang (spanning forest). Sisi dari graf G ditambahkan ke T jika tidak membentuk sirkuit di T.
Perbedaan prinsip antara algoritma Prim dan Kruskal adalah jika pada algoritma Prim sisi yang dimasukkan ke dalam T harus bersisian dengan sebuah simpul di T, maka pada algoritma Kruskal sisi yang dipilih tidak perlu bersisian dengan simpul di T asalkan penambahan sisi tersebut tidak membentuk sirkuit.
Langkah-langkah dalam algoritma Kruskal adalah sebagai berikut:
1.   Lakukan pengurutan terhadap setiap sisi di graf mulai dari sisi dengan bobot terkecil sampai terbesar.
2.  Pilih sisi yang mempunyai bobot minimum yang tidak membentuk sirkuit di pohon. Tambahkan sisi tersebut ke dalam pohon.
3.  Ulangi langkah 2 sampai pohon merentang minimum terbentuk, yaitu ketika sisi di dalam pohon merentang minimum berjumlah n-1 (n adalah jumlah simpul di graf).
                                                                        


             Berdasarkan gambar di atas, maka dilakukan pengurutan sisi pada graf mulai dari sisi dengan bobot 
terkecil sampai terbesar dapat dilihat pada tabel berikut:

Kalau masih kurang paham, bisa dilihat di video dibawah ini :

                                 


Algoritma Prim

17:47 Posted by Unknown No comments
                      
     Algoritma Prim adalah sebuah algoritma dalam teori graf untuk mencari pohon rentang minimum untuk sebuah graf berbobot yang saling terhubung. Ini berarti bahwa sebuah himpunan bagian dari edge yang membentuk suatu pohon yang mengandung node, di mana bobot keseluruhan dari semua edge dalam pohon diminimalisasikan. Bila graf tersebut tidak terhubung, maka graf itu hanya memiliki satu pohon rentang minimum untuk satu dari komponen yang terhubung.(Wiki).


Langkah-langkah untuk mencari bobot minimum:
  1. Ambil sisi dari graph (G) yang berbobot minimum, masukkan dalam Tree ( T ).
  2. Pilih sisi yang mempunyai bobot minimum dan bersisian dengan simpul di T ,tetapi sisi tersebut tidak membentuk sirkuit di T, kemudian tambahkan sisi tersebut ke dalam T.
  3. Ulangi langkah 2 sebanyak (N -2 ) kali.
Berikut ini adalah contoh sebuah kasus mengenai Algoritma Prim:  
                

Penyelesaiannya:
                          

Pohon Rentang Minimum

17:36 Posted by Unknown No comments
                                                    

      Pohon rentang minimum (minimal spanning tree) adalah teknik mencari jalan penghubung yang dapat menghubungkan semua titik dalam jaringan secara bersamaan sampai diperoleh jarak minimum.
      Masalah pohon rentang minimum serupa dengan masalah rute terpendek (shortest route), kecuali bahwa tujuannya adalah untuk menghubungkan seluruh simpul dalam jaringan sehingga total panjang cabang tersebut diminimisasi. Jaringan yang dihasilkan merentangkan (menghubungkan) semua titik dalam jaringan tersebut pada total jarak (panjang) minimum.

Langkah-langkah dari pohon rentang minimum adalah :
  1. pilih secara arbitrer sebuah node dalam jaringan
  2. hubungkan node tersebut dengan node terdekat yang dapat meminimalkan total jarak
  3. perhatikan semua node apakah terdapat node yang belum terhubung, temukan dan hubungkan node terdekat yang belum terhubung
  4. ulangi langkah ketiga sampai seluruh node dapat terhubung
       Sebagai contoh, gedung Istec Corporation yang baru memiliki beberapa ruangan dan tiap ruangan membutuhkan 1 lubang aliran listrik (atau biasa disebut sebagai steker). Teknisi listrik akan menyalurkan listrik dari ruang bagian depan sampai keseluruh ruangan dengan total panjang kabel yang seefisien mungkin. Adapun jarak antar ruangan dapat digambarkan dalam gambar jaringan berikut ini, sedangkan ruang bagian depan digambarkan sebagai node-1.
           Karena node-1 adalah ruangan terdepan yang menjadi sumber aliran listrik utama, maka node-1 akan dijadikan sebagai patokan dalam jaringan. Node yang paling dekat dengan node-1 adalah node dengan jarak 2 meter, sehingga kita hubungkan node 1 dengan node-3.

           Kemudian kita lihat node-node terdekat yang belum terhubung dengan node 1 dan 3, yaitu node 7, 6 dan 2. Yang terdekat dengan node 3 adalah node 7 dengan jarak 3 meter. Kemudian node 3 dan node 7 dapat dihubungkan.

             Node yang belum terhubung terdekat dengan node 1, 3 dan 7 adalah node 6 dengan panjang 2 meter.



           Node yang belum terhubung dan dekat dengan node 1,3,7 dan 6 adalah 5 dan 2. Node 5 dapat terhubung dengan node 6 dengan jarak 3 meter, sedangkan node 3 dapat dihubungkan dengan node-1 dengan jarak 3 meter.


              Sisa node yang belum terhubung adalah node 8, 4 dan 9. Node 4 dapat dihubungkan dengan node 5 dengan jarak 3 meter, dan untuk mencapai node 9 total jarak terdekat lebih pendek jika ditempuh dari node 8 ke 9 dari pada melalui node 4.



           Karena seluruh node telah terhubung atau telah terkait dalam satu jaringan, maka solusi di atas telah optimum. Jadi teknisi listrik dapat memulai merentangkan kabelnya dengan menghubungkan node 1 – 2, 1 – 3, 3 – 7, 6 – 7, 5 – 6, 4 – 5,6 – 8, 8 – 9
Panjang kabel yang dibutuhkan adalah : 21 meter


Tuesday, 8 April 2014

Algoritma Greedy

21:03 Posted by Unknown No comments
         Algoritma Greedy adalah salah satu algoritma yang dapat digunakan untuk mendapatkan solusi terbaik dan merupakan algoritma yang paling populer dalam hal ini.