PROBLEMA DAN MODEL GRAPH DALAM METODE GREEDY

PROBLEMA DAN MODEL GRAPH DALAM METODE

GREEDY

A.    TRAVELLING SALESMAN

Untuk menentukan waktu perjalanan seorang salesman seminimal mungkin.

Permasalahan:

Setiap minggu sekali, seorang petugas kantor telepon berkeliling untuk mengumpulkan coin-coin pada telepon umum yang dipasang diberbagai tempat. Berangkat dari kantornya, ia mendatangi satu demi satu telepon umum tersebut dan akhirnya kembali ke kantor lagi. Masalahnya ia menginginkan suatu rute perjalanan dengan waktu minimal.

MODEL GRAPH :

Misalnya : Kantor pusat adalah simpul 1 dan misalnya ada 4 telepon umum, yg kita nyatakan sebagai simpul 2, 3, 4 dan 5 dan bilangan pada tiap-tiap ruas menunjukan waktu ( dalam menit ) perjalanan antara 2 simpul .

Langkah penyelesaian :

1.      Dimulai dari simpul yg diibaratkan sebagai kantor pusat yaitu simpul.

2.      Dari simpul 1 pilih ruas yg memiliki waktu yg minimal.

3.      Lakukan terus pada simpul – simpul yg lainnya tepat satu kali yg nantinya Graph akan membentuk Graph tertutup karena perjalanan akan kembali ke kantor pusat.

4.      Problema diatas menghasilkan waktu minimalnya adalah 45 menit dan diperoleh perjalanan sbb :

 

Problema diatas menghasilkan waktu minimalnya adalah 45 menit dan diperoleh perjalanan sbb :

B.    MINIMUM SPANNING TREE

 

Kasus MST Problem = m’cari minimal biaya (cost) spanning tree dr setiap ruas (edge) graph yg membentuk pohon (tree). Solusi dari permasalahan ini :

a.      Dgn memilih ruas suatu graph yg memenuhi kriteria droptimisasi yg menghasilkan biaya min.

b.      Penambah’ dr setiap ruas pd seluruh ruas yg membentuk graph akan menghasilkan nilai/biaya yg kecil (minimum cost).

 

Kriteria dari spanning tree, yakni :

1.      Setiap ruas pada graph harus terhubung (conected).

2.      Setiap ruas pd graph hrs mpy nilai (label graph).

3.      Setiap ruas pd graph tdk mpy arah (graph tdk berarah)

 

Proses Total minimum cost terbentuknya graph dengan tahapan sbb:

·         Dari graph yg terbentuk, apakah memenuhi kriteria MST.

·         Lakukan secara urut dr simpul ruas awal s/d ruas akhir.

·         Pada setiap simpul ruas perhatikan nilai/cost dr tiap-tiap ruas.

·         Ambil nilai yg paling kecil (jarak tertpendek setiap ruas).

·         Lanjutkan s/d semua simpul ruas tergambar pd spanning tree.

·         Jumlahkan nilai/cost yg dipilih tadi.

 

 

 

 

 

 

 

C.     SHORTEST PATH PROBLEM

Permasalahan: menghitung jalur terpendek dari sebuah graph berarah.

Kriteria utk permasalahan jalur terpendek/SP problem tsb :

1.      Setiap ruas pada graph harus mempunyai nilai (label graph).

2.      Setiap ruas pada graph tidak harus terhubung (unconnected).

3.      Setiap ruas pada graph tersebut harus mempunyai arah (graph berarah).

 

 

 

CONTOH SOAL DAN PEMBAHASAN

1.      Gunakan metode “Traveling Salesman”.

Terdapat 4 kota yaitu A,B,C,D. Jarak antar kotanya sebagai berikut :

·         A ke B = 7

·         A ke C = 5

·         A ke D = 3

·         B ke C = 6

·         B ke D = 6

·         C ke D = 2

Grafnya dapat dilihat dibawah ini:

Buatlah solusi terpendeknya.

Penyelsaian:

Tentukan Jalur mana saja yang ingin dilalui, jalur yang dapat dilalui antar alain:

NO	JALUR	WAKTU TEMPUH	TOTAL
1	A – B – C – D – A	7 + 6 + 2 + 3	18
2	A – B – D – C – A	7 + 6 + 2 + 5	20
3	A – C – B – D – A	5 + 6 + 6 + 3	20
4	A – C – D – B – A	5 + 6 + 2 + 7	20
5	A – D – B – C – A	3 + 6 + 6 + 5	20
6	A – D – C – B – A	3 + 2 + 6 + 7	18

                                                                                                                                     

Jadi, untuk menempuh rute tercepat yaitu pada no/rute 1 dan rute 6.

2.      Buatlah minimum Spanning Tree (MST) dan Nilai bobotnya dari Graf berikut ini dengan menggunakan algoritma Solin dan Kruskal.

Graf G:

Penyelsaian :

a.         Algoritma Solin

1)      Urutkan ruas Graf G menurut bobotnya dari yang terbesar.

 

 

2)      Lakukan penghapusasan masing-masing ruas yang tidak menyebakan graf menjadi terhubung atau membentuk sirkuit dari bobot terbesar.

·         Bobot 10 EF dan EG

 

 

Ruas EF dan EG tidak dihapus karena kedua ruas tersebut menyebabkan graf terhubung.

 

·         Bobot 9 BE dan EI

 

 

Ruas BF dan EI tidak dihapus karena kedua ruas tersebut menyebabkan graf terhubung.

 

·         Bobot 8 DE dan EH

 

 

Ruas DE dan EH tidak dihapus karena kedua ruas tersebut menyebabkan graf terhubung.

 

·         Bobot 7 CF, GJ  dan IJ

 

 

Ruas IJ dihapus karena akan membentuk sirkuit EIJGE.

Ruas CF dan GJ tidak dihapus karena kedua ruas tersebut menyebabkan graf terhubung.

 

·         Bobot 6 DF, GH dan HJ

 

 

Ruas DF, GH dan HJ dihapus karena akan membentuk sirkuit DEFD, EGHE, HIJH.

 

·         Bobot 5 AB dan AC

 

 

Ruas AC dihapus karena akan membentuk sirkuit ABEGFCA.

Ruas AB tidak dihapus karena ruas tersebut menyebabkan graf terhubung.

 

·         Bobot 4 BD, CD dan HI

 

 

Ruas BC, CD dan HI  dihapus karena akan membentuk sirkuit BDEB, CDEFC, EHIE, HIJH.

 

·         Bobot 3 FG

 

 

Ruas FG dihapus karena akan membentuk sirkuit EFGE.

 

Tahap penghapusan selsai, gambar diatas adalah Minimum Spnning Tree dari Graf G denagan Bobot = 73

 

b.         Algoritma Kruskal

1)      Pertama kita buat Garf G hanya terdiri dari Simpul saja.

 

 

2)      Urutkan ruas dari bobot terkecil ( FG, BD, CD, HI, AB, AC, DF, GH, HJ, CF, GJ, J, DE, EH, BE, EI, EF dan EG). Kemudian sesuai urutan tersebut tambahkan ruas dengan mencegah terbentuknya sirkuit.

 

Penambahan ruas FG.

 

 

Penambahan ruas BD, CD dan HI.

 

 

Penambahan ruas AB. Penambahan ruas AC tidak dilakukan karena akan membentuk sirkuit.

 

 

Penambahan ruas DF, GH dan HJ.

 

 

Penambahan ruas CF, GJ IJ tidak dilakukan karena akan membentuk sirkuit.

 

 

Penambahan ruas DE,EH tidak dilakukan karena akan membentuk sirkuit.

 

 

Penambahan ruas BE, EI tidak dilakukan karena akan membentuk sirkuit.

 

 

Penambahan ruas EF dan Eg tidak dilakukan karena akan membentuk sirkuit.

 

 

Selesai. MST Graf G dengan nilai bobot = 38