BAB 2
LANDASAN TEORI
2.1. Pengertian Algoritma Algoritma adalah urutan atau deskripsi langkah-langkah untuk memecahkan suatu masalah. Algoritma merupakan jantung ilmu komputer atau informatika. Banyak cabang dari ilmu komputer yang diacu dalam terminologi algoritma, misalnya algoritma perutean (routing) pesan di dalam jaringan komputer, algoritma bresenham untuk menggambar garis lurus (bidang grafika komputer), algoritma Knuth-Morris-Pratt untuk mencari suatu pola di dalam teks (bidang information retrievel), dan sebagainya (Munir, 2011). 2.2.Shortest Path (Jarak Terpendek) Persoalan mencari jarak terpendek di dalam graf merupakan salah satu persoalan optimisasi.Graf yang digunakan dalam pencarian jarak terpendek adalah graf berbobot (weighted graph), yaitu graf yang setiap sisinya diberikan suatu nilai atau bobot. Kata terpendek berbeda-beda maknanya bergantung pada tipikal persoalan yang akan diselesaikan. Namun, secara umum terpendek berarti meminimisasi bobot pada suatu lintasan dalam graf (Triansyah, 2013). 2.3.Teori Dasar Graf Teori graf merupakanpokok bahasan yang sudah tua usianya namun memiliki banyak terapan dalam kehidupan sehari-hari sampai saat ini. Graf digunakan untuk merepresentasikan objekobjek diskrit dan hubungan antarampai saat ini. Graf digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut. Banyak persoalan pada dunia nyata yang sebenarnya merupakan representasi visual dari graf. Contoh salah satu representasi visual dari graf adalah peta. Banyak hal yang dapat digali dari representasi tersebut, diantaranya adalah menentukan jarak terpendek dari satu tempat ke tempat lain (Pradhana, 2006). Suatu graf G didefenisikan sebagai pasangan himpunan (V,E)yang dalam hal ini : V = himpunan tidak kosong dari simpul-simpul (vertices atau node): {V1,V2,...,Vn}
Universitas Sumatera Utara
E
=
himpunan sisi (edges atau arcs) yang menghubungkan sepasang simpul:
{E1,E2,...,En}
Atau dapat ditulis singkat notasi G = (V,E)
2.3.1. Grafsederhana dan Graftak-sederhana Graf sederhana (simple graph) yaitu graf yang tidak memiliki gelang maupun sisi-ganda. Sedangkan Graf tidak sederhana (unsimple graph) yaitu graf yang memiliki gelang maupun sisi ganda. Ada dua macam graf tak-sederhana, yaitu graf ganda (multigraph) dan graf semu (pseudograph). Graf ganda adalah graf yang memiliki sisi ganda, sedangkan graf semu adalah graf yang memiliki gelang. Sebagai contoh definisi dari graf pada gambar 1 berikut
(a)
(b)
(c)
Gambar 2.1Beberapa Graf a)GrafSederhana, b)Graf Ganda, c)Graf Semu
2.3.2. Graf berarah dan Graf tak-berarah Graf berarah (directed graph) merupakan graf yang setiap sisinya diberikan orientasi arah. Pada graf berarah, (vj, vk) dan (vk, vj) menyatakan dua busur yang berbeda, dengan kata lain (vj, vk) tidak sama dengan (vk, vj). Untuk busur (vj, vk), simpul vj disebut simpul asal (initial vertex) dan untuk simpul vk disebut simpul terminal (terminal vertex). Graf tak-berarah (undirected graph) merupakan graf yang sisinya tidak memiliki orientasi arah. Pada graf tidak berarah, urutan pasangan simpul yang dihubungkan oleh sisi tidak diperhatikan, dengan kata lain: (vj, vk) = (vk, vj) Contoh graf berarah dapat dilihat pada gambar 2 berikut
Universitas Sumatera Utara
Gambar 2.2 Graf Berarah 2.4.Algoritma L-Deque Antrian berakhir ganda (Deque) merupakan daftar yang menggabungkan sifat-sifat baik antrian dan tumpukan.Sebuah deque adalah daftar dimana penambahan dan penghapusan yang mungkin di kedua ujung, deque digunakan dalam algoritma D’Esopo – Pape, biasanya disebut Algoritma L-Deque (Gallo & Pallotino, 1986). Algoritma deque (double-ended antrian) adalah daftar penambahan dan penghapusan yang mungkin di kedua ujung. Sebuah deque dapat dilihat sebagai tumpukan dan antrian dihubungkan secara seri di sedemikian rupa sehingga ekor poin stack untuk kepala antrian. Deque digunakan untuk mengimplementasikan dua arah kriteria ide dikaitkan dengan D'Esopo dan Pape.Metode ini yang disebut L-Deque, menambahkan node di kepala Q jika sudah muncul di daftar sebelum node atau ditambahkan pada ekornya begitu juga sebaliknya.Node selalu dihapus dari kepala node yang layak pemindaian daftar. Ketika semua node memiliki label yang terbatas, metode berperilaku seperti algoritma yang menggunakan stack (Mondou et al, 1991). Deque menggunakan dua pointer penunjuk yaitu left petunjuk untuk elemen pada posisi kiri dan right petunjuk untuk elemen pada posisi kanan. Ada dua jenis deque : 1. Input-Restricted-Deque Adalah deque yang operasi pemasukan elemen datanya hanya dapat dilakukan di satu ujung kanannya (right), tetapi dapat menghapus dari kedua ujungnya (leftdan right).
2. Output-Restricted-Deque Adalahdeque yang operasi pemasukan elemen datanya dapat dilakukan melalui kedua ujungnya (left danright), tetapi hanya dapat menghapus dari ujung kanannya(right).
Universitas Sumatera Utara
2.5.Algoritma Bellman-Ford Algoritma bellman-ford merupakan salah satu algoritma yang menangani kasus pencarian lintasan dengan bobot terkecil.Algoritma ini memungkinkan apabila di dalam system yang dibangun terdapat pencilan.Seperti yang sudah dicobakan sebelumnya, apabila simpul yang dituju ataupun simpul asal merupakan sebuah pencilan maka hasil yang didapatkan adalah infinity.Tidak hanya itu bahkan apabila ternyata tidak ada lintasan yang menghubungkan antara simpul awal dan simpul tujuan, maka bobot yang dihasilkan juga berupa infinity (Utami, 2009). Algoritma Bellman-Ford menghitung jarak terpendek (dari satu sumber) pada sebuah diagraf berbobot.Maksudnya dari satu sumber ialah bahwa algoritma Bellman-Ford menghitung semua jarak terpendek yang berawal dari satu titik node. Algoritma BellmanFord menggunakan waktu sebesar O(V.E), di mana V dan E adalah menyatakan banyaknya vertex dan edge (Pradhana, 2006).
Gambar 2.3 Graf Berbobot untuk Algoritma Bellman-Ford 2.5.1. PSEUDOCODE Pseudocode Algoritma Bellman-Ford function Bellman Ford (list vertices, list edges, vertex source) : :distance [ ],predecessor [ ]
// Step 1: initialize graph for each vertex v in vertices: Distance[v] :=inf
Universitas Sumatera Utara
Predecessor[v] := null distance[source] := 0
// Step 2: relax edges repeatedly for i from 1 to size (vertices) -1 : for each edge (u, v) with weight w in edges: if distance [u] + w < distance[v]: distance[v] := distance[u] +w predecessor[v] := u
// Step 3: check for negative weight cycles for each edge (u, v) with weight w in edges: if distance[u] + w < distance [v] : error “Graph contains a negative-weight cycle” return distance[ ], predecessor[ ]
2.6.Kompleksitas Algoritma Algoritma tidak selalu memberikan hasil yang terbaik yang mungkin diperoleh maka diharapkan adanya suatu evaluasi mutu hasil dari algoritma tersebut. Sekali sebuah algoritma diberikan kepada sebuah permasalahan dan dijamin akan memberikan hasil yang diharapkan, maka langkah penting selanjutnya adalah menentukan waktu tempuh yang diperlukan algoritma tersebut untuk memperoleh hasil itu. Proses inilah yang disebut analisis algoritma. Dua buah algoritma yang berberda dapat digunakan memecahkan masalah yang sama dan mungkin saja mempunyai kompleksitas waktu (time complexity) yang sangat berbeda. Kompleksitas waktu algoritma terbaik untuk memecahkan masalah tersebut dinamakan sebagai kompleksitas waktu (time complexity of problem) (Putra, 2014). Teori komputasi pada dasarnya dibagi menjadi tiga bagian karakter yang berbeda.Pertama, pengertian yang tepat dari algoritma, waktu, kapasitas penyimpanan, dan-
Universitas Sumatera Utara
lain-lain harus diperkenalkan. Untuk ini, perbedaan model mesin matematika hatus digambarkan,waktu dan penyimpanan kebutuhan perhitungan dilakukan pada kebutuhan ini harus diperjelas (umumnya diukur sebagai fungsi dari ukuran input). Yang paling mendasar pada kompleksitas adalah memberikan kalsifikasi penting dari masalah yang timbul dalam praktek, bahkan timbul di daerah matematika klasik.Kedua, kita harus menentukan kebutuhan sumber daya dari algoritma yang paling penting dalam berbagai bidang matematika, dan memberikan algoritma yang efesien untuk membuktikan bahwa masalah tertentu memiliki kompleksitas tertentu.Ketiga, harus menemukan metode yang membuktikan “hasil negatif” yaitu untuk bukti beberapa masalah sebenarnya terpecahkan di bawah pembatasan sumber daya tertentu (Gács & Lovász, 1999). Terdapat beberapa jenis notasi asimtotik, tetapi peneliti hanya akan menggunakan dan membahas satu notasi saja, yaitu notasi Big-Theta. Big Theta dipilih karena merupakan notasi untuk menentukan kompleksitas suatu algoritma.
Universitas Sumatera Utara
