6

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

aksi 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

7

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 Sebagian besar instruksi hanya dieksekusi sekali. Jika semua instruksi

dari sebuah program memiliki properti ini maka running time program ini disebut konstan.

log N 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.

N Running time ini disebut linear dimana umumnya proses dilakukan pada setiap elemen input. Situasi ini optimal untuk algoritma yang harus memproses sejumlah N input.

N log N Runnig time ini disebut linearithmic dan terjadi saat algoritma memecahkan masalah dengan membaginya menjadi subproblem-subproblem yang lebih kecil, memecahkan subproblem tersebut masing-masing secara independen dan menggabungkan semua solusi-solusinya.

N2 Running time ini disebut quadratic, umumnya terjadi pada saat algoritma harus memproses setiap pasangan data (misalnya double-nested loop).

2N 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.

8

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

0n yang bernilai positif, sehingga 0 . ( ) ( )c g n f n≤ ≤ untuk 0n n≥ }. 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.

9

Misal:

Terdapat fungsi ( )g n , maka ( ( )) { ( ) :g n f nΘ = terdapat 2 nilai konstan 1c dan 2c

dan 0n yang bernilai positif, sehingga 1 20 . ( ) ( ) . ( )c g n f n c g n≤ ≤ ≤ untuk semua 0n n≥ }

Contoh kasus:

Pada algoritma insertion sort, pada kondisi rata-rata, terdapat 21 32

n n− operasi,

maka average case dari algoritma ini adalah 2 2 21 2

1 32

c n n n c n≤ − ≤ untuk semua 0n n≥ .

Lalu bagi setiap sisi dengan 2n , sehingga pertidaksamaan tersebut

menjadi 1 21 32

c cn

≤ − ≤ , maka pada saat 7n = nilai 11

14c ≤ , dan 2

12

c ≥ . Karena terdapat 2

buah nilai konstan tersebut, maka average case algoritma ini adalah 2 21 3 ( )2

n n n− = Θ .

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 0n

yang bernilai positif, sehingga 0 ( ) . ( )f n c g n≤ ≤ untuk semua 0n n≥ }.

Contoh kasus:

Pada algoritma insertion sort, 21( ) 32

g n n n= − , 12

c = , maka 2 21 3 ( )2

n n n− = Ο ,

yaitu pada saat data diinput terurut secara terbalik.

10

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.

5

4

7

6

3

2

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

11

• 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

12

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.

13

1 2 3 4 5 6 7 8 9

headtail

a.

4 9

1 2 3 4 5 6 7 8 9

head tail

c.

7 1 12 4 9

1 2 3 4 5 6 7 8 9

head tail

b.

5 4 9 1 13 17 3

1 2 3 4 5 6 7 8 9

headtail

d.

5 1 13 17 3

1 2 3 4 5 6 7 8 9

headtail

e.

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 )1(O .

Pada Standart Template Library (STL) yang terdapat dalam bahasa pemrograman

C++, sudah terdapat fungsi-fungsi yang mendukung operasi queue. Semuanya terdefinisi

dalam library <queue> seperti .push(…) yang berfungsi sebagai enqueue, .front() untuk

14

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

vertex 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 (1)O , 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+ .

15

0

1 2

3

4

5

6

7

Q 1

0

1 2

3

4

5

6

7

Q 0 2

0

1 2

3

4

5

6

7

Q 2

0

1 2

3

4

5

6

7

Q 3

a. b.

c. d.

0

1 2

3

4

5

6

7

Q 4e. 5

0

1 2

3

4

5

6

7

Q 5f. 6

0

1 2

3

4

5

6

7

Q 6g. 7

0

1 2

3

4

5

6

7

Q 7h.

0

1 2

3

4

5

6

7

Q.

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.

16

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:

,j i i jd d w≤ + (2.1)

Algoritma Bellman Ford menggunakan persamaan di atas, dengan langkah-langkah

sebagai berikut:

Langkah 1: Sebagai inisialisasi awal, set semua ( )i i Vd → ∈ = ∞ , dan set 0sd = .

Langkah 2: Lakukan langkah 3 sebanyak A kali.

Langkah 3: Untuk setiap ijw 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 .

17

0

oo

oo

oo

oo

6

7

-2

5

8

2

7

9

-3

-4s

t

u

v

w

t va.

0

6

7

oo

oo

67

-2

5

8

2

7

9

-3

-4s

u w

t vb.

0

6

7

4

2

6

7

-2

5

8

2

7

9

-3

-4s

u w

t v

c.

0

2

7

4

2

6

7

-2

5

8

27

9

-3

-4s

u wd.

0

2

7

4

-2

6

7

-2

5

8

2

7

9

-3

-4s

u we.

t v

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

0 1 2{ , , ,..., }kp v v v v= , dimana 0v 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.

18

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 1 2 3{ , , ,..., }nc c c c c= . 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:

19

• 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 – ic .

• 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: [ ] min( [ ], [ ] 1)idp m dp m dp m c= − + .

• 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 = ic to M do [ ] min( [ ], [ ] 1)idp j dp j dp j c= − +

2.8 Linear Programming (LP)

Linear programming, dapat digambarkan sebagai berikut: Diberikan matriks A

dengan ordo m x n bertipe integer, dimana 'ia sebagai baris, dan jx sebagai kolom.

20

Kemudian terdapat sebuah batas ib , dan sebuah konstanta jc . Dalam general form LP,

hal tersebut dituliskan sebagai berikut:

min 'c x 'i ia x b= i = 1, 2, 3, …, m

'i ia x b≥ i = 1, 2, 3, …, m

0jx ≥ j = 1, 2, 3, …, n

0jx ≠ 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:

,i ja = besar nutrisi ke j yang terkandung dalam bahan makanan yang ke i dimana

i m≤ dan j n≤ .

ib = kebutuhan nutrisi yang ke i, i m≤

jx = jumlah makanan ke j yang dikonsumsi, j n≤

jc = 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≥

0x ≥

21

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

min 'c x 'i ia x b= i = 1, 2, 3, …, m

'i ia x b≥ i = 1, 2, 3, …, m

0jx ≥ j = 1, 2, 3, …, n

0jx ≠ j = 1, 2, 3, …, n

max 'bπ 'j ja cπ = j = 1, 2, 3, …, n

'j ja cπ ≤ j = 1, 2, 3, …, n

0jπ ≥ i = 1, 2, 3, …, m

0jπ ≠ 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 ja

22

adalah jc , dan standar nutrisi yang ke i yang harus dikosumsi oleh seorang manusia

sebesar ib , 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 1 1

m n

i i j ji j

b c xπ= =

≤∑ ∑ .

Pembuktian:

Dengan menggunakan canonical form pada dua contoh sebelumnya sebagai

primal dan dual, pertama kalikan pertidaksamaan ke-2 dari canonical form pertama

dengan π , sehingga didapatkan pertidaksamaan 1 1 1

m m n

i i i ij ji i j

b a xπ π= = =

⎡ ⎤≤ ⎢ ⎥

⎣ ⎦∑ ∑ ∑ ,

kemudian kalikan pertidaksamaan ke-2 dari canonical form ke-2 dengan x, sehingga

didapatkan pertidaksamaan 1 1 1

n m n

j ij i j jj i j

x a x cπ= = =

⎡ ⎤ ≤⎢ ⎥⎣ ⎦∑ ∑ ∑ , karena sisi kanan dari

pertidaksamaan pertama sama dengan sisi kiri dari pertidaksamaan kedua, maka

berlaku 1 1

m n

i i j ji j

b c xπ= =

≤∑ ∑ .

Dalam teori ini, dapat disimpulkan, bahwa apabila terdapat optimal feasible solution

untuk primal dan dual, maka 1 1

m n

i i j ji j

b c xπ= =

=∑ ∑ .

• Teori Complementary Slackness Optimality Conditions, yaitu sebuah feasible

solution x dari primal dan sebuah feasible solution π dari dual merupakan optimal

23

feasible solution untuk primal dan dual, jika dan hanya jika keduanya memiliki

properti dari complementary slackness, yaitu: 1

0n

i ij j ij

a x bπ=

⎡ ⎤⎛ ⎞− =⎢ ⎥⎜ ⎟

⎢ ⎥⎝ ⎠⎣ ⎦∑ untuk setiap

1 i m≤ ≤ , dan 1

0m

j j ij ii

x c a π=

⎡ ⎤⎛ ⎞− =⎢ ⎥⎜ ⎟⎝ ⎠⎣ ⎦∑ untuk setiap 1 j n≤ ≤ .

Pembuktian:

Dari pembuktian terhadap teori weak duality, didapatkan pertidaksamaan

,1 1 1 1

m m n n

i i i j i j j ji i j j

b a x c xπ π= = = =

≤ ≤∑ ∑∑ ∑ (2.2)

karena x dan π merupakan optimal feasible solution, maka pertidaksamaan tersebut

diubah menjadi persamaan. Kemudian rumus (2.2) tersebut dapat ditulis sebagai

berikut: 1 1

0m n

i ij j ii j

a x bπ= =

⎡ ⎤⎛ ⎞− =⎢ ⎥⎜ ⎟

⎢ ⎥⎝ ⎠⎣ ⎦∑ ∑ , dan karena , 0x π ≥ , 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:

1 10

n m

j j ij ij i

x c a π= =

⎡ ⎤⎛ ⎞− =⎢ ⎥⎜ ⎟⎝ ⎠⎣ ⎦

∑ ∑ , dan karena , 0x π ≥ , maka agar hal tersebut dapat terjadi,

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 ijc A∈ .

24

s t

3

2

1

4

1

1

3

1

4

2

a.

s t

3, (2)

2, (2)

1

4, (2)

1, 1

1, (1)

3, (3)

1, (1)

4, (4)

2, (2)

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

flow, dan merupakan properti dari hampir semua problem network-flow, yaitu:

• Residual network / flow.

Residual network merupakan sisa kapasitas tampung maksimum dari suatu arc.

ij ij ijr c f= − (2.3)

ijr = sisa kapasitas untuk arc yang menghubungkan vertex i menuju vertex j .

ijc = kapasitas.

ijf = 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.

25

ij ij ijr c f= − (2.4.1)

ji ijr f= ( 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:

{ }

( )

,

ij ijj V j V

e i r r

i V s t∈ ∈

= −

∈ −

∑ ∑ (2.5)

Apabila ( ) 0e i < , maka vertex tersebut merupakan deficit vertex, dan apabila

( ) 0e i > , maka vertex tersebut merupakan excess vertex, sedangkan apabila ( ) 0e i = ,

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:

( )

( ) 0

h ii V

h t

= ∞∀ ∈

= (2.6.1)

26

( ) min( ( ), ( ) 1) : ( , )h i h i h j 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 langkah-

langkah sebagai berikut:

Langkah pertama: merupakan langkah inisialisasi. Set ( ) 0,e i 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 ( ) sie i c= 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( ( ), )vje v r dari vertex v ke vertex j, dimana vertex j harus

memenuhi ( ) ( ) 1h j h v= − dimana vjr > 0. Apabila tidak ada

satupun vertex j yang memenuhi kondisi tersebut, maka lanjutkan

langkah 6, jika tidak, ubah nilai-nilai tersebut sebagai berikut:

27

( ) ( ) min( ( ), )

( ) ( ) min( ( ), )

min( ( ), )

min( ( ), )

vj

vj

vj vj vj

jv jv vj

e v e v e v r

e j e j e v r

r r e v r

r r e v r

= −

= +

= −

= +

dan ulangi langkah 5.

Langkah keenam: ( ) min( ( ), ( ) 1)h v h v h j= + dimana 0vjr > . 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 1V − vertex. Berikutnya langkah 5 dan 6, memiliki

kompleksitas ( )O V karena seperti pada langkah 3, sebuah vertex paling banyak hanya

memiliki hubungan dengan 1V − 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 3 3( 2 ) ( )O V A V O V+ + = .

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.

28

2.10 Minimum-Cost Flow

Problem minimum cost flow, dapat digambarkan sebagai berikut: diberikan

sebuah graph },,,,,{ tsucAVG = , dimana s = vertex awal, t = vertex tujuan, Vts ∈, dan

u adalah kapasitas maksimum dari suatu arc, dan c adalah cost persatuan data pada suatu

arc, RAuc →:, . Temukan jalur-jalur yang dapat mengalirkan data dari s menuju t

semaksimal mungkin dengan biaya seminimal mungkin.

min ( , )

ij iji j A

c x∈∑

( , ) ( , )( )ij ji

i j A i j Ax x b i

∈ ∈

− =∑ ∑

0 ij ijx u≤ ≤

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 ijji cc −= .

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.

29

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

( ) ( ) ( ) ( )ijp P w W

x z p f p z w f w∈ ∈

= +∑ ∑ . Dari persamaan ini, terlihat bahwa flow on path

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:

30

'

( , ) ( , ) ( , ) ( )o

oij ij ij ij ij ij

i j A i j A i j G x

c x c x c x∈ ∈ ∈

= +∑ ∑ ∑

( , ) 1( , ) ( )

( ) ( )o

ro

ij ij ij ij k ki j A ki j G x

c x c z W f W∈ =∈

⎡ ⎤= + ⎢ ⎥⎣ ⎦∑ ∑ ∑

( , ) 1

( ) ( )r

oij ij k k

i j A k

c x c W f W∈ =

= +∑ ∑

Dari hasil tersebut, maka dapat terlihat, bahwa ( , )

ij iji j A

c x∈∑ 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:

0ijcπ ≥ untuk ( , ) ( *)i j G x∀ ∈ (2.7)

Pembuktian:

Pertama, perhatikan kondisi optimal dari shortest path, dapat ditulis sebagai

berikut: ( ) ( ) 0dij ijc c d i d j= + − ≥ , dimana d

ijc adalah reduced cost dari shortest path

( )d i dan ( )d j . Apabila dijc = 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 ( ) ( )ij ijc c i jπ π π= − + . Berikut ini

adalah properti yang menghubungkan antara primal dan dual:

a) Untuk sebuah path P dari node s menuju node t, maka

( , ) ( , )

( ) ( )ij iji j P i j P

c c s tπ π π∈ ∈

= − +∑ ∑ .

b) Untuk sebuah flow W, berlaku ( , ) ( , )

ij iji j W i j W

c cπ

∈ ∈

=∑ ∑ .

31

Dengan memasukkan rumus (2.7) pada properti (b), maka ( , ) ( , )

0ij iji j W i j W

c cπ

∈ ∈

= ≥∑ ∑

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 0,ijcπ > maka 0ijxπ =

jika 0 ,ij ijx uπ< < maka 0ijcπ =

jika 0,ijcπ < maka ij ijc uπ π=

Pembuktian:

Dengan menggunakan keterangan yang terdapat pada kondisi optimal

reduced cost, maka:

(1) Jika 0,ijcπ > maka tidak diperbolehkan ada flow untuk arc ( , )j i , karena

ij jic cπ π= − .

(2) Jika 0 ,ij ijx uπ< < maka terdapat flow baik arc ( , )i j , maupun arc ( , )j i , sehingga

agar dapat memenuhi kondisi optimal dari shortest path, maka 0ij jic cπ π= = .

(3) jika 0,ijcπ < , maka tidak diperbolehkan ada flow untuk arc ( , )i j .

32

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( : ( , ) )ijr 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 { (0), (1), (2),..., ( )}d d d d 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 ( ) ( ) ijd j d i c< + , maka terdapat negative cycle.

Karena ijc C≤ dan ijx 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 2( )O VA CU .