BAB 2 LANDASAN TEORI
2.1
Algoritma Algoritma berasal dari kata Algoris dan Ritmis, yang pertama kali diperkenalkan
oleh Abu Ja’far Mohammad Ibn Musa Al Khowarizmi dalam buku Al-jabr w’almulqabala (Horowitz, Ellis dan Sahni, 1978, p1). Ada beberapa definisi mengenai pengertian algoritma, antara lain: •
Menurut Thomas H. Cormen, Charles E. Liserson, Ronald L. Rivest, dan Clifford Stein (Introduction To Algorithms, 2nd ed, 2001, p5), algoritma adalah urutan langkah-langkah komputasi untuk merubah input menjadi output.
•
Menurut Robert Sedgewick (Algorithms in C++ part1-4, 3rd ed, 1998, p3), algoritma adalah metode untuk memecahkan masalah yang sesuai untuk implementasi komputer.
•
Menurut Steven S. Skiena (The Algorithm Design Manual, 1998, p3), algoritma adalah prosedur untuk melakukan tugas tertentu untuk memecahkan masalah.
•
Menurut Harvey M. Deitel dan Paul J. Deitel (C How To Program, 4th ed, 2004, p57), algoritma adalah prosedur untuk memecahkan masalah yang melibatkan aksiaksi yang akan dilaksanakan dan urutan dari aksi-aksi tersebut akan dilaksanakan. Algoritma memiliki kompleksitas, dimana ukuran kompleksitas tersebut
merupakan acuan utama, untuk mengetahui kecepatan dari algoritma tersebut. Biasanya, kompleksitas memiliki tiga buah ukuran, yaitu best case (Ω) , average case (Θ) , dan
6
worst case (Ο) . Hubungan ketiganya terhadap suatu fungsi n yaitu f (n) adalah sebagai berikut:
Gambar 2.1: Perbandingan worst case, average case, dan best case.
Dari ketiga notasi di atas, yang biasanya menjadi tolak-ukur suatu algoritma adalah average case dan worst case, sebab kondisi best case akan sangat jarang terjadi, dan penilaian terhadap suatu algoritma adalah efisiensi walaupun terjadi kondisi terburuk. Growth of Function 1
log N
N
N log N
N2 2N
Sebagian besar instruksi hanya dieksekusi sekali. Jika semua instruksi dari sebuah program memiliki properti ini maka running time program ini disebut konstan. Running time ini disebut logarithmic umumnya terjadi dalam program yang memecahkan masalah besar dengan mentransformasikan menjadi sekumpulan masalah-masalah yang lebih kecil, memotong ukuran dari permasalahan dengan pembagian yang konstan pada setiap langkahnya. Running time ini disebut linear dimana umumnya proses dilakukan pada setiap elemen input. Situasi ini optimal untuk algoritma yang harus memproses sejumlah N input. Runnig time ini disebut linearithmic dan terjadi saat algoritma memecahkan masalah dengan membaginya menjadi subproblemsubproblem yang lebih kecil, memecahkan subproblem tersebut masingmasing secara independen dan menggabungkan semua solusi-solusinya. Running time ini disebut quadratic, umumnya terjadi pada saat algoritma harus memproses setiap pasangan data (misalnya doublenested loop). Running time ini disebut exponential. Sangat sedikit algoritma seperti ini yang bisa disebut efektif, karena waktu proses yang terlalu lama. Algoritma ini umumnya muncul pada saat memecahkan masalah secara brute-force.
7
Tabel perbandingan Growth of Function log N N N log N N2 2N 3 10 33 100 1024 7 100 664 1000 1.26 x 1030 10 1000 9966 1000000 Table 2.1: Tabel pertumbuhan fungsi
2.1.1 Notasi Ω (best case) Best case adalah ukuran sebuah kompleksitas algoritma, dimana algoritma tersebut berjalan dalam kondisi terbaik. Misal: Terdapat fungsi g (n) , maka Ω( g (n)) = { f (n) : ada sebuah konstan c dan nilai n0 yang bernilai positif, sehingga 0 ≤ c.g (n) ≤ f (n) untuk n ≥ n0 }. Nilai konstan adalah nilai yang biasanya dipengaruhi oleh berapa jumlah operasi tetap yang dijalankan pada algoritma tersebut, bagaimana kondisi hardware, bagaimana kondisi saat algoritma tersebut dijalankan. Contoh kasus: Pada algoritma insertion sort, maka best case dari algoritma tersebut adalah
Ω(n) , yaitu ketika data yang akan diproses telah terurut dengan benar.
2.1.2 Notasi Θ (average case) Average case adalah ukuran sebuah kompleksitas algoritma dimana algoritma ini berjalan dalam kondisi netral, biasanya pengujian menggunakan input secara acak.
8
Misal: Terdapat fungsi g (n) , maka Θ( g (n)) = { f (n) : terdapat 2 nilai konstan c1 dan c2 dan n0 yang bernilai positif, sehingga 0 ≤ c1.g (n) ≤ f (n) ≤ c2 .g (n) untuk semua n ≥ n0 } Contoh kasus: Pada algoritma insertion sort, pada kondisi rata-rata, terdapat
maka average case dari algoritma ini adalah c1n 2 ≤ Lalu
bagi
menjadi c1 ≤
setiap
sisi
dengan
n2 ,
1 2 n − 3n operasi, 2
1 2 n − 3n ≤ c2 n 2 untuk semua n ≥ n0 . 2
sehingga
pertidaksamaan
tersebut
1 3 1 1 − ≤ c2 , maka pada saat n = 7 nilai c1 ≤ , dan c2 ≥ . Karena terdapat 2 2 n 14 2
1 buah nilai konstan tersebut, maka average case algoritma ini adalah n 2 − 3n = Θ(n 2 ) . 2
2.1.3 Notasi Ο (worst case) Worst case adalah ukuran sebuah kompleksitas algoritma dimana algoritma ini berjalan pada kondisi terburuk. Misal: Terdapat fungsi g (n) , maka Ο( g (n)) = { f (n) : terdapat nilai konstan c dan n0 yang bernilai positif, sehingga 0 ≤ f (n) ≤ c.g (n) untuk semua n ≥ n0 }. Contoh kasus: Pada algoritma insertion sort, g (n) =
1 2 1 1 n − 3n , c = , maka n 2 − 3n = Ο(n 2 ) , 2 2 2
yaitu pada saat data diinput terurut secara terbalik.
9
2.2
Graph
Graph adalah kumpulan vertex atau node yang terhubung oleh satu atau lebih edge atau arc. Biasanya edge atau arc tersebut memiliki bobot yang dinamakan weight.
7
3
5
6
2 4
Gambar
2.2:
Sebuah
graph,
dimana
lingkaran
merepresentasikan vertex, dan garis merepresentasikan edge atau arc. Berdasarkan arah edge, sifat graph dapat dibagi dua, yaitu: •
Directed graph. Graph yang memiliki edge berarah, maka edge yang menghubungkan vertex 1 menuju vertex 2, bukan merupakan edge yang menghubungkan vertex 2 menuju vertex 1. Edge pada graph berjenis ini biasa disebut dengan arc, dan graph pun dirumuskan sebagai berikut: G = (V , A) .
Gambar 2.3: Directed graph
10
•
Undirected graph. Graph yang memiliki edge tidak berarah, sehingga apabila terdapat edge yang menghubungkan vertex 1 menuju vertex 2, maka edge tersebut juga menghubungkan vertex 2 menuju vertex 1. Pada graph bertipe ini, biasa dirumuskan sebagai berikut: G = (V , E ) .
Gambar 2.4: Undirected graph Berdasarkan strukturnya penghubungnya (connectivity), graph juga dapat dibagi menjadi dua, yaitu: •
Cycle Cycle adalah struktur graph dimana satu atau lebih vertex yang menjadi anggota graph tersebut memiliki jalur menuju dirinya sendiri.
Gambar 2.5: Graph yang mengandung cycle
•
Trees
11
Trees adalah struktur graph, dimana tidak ada satupun vertex yang menjadi anggota graph tersebut memiliki jalur menuju dirinya sendiri.
Gambar 2.6: Graph yang memiliki struktur trees
2.3
Queue
Queue adalah struktur data yang menggunakan prinsip FIFO (First In First Out), sehingga operasi yang ada dapat digambarkan seperti antrian. Queue memiliki sebuah head dan sebuah tail, dimana head menandakan awal antrian, dan tail menandakan akhir antrian. Dalam queue terdapat dua operasi dasar, yaitu operasi penambahan data yang biasa disebut enqueue, dan operasi pengeluaran data yang biasa disebut dequeue.
12
1
2
3
4
5
6
7
8
9
a.
b.
head tail 1
1
2
3
4
5
7
1
12
4
9
head
2
3
c.
4
5
4
9
head
6
7
8
9
1
e.
2
3
5
tail
tail 2
3
4
5
5
tail
7
8
9
tail
1
d.
6
4
5
6
7
8
9
4
9
1
13
17
3
head
6
7
8
9
1
13
17
3
head
Gambar 2.7: Sebuah queue yang diimplementasikan menggunakan array[1..9], dimana isi dari queue dimulai dari posisi head, dan diakhiri oleh posisi tail. (a) kondisi awal queue, ketika masih kosong. (b) kondisi ketika queue mendapatkan perintah enqueue(7), enqueue(1), enqueue(12), enqueue(4), enqueue(9). (c) kondisi ketika queue mendapatkan perintah dequeue() sebanyak 3 kali. (d) kondisi ketika queue mendapatkan perintah enqueue(1), enqueue(13), enqueue(17), enqueue(3), enqueue(5), kondisi ini membuat queue overlap, dan data dimasukkan kembali dari depan (selama queue masih memiliki tempat kosong). (e) kondisi ketika queue mendapatkan perintah dequeue() sebanyak 2 kali.
Seperti yang ditunjukkan pada gambar 2.7, operasi enqueue dan dequeue memiliki kompleksitas O(1) . Pada Standart Template Library (STL) yang terdapat dalam bahasa pemrograman C++, sudah terdapat fungsi-fungsi yang mendukung operasi queue. Semuanya terdefinisi dalam library
seperti .push(…) yang berfungsi sebagai enqueue, .front() untuk
13
mengambil elemen pada posisi head, .pop() untuk menghapus elemen pada queue (operasi dequeue tanpa mengembalikan elemen), .empty() untuk mengecek apakah queue dalam kondisi kosong (dimana head dan tail berada pada posisi yang sama).
2.4
Breadth First Search (BFS)
Diberikan sebuah graph G = (V , E , s ) , dimana s ∈ V (s anggota V) adalah source, cari semua vertex yang terhubung oleh s. Salah satu algoritma yang biasa digunakan untuk menyelesaikan masalah ini, adalah BFS. BFS akan mencari vertexvertex tersebut dimulai dari vertex s, kemudian akan mengeksplorasi vertex mana saja yang terhubung langsung dengan vertex s, dan memasukkan setiap vertex tersebut ke dalam queue, setelah itu, tandai bahwa vertex tersebut sudah pernah dicapai. Kemudian keluarkan sebuah vertex dari queue, dan lakukan operasi yang sama seperti pada vertex s, hingga queue kosong, dan akhiri pencarian. Dengan menggunakan BFS, maka akan menghasilkan tree yang memiliki root vertex s. BFS
akan
mengeksplorasi
vertex
sementara,
berdasarkan
edge
yang
menghubungkan vertex tersebut dengan vertex lain, kemudian memasukkannya kedalam queue. Karena operasi enqueue, dan dequeue memiliki kompleksitas O (1) , sehingga jumlah operasi dequeue adalah sebanyak jumlah vertex dan memiliki kompleksitas O(V ) , dan jumlah operasi pencarian apakah vertex sementara terhubung oleh sebuah edge secara langsung dengan vertex lainnya, dan kemudian melakukan proses enqueue yaitu O( E ) , maka total pencarian secara keseluruhan memiliki kompleksitas O (V + E ) .
14
1
2
4
6
1 Q
a.
1
2
4
6
b.
0
3
5
7
0
3
5
7
1
2
4
6
1
2
4
6
c.
Q
2
d.
0
3
5
7
0
3
5
7
1
2
4
6
1
2
4
6
e.
Q
4
5
f.
0
3
5
7
0
3
5
7
1
2
4
6
1
2
4
6
g.
Q 0
3
5
6
7
h.
7
1
0
2
4
5
0
Q
3
Q
5
Q
7
2
6
7
6
. 0
3
Q
Q 3
5
7
Gambar 2.8: Menunjukkan cara kerja BFS dimana source adalah vertex 1.
2.5
Algoritma Topological Sorting Diberikan sebuah graph G = (V , A) , tentukan urutan vertex pada graph tersebut,
apabila suatu vertex hanya dapat digunakan jika dan hanya jika tidak ada lagi vertex yang memiliki hubungan langsung dengan vertex tersebut. Algoritma ini memiliki langkah-langkah sebagai berikut: Langkah 1:
Set degree dari masing-masing vertex, dimana degree adalah jumlah koneksi dari vertex lain, ke vertex tersebut.
Langkah 2:
Masukkan semua vertex yang memiliki degree = 0 kedalam queue.
15
Langkah 3:
Lakukan dequeue, apabila langkah 3 tidak dalam kondisi queue kosong, maka lakukan langkah 4.
Langkah 4:
Hilangkan semua arc yang terkoneksi pada vertex tersebut, dan kurangi degree dari vertex yang terhubung padanya.
Langkah 5:
Ketika langkah 4 menghasilkan vertex dengan degree = 0, maka masukkan kedalam queue. Kembali ke langkah 3.
2.6
Algoritma Bellman Ford Algoritma ini biasa digunakan untuk menyelesaikan problem single shortest
path, dimana problem ini diformulasikan sebagai berikut : G = (V , A, s, w) dimana s ∈ A dan w : A → R (w anggota A dimana nilai w merupakan bilangan Real), tentukan jalur dengan total w terkecil, dimulai dari vertex s menuju vertex lainnya. Problem single shortest path ini, memiliki kondisi optimal sebagai berikut:
d j ≤ di + wi , j
(2.1)
Algoritma Bellman Ford menggunakan persamaan di atas, dengan langkah-langkah sebagai berikut: Langkah 1: Sebagai inisialisasi awal, set semua di →( i∈V ) = ∞ , dan set d s = 0 . Langkah 2: Lakukan langkah 3 sebanyak A kali. Langkah 3: Untuk setiap wij ∈ A , jalankan rumus (2.1) Karena algoritma ini menjalankan operasi 3 yang memiliki kompleksitas O( A) sebanyak V kali, maka kompleksitas algoritma ini sebesar O(VA) .
16
v
t
oo
6
-2
6
6
7
w
u
9
oo
7
w
u
b. v
t
4
2
9
2 w
c. v
-2
4
7
-3
-3
0
-4
s
8
-4
8
7
6
5
6
5
0
7
-3
-3
7
6
-2
2
-4
7
oo
a.
s
0
2
7
7
9
t
s
2
u
v 4
8
0
2
oo
-2 5
-4
s
8
-4
8
0
t 6
5
5
s
v oo
7
-2
-3
t oo
2
2 7
7
7
9
u
2
7
w
u
d.
9
-2 w
e.
Gambar 2.9: gambar di atas, menunjukkan proses algoritma bellman-ford, dimulai dari vertex s.
Pembuktian: Misalkan G = (V , A, s, w) merupakan graph yang tidak memiliki cycle yang bernilai negatif yang dapat dicapai dari vertex s. Kemudian setiap vertex yang terhubung (baik secara langsung maupun tidak) dengan vertex s dinamakan vertex v, dan
p = {v0 , v1 , v2 ,..., vk } , dimana v0 = s maka setelah terjadi pengulangan sebanyak k kali, maka kita telah melibatkan paling sedikit k vertex dalam langkah 3. Karena langkah 3 melibatkan semua edge yang ada dalam menghitung kondisi optimal yang dituliskan pada rumus (2.1), maka semua vertex dalam set p merupakan shortest path tree dimana s sebagai root.
17
2.7
Dynamic Programming Daripada disebut sebagai algoritma, dynamic programming ini lebih tepat
disebut sebagai teknik, dimana teknik ini merupakan salah satu teknik optimalisasi. Cara kerja dari teknik ini adalah, mencari subproblem, dimana jika subproblem tersebut telah didapatkan solusinya, maka akan dapat membentuk solusi dari problem di atasnya. Untuk mengembangkan teknik ini, biasanya dibagi menjadi empat langkah, yaitu:
•
Temukan karakterisktik dynamic programming dalam problem tersebut.
•
Definisikan persamaan rekursif untuk menghasilkan nilai optimal dari problem tersebut.
•
Selesaikan semua subproblem yang berada pada level paling bawah terlebih dahulu, kemudian baru subproblem yang ada di atasnya, hingga pada akhirnya mencapai
problem yang dicari. •
Bentuk jalur-jalur yang dilalui untuk mendapatkan solusi optimal dari problem tersebut.
Untuk langkah terakhir ini, dilakukan apabila diperlukan untuk mencari jalur untuk membentuk solusi. Tetapi untuk mendapatkan nilai optimal dari suatu problem cukup dilakukan langkah 1 – 3. Contoh: Diberikan n buah jenis koin dengan nilai c = {c1 , c2 , c3 ,..., cn } . Diasumsikan jumlah masing-masing koin tak hingga, Tentukan jumlah koin minimum yang dapat digunakan untuk menukarkan uang sebesar M. Untuk menjawab soal di atas, maka dapat dijabarkan sebagai berikut:
18
•
Temukan karakterisktik dynamic programming dalam problem tersebut. Karakteristik dari dynamic programming yaitu adanya subproblem dimana nilai optimal dari subproblem tersebut dapat membentuk solusi optimal dari
subproblem/problem yang berada pada level yang lebih global. Pada soal di atas memiliki karakteristik, bahwa solusi optimal dari M, dapat dibentuk dari solusi optimal M – ci .
•
Definisikan persamaan rekursif untuk menghasilkan nilai optimal dari problem tersebut. Dari penjabaran karakteristik di atas, maka persamaan rekursif dapat dijabarkan kedalam bentuk iteratif sebagai berikut: dp[m] = min(dp[m], dp[m − ci ] + 1) .
•
Selesaikan semua subproblem yang berada pada level paling bawah terlebih dahulu, kemudian baru subproblem yang ada di atasnya, hingga pada akhirnya mencapai
problem yang dicari Pertama tentukan nilai dari level terbawah, yaitu dp[0] di set 0, dan untuk sisanya, dapat diset tak hingga. Kemudian dengan persamaan berikut, dapat didapatkan solusi optimal untuk soal di atas:
for i = 0 to n do for j = ci to M do dp[ j ] = min(dp[ j ], dp[ j − ci ] + 1)
2.8
Linear Programming (LP) Linear programming, dapat digambarkan sebagai berikut: Diberikan matriks A
dengan ordo m x n bertipe integer, dimana a 'i sebagai baris, dan x j sebagai kolom.
19
Kemudian terdapat sebuah batas bi , dan sebuah konstanta c j . Dalam general form LP, hal tersebut dituliskan sebagai berikut: min c ' x
ai' x = bi
i = 1, 2, 3, …, m
ai' x ≥ bi
i = 1, 2, 3, …, m
xj ≥ 0
j = 1, 2, 3, …, n
xj ≠ 0
j = 1, 2, 3, …, n
Contoh: Ketika seseorang ingin membeli bahan-bahan makanan, dia memiliki n pilihan bahan makanan, dan setiap makan memiliki m kriteria nutrisi, sebagai berikut:
ai , j = besar nutrisi ke j yang terkandung dalam bahan makanan yang ke i dimana i ≤ m dan j ≤ n . bi
= kebutuhan nutrisi yang ke i, i ≤ m
x j = jumlah makanan ke j yang dikonsumsi, j ≤ n c j = harga makanan yang ke j, j ≤ n dan nilai x yang mewakili jumlah makanan yang ke j yang dikonsumsi tentu lebih besar daripada 0. Maka susunlah daftar belanja orang tersebut sedemikian rupa, sehingga didapatkan makanan yang dapat memenuhi kebutuhan nutrisi dengan total harga yang paling murah. Dalam LP, soal di atas dapat dituliskan dalam canonical form sebagai berikut: min c ' x Ax ≥ b
x≥0
20
2.8.1 Duality Dalam LP, terdapat konsep duality, dimana problem LP memiliki primal
problem dan dual problem, dimana antara yang satu dengan yang lain memiliki keterkaitan yang kuat. Sehingga solusi untuk primal juga merupakan solusi untuk dual. Berikut ini adalah general form untuk primal dan dual:
Primal
Dual max π ' b
min c ' x
ai' x = bi
i = 1, 2, 3, …, m
a 'j π = c j
j = 1, 2, 3, …, n
ai' x ≥ bi
i = 1, 2, 3, …, m
a 'j π ≤ c j
j = 1, 2, 3, …, n
xj ≥ 0
j = 1, 2, 3, …, n
πj ≥0
i = 1, 2, 3, …, m
xj ≠ 0
j = 1, 2, 3, …, n
πj ≠0
i = 1, 2, 3, …, m
Tabel 2.2: Tabel primal dual
Contoh: Apabila primal problem adalah contoh sebelumnya, maka dual problem adalah: max π ' b
Aπ ' ≤ c '
π ≥0
sehingga memiliki soal cerita kira-kira sebagai berikut: Seorang penjual makanan kesehatan memiliki m jenis pil yang mengandung nutrisi yang berbeda satu dengan lainnya. Apabila harga jenis makanan yang ke j yang memiliki kandungan nutrisi a j
21
adalah c j , dan standar nutrisi yang ke i yang harus dikosumsi oleh seorang manusia sebesar bi , maka harga yang harus ia jual untuk pil yang mengandung nutrisi yang ke i agar ia dapat berkompetisi dengan harga makanan pada umumnya, tetapi juga dapat mendapatkan keuntungan sebesar-besarnya adalah π i . Berikut ini adalah beberapa teori dari konsep duality LP:
•
Teori Weak Duality, yaitu jika x merupakan feasible solution dari primal problem, dan π merupakan feasible solution dari dual problem, maka
m
n
i =1
j =1
∑ biπ i ≤ ∑ c j x j .
Pembuktian: Dengan menggunakan canonical form pada dua contoh sebelumnya sebagai
primal dan dual, pertama kalikan pertidaksamaan ke-2 dari canonical form pertama dengan
π,
m
sehingga
didapatkan
pertidaksamaan
⎡
m
n
∑ b π ≤ ∑ π ⎢∑ a i =1
i
i
i =1
i
⎣ j =1
ij
⎤ xj ⎥ , ⎦
kemudian kalikan pertidaksamaan ke-2 dari canonical form ke-2 dengan x, sehingga
⎡m ⎤ n x a π ∑ j ⎢ ∑ ij i ⎥ ≤ ∑ x j c j , karena sisi kanan dari j =1 ⎣ i =1 ⎦ j =1 n
didapatkan pertidaksamaan
pertidaksamaan pertama sama dengan sisi kiri dari pertidaksamaan kedua, maka berlaku
m
n
i =1
j =1
∑ biπ i ≤ ∑ c j x j .
Dalam teori ini, dapat disimpulkan, bahwa apabila terdapat optimal feasible solution untuk primal dan dual, maka
•
m
n
i =1
j =1
∑ biπ i = ∑ c j x j .
Teori Complementary Slackness Optimality Conditions, yaitu sebuah feasible
solution x dari primal dan sebuah feasible solution π dari dual merupakan optimal
22
feasible solution untuk primal dan dual, jika dan hanya jika keduanya memiliki
⎡⎛ n ⎤ ⎞ properti dari complementary slackness, yaitu: π i ⎢⎜ ∑ aij x j ⎟ − bi ⎥ = 0 untuk setiap ⎠ ⎣⎢⎝ j =1 ⎦⎥ ⎡ ⎛ m ⎞⎤ 1 ≤ i ≤ m , dan x j ⎢c j − ⎜ ∑ aij π i ⎟ ⎥ = 0 untuk setiap 1 ≤ j ≤ n . ⎝ i =1 ⎠⎦ ⎣
Pembuktian: Dari pembuktian terhadap teori weak duality, didapatkan pertidaksamaan m
m
n
i =1
i =1 j =1
n
∑ biπ i ≤ ∑∑ ai, jπ i x j ≤ ∑ c j x j
(2.2)
j =1
karena x dan π merupakan optimal feasible solution, maka pertidaksamaan tersebut diubah menjadi persamaan. Kemudian rumus (2.2) tersebut dapat ditulis sebagai berikut:
m
⎡⎛
n
⎞
⎤
i =1
⎢⎣⎝
j =1
⎠
⎥⎦
∑ π i ⎢⎜ ∑ aij x j ⎟ − bi ⎥ = 0 , dan karena x, π ≥ 0 , maka agar hal tersebut
dapat terjadi, nilai yang ditambahkan dalam setiap iterasi yang ke i sama dengan 0. Pertidaksamaan
pada
rumus
(2.2)
juga
dapat
ditulis
sebagai
berikut:
⎡ ⎛ m ⎞⎤ x c − ∑ j ⎢ j ⎜ ∑ aijπ i ⎟ ⎥ = 0 , dan karena x, π ≥ 0 , maka agar hal tersebut dapat terjadi, j =1 ⎝ i =1 ⎠⎦ ⎣ n
nilai yang ditambahkan dalam setiap iterasi yang ke j juga sama dengan 0.
2.9
Algoritma Push-Relabel Algoritma ini adalah algoritma untuk menyelesaikan problem maximum-flow.
Dimana problem maximum-flow dapat digambarkan sebagai berikut : terdapat graph G = (V , A, s, t , c) , alirkan data sebanyak mungkin dari vertex s ke vertex t dimana s, t ∈ V melewati arc-arc yang memiliki kapasitas cij ∈ A .
23
1 1,
1
3, (
)
4, (4)
1, (1)
a.
(3
)
2, (2)
3,
2
(1
s
1,
t
1
3
4
1
2
s
1
1
3
4, (2) 2)
4
2,
(2
t
)
b.
Gambar 2.10: (a) gambar graph awal, (b) gambar jalur aliran data dengan jumlah data maksimal dari s menuju t.
Berikut ini adalah beberapa properti yang terdapat dalam problem maximumflow, dan merupakan properti dari hampir semua problem network-flow, yaitu: •
Residual network / flow. Residual network merupakan sisa kapasitas tampung maksimum dari suatu arc.
rij = cij − f ij
(2.3)
rij = sisa kapasitas untuk arc yang menghubungkan vertex i menuju vertex j . cij = kapasitas. fij = aliran data yang melewati arc tersebut.
•
Augmenting path Augmenting path adalah sebuah konsep aksi-reaksi, yaitu, apabila terdapat aliran data dari vertex i ke vertex j, maka terdapat residual network dari vertex j ke vertex i sebesar aliran data tersebut.
24
rij = cij − f ij
(2.4.1)
rji = fij
( 2.4.2)
Algoritma ini memiliki konsep dasar, seperti aliran air, yang mengalir dari tempat yang tinggi menuju ke tempat yang lebih rendah, dan mengalirkan air tersebut sebanyak mungkin di titik-titik yang secara langsung berhubungan dengan titik asal, hingga pada akhirnya air tersebut memenuhi titik terbawah. Dengan menggunakan konsep ini, maka terdapat beberapa properti pada algoritma ini, yaitu: •
Excess. Excess adalah properti pada algoritma push-relabel yang dirumuskan sebagai berikut: e(i ) = ∑ rij − ∑ rij j∈V
j∈V
i ∈ V − { s , t}
(2.5)
Apabila e(i ) < 0 , maka vertex tersebut merupakan deficit vertex, dan apabila
e(i ) > 0 , maka vertex tersebut merupakan excess vertex, sedangkan apabila e(i ) = 0 , maka vertex tersebut merupakan balance vertex. •
Height. Height adalah variabel yang digunakan untuk menandakan tinggi dari suatu vertex. Properti inilah yang menandakan apakah suatu vertex dapat men-push aliran data ke vertex lain atau tidak. Properti ini dapat dirumuskan sebagai berikut: h(i ) = ∞ ∀i ∈ V h(t ) = 0
25
(2.6.1)
h(i ) = min(h(i ), h( j ) + 1) : (i, j ) ∈ A •
(2.6.2)
Active vertex. Active vertex adalah status dari sebuah vertex. Sebuah vertex akan berstatus active vertex, jika dan hanya jika e(i) > 0.
Dengan menggunakan properti di atas, maka algoritma push-relabel memiliki langkahlangkah sebagai berikut: Langkah pertama:
merupakan
langkah
inisialisasi.
Set
e(i ) = 0, ∀i ∈ V ,
dan
inisialisasi variabel h seperti pada rumus (2.6.1) Langkah kedua:
gunakan BFS untuk mencari height awal untuk setiap vertex.
Langkah ketiga:
Inisialisasi active vertex awal, dengan cara, push data dari vertex s ke vertex lain yang memiliki hubungan langsung dengan vertex s. Kemudian set e(i ) = csi dan ubah nilai h( s ) = V . Setelah itu ubah status vertex-vertex tersebut, menjadi active vertex.
Langkah keempat:
Selama masih ada active vertex pada graph (G), maka jalankan langkah 5.
Langkah kelima:
Pilih sebuah active vertex (v), dan push data sebanyak min(e(v), rvj ) dari vertex v ke vertex j, dimana vertex j harus memenuhi h( j ) = h(v) − 1 dimana rvj > 0. Apabila tidak ada satupun vertex j yang memenuhi kondisi tersebut, maka lanjutkan langkah 6, jika tidak, ubah nilai-nilai tersebut sebagai berikut:
26
e(v) = e(v) − min(e(v), rvj ) e( j ) = e( j ) + min(e(v), rvj ) rvj = rvj − min(e(v), rvj ) rjv = rjv + min(e(v), rvj )
dan ulangi langkah 5. Langkah keenam:
h(v) = min(h(v), h( j ) + 1) dimana rvj > 0 . Proses pada langkah 6 ini disebut juga dengan proses relabel.
Pada langkah pertama, proses inisialisasi memiliki kompleksitas O(V ) . Kemudian langkah 2 memiliki kompleksitas O(V + A) yang merupakan kompleksitas BFS. Langkah 3 memiliki kompleksitas O(V ) , karena sebuah vertex paling banyak
hanya memiliki hubungan dengan V − 1 vertex. Berikutnya langkah 5 dan 6, memiliki kompleksitas O(V ) karena seperti pada langkah 3, sebuah vertex paling banyak hanya memiliki hubungan dengan V − 1 vertex. Pada algoritma ini, langkah 5 dan 6 paling banyak hanya dijalankan sebanyak 2 x V x V kali, sehingga total kompleksitas algoritma ini adalah O(V + A + 2V 3 ) = O(V 3 ) . Pembuktian : Proses relabeling yang terjadi pada suatu active vertex, hanya akan terjadi paling banyak V kali, karena paling banyak hanya ada V vertex yang terhubung dengan active vertex tersebut. Apabila active vertex tersebut selalu menjadi active vertex, maka pada
saat ke-V kali, vertex tersebut tidak akan pernah menjadi active vertex karena Excess(i) sudah terkirim kembali menuju vertex sumbernya.
27
2.10
Minimum-Cost Flow Problem minimum cost flow, dapat digambarkan sebagai berikut: diberikan
sebuah graph G = {V , A, c, u, s, t} , dimana s = vertex awal, t = vertex tujuan, s, t ∈ V dan u adalah kapasitas maksimum dari suatu arc, dan c adalah cost persatuan data pada suatu arc, c, u : A → R . Temukan jalur-jalur yang dapat mengalirkan data dari s menuju t
semaksimal mungkin dengan biaya seminimal mungkin. min
∑
cij xij
∑
x ji = b(i )
( i , j )∈ A
∑
( i , j )∈A
xij −
( i , j )∈ A
0 ≤ xij ≤ uij Untuk itu perlu ditambahkan sebuah properti dalam mentransformasi network kedalam graph, yaitu: apabila terdapat arc dari vertex i menuju vertex j, maka terdapat arc dari vertex j menuju vertex i, dimana c ji = −cij .
2.10.1 Kondisi Optimal yang Harus Dicapai Seperti problem shortest path yang telah ditulis pada subbab 2.5, untuk mendapatkan hasil optimal, maka harus memenuhi kondisi optimal seperti yang telah ditunjukkan oleh rumus (2.1). Problem minimum cost flow memiliki beberapa kondisi optimal sebagai berikut: •
Kondisi optimal negative cycle: sebuah feasible solution x* merupakan solusi dari minimum cost flow jika dan hanya jika G(x*) tidak memiliki negative cycle. Pembuktian: Graph pada problem network-flow dapat dipandang sebagai flow on arcs dan flow on path and cycles. 28
(a)
(b)
Gambar 2.11: (a) merupakan network flow yang dipandang sebagai flow on arcs. (b) merupakan network flow yang dipandang sebagai flow on path and cycle.
Ketika memandang minimum cost flow sebagai flow on path and cycle, diasumsikan P sebagai path, dan W sebagai cycle. Kemudian terdapat fungsi f sebagai flow, dan fungsi z sebagai ada atau tidaknya flow atau cycle pada arc tersebut,
sehingga
dapat
dirumuskan
sebagai
berikut:
xij = ∑ z ( p ) f ( p) + ∑ z ( w) f ( w) . Dari persamaan ini, terlihat bahwa flow on path p∈P
w∈W
and cycle dapat didekomposisikan menjadi flow on arcs, sebaliknya, flow on arcs dapat didekomposisikan menjadi flow on path and cycle, apabila setiap path dengan flow bernilai positif menghubungkan sebuah defecit vertex menuju sebuah excess vertex. Mengacu kepada perumusan problem minimum cost flow, serta kedua cara pandang terhadap network flow, maka apabila dalam graph terdapat r augmenting cycle (cycle yang dialiri oleh flow), maka:
29
∑
( i , j )∈ A
cij xij =
∑
cij xijo +
∑
cij xijo +
∑
cij xijo + ∑ c(Wk ) f (Wk )
( i , j )∈ A
=
( i , j )∈ A
=
( i , j )∈ A
∑
cij xij'
( i , j )∈G ( x o )
⎡ r ⎤ c zij (Wk ) f (Wk ) ⎥ ∑ o ij ⎢⎣∑ k =1 ⎦ ( i , j )∈G ( x ) r
k =1
∑
Dari hasil tersebut, maka dapat terlihat, bahwa
( i , j )∈ A
cij xij akan berkurang ketika
terdapat cycle yang memiliki cost negatif. •
Kondisi optimal reduced cost: sebuah feasible solution x* merupakan solusi optimal dari minimum cost flow jika dan hanya jika untuk beberapa node potential π memiliki kondisi reduced cost sebagai berikut: cijπ ≥ 0 untuk ∀(i, j ) ∈ G ( x*)
(2.7)
Pembuktian: Pertama, perhatikan kondisi optimal dari shortest path, dapat ditulis sebagai berikut: cijd = cij + d (i ) − d ( j ) ≥ 0 , dimana cijd adalah reduced cost dari shortest path
d (i ) dan d ( j ) . Apabila cijd = 0, maka arc (i, j ) merupakan jalur dari shortest path. Sekarang asosiasikan π (variable dual ) sebagai node potential. Berdasarkan konsep duality LP, maka reduced cost dari dual adalah cijπ = cij − π (i ) + π ( j ) . Berikut ini adalah properti yang menghubungkan antara primal dan dual: a) Untuk
∑
( i , j )∈P
sebuah
cijπ =
∑
( i , j )∈P
path
P
dari
node
s
cij − π ( s ) + π (t ) .
b) Untuk sebuah flow W, berlaku
∑
( i , j )∈W
cijπ =
30
∑
( i , j )∈W
cij .
menuju
node
t,
maka
Dengan memasukkan rumus (2.7) pada properti (b), maka
∑
( i , j )∈W
cijπ =
∑
( i , j )∈W
cij ≥ 0
sehingga graph G(x*) tidak memiliki negative cycle, dan sesuai dengan kondisi optimal negative cycle, maka kondisi optimal reduced cost terbukti.
•
Kondisi optimal complementary slackness: sebuah feasible solution x* merupakan solusi optimal dari minimum cost flow jika dan hanya jika untuk setiap reduced cost dari node potential π dan nilai flow x*, memenuhi complementary slackness optimal condition dimana (i, j ) ∈ A : jika cijπ > 0, maka xijπ = 0 jika 0 < xijπ < uij , maka cijπ = 0 jika cijπ < 0, maka cijπ = uijπ
Pembuktian: Dengan menggunakan keterangan yang terdapat pada kondisi optimal reduced cost, maka: (1) Jika
cijπ > 0, maka tidak diperbolehkan ada flow untuk arc ( j , i ) , karena
cijπ = −cπji .
(2) Jika 0 < xijπ < uij , maka terdapat flow baik arc (i, j ) , maupun arc ( j , i ) , sehingga agar dapat memenuhi kondisi optimal dari shortest path, maka cijπ = cπji = 0 . (3) jika cijπ < 0, , maka tidak diperbolehkan ada flow untuk arc (i, j ) .
31
2.10.2 Cycle Canceling Cycle canceling adalah suatu metode untuk menyelesaikan problem minimum cost flow, dengan memanfaatkan kondisi optimal negative cycle. Secara umum, metode ini memiliki langkah-langkah sebagai berikut: Langkah 1:
Cari basic feasible solution x* dengan menyelesaikan problem maximum flow pada graph.
Langkah 2:
Selama feasible solution x* masih mengandung negative cycle, lakukan langkah 3.
Langkah 3:
Cari negative cycle W −
Langkah 4:
hilangkan negative cycle tersebut dengan mengalirkan data sebanyak min(rij : (i, j ) ∈ W − ) .
Bagaimana cara mencari negative cycle pada graph ? Gunakan algoritma bellman ford untuk mencari jalur terpendek dari vertex s menuju vertex lainnya, dan setelah selesai, maka didapatkan jalur terpendek tersebut d = {d (0), d (1), d (2),..., d (V )} . Apabila terdapat negative cycle graph, maka kondisi optimal tidak akan pernah tercapai, dan lakukan langkah berikut ini untuk pengecekan: Langkah 1:
Lakukan langkah 2 sebanyak V kali.
Langkah 2:
Jika d ( j ) < d (i )+ cij , maka terdapat negative cycle.
Karena cij ≤ C dan xij ≤ U untuk semua (i, j ) ∈ A , maka cycle canceling dengan pemilihan negative cycle tanpa menggunakan aturan khusus ini, memiliki O( ACU ) proses canceling, dan pada setiap iterasi canceling, dilakukan algoritma bellman-ford sehingga memiliki kompleksitas O(VA2CU ) .
32
