20penyelesaian dengan algoritma

7/24/2019 20Penyelesaian Dengan Algoritma

1/24

PERTEMUAN 13

Penyelesaian Dengan Algoritma

Pemrograman Greedy


2/24

Penyelesaian Dengan Algoritma Pemrograman Greedy

Algoritma GREEDY KNAPSACK.

PROCEDURE GREEDY KNAPSACK ( W, x, n)

float W[n], x[n], M, isi;

Int i, n;

x(1 : 1) 0 ; isi M ;

FOR i 1 TO n

{IF W[i] > M ; EXIT ENDIF

x[i] 1

isi

isi W[i]}

IF i n ; x[i] isi / W[i] ENDIF

END_GREEDY KNAPSACK


3/24

Algoritma Pemrograman Greedy (Lanjutan)

Efektif jk data (Pi/Wi) disusun scr non decreasingdahulu.

Penyelesaiannya : Dengan Algoritma Prg. Greedy.

Diket. bhw kapasitas M = 20kg, dgn jmlh brg n=3

Berat Wi masing2 brg = (W1, W2, W3) = (18, 15, 10)

Nilai Pi masing2 brg = (P1, P2, P3) = (25, 24, 15)

Lakuk purutan scr tdk naik thdp hasil Pi/Wi, misalnya :

P1/Wi 25/18 = 1,39 menjadi urutan ke 3

P2/W2 24/15 = 1,60 menjadi urutan ke 1P3/W3 15/10 = 1.50 menjadi urutan ke 2

Sehingga mhasilk pola urutan data yg baru,yaitu

W1,W2,W3 15, 10, 18 dan P1,P2,P3 24, 15, 25


4/24

Algoritma Pemrograman Greedy (Lanjutan)

Lalu data2

tsb diinputk pd Alg. Greedy, terjadi proses :

x(1:n) 0 ; isi 20 ; i = 1

W(i) > isi ? 15 > 20 ? kondisi SALAH

x(1) = 1 barti bhw brg tsb dpt dimuat seluruhnya.

Isi = 20 - 15 kapasitas ransel bkurang dgn sisa 5kgi =2

W(2) > isi ?? 10 > 5 ?? kondisi BENARx(2)=5/10=1/2benda 10kg hanya dpt dimuat 1/2 bgn

yaitu 5 kg.

i=3

Endif diakhiri krn ransel sdh penuh (max =20kg)

Profit nilai yang didapat adalah : P1 + P2 + P3 yaitu:

24.1+ 15.1/2 + 18.0 = 24 + 7.5 = 31.5


5/24

PROBLEMA DAN MODEL GRAPH DALAMMETODE GREEDY

1. TRAVELLING SALESMAN

Untuk menentukan waktu perjalanan seorang salesman

seminimal mungkin.Permasalahan:

Setiap minggu sekali, seorang petugas kantor telepon

berkeliling untuk mengumpulkan coin-coin pada teleponumum yang dipasang diberbagai tempat. Berangkat darikantornya, ia mendatangi satu demi satu telepon umumtersebut dan akhirnya kembali ke kantor lagi. Masalahnya

ia menginginkan suatu rute perjalanan dengan waktuminimal.


6/24

MODEL GRAPH TRAVELLING SALESMAN

Misalnya :Kantor pusat adalah simpul 1 dan misalnya ada 4 teleponumum, yg kita nyatakan sebagai simpul 2, 3, 4 dan 5 dan

bilangan pada tiap-tiap ruas menunjukan waktu ( dalammenit ) perjalanan antara 2 simpul .

5

34

1 2

8 107

1112

119

9

10

8


7/24

Langkah penyelesaian Model GraphTRAVELLING SALESMAN

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

45 menit dan diperoleh perjalanan sbb :


8/24

Langkah penyelesaian Model Graph

TRAVELLING SALESMAN (Lanjutan)

Problema diatas menghasilkan waktu minimalnya adalah45 menit dan diperoleh perjalanan sbb :

1

5

4 3

2

7

812

10

8


9/24

2. MINIMUM SPANNING TREE

Kasus MST Problem = mcari min.biaya (cost) spanningtree dr setiap ruas (edge) graph yg mbtk pohon (tree).

Solusi dr pmasalah ini :

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

b. Penambah dr setiap ruas pd seluruh ruas yg mbtkgraph akan mhasilk nilai/biaya yg kecil (minimumcost).

Kriteria2 dr 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)


10/24

MINIMUM SPANNING TREE (Lanjutan)

Proses Total minimum costterbentuknya graph dgn

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-tiapruas

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.


11/24

Permasalahan MINIMUM SPANNING TREE

Tentukanlah nilai Minimum Spanning Tree dari Graph Zdibawah ini, dengan menentukan ruas (edge) yang

membentuknya.

1 2

4 3

5

6

10

30

20

55

40

35

15

5045

25


12/24

Penyelesaian MINIMUM SPANNING TREE

Perhatikan Kriteria dari MST, yaitu:

1. Graph Z sudah merupakan graph terhubung

2. Graph Z merupakan graph yang tidak berarah3. Masing-masing ruasnya mempunyai label

Menghitung MST dari tiap-tiap ruas yang membentuk

graph tersebut dengan cara:a. Dilakukan secara urut dari ruas/edge pertama

sampai dengan edge terakhir.

b. Setiap ruas/edge harus digambarkan pada spanning

tree yang terbentuk.


13/24

Tahapan Proses Penyelesaian dari edge (ruas),

Cost(biaya) dan spanning tree

Edge (Ruas) Cost (Biaya) Spanning Tree

(1,2) 10

(2,6) (25)

1 2

1 2

6


14/24

Tabel Lanjutan Proses Penyelesaian dari edge(ruas), Cost(biaya) dan spanning tree


(3,6) 15

(4,6) 20

1 2

63

1 2

63

4


15/24

Tabel Lanjutan Proses Penyelesaian dari edge

(ruas), Cost(biaya) dan spanning tree


(3,5) 35

Total Cost 105

1 2

63

45


16/24

3. SHORTEST PATH PROBLEM

Permasalahan : Menghitung jalur terpendek dr sbh graphberarah.

Kriteria utk permasalahan jalur terpendek/SP problem tsb :1. Setiap ruas pd graph hrs mpy nilai (label graph)

2. Setiap ruas pd graph tdk hrs terhubung (unconnected)3. Setiap ruas pd graph tsb hrs mempunyai arah (graph

berarah).

A B E

C D F

45

20

15

10 15 20 35

1050

30

3


17/24

Proses SHORTEST PATH PROBLEM

1. Hitung jarak satu per satu sesuai dengan arah yangditunjukkan oleh tiap-tiap ruas.

2. Perhitungan dilakukan terhadap ruas graph yangmemiliki jalur awal dan akhir.

A B E

C D F

45

20

15

10 15 20 35

1050

30

3


18/24

Penyelesaian SHORTEST PATH PROBLEM

Pertama: Melihat proses simpul yang mempunyai awal

dan akhir tujuan dari graph, yaitu:

A B, A C, A D, A E

Kedua: Mencari jalur terpendek dari tiap-tiap proseskeempat jalur tersebut dengan menghitung

panjang tiap-tiap jalur.


19/24

Langkah 1 Penyelesaian SHORTEST PATH PROBLEM

Jalur A - B

A B = 50

A C D B = 10 + 15 + 20 = 45 A E D B = 45 + 30 + 20 = 95

Jalur terpendek untuk simpul A tujuan B adalah:

A C D B = 45


20/24


Jalur A - C

A C = 10

A B C = 50 + 15 = 65 A B E D B C = 50 + 10 + 30 + 20 + 15 = 125

A E D B C = 45 +30 +20 + 15 = 110

Jalur terpendek untuk simpul A tujuan C adalah:

A C = 10


21/24


Jalur A - D

A C D = 10 + 15 = 25

A B E D = 50 + 10 + 30 = 90 A B C D = 50 + 15 + 15 = 80

A E D = 45 + 30 = 75

Jalur terpendek untuk simpul A tujuan D adalah:

A C D = 25


22/24


Jalur A - E

A E = 45

A B E = 50 + 10 = 60 A C D B E = 10 + 15 + 30 + 10 = 65

A C D E = 10 + 15 + 35 = 60

Jalur terpendek untuk simpul A tujuan E adalah

A E = 45


23/24

Tabel Jalur SHORTEST PATH PROBLEM

Jalur Panjang jarak

A C 10A C D 25

A C D B 45

A E 45


24/24

Latihan

Buatlah Shortest Path Problem untuk graph dibawah ini.

25

A B

E D

C

45

15 10

55

5

35

20

20penyelesaian dengan algoritma

Documents