BAB 1
PENDAHULUAN
1.1 Latar Belakang
Graf adalah salah satu metode yang sering digunakan untuk mencari solusi dari permasalahan diskrit dalam dunia nyata. Dalam
kehidupan sehari-hari, graf
digunakan untuk menggambarkan struktur yang ada. Tujuannya adalah sebagai visualisasi objek-objek agar lebih mudah dimengerti. Graf mempunyai banyak konsep, salah satunya adalah konsep pohon. Konsep ini mampu mendukung penerapan graf dalam berbagai bidang ilmu. Aplikasi yang menggunakan konsep pohon ini adalah pembangunan jalan dan rel kereta api, pembuatan jaringan computer, mencari jalur pemeliharaan dengan bobot biaya yang minimum. Masalah ini dapat dipecahkan dengan menggunakan pohon merentang minimum (minimum spanning tree). Dan algoritma algoritma greedy merupakan metode paling sesuai untuk memecahkan persoalan optimasi.
Algoritma greedy adalah algoritma yang memecahkan maslah langkah perlangkah dimana pada setiap langkah dibuat pilihan optimum (local optimum) dengan harapan bahwa langkah berikutnya mengarah ke solusi optimum global (global optimum). Algoritma greedy membuat keputusan berdasarkan pilihan yang ada sekarang, tidak melihat pilihan yang akan muncul kemudian. Terkadang algoritma greedy mengambil keputusan yang diambil terlalu dini tanpa melihat yang akan ditemui berikutnya sehingga menimbulkan apa yang disebut good next move, bad overall move .
Universitas Sumatera Utara
2
Melihat kelemahan yang dimiliki, solusi optimum global yang didapatkan belum tentu merupakan solusi optimum (terbaik) karena algoritma greedy tidak beroperasi secara menyeluruh terhadap semua alternatif solusi yang ada. Namun begitu algoritma ini tetap merupakan pilihan utama untuk memecahkan permasalahan sederhana karena metode ini yang paling cepat dibandingkan dengan metode yang lainnya. Metode ini juga dapat memberikan solusi hampiran atau aproksimasi terhadap nilai optimum yang diinginkan dan hasil yang diberikan masih merupakan solusi yang layak (feasible solution).
Algoritma yang termasuk ke dalam algoritma greedy antara lain kode Huffman, algoritma Djikstra, algoritama Prim dan algoritma Kruskal yang digunakan dalam menyelesaikan permasalahan optimasi pada graf. Karena kasus yang dipakai untuk memecahkan permasalahan dalam membangun pohon merentang minimum, maka algoritma yang ada dan dapat digunakan adalah algoritma Prim dan algoritma Kruskal.
Dalam tulisan ini penulis akan menggunakan strategi algoritma greedy dengan menggunakan
algoritma
Prim
dan
algoritma
Kruskal
untuk
memecahkan
permasalahan dalam membangun pohon merentang minimum pada graf berbobot dengan membandingkan dengan algoritma program dinamik.
1.2 Perumusan Masalah
Masalah pokok dalam penelitian ini adalah memecahkan permasalahan pada spanning tree dengan menggunakan strategi greedy dan dinamik untuk memperoleh solusi yang layak (feasible) dan efisien.
Universitas Sumatera Utara
3
1.3. Pembatasan Masalah
Pada tulisan ini masalah mendapatkan solusi untuk membangun minimum spanning tree dibatasi pada model graf tak berarah (undirected graph), connected graph dan berbobot (weighted).
1.4
Tinjauan Pustaka
Sebagai pendukung teori dalam penulisan tugas akhri ini, penulis menggunakan beberapa jurnal dan buku antara lain :
Graf G didefinisikan sebagai pasangan himpunan
dalam hal ini:
= himpunan tidak kosong dari simpul-simpul (vertices atau node).
V = {v1 , v2 ,K, vn } dan = himpunan sisi (edges atau arcs) yang menghubungkan sepasang simpul
E = {e1 , e2 ,K, en }
Atau dapat ditulis singkat notasi
Narsingh Deo (2) dalam buku and Computer Science
(Munir, 2003)
graph teory with Application to Engineering
menjelaskan bahwa graf
adalah pasangan
dengan
adalah himpunan yang tidak kosong yang anggotanya disebut simpul (vertex) dan adalah himpunan yang anggotanya adalah pasangan-pasangan tidak berurut dari vertex dan disebut sisi (edge).
Pohon merentang (spanning tree) didefinisikan: Sebuah subgraf disebut sebuah pohon merentang (spanning tree) dari (tree) dan
jika
dari graf
adalah sebuah pohon
memuat semua simpul (vertex) dari . (Seymour and Lipson hal 89)
Universitas Sumatera Utara
4
Pohon adalah graf tak berarah terhubung dan tidak mengandung sirkuit. Sifat yang terpenting pada pohon adalah terhubung dan tidak mengandung sirkuit. Pohon dinotasikan sama dengan:
T = (V , E ) dimana: = tree (pohon). = verteks atau node atau simpul.
merupakan himpunan tidak kosong.
V = {v1, v2 ,K, vn } = edges atau sisi yang menghubungkan simpul.
E = {e1, e2 ,K, en }
Algoritma Prim membentuk pohon merentang minimum dimulai dari graf yang kosong sama sekali dengan meminimumkan langkah per langkah. Pada setiap langkah kita pilih sebuah titik sebarang dari sisi graf namun yang terhubung dengan pohon merentang
yang memiliki bobot minimum
yang telah terbentuk.
Algoritmanya adalah : 1. Ambil sisi dari graf 2. Pilih sisi , tetapi
yang berbobot minimum, masukan kedalam .
yang memiliki bobot minimum dan bersisian dengan simpul di tidak membentuk sirkuit di . Tambahkan
3. Ulangi langkah 2 sebanyak
ke dalam .
kali.
Algoritma Kruskal juga dapat digunakan dalam memecahkan permasalahan pada pemodelan pohon merentang minimum. Pada algoritma Kruskal mula-mula semua garis dalam
diurutkan berdasarkan bobotnya dari kecil hingga ke besar. Pada setiap
langkah, dipilih garis dengan bobot terkecil, tetapi tidak membentuk loop dengan garis-garis yang sudah dipilih terdahulu.
Algoritmanya adalah : 1.
Isi
dengan semua titik-titik
tanpa garis.
Universitas Sumatera Utara
5
2.
Buat
3.
Ambil sisi selanjutnya dari , jika sisi itu tidak membentuk sirkuit.
4.
Masukkan simpul-simpul sisi itu ke .
1.5
Tujuan Penelitian
dengan memasukkan satu sisi terpendek dari
tersebut.
Adapun tujuan penelitian ini adalah untuk memecahkan permasalahan dalam membangun pohon merentang minimum untuk memberikan solusi yang layak (feasible), efisien dan cepat.
1.6 Manfaat Penelitian
Adapun manfaat yang diharapkan dari penelitian ini adalah menambah wawasan ilmu dan pemahaman kepada penulis dan pembaca penggunaan algoritma greedy dalam membangun minimum spanning tree.
1.7 Metode Penelitian
Metode penelitian yang akan digunakan adalah penelitian literatur yang disusun berdasarkan rujukan pustaka dengan langkah-langkah sebagai berikut:
Langkah-1 : Pengenalan gambaran umum mengenai pohon merentang minimum yang merupakan masalah dari graf. Langkah-2 : Membangun pohon merentang minimum kedalam algoritma greedy yang mana algoritma yang digunakan adalah algoritma Prim dan algoritma Kruskal. Langkah-3 : Menggunakan algoritma Prim dan Kruskal untuk mendapatkan solusi yang layak (feasible) untuk membangun pohon merentang minimum. Langkah-4 : Kesimpulan.
Universitas Sumatera Utara