4/29/2010
Terminologi Single source shortest path dijkstra j wijanarto
• Dijkstra’s algorithm di pakai untuk menemukan shortest path dari satu source ke seluruh vertek dalam graph. • Algo ini menggunakan 2 himp node yaitu S dan C. • Pada himp. S berisi node yang terpilih yang memiliki jarak minimal dari source. • Pada himp. C berisi node selain yang terpilih dalam S, yang belum di ketahui dan merupakan kandidat yang akan di pilih pada langkah berikutnya
Terminologi • Dengan demikian kita akan peroleh N=S∪C • Pada saat algoritma berhenti, S berisi seluruh node dari G dan masalah terselesaikan. • Tiap i langkah l k h yang terpilih ilih dalam d l C C merupakan k jarak terkecil pada source dan di tambahkan ke S
Abstraksi • Diberikan G={V,E}, directed graph dengan fungsi l:EÆR+ 5 0.5 S source
1.1
3
3.1
2 7
T (destination)
• Problem mencari jalur terpendek dari S ke T
1
4/29/2010
Abstraksi • Berapa pa tadi?
Abstraksi
th yang mungkin dari garaph G
86 8.6 7.2
• Dapatkah kita mencari SP dengan cara seperti sebelumnya ??? Kenapa ?? • Sebab dalam praktek, mungkin terdapat G yang besar dengan path yang tidak yang besar path yang tidak di ketahui, ketahui misal :
8.6 9
• Shortest path = 7.2
Property SP (single short shortest path)
• Sehingga jika terdapat n vertek, maka terdapat 2 n/3 path • Lalu bagaimana kita mencari SP pada problem seperti ini?? 0.5
1
0.3
0.4
1.1
0.2
0.5
0.8
3k+1
k
Abstraksi
S
T
S
• Jika terdapat k diamond, berapa vertek‐nya • Berapa Path?? 2 diantara S dan T
8.1
T
• Untuk melakukannya kita harus tahu property dari SP
• Di berikan path dalam G, dari s ke t
s
x
t
• X salah satu vertek dalam path s‐t, sehingga terdapat path s‐x dalam s‐t, dimana merupakan SP • Jadi Algoritma yang akan di bicarakan adalah SP dalam setiap vertek dalam GÆSSSP
2
4/29/2010
contoh
IDE SSSP
• Misal l1
l2
v2
l3
0.4
s
0.5
v5
0.5 v2
1.1 2.3
v4
v1 0.7
0.3 v3 3
• D[v1]=0.7, karena hanya terdapat 1 path • D[2]=1.1Î1.2, ada path lain (s‐v1‐v2) tp tdk update • D[3]=2.3 Î1,ada path lain(s‐v1‐v3) – Path d[2] dan d[3] mengalami update utk mendapatkan shortest path
• D[4]=1.1 • D[5]=1.2
v3
Algoritma procedure Dijkstra; { Dijkstra menghitung cost shortest path dr vertex 1 ke tiap vertex dr directed graph } begin 1. S := {1}; 2. for i := 2 to n do 3. D[i] := C[1, , i]; { inisialkan D } 4. for i := 1 to n-1 do begin 5. Pilih vertex w dlm V-S sedemikian sehingga D[w] adlh minimum; 6. Tambahkan w ke S; 7. for tiap vertex v dlm V-S do 8. D[v] := min(D[v], D[w] + C[w, v]) end end; { Dijkstra }
SSSP Manual • Misalkan source 1, maka 45 1
2 50
10
20
15
20
5
10 35 30
3
15
4
6 3
3
4/29/2010
SSSP Manual
SSSP Manual – 1‐3
• Cari Source Ke Akhir simpul, ternyata ada:
• • • •
– 1‐2,1‐3,1‐4,1‐5
• Cari jalur terpendek dari tiap‐tiap simpul yang berhubungan dr source ke source ke akhir
• • • •
=50 =45, terpendek =95
SSSP Manual – 1‐5 • • • •
1‐5 1‐2‐5 1‐3‐4‐2‐5 1‐3‐4‐5
=45,terpendek =60 =65 =60
• Kumpulkan jalur terpendek dari masing‐ masing simpul yang berhubungan dr source ke akhir
=10 =65, terpendek =125 =110 110
– 1‐4
– 1‐2 • 1‐2 • 1‐3‐4‐2 • 1‐5‐4‐2
1‐3 1‐2‐3 1‐2‐5‐4‐2‐3 15423 1‐5‐4‐2‐3 1‐3‐4 1‐2‐5‐4 1‐2‐3‐4 1‐5‐4
=25, terpendek =90 =80 =75
SSSP Manual‐Hasil Akhir Jalur
Jarak
1‐3
10
1‐3‐4
25
1‐3‐4‐2
45
1‐5
45
45 1
2
10
5
20
3
15
4
4
4/29/2010
Problem
Algoritma Semi‐Greedy
• Di ketahui G=(V,E), directed and weighted. • Hitung panjang (cost) shortest path dari node 1 ke setiap node dalam G. p p paths (1 ‐> 4 ‐ ( • source node 1 ke 3. Ada beberapa > 3, 1 ‐> 2 ‐> 3, dst.), tetapi shortest dari path tsb adalah 1 ‐> 4 ‐> 2 ‐>3 dg panjang 9. • Tugas kita adalah bagaimana menemukan .
• Kompleksitas O(n*lg(lg(n))) hingga O(n2). • Ambil cost dari shortest path ke seluruh node dan tandai dengan infinity (∞). Dan.. • Tandai d i panjang j ( (cost) shortest path pada ) h h d source dengan 0.
Algoritma (lanj.)
Algoritma (lanj.)
• Pilih node yg terdekat dg source dan blm optimal dan yang menjanjikan adalah path ke node 2 dan 4. • Update cost ∞ Update cost ∞ pada 2 dan 2 dan 4 – 2Î0+10=10 – 4Î0+5=5 (node terpilih)
• Dari 4 kita akan update cost node 2, 3 dan 5, yaitu: • 2Î 5+2=7 (node terpilih) • 3Î5+9=14 3Î 9 • 5Î5+2=7
5
4/29/2010
Algoritma (lanj.)
Algoritma (lanj.)
• Dari 2 kita akan update cost node 3 : • 2Î 5+2=7 (node terpilih) • 3Î5+9=14 • 5Î5+2=7
• Algoritma berhenti karena semua node sudah di kunjungi dan terupdate optimal cost • Panjang (cost) optimal =1‐4‐2‐3Î8
Cost selected
SSSP Greedy F
50
10 10
B 20
40
A
50 90 30
20 G
Total cost=
D 20
10 10
80
E
C
Current lowest cost
step
Dari AÎ
B
C
D
E
F
G
H
1
A
20 A
∞
80 A
∞
∞
90 A
∞
2
B
20 A
∞
80 A
∞
30 B
90 A
∞
40 F
70 F
90 A
∞
90 A
60 C
20
3
F
20 A
∞
30 B
H
4
C
20 A
40 F
50 C
∞
30 B
5
D
20 A
40 F
50 C
∞
30 B
70 D
60 C
6
H
20 A
40 F
50 C
∞
30 B
70 D
60 C
7
G
20 A
40 F
50 C
∞
30 B
70 D
60 C
8
E=∞ artinya tidak ada path lagi,walau ada edge Ke B dan G tapi cost update tidak lebih baik Dari yang sekarang
Algoritma Knapsack • Ada beberapa versi dari masalah klasik ini. Salah satunya bisa diilustrasikan sebagai berikut. Diberikan n objek dan sebuah ransel (knapsack). Masing‐masing objek i mempunyai berat wi dan vi. Ransel tersebut bisa memuat objek maksimal y g p g seberat W. Masalah yang harus dipecahkan adalah bagaimana mengisi ransel dengan objek yang nilai maksimal tanpa melewati batas kapasitas dari ransel. Dalam versi ini, diasumsikan bahwa masing‐masing objek dapat dibagi menjadi bagian yang lebih kecil, sehingga kita dapat memutuskan untuk hanya membawa sebagian objek i sebanyak x1. Dengan demikian, algoritma untuk masalah ini dapat disusun sebagai berikut.
6
4/29/2010
Algoritma • n adalah jumlah objek wi adalah variabel yang menyatakan berat dari objek i, vi adalah variabel yang menyatakan nilai dari objek i, xi adalah pecahan yang menyatakan beberapa adalah pecahan yang menyatakan beberapa bagian dari objek i yang dimasukkan dalam ransel. Variabel berat menyatakan jumlah berat objek yagn sudah dimasukkan dalam ransel, sedangkan W adalah kapasitas dari ransel.
rumus
∑P X i i =1
i
∑W X i =1
– Fungsi yg mjd penyelesaian masalah dengan mendapatkan solusi optimal, yaitu mendapatkan p yg j y y g nilai profit yg maksimal utk sejumlah obyek yang akan di muat dalam ransel yg sesuai kapasitasnya
• Fungsi Pembatas/Subyektif – Bertujuan memberikan batas maksimal setiap obyek untuk di muatkan dalam ransel sesuai kapasitasnya
• Pilih obyek dengan nilai Pi maksimal • Pilih obyek dengan bobot Wi minimal • Pilih obyek dengan perbandingan Pi/Wi terbesar b
n
Fungsi Pembatas
• Fungsi Utama/Tujuan/Objektif
Solusi Greedy
n
Fungsi Tujuan
Secara Matematis
i
≤M
0 ≤ X i ≤ 1, Pi > 0, Wi > 0
7
4/29/2010
Algoritma Knapsack Greedy void GREEDY(int n,int c, int p[],int w[]){ int cc,jj,j; cc=c; zg=0; jj=1; for(j=1;j
cc) x[j]=0; else { x[j] = 1; cc=cc-w[j]; g g p[j]; zg=zg+p[j]; } if (p[j]>p[jj]) jj=j; } if (p[jj]>zg){ zg=p[jj]; for (j=1;j
Psuedocode Algoritma – Inisiasi • Untuk setiap i, set xi = 0 • Set berat = 0 – Selama berat < W lakukan • Pilih i, yaitu objek yang paling potensial (lihat keterangan di bawah) dari objek yang tersisa. • Jika berat + wi ≤ maka xi = 1 Berat = berat + wi Jika tidak maka xi = (W – berat) / wi berat = W
Contoh Soal
Secara Matematika 3
∑P X
• Diketahui – n=3 dengan Wi(18,15,10) dan Pi(25,24,15) dan M=20
• Ditanyakan – Tentukan berat tiap‐tiap barang yang dpt di muat dalam ransel dengan kapasitas M ?
i i =1 3
i
i =1
i
∑W X
≤ 20
0 ≤ X i ≤ 1, Pi > 0, Wi > 0 Batas bawah
Batas atas
8
4/29/2010
Step 1
Step 2
• Tentukan solusi feasibel yaitu 2 X n dari batas bawah dan atas, lalu hitung sesuai kapasitas M<=20, untuk masing masing bobotnya X1=0,X 0 X2=1,X 1 X3=? ? 18X1+15X2+10X3≤20 18.0+15.1+10.X3 ≤20 10X3 ≤20-15 X3=1/2
X1=1,X 1 X2=0,X 0 X3=? ? 18X1+15X2+10X3≤20 18.1+15.0+10.X3 ≤20 10X3 ≤20-18 X3=1/5
X1=0,X2=?,X3=1 18X1+15X2+10X3≤20 18.0+15. X2+10.1 ≤20 15X2 ≤20-10 X2=2/3
X1=?,X2=1,X3=0 18X1+15X2+10X3≤20 18X1+15.1+10.0 ≤20 18X1 ≤20-15 X1=5/18
X1=1,X =1 X2=?,X =? X3=0 18X1+15X2+10X3≤20 18.1+15X2+10.0 ≤20 15X2 ≤20-18 X2=2/15 X1=?,X2=0,X3=1 18X1+15X2+10X3≤20 18X1+15.0+10.1 ≤20 18X1 ≤20-10 X1=5/9
• Buat tabel Untuk solusi fisibel Solusi ke
(X1,X2,X3)
ΣWiXi
ΣPiXi Profit
1
(0 1 1/2) (0,1,1/2)
20
31 5 31.5
2
(1,0,1/5)
20
28
3
(1,2/15,1)
20
28.2
4
(0,2/3,1)
20
31
5
(5/18,1,0)
20
30.9
6
(5/9,0,1)
20
28.8
Metode Greedy • Pilih barang dengan nilai profit Maksimal – P1=25 Î x1=1, batas atas fungsi – P2=24 Î x2=2/15, hasil perhit. fungsi pembatas – P3=15 Î x3=0, batas bawah fungsi • Pilih barang dengan berat Minimal – W1=18 Î x1=0, batas bawah fungsi – W2=15 Î x2=2/3, hasil perhit. fungsi pembatas – W3=10 Î x3=1, batas atas fungsi • Hitung Wi/Pi
solusi fisibel solusi fisibel
Metode Greedy • Buat Tabel (X1,X2,X3)
ΣWiXi
ΣPiXi Profit
Pi max Pi max
(1 2/15 0) (1,2/15,0)
20
28 2 28.2
Wi min
(1,2/3,1)
20
31
Pi/Wi
(0,1,1/2)
20
31.5
Solusi ke
solusi fisibel
– P1/W1=25/18 Î karena terkecil, maka x1=0, batas bawah fungsi – P2/W2=24/15 Î karena terbesar, maka x2=1, batas atas fungsi – P3/W3=15/10 Î di hit dengan F pembatas x3=1/2 F pembatas
0 ≤ X i ≤ 1, Pi > 0, Wi > 0
9
4/29/2010
Algortima Greedy • Sorting Descending thd Pi/Wi – P1/W1=25/18 =1.39 Î urutan 3 – P2/W2=24/15 =1.60 Î urutan 1 – P3/W3=15/10 P3/W3 15/10 =1.50 Î 1 50 Î urutan 2 – Shg di peroleh urutan terhadap P dan W sbb: • W1,W2,W3 Æ 15,10,18 • P1,P2,P3 Æ 24,15,25
Running Algorithm • Di Inputkan ke algo Knapsak Greedy X(1:n)Å0 IsiÅ20 Mulai iterasi i=1 W(i)>isi ? Î 15>20, tidak, maka x(1)Å1, brg (1)Å1 brg dpt dimuat dim at seluruhnya sel r hn a dari W(1)=15 W(1) 15 isi=20‐15, kapasitas ransel berkuran mjd 5 i=2 W(2)>isi ? Î 5>10, ya, maka x(2)Å5/10=1/2, brg dpt dimuat sebanyak ½ bagian saja dari W(2)=10 isi=5‐5, kapasitas ransel habis i=3, X(3)=0, isi=0, selesai, karena isi=0
• Menghitung Profit (P1+P2+P3)=(24*1+15*1/2+18*0)=31.5
10
