minimum spaning tree - gunadarma...
TRANSCRIPT
![Page 1: Minimum spaning tree - Gunadarma Universitykarmila.staff.gunadarma.ac.id/Downloads/files/56606/minimum... · algoritma secara efektif dan efisien Pengambilan jalan tengah yaitu pencarian](https://reader030.vdokumen.com/reader030/viewer/2022020115/5c9d951388c99397348d0074/html5/thumbnails/1.jpg)
ALGORITMA GREEDY :
MINIMUM SPANNING TREE
Perbandingan Kruskal dan Prim
![Page 2: Minimum spaning tree - Gunadarma Universitykarmila.staff.gunadarma.ac.id/Downloads/files/56606/minimum... · algoritma secara efektif dan efisien Pengambilan jalan tengah yaitu pencarian](https://reader030.vdokumen.com/reader030/viewer/2022020115/5c9d951388c99397348d0074/html5/thumbnails/2.jpg)
AGENDA
Pendahuluan
Dasar Teori
Contoh Penerapan Algoritma
Analisis perbandingan algoritma Prim dan
Kruskal
Kesimpulan
![Page 3: Minimum spaning tree - Gunadarma Universitykarmila.staff.gunadarma.ac.id/Downloads/files/56606/minimum... · algoritma secara efektif dan efisien Pengambilan jalan tengah yaitu pencarian](https://reader030.vdokumen.com/reader030/viewer/2022020115/5c9d951388c99397348d0074/html5/thumbnails/3.jpg)
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)
![Page 4: Minimum spaning tree - Gunadarma Universitykarmila.staff.gunadarma.ac.id/Downloads/files/56606/minimum... · algoritma secara efektif dan efisien Pengambilan jalan tengah yaitu pencarian](https://reader030.vdokumen.com/reader030/viewer/2022020115/5c9d951388c99397348d0074/html5/thumbnails/4.jpg)
DASAR TEORI
Algorimta Greedy
Minimum spanning Tree
Algoritma Kruskal
Algoritma Solin
Algoritma Prim
![Page 5: Minimum spaning tree - Gunadarma Universitykarmila.staff.gunadarma.ac.id/Downloads/files/56606/minimum... · algoritma secara efektif dan efisien Pengambilan jalan tengah yaitu pencarian](https://reader030.vdokumen.com/reader030/viewer/2022020115/5c9d951388c99397348d0074/html5/thumbnails/5.jpg)
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
![Page 6: Minimum spaning tree - Gunadarma Universitykarmila.staff.gunadarma.ac.id/Downloads/files/56606/minimum... · algoritma secara efektif dan efisien Pengambilan jalan tengah yaitu pencarian](https://reader030.vdokumen.com/reader030/viewer/2022020115/5c9d951388c99397348d0074/html5/thumbnails/6.jpg)
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
![Page 7: Minimum spaning tree - Gunadarma Universitykarmila.staff.gunadarma.ac.id/Downloads/files/56606/minimum... · algoritma secara efektif dan efisien Pengambilan jalan tengah yaitu pencarian](https://reader030.vdokumen.com/reader030/viewer/2022020115/5c9d951388c99397348d0074/html5/thumbnails/7.jpg)
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
![Page 8: Minimum spaning tree - Gunadarma Universitykarmila.staff.gunadarma.ac.id/Downloads/files/56606/minimum... · algoritma secara efektif dan efisien Pengambilan jalan tengah yaitu pencarian](https://reader030.vdokumen.com/reader030/viewer/2022020115/5c9d951388c99397348d0074/html5/thumbnails/8.jpg)
Pseudo-code algoritma kruskal
![Page 9: Minimum spaning tree - Gunadarma Universitykarmila.staff.gunadarma.ac.id/Downloads/files/56606/minimum... · algoritma secara efektif dan efisien Pengambilan jalan tengah yaitu pencarian](https://reader030.vdokumen.com/reader030/viewer/2022020115/5c9d951388c99397348d0074/html5/thumbnails/9.jpg)
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.
![Page 10: Minimum spaning tree - Gunadarma Universitykarmila.staff.gunadarma.ac.id/Downloads/files/56606/minimum... · algoritma secara efektif dan efisien Pengambilan jalan tengah yaitu pencarian](https://reader030.vdokumen.com/reader030/viewer/2022020115/5c9d951388c99397348d0074/html5/thumbnails/10.jpg)
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.
![Page 11: Minimum spaning tree - Gunadarma Universitykarmila.staff.gunadarma.ac.id/Downloads/files/56606/minimum... · algoritma secara efektif dan efisien Pengambilan jalan tengah yaitu pencarian](https://reader030.vdokumen.com/reader030/viewer/2022020115/5c9d951388c99397348d0074/html5/thumbnails/11.jpg)
Pseudo-code algoritma prim :
![Page 12: Minimum spaning tree - Gunadarma Universitykarmila.staff.gunadarma.ac.id/Downloads/files/56606/minimum... · algoritma secara efektif dan efisien Pengambilan jalan tengah yaitu pencarian](https://reader030.vdokumen.com/reader030/viewer/2022020115/5c9d951388c99397348d0074/html5/thumbnails/12.jpg)
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.
![Page 13: Minimum spaning tree - Gunadarma Universitykarmila.staff.gunadarma.ac.id/Downloads/files/56606/minimum... · algoritma secara efektif dan efisien Pengambilan jalan tengah yaitu pencarian](https://reader030.vdokumen.com/reader030/viewer/2022020115/5c9d951388c99397348d0074/html5/thumbnails/13.jpg)
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.
![Page 14: Minimum spaning tree - Gunadarma Universitykarmila.staff.gunadarma.ac.id/Downloads/files/56606/minimum... · algoritma secara efektif dan efisien Pengambilan jalan tengah yaitu pencarian](https://reader030.vdokumen.com/reader030/viewer/2022020115/5c9d951388c99397348d0074/html5/thumbnails/14.jpg)
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.
![Page 15: Minimum spaning tree - Gunadarma Universitykarmila.staff.gunadarma.ac.id/Downloads/files/56606/minimum... · algoritma secara efektif dan efisien Pengambilan jalan tengah yaitu pencarian](https://reader030.vdokumen.com/reader030/viewer/2022020115/5c9d951388c99397348d0074/html5/thumbnails/15.jpg)
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.
![Page 16: Minimum spaning tree - Gunadarma Universitykarmila.staff.gunadarma.ac.id/Downloads/files/56606/minimum... · algoritma secara efektif dan efisien Pengambilan jalan tengah yaitu pencarian](https://reader030.vdokumen.com/reader030/viewer/2022020115/5c9d951388c99397348d0074/html5/thumbnails/16.jpg)
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
![Page 17: Minimum spaning tree - Gunadarma Universitykarmila.staff.gunadarma.ac.id/Downloads/files/56606/minimum... · algoritma secara efektif dan efisien Pengambilan jalan tengah yaitu pencarian](https://reader030.vdokumen.com/reader030/viewer/2022020115/5c9d951388c99397348d0074/html5/thumbnails/17.jpg)
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
![Page 18: Minimum spaning tree - Gunadarma Universitykarmila.staff.gunadarma.ac.id/Downloads/files/56606/minimum... · algoritma secara efektif dan efisien Pengambilan jalan tengah yaitu pencarian](https://reader030.vdokumen.com/reader030/viewer/2022020115/5c9d951388c99397348d0074/html5/thumbnails/18.jpg)
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.
![Page 19: Minimum spaning tree - Gunadarma Universitykarmila.staff.gunadarma.ac.id/Downloads/files/56606/minimum... · algoritma secara efektif dan efisien Pengambilan jalan tengah yaitu pencarian](https://reader030.vdokumen.com/reader030/viewer/2022020115/5c9d951388c99397348d0074/html5/thumbnails/19.jpg)
REALISASI ALGORITMA PRIM
10 12
9A
D
B
C
![Page 20: Minimum spaning tree - Gunadarma Universitykarmila.staff.gunadarma.ac.id/Downloads/files/56606/minimum... · algoritma secara efektif dan efisien Pengambilan jalan tengah yaitu pencarian](https://reader030.vdokumen.com/reader030/viewer/2022020115/5c9d951388c99397348d0074/html5/thumbnails/20.jpg)
REALIASI ALGORITMA KRUSKAL
10 12
9A
D
B
C
![Page 21: Minimum spaning tree - Gunadarma Universitykarmila.staff.gunadarma.ac.id/Downloads/files/56606/minimum... · algoritma secara efektif dan efisien Pengambilan jalan tengah yaitu pencarian](https://reader030.vdokumen.com/reader030/viewer/2022020115/5c9d951388c99397348d0074/html5/thumbnails/21.jpg)
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.
![Page 22: Minimum spaning tree - Gunadarma Universitykarmila.staff.gunadarma.ac.id/Downloads/files/56606/minimum... · algoritma secara efektif dan efisien Pengambilan jalan tengah yaitu pencarian](https://reader030.vdokumen.com/reader030/viewer/2022020115/5c9d951388c99397348d0074/html5/thumbnails/22.jpg)
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.
![Page 23: Minimum spaning tree - Gunadarma Universitykarmila.staff.gunadarma.ac.id/Downloads/files/56606/minimum... · algoritma secara efektif dan efisien Pengambilan jalan tengah yaitu pencarian](https://reader030.vdokumen.com/reader030/viewer/2022020115/5c9d951388c99397348d0074/html5/thumbnails/23.jpg)
Jadi perkiraan total waktu
yang dibutuhkan :
Sehingga kompleksitas algoritmanya: O(V2), dengan
V menyatakan banyaknya simpul.
![Page 24: Minimum spaning tree - Gunadarma Universitykarmila.staff.gunadarma.ac.id/Downloads/files/56606/minimum... · algoritma secara efektif dan efisien Pengambilan jalan tengah yaitu pencarian](https://reader030.vdokumen.com/reader030/viewer/2022020115/5c9d951388c99397348d0074/html5/thumbnails/24.jpg)
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.
![Page 25: Minimum spaning tree - Gunadarma Universitykarmila.staff.gunadarma.ac.id/Downloads/files/56606/minimum... · algoritma secara efektif dan efisien Pengambilan jalan tengah yaitu pencarian](https://reader030.vdokumen.com/reader030/viewer/2022020115/5c9d951388c99397348d0074/html5/thumbnails/25.jpg)
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.
![Page 26: Minimum spaning tree - Gunadarma Universitykarmila.staff.gunadarma.ac.id/Downloads/files/56606/minimum... · algoritma secara efektif dan efisien Pengambilan jalan tengah yaitu pencarian](https://reader030.vdokumen.com/reader030/viewer/2022020115/5c9d951388c99397348d0074/html5/thumbnails/26.jpg)
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.