jangan d buka

PERTEMUAN 9

LARIK ATAU

ARRAY

LARIK ATAU ARRAY

adalah tipe terstruktur yang terdiri dari

sejumlah komponen yang mempunyai

tipe data yang sama.

Variabel Array terdiri dari :

1. Array Berdimensi Satu

2. Array Berdimensi Dua

1. Array Berdimensi Satu

Bentuk Umum :

Tipe_Data Nama_Variabel [ukuran]

Contoh:

int nilai [6];

jumlah elemen

nama array

tipe data elemen array

2. Array Berdimensi Dua

Bentuk Umum :

Tipe_Data Nama_Variabel [index-1] [index-2]

Contoh:

int nilai [2] [3] ;

jumlah kolom

jumlah baris

nama array

tipe data elemen array

Contoh I :

int i, j ;

int tabel [3] [2] ;

for (i=0; i<=2 ; i++)

{

for (j=0; j<=1 ; j++)

{

cout<< “data ke - ”<< i << j<<endl;

cout<< “nilai =“ ;

cin>> tabel [ i ] [ j ];

}

}

Hasil Tabel

Tabel[0][0] Tabel[0][1]

Tabel[1][0] Tabel[1][1]

Tabel[2][0] Tabel[2][1]

Contoh II :

Diberikan matriks A sebagai berikut :

1 1 1 1

0 1 1 1

0 0 1 1

0 0 0 1

Perintah pokok yg digunakan pd pengisian

matriks A adalah :

A[i,j] = 1, jika i <=j , A[i,j] = 0, jika i > j

1. Diberikan matriks A sebagai berikut :

1 2 3 4

0 2 3 4

0 0 3 4

0 0 0 4

Latihan :

Perintah pokok yg digunakan pd pengisian

matriks A adalah :

2. Diberikan matriks A sebagai berikut :

1 0 0 0

2 2 0 0

3 3 3 0

4 4 4 4

Perintah pokok yg digunakan pd pengisian

matriks A adalah .

3. Diberikan matriks A sebagai berikut :

1 0 0 0

0 1 0 0

0 0 1 0

0 0 0 1

Perintah pokok yg digunakan pd pengisian

matriks A adalah :

4. Diberikan algoritma sbb :

int i ;

int nilai[4];

for(i=0;i<=3;i++)

{

a[i] = 2 * i + 1;

cout<<a[i];

}

Algoritma di atas akan menghasilkan nilai .....

5. Diberikan algoritma sbb, diketahui nilai dari array

x[0]=10, x[1]=12, x[2]=12, x[3]=10 dan y[0]=2, y[1]=3,

y[2]=4, y[3]=5

int i;

int x[4], y[4];

float hasil ;

hasil=0;

for(i=0; i<=3; i++)

hasil = hasil + x[i] / y[i];

cout<<“hasil=“<<hasil;

Maka nilai hasil dari algoritma diatas adalah......

Tugas Kelompok (max 5 orang)

Buatlah program dengan menggunakan C++

1. Penjumlahan dua buah matriks

2. Pengurangan dua buah matriks

Ket :

Masing-masing kelompok dapat memilih salah satu dari

program di atas.

Listing program & output dicetak

Nama, Nim dan Kelas dicetak di listing program

PERTEMUAN 10

METODE DEVIDE AND

CONQUER

Bentuk Umum Proses Metode D And C dpt

dilihat sbb :

n input I

n input

n input II n input III n input K

Subproblem I

Subsolusi I

Solusi Optimal

Subsolusi II Subsolusi III Subsolusi K

Subprob. II Subprob. III Subprob. K

1. Metode Selection Sort

2. Metode Buble Sort

3. Metode Merge Sort

4. Metode Quick Sort

SORTING

5. Metode Insertion.

Hal yg mempengaruhi Kecepatan Algoritma Sort :

Jumlah Operasi Perbandingan & Jumlah Operasi

Pemindahan Data

Tehnik pengurutan dgn cara pemilihan elemen

atau proses kerja dgn memilih elemen data

terkecil utk kemudian dibandingkan &

SELECTION SORT

ditukarkan dgn elemen pd data awal, dst s/d

seluruh elemen shg akan menghasilkan pola

data yg telah disort.

Prinsip Kerja dari Teknik Selection Sort ini

adalah :

1. Pengecekan dimulai data ke-1 sampai

dengan data ke-n

2. Tentukan bilangan dengan Index terkecil

dari data bilangan tersebut

3. Tukar bilangan dengan Index terkecil

tersebut dengan bilangan pertama ( I = 1 )

dari data bilangan tersebut

4. Lakukan langkah 2 dan 3 untuk bilangan

berikutnya ( I= I+1 ) sampai didapatkan

urutan yg optimal.

Contoh : 22 10 15 3 8 2

Iterasi 1

1 2 3 4 5

6

Langkah 1: 22 10 15 3 8 2

Langkah 2 : 22 10 15 3 8

2

Langkah 3 : 2 10 15 3 8 22

Langkah 4 : Ulangi langkah 2 dan 3 .

Iterasi 2

Langkah 1: 2 10 15 3 8 22

Langkah 2: 2 10 15 3 8 22

Langkah 3: 2 3 15 10 8 22

Langkah 4: Ulangi langkah 2 dan 3 .

Lakukan Iterasi selanjutnya sampai iterasi

ke-6

BUBBLE SORT

Tehnik Sort yg bekerja dgn menggunakan prinsip

gelembung (bubble) udara yg akan bergerak

naik ke atas secara satuper satu.

Prinsip Kerja dari Bubble Sort adalah :

1. Pengecekan mulai dari data ke-1 sampai data

ke-n

2. Bandingkan data ke-n dengan data sebelumnya

(n-1)

3. Jika lebih kecil maka pindahkan bilangan

tersebut dengan bilangan yg ada didepannya

( sebelumnya ) satu persatu (n-1,n-2,n-3,....dst)

4. Jika lebih besar maka tidak terjadi pemindahan

5. Ulangi langkah 2 dan 3 s/d sort optimal.

Contoh : 22 10 15 3 8 2

terasi 1

1 2 3 4 5 6

Langkah 1: 22 10 15 3 8 2

Langkah 2: 22 10 15 3 8 2

Langkah 3: 22 10 15 3 2 8

Langkah 4: Ulangi langkah 2 dan 3

Hasil iterasi 1 : 2 22 10 15 3 8

Iterasi 2

Langkah 1: 2 22 10 15 3 8

Langkah 2: 2 22 10 15 3 8

- 8>3, maka 8 tidak pindah,

untuk selanjutnya bandingkan

data sebelunya yaitu 3.

Langkah 3: 2 22 10 3 15 8

Langkah 4: Ulangi langkah 2 dan 3

Hasil Iterasi 2 : 2 3 22 10 15 8

Lakukan Iterasi selanjutnya sampai iterasi ke- 6

Quick Short

merupakan suatu algoritma pengurutan data yang

mempergunakan teknik pemecahan data menjadi partisi-partisi.

Suatu metode pengurutan yang membandingkan suatu elemen

(pivot) dengan elemen yang lain dan menyusunnya sedemikian

rupa sehingga elemen yang lain yang lebih kecil daripada pivot

terletak disebelah kiri pivot sedangkan elemen yang lebih besar

dari pivot diletakkan di sebelah kanan pivot.

Prinsip Kerjanya adalah:

1. pertama-tama tentukan sebuah elemen dipilih dari data yang akan

diurutkan. Elemen tersebut dikatakan sebagai variabel sementara,

sehingga nilai variabel sementara berada di suatu posisi ke I yang

memenuhi kondisi sebagai berikut:

2. Semua elemen di posisi ke-1 sampai dengan ke I-1 adalah

lebih kecil atau sama dengan Sementara.

3. Semua elemen di Posisi ke I+1 sampai dengan ke N adalah

lebih besar atau sama dengan Sementara.

Contoh:

33 45 18 7 5 99 57 25 55 10 40

Misal elemen yang dipilih adalah elemen yang pertama, yaitu 33. Maka hasil

sementara adalah sebagai berikut:

10 25 18 7 5 33 57 99 55 45 40

Tampak kondisi berikut terpenuhi, yaitu:

Semua elemen di posisi ke 1 sampai ke 5 adalah 10, 25,

18, 7, dan 5 (lebih kecil dari 33).

Semua elemen di posisi ke 7 sampai dengan 11 adalah 57,

99, 55, 45, dan 40 (lebih besar atau sama dengan 33).

Dengan demikian data tersebut akan terpecah menjadi 2

partisi, yaitu:

(10 25 18 7 5) 33 (57 99 55 45 40)

Proses ini diulangi untuk masing-masing partisi data. Untuk

partisi yang pertama bila nilai Sementara yang diambil

adalah data pertama kembali dalam partisi yang

bersangkutan, yaitu 10 dan diatur kembali sedemikian

rupa, maka nilai data yang dipilih akan terletak di posisi

sebagai berikut:

(5 7) 10 (18 25) 33 (57 99 55

45 40)

INSERTION SORT

Prinsip dasar Insertion adalah secara berulang-ulang

menyisipkan / memasukan setiap elemen. ke dlm

posisinya / tempatnya yg benar.

1. Prinsip Kerja Insertion Sort adalah

2. Pengecekan mulai dari data ke-1 sampai data

ke-n

3. Bandingkan data ke-I ( I = data ke-2 s/d data ke-n

)

4. Bandingkan data ke-I tersebut dengan data

sebelumnya (I-1), Jika lebih kecil maka data

tersebut dapat disisipkan ke data awal sesuai

dgn posisisi yg seharusnya

5. Lakukan langkah 2 dan 3 untuk bilangan

berikutnya ( I= I+1 ) sampai didapatkan urutan yg

optimal.

Contoh : 22 10 15 3 8 2

Iterasi 1

1 2 3 4 5 6

Langkah 1: 22 10 15 3 8 2

Langkah 2: 22 10 15 3 8 2

Langkah 3: 10 22 15 3 8 2

Langkah 4: Ulangi langkah 2 dan 3

Iterasi 2

Langkah 1: 10 22 15 3 8 2

Langkah 2: 10 22 15 3 8 2

Langkah 3: 10 15 22 3 8 2

Langkah 4: Ulangi langkah 2 dan 3

Lakukan Iterasi selanjutnya sampai iterasi

ke- 6

Catatan : Setiap ada pemindahan, maka elemen.

Yang sudah ada akan di insert sehingga akan

bergeser kebelakang.

Prinsip Kerja Merge Sort adalah :

Kelompokan deret bilangan kedalam 2 bagian, 4

bagian, 8 bagian, ......dst _ (2n)

Urutkan secara langsung bilangan dalam

MERGE SORT

kelompok tsb.

Lakukan langkah diatas untuk kondisi bilangan yg

lain sampai didapatkan urutan yg optimal .

Contoh : 22 10 15 3 8 2

Iterasi 1

1 2 3 4 5 6

Langkah 1: 22 10 15 3 8 2

Langkah 2: 10 22 3 15 2 8

Iterasi 2

Langkah 1: 10 22 3 15 2 8

Langkah 2: 3 10 15 22 2 8

Iterasi 3

Langkah 1:3 10 15 22 2 8

Langkah 2:2 3 8 10 15 22

Contoh : 22 10 15 3 8 2

Iterasi 1

1 2 3 4 5 6

Langkah 1: 22 10 15 3 8 2

Langkah 2: 10 22 3 15 2 8

Iterasi 2

Langkah 1: 10 22 3 15 2 8

Langkah 2: 3 10 15 22 2 8

Iterasi 3

Langkah 1:3 10 15 22 2 8

Langkah 2:2 3 8 10 15 22

PERTEMUAN 11

TEHNIK SEARCHING

1. Tehnik Pencarian Tunggal :

a. Tehnik Sequential Search / Linier Search

TEHNIK SEARCHING

Tehnik Pencarian :

b. Tehnik Binary Search

2. Tehnik Pencarian Nilai MAXMIN :

a. Tehnik StraitMAXMIN

b. Tehnik D and C

1. Tehnik Pencarian Tunggal :

a. Linear/Sequential Search ( Untuk data yg belum

terurut / yg sudah terurut )

Pencarian yg dimulai dari record-1 diteruskan ke

record selanjutnya yaitu record-2, ke-3,..., sampai

diperoleh isi record sama dengan informasi yg

dicari

Algoritma :

1. Tentukan I = 1

2. Ketika Nilai (I) <> X Maka Tambahkan I = I +1

3. Ulangi langkah No. 2 sampai Nilai(I) = X

4.Jika Nilai (I) = N+1 Maka Cetak “Pencarian Gagal” selain

itu Cetak “ Pencarian Sukses “

b. Binary Search ( Untuk data yg sudah

terurut )

Digunakan mencari sebuah data pd himp.datadata

data yg tersusun secara urut, yaitu data yg telah

diurutkan dr besar ke kecil/sebaliknya. Proses

dilaksanakan pertama kali pd bgn tengah dr

elemen himpunan, jk data yg dicari ternyata <

elemen bagian atasnya, maka pencarian

dilakukan dr bagian tengah ke bawah.

1. Low = 1 , High = N

2. Ketika Low <= High Maka kerjakan langkah No .3, Jika

tidak Maka kerjakan langkah No.7

3. Tentukan Nilai Tengah dengan rumus

Algoritma :

mid = ( Low + High ) Div 2

4. Jika X < Nil. Tengah Maka High = Mid –1

5. Jika X > Nil. Tengah Maka Low = Mid +1

6. Jika X = Nil. Tengah Maka Nil. Tengah = Nil. Yg dicari

7. Jika X > High Maka Pencarian GAGAL

2. Tehnik Pencarian MAXMIN

Searcing dengan Tehnik STRAITMAXMIN

Menentukan / mencari elemen max & min. Pada

Himpunan yg berbentuk array linear. Waktu

tempuh/time complexity yg digunakan untuk

menyelesaikan pencarian hingga mendapatkan

solusi yg optimal terbagi atas best case,average

case dan worst case.

Algoritma untuk mencari elemen MaxMin :

PROCEDURE STRAITMAXMIN(A,n,i,max,min)

int i,n, A [n], max,min

max _ min _A[0]

FOR i _1 To n

IF A[i] > max; max _A[i];

ELSE IF A[i] < min ; min _A[i] ENDIF

ENDIF

REPEAT

END STRAITMAXMIN

BEST CASE

• Keadaan yg tercapai jika elemen pada himpunan

A disusun secara increasing (menaik). Dengan

perbandingan waktu n - 1 kali satuan operasi.

• Contoh : Terdapat himp.A yg berisi 4 buah

bilangan telah disusun secara increasing dengan

A[0] = 2, A[1] = 4, A[2]=5, A[3]=10. Tentukan /

cari Bilangan Max&Min serta jumlah operasi

perbandingan yg dilakukan.

Penyelesaian

untuk masalah tersebut dapat digunakan procedure

STRAITMAXMIN yg menghasilkan

bilangan Min=2 & bilangan Max=10,

Operasi perbandingan data mencari bilangan

MaxMin dari himpunan tersebut (n-1) =3 kali

operasi perbandingan.

WORST CASE

• Terjadi jika elemen dalam himp. disusun

secara decreasing (menurun). Dengan.

Oprasi perbandingan sebanyak 2(n-1) kali

satuan operasi.

• Contoh : Mencari elemen MaxMin & jumlah

oprasi perbandingan yg dilakukan terhadap

himp.A yg disusun decreasing.

A[0]=80, A[1]=21, A[2]=6, A[3]=-10

Penyelesaian

untuk masalah tersebut dengan proses

STRAITMAXMIN adalah elemen max=80 &

elemen min=-10, Operasi. perbandingan

untuk elemen Maxmin tersebut adalah 2(4-1)

= 6 kali satuan operasi.

AVERAGE CASE

• Jika pencarian elemen MaxMin dilakukan pada

elemen dalam himpunan yg tersusun secara acak

(tidak decreasing/tidak increasing). Jumlah oprasi.

Perbandingan yg dilakukan adalah rata-rata waktu

tempuh best case & worst case, yaitu ½ [ (n-1) +

2(n-1) ] = ( 3n/2 -1 ) kali.

• Contoh, Pada himpuan A yg berisi { 5,-4, 9,7 }

dilakukan pencarian elemen max & min dengan

menggunakan proses STRAITMAXMIN. Berapa

elemen maxmin yg didapatkan & jumlah oprasi

perbandingan yg dilakukan.

Penyelesaiannya :

Elemen max=9, & elemen min=-4. Jumlah

operasi perbandingan adalah ( 3. 4/2 - 1) = 5

kali satuan operasi.

Searching dengan Tehnik DANDC

• Dengan Prinsip Dasar Metode Devide & akan

dapat dipecahkan suatu permasalahan

proses Searching elemen Max&Min dengan

teknik DANC

• Contoh : Tentukan elemen MaxMin suatu

array A yg terdiri 9 bil. :

A[1] = 22, A[4] = -8, A[7] = 17

A[2] = 13, A[5] = 15, A[8] = 31

A[3] = -5, A[6] = 60, A[9] = 47

Penyelesaian :

1,5

1,9

6,9

4,5

1,2 3,3

1,3 6,7 8,9

Lalu Proses tree call dr setiap elemen yg ditunjuk pada

bagan tree tersebut diatas. Dengan cara, membalik

terlebih dahulu posisi tree dr bawah ke atas. Lalu

mengisinya dengan elemen-elemnnya sesuai dengan

bagan tree. Perhatikan bagan tree call ini :

1,2 22,13 3,3 -5,-5

1,3 22,-5 4,5 -8,15 6,7 60,17

1,5 22,-8

6,9 60,17

1,9 60,-8

8,9 31,47

PERTEMUAN 12

METODE GREEDY

Untuk mendapatkan solusi optimal dr

permasalahan yg mempunyai dua kriteria

yaitu Fungsi Tujuan/Utama & nilai

pembatas (constrain)

METODE GREEDY

Proses Kerja Metode Greedy :

Untuk menyeselesaikan suatu permasalahan dgn n input

data yg terdiri dari beberapa fungsi pembatas & 1 fungsi

tujuan yg diselesaikan dgn memilih beberapa solusi yg

mungkin (feasible solution/feasible sets), yaitu bila telah

memenuhi fungsi tujuan/obyektif.

Metode GREEDY digunakan dlm

penyelesaian masalah - masalah :

1. Optimal On Tape Storage Problem

2. Knapsack Problem

3. Minimum Spanning Tree Problem

4. Shortest Path Problem.

1. Optimal Storage On Tapes Problem

Permasalahan Bagamana mengoptimalisasi

storage/memory dalam komputer agar data yg

disimpan dapat termuat dgn optimal.

Misalkan terdapat n program. yg akan disimpan

didalam pita (tape).Pita tsb mempunyai panjang

maks. sebesar L, masing2 prg. yg akan disimpan

mempunyai panjang L1,L2,L3 ...,Ln. Cara

penyimpanan adalah penyimpanan secara terurut

(sequential).

Persoalan = Bagamana susunan penyimpanan

program2 tersebut sehingga

L1 + L2 + L3 + ... + Ln = L ?

L1 L2 L3 . . . Ln

Pemecahannya = jika program.2 tersebut disimpan

dlm Order, dimisalkan adalah Order I, yaitu : j

sama dengan S tik maka akan didapat

k=1

n

Mean Retrieval Time (MRT) = S tj /n

j=1

n j

dan Optimal Storage = D(I) = S S lik

j=1 k=1

Contoh,

Misal terdapat 3 buah prg.(n=3) yg masing2

mpy panjang prg. (I1,I2,I3)=(5,10,3). Tentukan

urutan penyimpanannya scr berurutan

(sequential) agar optimal....!

Penyelesaiannya :

Dari 3 program tersebut akan didapat 6 buah

kemungkinan order, yg didapat dr nilai faktorial

3_3! (ingat faktorial n!).

ORDERING D ( I )

1,2,3 5 + (5+10) + (5+10+3) = 38

1,3,2 5 + (5+3) + (5+3+10) = 31

2,1,3 10 + (10+5) + (10+5+3) = 43

2,3,1 10 + (10+3) + (10+3+5) = 41

3,1,2 3 + (3+5) + (3+5+10) = 29

3,2,1 3 + (3+10) + (3+10+5) = 34

Dari tabel tersebut, didapat Susunan /

order yg optimal,sbb :

susunan pertama untuk program ke tiga

susunan kedua untuk program kesatu

susunan ketiga untuk program kedua

METODE GREEDY (lanjutan)

2. KNAPSACK Problem

Kasus : Terdapat n obyek (Xi;i=1,2,3,....n) yang

masing-masing mempunyai berat (weight)/ Wi &

masing-masing memiliki nilai (profit)/Pi yg berbedabeda.

Masalah :

Bagamana obyek-obyek tersebut dimuat /

dimasukan kedalam ransel (knapsack) yg mempunyai

kapasitas maks. = M. Sehingga timbul permasalahan

sbb:

Bagaimana memilih obyek yg akan dimuat dr n

obyek yg ada sehingga nilai obyek termuat jumlahnya

sesuai dgn kapasitas(£ M)

Jika semua obyek harus dimuat kedalam ransel

maka berapa bagian dr setiap obyek yg ada dapat

dimuat kedalam ransel sedemikian shg nilai kum.

maks. & sesuai dgn kapasitas ransel ?

Penyelesaian Knapsack Problem :

1. Dengan Secara Matematika

2. Dengan Kriteria Greedy.

3. Dengan Algoritma Pemrograman Greedy.

Penyelesaian Knapsack Dengan Secara

Matematika

Fungsi tujuan = fungsi utama/obyektif = fungsi yg mjd

penyelesaian permasalahan dgn mendptkan solusi yg optimal.

Solusi dimaksud = menemukan nilai/profit yg maks. utk jml

obyek yg dimuat dlm ransel shg sesuai kapasitas.

n

Fungsi Tujuan Maksimum : Ó Pi Xi

I=1

Fungsi pembatas = fungsi subyektif = fungsi yg bertujuan

untuk memberikan batas maks. dr setiap obyek untuk dapat

dimuat dalam ransel sehingga kapasitasnya tdk melebihi dr

jumlah maks.daya tampung ransel.

n

Fungsi Pembatas : Ó Wi Xi £ M

i=1

dimana : 0 £ Xi £ 1; Pi >0;Wi>0

Catatan : karena dengan menggunakan

Matematikan sangat sulit dan rumit maka tidak dibahas

lebih mendalam.

Penyelesaian Dengan Kriteria Greedy.

Konsep dr kriteria yg ditawarkan oleh metode Greedy yaitu :

Pilih obyek (barang) dengan nilai Pi maximal atau terbesar

Pilih obyek (barang) dengan beratWi minimal dahulu.

Pilih obyek (barang) dgn perbandingan nilai & berat yaitu

Pi/Wi yang terbesar.

Penyelesaiannya : Dengan Kriteria

Greedy.

Diketahui bahwa kapasitas M = 20kg ,

Dengan jumlah barang n=3

Berat Wi masing-masing barang

(W , W , W ) = (18, 15, 10)

123Nilai Pi masing-masing barang

(P1, P2, P3) = (25, 24, 15)

Pilih barang dengan Nilai Profit Maksimal

P1 = 25 _ X1 = 1, dimisalkan sebagai

batas atas nilai

P2 = 24 _ X2 = 2/15, dihitung dengan

Fungsi Pembatas

P3 = 15 _ X3 = 0, dimisalkan sebagai

batas bawah nilai

Pilih barang dengan Berat Minimal

W1 = 18 _ X1 = 0, sebagai batas bawah

W2 = 15 _ X2 = 2/3,dihitung dgn Fungsi

Pembatas

W3 = 10 _ X3 = 1, sebagai batas atas

Pilih barang dgn menghitung perbandingan yg terbesar

dr Profit dibagi Berat (Pi/Wi) yg diurut secara tidak naik,

yaitu :

P1/W1 = 25/18 _karena terkecil maka X1 = 0

P2/W2 = 24/15 _karena terbesar maka X2 = 1

P3/W3 = 15/10 _dengan Fungsi pembatas

X3 = 1/2.

Dibuatkan tabel berdasarkan elemen dr

ke-3 kriteria metode Greedy

Solusi ke (X1,X2,X3) ÓWiXi ÓPiXi

Pi Max ( 1, 2/15, 0) 20 28.2

( 0, 2/3, 1) 20 31.0

Pi/Wi max ( 0, 1, 1/2 ) 20 31.5

Nilai profit maksimal = 31.5 dengan komposisi yang

Sama

Pertemuan 13

Penyelesaian Dengan

Algoritma Pemrograman

Greedy.

Pertemuan 13

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

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

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’ p’urutan scr tdk naik thdp hasil Pi/Wi, misalnya :

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

2/W2 _ 24/15 = 1,60 menjadi urutan ke 1

P3/W3 _ 15/10 = 1.50 menjadi urutan ke 2

Sehingga m’hasilk’ pola urutan data yg baru,yaitu

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

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 _b’arti bhw brg tsb dpt dimuat seluruhnya.

Isi = 20 - 15 _kapasitas ransel b’kurang dgn sisa 5kg i =2

W(2) > isi ?? _ 10 > 5 ?? _kondisi BENAR

x(2)=5/10=1/2_benda 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

PROBLEMA DAN MODEL GRAPH DALAM METODE

GREEDY ( Lanjutan )

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

5

3

1 2

8 7 10

11

12

11

9

9

10

8

4

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

Problema diatas menghasilkan waktu minimalnya

adalah 45 menit dan diperoleh perjalanan sbb :

1

2

7

5

4 3

8

12

10

8

2. MINIMUM SPANNING TREE

Kasus MST Problem = m’cari min.biaya (cost) spanning tree

dr setiap ruas (edge) graph yg m’btk pohon (tree).

Solusi dr p’masalah’ ini :

a. Dgn memilih ruas suatu graph yg memenuhi kriteria

dr optimisasi yg m’hasilk’ biaya min.

b. Penambah’ dr setiap ruas pd seluruh ruas yg m’btk

graph akan m’hasilk’ nilai/biaya yg kecil (minimum cost).

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)

Proses Total minimum cost terbentuknya graph dgn

tahapan sbb:

• Dari graph yg tetbentuk, 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.

3. SHORTEST PATH PROBLEM

1 2

4 3

5

6

10

30

20

55

40

35

15

45 50

25

Permasalahan : menghitung jalur terpendek dr sbh graph

berarah.

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

50 10

30

3

Jalur Panjang jarak

A – C 10

A – C – D 25

A – C – D – B 45

A – E 45

Penyelesaian:

PROBLEMA DAN MODEL GRAPH DALAM METODE

GREEDY

1. PEWARNAAN ( COLORING )

Problema pemberian warna kepada semua

simpul, sedemikian sehingga 2 simpul yang

berdampingan ( ada ruas menghubungkan

ke dua simpul tersebut ) mempunyai warna

yang berbeda .Banyak warna yang

dipergunkan , diminta seminimal mungkin

Contoh :

D

C

B

E

A

Permasalahan :

Menentukan pola lampu lalulintas dengan jumlah fase

minimal, dan pada setiap fase tidak ada perjalanan yang

saling melintas . Perjalanan yang diperbolehkan adalah : A ke

B, A ke C, A ke D, B ke C, B ke D, E ke B, E ke C dan E ke D

Langkah-langkah penyelesaian masalah :

1.Tentukan simpul dari perjalanan yang diperbolehkan

( untuk peletakan simpulnya bebas )

2.Tentukan ruas untuk menghubungkan 2 simpul yg

menyatakan 2 perjalanan yg saling melintas

EB

AD

EC

AC

AB BC

ED

BD

3. Beri warna pada setiap simpul dengan warna

warna baru.

- Bila Simpul berdampingan maka berilah warna

lain.

- Bila simpul tidak bedampingan maka berilah

warna yang sama

P

AB BC EC

EB

AD

AC

ED

BD H

H

M

P

4. Kita lihat Bahwa simpul AB , BC dan ED tidak

dihubungkan oleh suatu ruas jadi untuk simpul tersebut

tidak pernah melintas perjalanan-perjalanan lain dan

simpul tersebut selalu berlaku lampu hijau

5. Tentukan pembagian masing –masing simpul yang

sudah diberikan warna.

Putih = ( AC, AD )

Hitam = ( BD, EB )

Merah = ( EC )

Catatan :

Pembagian simpul berdasarkan simpul yang tidak langsung

berhubungan seminimal mungkin ( BISA DILAKUKAN

DENGAN BEBERAPA KEMUNGKINAN )

6.Dari langkah ke 5 diperoleh 3 fase, sehingga bisa kita

simpulkan keseluruhan situasi dan hasilnya dapat

dinyatakan dengan :

HIJAU AC, AD, AB, BC, ED

MERAH BD, EB, EC

Fase 1:

HIJAU BD, EB, AB, BC, ED

MERAH AC, AD, EC

Fase 2:

Fase 3 :

HIJAU EC, AB, BC, ED

MERAH AC, AD, BD, EB