BAB 2
LANDASAN TEORI
2.1 Shortest Path
Shortest path adalah pencarian rute atau path terpendek antara node yang ada pada
graph, biaya (cost) yang dihasilkan adalah minimum. Sedangkan menurut (Dublin.
2009) menemukan jalan terpendek dari total panjang jalan antara dua node grafik
diarahkan dengan panjang berkaitan dengan tepi masing-masing. Dalam pencarian
lintasanterpendek masalah yang dihadapi adalah mancari lintasan mana yang akan
dilaluisehingga didapat lintasan yang paling pendek dari satu verteks ke verteks
yanglain.
Ada beberapa macam persoalan lintasan terpendek, antara lain :
1. Lintasan terpendek antara dua buah verteks.
2. Lintasan terpendek antara semua pasangan verteks.
3. Lintasan terpendek dari verteks tertentu ke semua verteks yang lain
4. Lintasan terpendek antara dua buah verteks yang melalui beberapa
verteks tertentu(Boy,A.F. 2013).
Dalam pencarian lintasan terpendek ada beberapa algoritma yang dapat dipergunakan
namun, disini yang digunakan adalah algoritma Exhaustive Search dalam menentukan
lintasan terpendek dalam satuan kilometer (km)
Universitas Sumatera Utara
7
2.2 Graph
Suatu graph sederhana G adalah suatu pasangan terurut (V, E), dimana V adalah suatu
himpunan berhingga yang tak kosong yang elemen-elemennya disebut verteks dan E
adalah suatu himpunan garis yang menghubungkan dua elemen subset dari E yang
disebut edges (Iryanto. 2003). Contoh graph dapat dilihat seperti gambar 2.1.
v1 e4 v2
e1 e5
e3
v4
v3
e2
Gambar 2.1 Graph dengan 4 verteks dan 5 edges
Pada contoh diatas graph G = (V, E) dimana:
1. V adalah himpunan titik, simpul, verteks atau nodes dari G, yaitu
V = {v1, v2, v3, v4}
2. E adalah himpunan rusuk, edges, atau sisi dari G, yaitu
E = {e1, e2, e3, e4, e5}
2.2.1 Macam – macam Graph Menurut Arah dan Bobotnya
Menurut(Iryanto. 2003) macam-macam graph menurut arah dan bobotnya, graph
dibagi menjadi empat bagian, yaitu :
1. Graph berarah (digraph) dan berbobot: setiap edges mempunyai arah (yang
ditunjukkan dengan anak panah) dan bobot. Gambar 2.2 adalah contoh graph
berarah dan berbobot, yang terdiri dari tujuh verteks yaitu verteks A, B, C, D, E, F,
G dan 12 edges. Verteks A mempunyai dua edges yang masing-masing menuju ke
verteks B dan verteks C, verteks B mempunyai tiga edges yang masing-masing
menuju ke verteks C, verteks D dan verteks E dan seterusnya. Tiap-tiap edges
mempunyai arah dan bobot yang telah diketahui.
Universitas Sumatera Utara
8
2
2 B E
2
1
1
A
1 2 G
D
4 1
2
3
C 4
F
Gambar 2.2 Graph berarah dan berbobot
2. Graph tidak berarah dan berbobot: setiap edges tidak mempunyai arah tetapi
mempunyai bobot. Gambar 2.3 adalah contoh graph tidak berarah dan berbobot.
Edges yang menghubungkan antar verteks mempunyai bobot yang telah diketahui
namun tidak mempunyai arah.
B 2 E
2
2
A 1
1 G
1 D 2
4 1 2
C 3
F
4
Gambar 2.3 Graph tidak berarah dan berbobot
3. Graph berarah (digraph) dan tidak berbobot: setiap edges mempunyai arah tetapi
tidak mempunyai bobot. Gambar 2.4 adalah contoh graph berarah dan tidak
berbobot. B E
A
G
D
C
F
Gambar 2.4 Graph berarah dan tidak berbobot
Universitas Sumatera Utara
9
4. Graph tidak berarah dan tidak berbobot: setiap edges tidak mempunyai arah dan
tidak mempunyai bobot. Gambar 2.5 adalah contoh graph tidak berarah dan tidak
berbobot.
B E
A
G
D
C
F
Gambar 2.5 Graph tidak berarah dan tidak berbobot
2.3 Lintasan
Lintasan yang panjangnya n dari simpul awal v0 ke simpul tujuan vn di dalam graf G
ialah barisan berselang-seling simpul-simpul dan sisi-sisi yang berbentuk v0, e1, v1,
e2, v2, … , vn-1, en, vn sedemikian sehingga e1 = (v0, v1), e2 = (v1, v2), … , en =
(vn-1, vn) adalah sisi – sisi dari graf G (Rinaldi Munir, 2003). Jika graf yang ditinjau
merupakan graf sederhana, maka lintasan cukup dituliskan sebagai barisan simpul: v0,
v1, v2, …, vn-1, vn, karena antara dua buah simpul yang berurutan dalam lintasan
tersebut hanya terdapat satu sisi. Jika graf yang ditinjau memiliki sisi ganda, maka,
lintasan ditulis sebagai barisan berselang-seling antara simpul dan sisi: v0, e1, v1, e2,
v2, e3, …, vn-1, en, vn. Simpul dan sisi yang dilalui di dalam lintasan boleh berulang.
Sebuah lintasan yang semua simpulnya berbeda (setiap sisinya dilalui hanya sekali)
dikatakan lintasan sederhana.
2.4 Metode
Defenisi metode adalah urutan langkah-langkah logis penyelesaian masalah yang
disusun secara sistematis dan [Link] Logis merupakan kata kunci dalam Metode.
Langkah-langkah dalam metode harus logis dan harus dapat ditentukan bernilai salah
atau [Link] adalah teknik penyusunan langkah-langkah penyelesaian masalah
Universitas Sumatera Utara
10
dalam bentuk kalimat dengan jumlah kata terbatas tetapi tersusun secara logis dan
sistematis (Suarga. 2012). Sedangkan menurut whitten. et al (2004) metode yaitu
spesifik, tahap-tahap strategis untuk menyelesaikan satu tahap atau lebih dari
perkembangan sistem yang berulang.
Karena itu suatu metode harus dinyatakan dalam bentuk yang dapat dimengerti
oleh [Link] suatu pemroses harus :
1. Mengerti setiap langkah dalam Metode
2. Mengerjakan operasi yang bersesuaian dengan langkah tersebut.
3. Mekanisme pelaksanan metode oleh pemroses
Komputer hanyalah salah satu pemroses. Agar dapat dilaksanakan oleh komputer,
metode harus ditulis dalam notasi bahasa pemrograman sehingga dinamakan
[Link] program adalah perwujudan atau implementasi teknis. Metode yang
ditulis dalam bahasa pemrogaman tertentu sehingga dapat dilaksanakan oleh
[Link] penting metode yaitu :
1. Metode harus berhenti setelah mengerjakan sejumlah langkah terbatas.
2. Setiap langkah harus didefinisikan dengan tepat dan tidak berarti-dua
(Ambiguitas).
3. Metode memiliki nol atau lebih masukkan.
4. Metode memiliki nol atau lebih keluaran.
5. metode harus efektif (setiap langkah harus sederhana sehingga dapat
dikerjakan dalam waktu yang masuk akal).
2.5 Metode Exhaustive Search
Exhaustive search merupakan teknik pencarian solusi secara brute force pada masalah
yang melibatkan pencarian elemen dengan sifat khusus, biasanya di antara objek-
objek kombinatorik seperti permutasi, kombinasi, atau himpunan bagian dari sebuah
himpunan (Sani. 2006).
Universitas Sumatera Utara
11
Dari defenisi lain yang penulis kutip adalah metode exhaustive search adalah
metode yang terbaik dalam hal mencari solusi terbaik dengan sifat tertentu. Waktu
penyelesaiannya yang lama sebenarnya dapat dipersingkat dengan menggunakan
teknik heuristik, contohnya dengan mengeliminasi kemungkinan solusi yang tidak
mungkin menjadi solusi terbaik, ataupun dengan memadukanmetode tersebut dengan
metode [Link] pemecahan masalah adalah sebagai berikut :
a) Menyebutkan (Enumerasi) dari daftar (list) disetiap kemungkinan solusi secara
sistematis.
b) Mengevaluasi disetiap kemungkinan solusi satupersatu. Kemungkinan
beberapa solusi yangtidak layak bisa saja muncul, dan simpan solusiterbaik
yang ditemukan sampai proses terakhir(the best solusi found so far).
c) Bila pencarian berakhir, tampilkan solusi terbaik(the winner).
d) Membutuhkan waktu dan sumber daya yangbesar dalam mencari suatu solusi.
Persoalan rute terpendek tidak lain adalah menemukan sirkuit Hamilton dengan
bobot minimum. Metode exhaustive search untuk persoalan rute terpendek ini adalah:
a. Enumerasikan (list) semua sirkuitHamilton dari graf lengkap dengan n
buahsimpul.
b. Hitung (evaluasi) bobot setiap sirkuit Hamilton yang ditemukan pada langkah.
c. Pilih sirkuit Hamilton yang mempunyai bobot [Link] simpul a
adalah kota tempat dimulainya perjalanan (starting city).
Menurut (Maulina. 2008) adapun penulis sediakan contoh persoalan Travel Sales
person Problem dalam Metode exhaustive search dengan n=4 dapat ditunjukkan pada
gambar 2.6 sirkuit Hamilton .
:
Gambar 2.6 Penggambaran Graph Hamilton
Universitas Sumatera Utara
12
Keterangan Gambar 2.6:
(a) Graf yang memiliki Lintasan Hamilton : (c, b, a, d)
(b) Graf yang memiliki Sirkuit Hamilton :(a, b, c, d, a)
(c) Graf yang tidak memiliki lintasan maupunSirkuit Hamilton.
Misalkan simpul a adalah kota tempat dimulainya perjalanan (starting city).
Enumerasikan semua sirkuit Hamilton seperti tabel 2.1:
Tabel 2.1 Enumerasikan semua sirkuit Hamilton
Rute perjalanan (tour) Bobot
abcda 10+12+8+15 = 45
abdca 12+5+9+15 = 41
acbda 10+5+9+8 = 32
acdba 12+5+9+15 = 41
adbca 10+5+9+8 = 32
adcba 10+12+8+15 = 45
Ruteperjalananan terpendek adalah:
a→c→b→d→a
a→d→b→c→a, dengan bobot= 32.
Untuk 4 kota, terdapat 6 buah kemungkinan rute perjalanan (atau sirkuitHamilton).
Rute perjalananan terpendek adalah a-c-b-d-a atau a-d-b-c-a denganbobot = [Link]
perjalanan berawal dan berakhir pada simpul yang sama, makauntuk n buah simpul
semua rute perjalanan yang mungkin dibangkitkan denganpermutasi dari n – 1 buah
simpul. Permutasi dari n – 1 buah simpul adalah (n – 1). Pada contoh di atas, untuk n
= 6 akan terdapat (4 – 1)! = 3! = 6 buah ruteperjalanan.
Meskipun metode exhaustive secara teoritis menghasilkan solusi, namunwaktu
atau sumberdaya yang dibutuhkan dalam pencarian solusinya sangat [Link] dalam
beberapa literatur strategi algoritmik, contoh masalah yang seringdiasosiasikan
dengan exhaustive search atau brute force adalah masalah pencarian lintasan
terpendek. Meskipun metode exhaustive search tidak mangkus, namun nilai
plusnyaterletak pada keberhasilannya yang selalu menemukan solusi (jika
diberikanwaktu yang cukup).Metode exhaustive memberikan hasil pencarian rute
yang lebih optimum dan waktu yang singkat (Adipranata, et al. 2006).
Universitas Sumatera Utara
13
2.6 Kecerdasan Exhaustive Search
2.6.1 Backtracking
Backtracking merupakan perbaikan dari algoritma brute-force (exhaustive search).
Pada exhaustive search, semua kemungkinan solusi dieksplorasi satu per satu.
Backtracking, hanya pilihan yang mengarah ke solusi yang dieksplorasi, pilihan yang
tidak mengarah ke solusi tidak dipertimbangkan lagi , Memangkas (pruning) simpul-
simpul yang tidak mengarah ke solusi. Backtracking didasarkan pada pengamatan
bahwa hal tersebut sering dapat menolak solusi dengan melihat hanya sebagian kecil
dari itu. Misalnya, jika contoh SAT berisi klausa (x1∨x2), kemudian semua tugas
dengan x1=x=0 (yaitu,false) dapat langsung [Link] menempatkan dengan
berbeda, dengan cepat memeriksa dan membuat tugas parsial ini, Berikut adalah
bagaimana hal itu dilakukan. Mempertimbangkan φ formula Boolean(w,x,y,z)
specified dengan set persyaratan (w∨x∨y∨z), (w∨x), (x∨y), (y∨z), (z∨w), (w∨z).
( Dasgupta, et al. 2006).
Lebih secara abstraknya, algoritma backtracking yang memerlukan tes yang
terlihat di subproblem dan cepat menyatakan salah satu dari tiga hasil:
a. kegagalan: subproblem telah tidak
b. ada solusi.
c. sukses: solusi untuk subproblem ditemukan. ketidakpastian.
2.6.2 Branch-and-bound
Branch-and-bound memiliki defenisi yang sama dengan backtracking, namunbranch-
and-bound ruang solusi dibangun dengan skema Breadth-First Search (BFS). Prinsip
yang sama dapat generalized dari pencarian masalah seperti SAT untuk optimasi
masalah. Untuk kepastian, katakanlah memiliki masalah minimalisasi; maksimalisasi
akan mengikuti pola yang sama. Pada kenyataannya, akan menjadi fixed seluruh
algoritma. Sub problem sesuai adalah untuk studi penyelesaian terbaik dari tour, yaitu
pelengkap jalan termurah dengan menengah node V−S.
Pemberitahuan bahwa masalah awal adalah bentuk [,{},] untuk setiap ∈V Oleh karena
itu, biaya adalah sedikitnya jumlah dari berikut:
a. tepiringandariuntukV−S.
b. ringan tepi dari b ke V − S.
c. minimal mencakup pohon V − S.( Dasgupta, et al. 2006).
Universitas Sumatera Utara
14
2.7 Mempercepat Metode Exhaustive Search
Di dalam metode-metode yang termasuk heuristic search, fungsi heuristik memainkan
peranan yang sangat menentukan. Suatu fungsi dapat diterima sebagai fungsi heuristik
jika biaya perkiraan yang dihasilkan tidak melebihi dari biaya sebenarnya ( Suyanto.
2007).Adapun teknik mempercepat metode exhaustive searchadalah sebagai berikut
penjelasannya :
1. Agoritma exhaustive search dapat diperbaiki kinerjanya sehingga tidak perlu
melakukan pencarian terhadap semua kemungkinan solusi.
2. Salah satu teknik yang digunakan untuk mempercepat pencarian solusi adalah
teknik heuristik (heuristic).
3. Teknik heuristik digunakan untuk mengeliminasi beberapa kemungkinan
solusi tanpa harus mengeksplorasinya secara penuh. Selain itu, teknikheuristik
juga membantu memutuskan kemungkinan solusi mana yang pertama kali
perlu dievaluasi.
4. Heuristik adalah seni dan ilmu menemukan (art and science of discovery).
Kata heuristik diturunkan dari Bahasa Yunani yaitu “eureka” yang berarti
“menemukan” (to find atau to discover).
5. Heuristik berbeda dari metode karena heuristik berlaku sebagai panduan
(guideline), sedangkan metode adalah urutan langkah-langkah penyelesaian.
6. Heuristik mungkin tidak selalu memberikan hasil yang diinginkan, tetapi
secara ekstrim ia bernilai pada pemecahan masalah.
7. Heuristik yang bagus dapat secara dramatis mengurangi waktu yang
dibutuhkan untuk memecahkan masalah dengan cara mengeliminir kebutuhan
untuk mempertimbangkan kemungkinan solusi yang tidak perlu.
8. Dalam bidang ilmu komputer, heuristik adalah teknik yang dirancang untuk
memecahkan masalah dengan mengabaikan apakah solusi yang dihasilkan
dapat dibuktikan (secara matematis) benar, tapi biasanya menghasilkan solusi
yang bagus.
9. Heuristik tidak menjamin selalu dapat memecahkan masalah, tetapi seringkali
memecahkan masalah dengan cukup baik untuk kebanyakan masalah, dan
seringkali pula lebih cepat daripada pencarian solusi secara lengkap.
Universitas Sumatera Utara
15
Mulai
Input
node
awal dan
tujuan
Mencari node
dengan nilai
terkecil
Coba semua kemungkinan
yang menghasilkan jarak
total terkecil
Pilih node terdekat Jarak antar
dengan node asal pusat
perbelanjaan
Pilih node
terdekat dari rute
terakhir
Jika menghasilkan Tampilkan
jarak total terkecil? Lintasan
Tidak Ya
Lintasan
tidak Selesai
ditemukan
Gambar 2.7 Flowchart Metode Exhaustive Search
Langkah berikut setelah pencarian kombinasi adalah perhitungan bobot atau jarak
total dari titik-titik yang telah terbentuk dalam suatu [Link] metode exhaustive
search secara teoritis menghasilkan solusi, namun waktu atau sumber daya yang
dibutuhkan dalam pencarian solusinya sangat besar (Boy,A.F, et al. 2013).
Universitas Sumatera Utara
16
2.8 Tinjauan Penelitian Terdahulu
Penelitian shortest path problem sudah banyak dilakukan dan dikembangkan
sebagaimana dalam studi kasusnya masing-masing adalah sebagai berikut:
Dari hasil penelitian Yulian Sani(2006)menyatakan bahwa pemecahan
permasalahan pada TSP ini dilakukan untuk menemukan solusi pada TSP, Salah
satunya adalah menggunakan metode Brute Force dengan teknik Exhaustive Search,
serta mengkoputerisasikannya untuk menghasilkan perangkat lunak yang dapat
mempermudah menemukan solusi yang paling optimal.
Dari hasil penelitian Rudy Adipranata, Felicia Soedjianto, & Wahyudi Tjondro
(2006) menyatakan bahwa metode yang dibandingkan dalam pencarian rute adalah
metode exhaustive, genetic algorithm dan neural network hopfield dimana ketiga
metode ini memiliki kelebihan dan kekurangan yang berbeda-beda. ketiga metode
tersebut dapat disimpulkan bahwa untuk kasus dengan skala kecil (n < 10), metode
exhaustive memberikan hasil pencarian rute yang lebih optimum dan waktu yang
singkat. Di samping itu, genetic algorithm harus memiliki input yang tepat untuk
memberikan hasil optimum, sedangkan neural network hopfield memiliki hasil rute
yang kurang memuaskan untuk kasus dengan skala besar.
Dari hasil penelitian Ahmad Fitri Boy, [Link].,[Link]. Nurcahyo Budi Nugroho,
[Link]. [Link] (2013) menyatakan bahasa pemograman PHP untuk tampilan
Node,jalur dan jarak diinput secara manual dan aplikasi ini berhasil menemukan
ruteterdekat menuju bandara Polonia dengan menggunakan Metode Exhaustive
Search. Hasil program ini menunjukkan bahwa sistem ini dapat digunakan
olehmasyarakat yang ingin menuju Bandara Polonia Medan yang membutuhkan
petunjuk terhadap rute terdekat menuju bandara tersebut.
Dari hasil penelitian Nico Saputro dan Joice Aritonang (2005) menyatakan bahwa
metode genetik akan dibandingkan dengan metode exhaustive search untuk
mengetahui pemampatan matriks jarang dengan metode genetik sudah maksimal atau
belum.
Universitas Sumatera Utara