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
e5
e1
v4 e2
v2
e3
v3
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
B
2
E 2
1
1
A
2
1 D
1
4
G
2 3 4
C
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.
2
B
E
2
2
1
A
1
G
D
1
2
1
4
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 logis.Kata Logis merupakan kata kunci dalam Metode. Langkah-langkah dalam metode harus logis dan harus dapat ditentukan bernilai salah atau benar.Metode 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 pemroses.Jadi 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 program.Jadi program adalah perwujudan atau implementasi teknis. Metode yang ditulis dalam bahasa pemrogaman tertentu sehingga dapat dilaksanakan oleh komputer.Ciri 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 objekobjek 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 lain.Strategi 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 terkecil.Misalkan 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 abdca acbda acdba adbca adcba
10+12+8+15 = 45 12+5+9+15 = 41 10+5+9+8 = 32 12+5+9+15 = 41 10+5+9+8 = 32 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 = 32.Karena 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 besar.Di 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) simpulsimpul 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 dihilangkan.Untuk 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, namunbranchand-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 dengan node asal
Jarak antar pusat perbelanjaan
Pilih node terdekat dari rute terakhir
Jika menghasilkan jarak total terkecil? Tidak Lintasan tidak ditemukan
Tampilkan Lintasan Ya Selesai
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 rute.Meskipun 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, S.Kom.,M.Kom. Nurcahyo Budi Nugroho, S.Kom. M.Kom (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
