PROBLEMA DAN MODEL GRAPH DALAM METODE GREEDY
Contoh:
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 .
Tentukan model graph dengan waktu perjalanan seminimal mungkin.
Jawab:
Langkah penyelesaian :
1. Dimulai dari simpul yg diibaratkan sebagai
kantor pusat yaitu simpul 1 .
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 39 menit dan diperoleh
perjalanan sbb :
Dimulai dari simpul 1, kemudian berjalan ke simpul 4, kemudian berjalan lagi ke simpul 5, kemudian bejalan lagi ke simpul 3, kemudian berjalan lagi ke simpul 2, dan berjalan lagi untuk kembali ke simpul 1. 1 ke 4 ke 5 ke 3 ke 2 ke 1 = 6+4+9+8+12 = 39
MODEL GRAPH :
