Analisis Algoritma Pemrograman Greedy

Algoritma Greedy adalah salah satu jenis algoritma, algoritma greedy menggunakan pendekatan penyelesaian masalah dengan mencari nilai maksimum sementara dalam setiap langkahnya atau local maxium.

Algoritma greedy biasanya memberikan solusi yang mendekati nilai optimum dalam waktu yang cukup cepat.

Disini Akan di Paparkan berbagai Macam Metode penyelesaian yang ada pada Algoritma Greedy. Yaitu Metode Traveling Salesman, Algoritma Solin dan Kruskal, dan yang terakhir Dijkstra’s Algoritma (Algoritma Dijkstra) 

a. Travelling Salesman Problem

Travelling Salesman Problem (TSP) adalah pencarian rute terpendek atau jarak minimum oleh seorang salesman dari suatu kota ke n-kota tepat satu kali dan kembali ke kota awal keberangkatan. TSP dapat diterapkan pada graph komplit berbobot yang memiliki total bobot sisi minimum, dimana bobot pada sisi adalah jarak. Rute TSP ini memuat semua titik pada graph tersebut tepat satu kali.

Berikut contoh soal

Gunakan Metode Traveling Salesman. Terdapat 4 kota yaitu ABCD

Jarak antar kota A,B,C dan D sebagai berikut :

Jarak A ke B = 7, A ke C = 5, A ke D = 3, B ke C = 6, B ke D = 6, dan C ke D = 2.

Kota Pusat A

Dan buatlah solusi untuk jalur terpendeknya

 Langkah Penyelesaian  :

1.   Dimulai dari simpul pertama sebagai kota pusatnya yaitu kota A

2.   Dari kota A tersebut pilih lah kota yang memiliki jarak minimalnya yaitu kota D

3.   Setelah kota D, yang memiliki jarak minimal berikutnya yaitu kota C

4.   Dari kota C berlanjut pada kota terakhir adalah B

5.   Jika ke tiga kota telah dilalui akan kembali ke kota pusatnya.

Problema diatas menghasilkan waktu minimalnya adalah 18

Menghasilkan jarak minimal 18 dengan perjalanan sebagai berikut:

b. Algoritma Solin dan Kruskal

Buatlah Minimum Spanning Tree (MST) dan Nilai Bobotnya dari Graf   berikut ini dengan menggunakan Algoritma Solin dan Kruskal

BOBOT	RUAS
10	E.F	E.G
9	B.E	E.I
8	E.D	E.H
7	C.F	G.J	I.J
6	D.F	G.H	H.J
5	A.B	A.C
4	B.D	C.D	H.I
3	F.G

 Solin

1.Bobot 10 = (E,F) dan (E,G)

Ruas E,F dan E,G tidak dihapus karna kedua ruas tersebut menyebabkan graf terhubung

2.Bobot 9 = (B,E) dan (E,I)

Ruas B,E dan E,I dihapus karna membentuk sirkuit B,D,E,B dan E,H, I, E

3.Bobot 8 = (D,E) dan (E,H)

Ruas D,E dan E,H dihapus karena membentuk sirkuit D,E,F,D dan E, G,H,E

4.Bobot 7 = (C,F) (G,J) dan (I,J)

Ruas C,F dan G,J dihapus karena membentuk sirkuit C,D,F,C dan G,H,J,G

Ruas I,J tidak dihapus karena menghubungkan I dan J

5.Bobot 6 = (D,F) (G,H) (H,J)

Ruas D,F dan G,H tidak dihapus

Ruas H,J dihapus karena membentuk sirkuit H,I,J,H

 6.Bobot 5 = (A,B) (A,C)

Ruas A,B tidak dihapus

Ruas A,C dihapus karena membentuk sirkuit A,B,D,C,A

7.Bobot 4 = (B,D) (C,D) (H,I)

Ruas BD,CD, dan HI tidak dihapus karena menyebabkan grafik terhubung

8.Bobot 3 = F,G

Ruas F,G dihapus karena membentuk sirkuit E,F,G,E

Jadi tahap penghapusan selesai, gambar no 8 adalah Spanning Tree dari Graf G dengan nilai Bobot 56.

KRUSKAL

Pertama buat titik penghubung yang sesuai dengan jumlah titik pada gambar,

(F,G) (B,D) (C,D) (H,I) (A,B) (A,C)

(D,F) (G,H) (H,J) (C,F) (G,J) (I,J)

(D,E) (E,H) (B,E) (E,I) (E,F) (E,G)

Urutkan ruas mulai dari nilai yang terkecil ke yang terbesar,lalu hubungkan setiap ruas dengan mencegah adanya sirkuit (penghubung). 

c. Dijkstra’s Algoritma (Algoritma Dijkstra)