PENCARIAN RUTE TERPENDEK

DENGAN MENGUNAKAN DYNAMIC PROGRAMMING

M. FATHONI1)

ARI TRIPRABOWO2)

1) NIM : 080916062, S1 Sistem Informasi, Universitas Airlangga Surabaya, email: m.fathoni@mail.com

2) NIM : 080916047, S1 Sistem Informasi, Universitas Airlangga Surabaya, email: ari.triprabowo@gmail.com

Abstract: Permasalahan pencarian jalur terpendek adalah permasalahan umum yang sering terjadi di dunia

nyata. Untuk menyelesaikannya terdapat banyak metode yang bisa digunakan, salah satunya adalah dengan

menggunakan metode dynamic programming. Dengan menggunakan metode ini, hasil dari pencarian jalur akan

menjadi sangat optimum.

Keywords: dynamic programming, algorithm, shortest path

Pemrograman dinamis merupakan suatu

teknik analisa kuantitatif untuk membuat tahapan

keputusan yang saling berhubungan. Teknik ini

menghasilkan prosedur yang sistematis untuk mencari

keputusan dengan kombinasi yang optimal.

Pemrograman dinamis membagi

permasalahan menjadi beberapa tahap keputusan,

dimana hasil keputusan dari satu tahap akan

mempengaruhi keputusan dari tiap-tiap tahapan

selanjutnya.

Berbeda dengan pemrograman linier, dalam

pemrograman dinamis tidak ada formulasi matematis

standar. Tetapi, pemrograman dinamis adalah sebuah

pendekatan umum untuk pemecahan masalah, dan

perhitungan yang digunakan harus dikembangkan

agar sesuai dengan tiap-tiap situasi tertentu. Oleh

karenanya, diperlukan suatu kepandaian dan

pemahaman pada struktur umum permasalahan untuk

mengetahui kapan dan bagaimana suatu permasalahan

harus dipecahkan dengan pemrograman dinamis.

Ada 2 perbedaan mendasar antara

pemrograman dinamis dan pemrograman linier.

Pertama, tidak ada algoritma (seperti metode simplex)

yang bisa diprogramkan untuk memecahkan semua

permasalahan. Sebaliknya, pemrograman dinamis

adalah teknik yang mengarahkan kita untuk

memecahkan masalah yang sulit menjadi tahapan dari

beberapa masalah yang lebih mudah, yang kemudian

dievaluasi berdasarkan tahapan. Kedua, pemrograman

linier adalah suatu metode yang menghasilkan solusi

satu tahap (single stage solution) atau satu periode

waktu. Pemrograman dinamis mempunyai

kemampuan untuk mencari solusi optimal dari suatu

permasalahan menjadi beberapa permasalahan dalam

satuan waktu yang lebih kecil dan memecahkan tiap

permasalahan tersebut dengan optimal (misal

permasalahan dengan jangka waktu satu tahun dapat

dibagi menjadi 12 permasalahan dengan jangka waktu

1 bulan). Jadi pemrograman dinamis menggunakan

pendekatan banyak tahap (multistage).

TAHAPAN PADA DYNAMIC

PROGRAMMING Pemecahan masalah dengan menggunakan

pemrrograman dinamis mempunyai 4 tahapan :

1. Memecah permasalah asli (original

problem) menjadi bagian permasalahan

(subproblem) yang juga disebut sebagai

tahapan (stage), dengan aturan

keputusan di tiap-tiap tahapan.

2. Memecahkan tahapan terakhir dari

permasalahan dengan semua kondisi dan

keadaan yang memungkinkan

3. Bekerja mundur dari tahap terakhir, dan

memecahkan tiap tahap. Hal ini

dikerjakan dengan mencari keputusan

optimal dari tahap tersebut sampai

dengan tahap terakhir.

4. Solusi optimal dari permasalhan

didapatkan jika semua tahap sudah

terpecahkan.

Salah satu contoh umum dari penggunaan

pemrograman dinamis adalah pencarian rute

terpendek, berikut adalah contoh pemecahan masalah

rute terpendek.

PEMBAHASAN PERMASALAHAN RUTE

TERPENDEK Agus akan melakukan perjalanan dari Jakarta

menuju Bandung, dengan melewati kota / tempat

seperti di peta perjalanan Gambar 1. Tanda bulatan

(node) mewakili kota, tanda panah (arc) mewakili

jalan raya antar kota / tempat, jarak antar kota tertulis

di tanda panah.

Gambar 1 : Peta Perjalanan

Langkah 1 :

Tahap pertama adalah membagi permasalahan

menjadi subproblem. Gambar 2 menunjukan tahapan

dalam problem ini. Dalam pemrograman dinamis,

biasanya dimulai dari bagian terakhir problem,

sebagai tahap 1, dan bekerja mundur sampai dengan

permulaan problem atau jaringan.

Tabel 1 menunjukan jarak arc antar tahapan.

Gambar 2 : Tahapan pencarian rute terpendek

Tabel 1 : Jarak Tiap Arc

Stage Arc Jarak

1 5 – 7

6 – 7

14

2

2 4 – 5

3 – 5

3 – 6

2 – 5

2 – 6

10

12

6

4

10

3 1 – 4

1 – 3

1 – 2

4

5

2

Langkah 2 :

Pada langkah berikut, kita memecahkan

stage 1, bagian terakhir dari jaringan, dalam problem

ini node 7. Pada tahap 1, jalur terpendek hanya terdiri

dari node 5 dan node 6 ke node 7. Kita gambarkan

jarak minimum tersebut dalam kotak di node awal di

tahap 1, yaitu node 5 dan node 6.

Gambar 3. Solusi Stage 1, One Stage Problem

Tabel 2 : Stage 1

Node Awal Jarak

Terpendek ke

Node 7

Arc dalam

jalur

5 14 5 – 7

6 2 6 – 7

Langkah 3 :

Solusi stage 2 dapat dilihat di gambar 4. Pada

node 4, jarak terpendek ke node 7 adalah arc 4 – 5 dan

5 – 6 dengan jarak total 14. Pada node 3, jalur

terpendek adalah arc 3 – 6 dan 6 – 7 dengan jarak

minimum 8. Pada node 2, jalur terpendek adalah 2 – 6

dan 6 – 7 dengan jarak minimum 12.

Gambar 4 : Solusi Stage 2, Two Stage Problem

Tabel 3 : Stage 2

Node Awal Jarak

Terpendek ke

Node 7

Arc dalam

jalur

4 24 4 – 5

5 – 7

3 8 3 – 6

6 – 7

2 12 2 – 6

6 – 7

Untuk mendapatkan solusi optimal pada tiap-

tiap tahap, yang harus kita perhitungkan adalah arc ke

tahap berikutnya dan solusi optimal dari tahap

berikutnya. Pada stage 3, kita hanya perlu

memperhitungkan 3 arc yang mengarah ke stage 2 (1

– 2, 1 – 3, dan 1 – 4) dan hasil optimal di stage 2,

yang telah dicatat dalam tabel sebelumnya.

Solusi stage 3 terlihat pada gambar 5

Gambar 5 : Solusi Stage 3, Three Stage Problem

Tabel 4 : Stage 3

Node Awal Jarak

Terpendek ke

Node 7

Arc dalam

jalur

1 13 1 – 3

3 – 6

6 – 7

Solusi akhir dari problem tersebut adalah

seperti terlihat di tabel diatas, jalur yag ditempuh

adalah 1 – 3, 3 – 6, dan 6 – 7 seperti terlihat di gambar

6, dengan panah dicetak tebal.

Gambar 6 : Solusi Akhir.

Jadi rute terpendek yang dapat ditempuh oleh

Agus adalah Jakarta – Ciawi – Puncak – Bandung.

DAFTAR PUSTAKA Farmer, J. 2008. Introduction to Dynamic

Programming.

(http://20bits.com/article/introduction-to-

dynamic-programming, diakses pada 24 April

2012)

Wahyujati, A. 2008. Dynamic Programming.

Trick, M. A. 1997. A Tutorial on Dynamic

Programming.

(http://mat.gsia.cmu.edu/classes/dynamic/node

8.html, diakses pada 24 April 2012)