minimum spaning tree - gunadarma...

ALGORITMA GREEDY :

MINIMUM SPANNING TREE

Perbandingan Kruskal dan Prim

AGENDA

Pendahuluan

Dasar Teori

Contoh Penerapan Algoritma

Analisis perbandingan algoritma Prim dan

Kruskal

Kesimpulan

PENDAHULUAN

Parameter algoritma di ukur dari performa

algoritma secara efektif dan efisien

Pengambilan jalan tengah yaitu pencarian solusi

optimal

Salah satu cara pencapaian solusi algoritma

optimal adalah dengan metode Greedy

Greedy digunakan untuk penyelesaian beberapa

masalah antara lain :

a. TSP (Traveling Sallesperson Problem)

b. MST (Minimum spanning Tree)

c. Minimasi waktu dalam sistem (penjadwalan)

DASAR TEORI

Algorimta Greedy

Minimum spanning Tree

Algoritma Kruskal

Algoritma Solin

Algoritma Prim

Memecahkan masalah dengan cara step by step,

langkahnya sebagai berikut :

a. Memilih langkah yang terbaik pada saat itu tanpa

memprediksi kedepanya

b. Memilih optimum lokan dan berakhir pada optimum

global

Secara umum algoritma greedy disusun oleh elemen-

elemen berikut :

a. Himpunan kandidat

b. Himpunan Solusi

c. Fungsi Seleksi (Selection Function)

d. Fungsi Kelayakan (feasible)

ALGORITMA GREEDY

MINIMUM SPANNING TREE

Pencarian biaya yang minimum dari suatu graph sehingga

membentuk pohon .

Syarat Graph yang dapat dicari minimum spanning

treenya :

a. Graph harus terhubung

b. Ruasnya punya bobot

c. Graph tidak berarah

Algoritma yang dipakai untuk menentukan minimum

spanning tree :

a. Algoritma Kruskal

b. Algoritma Solin

c. Algoritma Prim

ALGORITMA KRUSKAL

Himpunan sisi dari G diurutkan membesar

sesuai bobot sisi tersebut.

Buat T dengan memasukan 1 sisi terpendek dari

G tersebut.

Ulang (banyak sisi T = (banyak simpul G)-1)

Ambil sisi selanjutnya dari G.

Jika sisi itu tidak membuat sirkuit di T Masukan sisi itu ke T

Masukan simpul-simpul sisi itu ke T

Pseudo-code algoritma kruskal

ALGORITMA SOLIN

Algoritma Solin untuk MST merupakan

kebalikan dari algoritma Kruskal, yaitu

membuat tree didahului dengan melakukan

pengurutan garis dari garis yang mempunyai

bobot terbesar. Algoritma Solin tidak akan

dibahas lebih lanjut dalam makalah ini.

ALGORITMA PRIM’S

Ambil sisi graph G yang berbobot minimum,

masukan kedalam T.

Pilih sisi (u,v) yang memiliki bobot minimum dan

bersisian dengan simpul di T. Tetapi (u,v) tidak

membentuk sirkuit di T. Tambahkan (u,v)

kedalam T.

Ulangi langkah ke-2 sebanyak (n-2) kali.

Pseudo-code algoritma prim :

CONTOH PENERAPAN ALGORITMA

pemerintah ingin mengganti sistem jaringan kabel

telepon yang sudah ada di satu daerah dengan kabel

yang baru. Namun karena ini baru, pemerintah tidak

mau ambil resiko mengganti semua kabel yang

menghubungkan wilayah satu dengan yang lain. Ia

hanya akan memasang jaringan di wilayah itu jika

wilayah itu memang belum tersentuh jaringan yang

baru.

Dengan asumsi, semakin panjang kabel yang

dipasang, semakin mahal biaya yang harus

dikeluarkan, buatlah jaringan yang dibangun ini

memakan biaya sesedikit mungkin.

Masukan :

Masukkan terdiri dari beberapa baris bilangan.

Baris pertama terdiri dari 2 angka V dan E,

masing-masing menyatakan banyaknya wilayah

dan banyaknya jalur yang lama. E baris

selanjutnya menggambarkan bagaimana

wilayah-wilayah yang ada dihubungkan oleh

jalur-jalur yang lama. Wilayah diberi nomor

mulai dari 1 hingga V. Diberikan pula W pada

tiap jalur yang menyatakan panjang jalur

tersebut.

Contoh 1 : Contoh 2

4 5 7 11

1 2 10 1 4 5

1 3 14 3 5 5

1 4 15 4 6 6

2 3 12 2 4 9

3 4 9 1 2 7

2 5 7

2 3 8

4 5 15

5 6 8

5 7 9

6 7 11

Batasan 1 < V <= 100; 1<=E<=100; 1<=W<=3000.

Keluaran:

Hasil keluaran hampir sama dengan masukkan.

Cukup tampilkan saja panjang kabel minimum

yang harus dibuat, kemudian, tampilkan,

wilayah, wilayah mana saja yang harus

dihubungkan, beserta dengan panjangnya. Hasil

maupun urutan dari jaringan yang terbentuk

boleh berbeda, namun panjang minimum yang

didapat harus sesuai.

KELUARAN

Contoh 1 Contoh 2

31 39

1 2 10 1 4 5

2 3 12 3 5 5

3 4 9 4 6 6

1 2 7

2 5 7

5 7 9

SOLUSI

Dengan algoritma yang sudah diberikan, kita

bisa menyelesaikan permasalahan ini, salah

satunya dengan menggunakan bahasa

pemrograman Pascal. Dua contoh kode di bawah

ini merupakan contoh solusi dari permasalahan

pemasangan kabel telepon diatas. Dalam kode

yang dibuat dibawah ini, graf dan pohon

direpresentasikan dalam representasi himpunan.

Hal ini dilakukan untuk mempermudah

pengkodean.

Demo Program

REALISASI

Dengan algoritma yang diberikan tersebut serta

dengan contoh masukkan yang sudah diberikan,

kita bisa menggambarkan bagaimana proses

pembentukkan pohon merentang minimum dari

dua algoritma yang berbeda tersebut.

REALISASI ALGORITMA PRIM

10 12

9A

D

B

C

REALIASI ALGORITMA KRUSKAL

10 12

9A

D

B

C

Langkah Algoritma Prim Algoritma Kruskal

Terpilih

(Simpul)

Sisi

Terbentuk

Terpilih

(Sisi)

Simpul

Masuk

0 1 - (1,4) {1,4}

1 4 {(1,4)} (3,5) {1,3,4,5}

2 6 {(1,4), (4,6)} (4,6) {1,3,4,5,6}

3 2 {(1,4), (4,6),

(1,2)}

(1,2) {1,2,3,4,5,6}

4 5 {(1,4), (4,6),

(1,2), (2,5)}

(2,5) {1,2,3,4,5,6}

5 3 {(1,4), (4,6),

(1,2), (2,5),

(5,3)}

(2,3) Ditolak

6 7 {(1,4), (4,6),

(1,2), (2,5),

(5,3), (5,7) }

(5,7) {1,2,3,4,5,6,

7}

Contoh 2, bisa kita gambarkan dengan teknik yang berbeda.

ANALISIS PERBANDINGAN ALGORITMA

PRIM DAN KRUSKAL

Jika kita melihat algoritma Prim dan Kruskal yang telah

disebutkan di atas serta dengan melihat potongan kode yang

telah dibuat, kita bisa memeperkirakan waktu yang dibutuhkan

untuk menjalankan program tersebut.

Jadi perkiraan total waktu

yang dibutuhkan :

Sehingga kompleksitas algoritmanya: O(V2), dengan

V menyatakan banyaknya simpul.

Untuk algoritma Kruskal:

Jadi perkiraan total waktu yang dibutuhkan :

TK(V,E) = E 2log E + 1 + E(1+1) + V(1+1) = E 2log E + 2V + 2E + 1

Sehingga kompleksitas algoritmanya:

O(E log E + V), dengan E menyatakan banyaknya sisi dan V

menyatakan banyaknya simpul.

untuk melihat kecepatan dari program ini, cukup melihat waktu

perkiraan T(V,E) saja.

Dari tabel terlihat bahwa secara umum, algoritma Kruskal bisa

berjalan lebih cepat dibanding algoritma Prim.

KESIMPULAN

Algoritma Prim dan Algoritma Kruskal dapat

menyelesaikan permasalahan pencarian pohon

merentang minimum dengan tepat.

Algoritma Prim lebih efisien dibanding algoritma

Kruskal saat graf yang diberikan memiliki

banyak sisi dengan simpul yang sedikit (graf

lengkap).

Algoritma Kruskal lebih efisien dibanding

algoritma Prim saat graf yang diberikan

memiliki banyak simpul dengan sisi yang sedikit.