BAB 2 TEORI DASAR Bab ini akan membahas mengenai Pemodelan basis data (dibahas pada subbab 2.1), pengenalan peta dijital beserta model data (dibahas pada subbab 2.2), teori dasar mengenai graf serta representasi graf (dibahas pada subbab 2.3), dan berbagai macam algoritma pencarian jalur jalan seperti algoritma Djikstra, A-star (A*), dan Shooting-star (shooting*) (dibahas pada subbab 2.4).
2.1 Pemodelan Basis Data Dalam SIG, dunia nyata harus disederhanakan karena pada dasarnya dunia nyata sendiri bersifat tidak teratur (irregular), kompleks, dan secara tetap mengalami perubahan yang tidak bisa diprediksi dengan mudah. Persepsi dunia nyata dalam SIG sangat bergantung pada pengamat (subjektif). Proses-proses yang terlibat dalam mentranslasikan hasil pengamatan dari dunia nyata ke dalam data yang dimengerti dan dibutuhkan oleh SIG dengan menggunakan model dunia nyata dan model data disebut dengan pemodelan data (data modelling) [Prahasta, 2001]. 2.1.1 Model
Model Entity-Relationship (ER) Entity-Relationship
merupakan
model
yang
dipakai
untuk
mentransformasikan keadaan dunia nyata dengan menggunakan seperangkat konseptual sehingga menjadi sebuah diagram relasi antar entitas. Komponen utama pembentuk model ER adalah relasi dan entitas. Kedua komponen ini dideskripsikan dengan menggunakan atribut-atribut (properties). Model ER ini menggambarkan relasi atau hubungan antar entitas, dimana terdapat 2 jenis hubungan, yaitu : a. Obligatory : bila semua anggota dari suatu entitas harus berpartisipasi atau memiliki hubungan dengan entitas yang lain. b. Non-obligatory : bila tidak semua anggota dari suatu entitas harus berpartisipasi atau memiliki hubungan dengan entitas lain. Dalam menggambarkan model ER, terdapat beberapa komponen yang harus diperhatikan, yaitu : 6
1. Entitas Entitas merupakan individu yang mewakili sesuatu yang nyata eksistensinya dan dapat dibedakan dengan yang lainnya. Sekumpulan entitas yang sama atau sejenis yang terdapat dalam lingkup yang sama akan membentuk entity set (sekumpulan entitas) [Prahasta, 2001]. 2. Atribut Setiap entitas pasti memiliki atribut-atribut yang akan mendeskripsikan karakteristik-karakteristik dari entitas yang bersangkutan. Penentuan atau pemilihan atribut-atribut yang relevan bagi suatu entitas merupakan hal penting di dalam pembentukan model data. Penentuan atribut-atribut bagi suatu entitas pada umumnya didasarkan pada fakta-fakta yang ada. 3. Relasi Relasi menunjukkan adanya hubungan atau keterkaitan antara suatu entitas dengan entitas lain yang berbeda. Jika relasinya banyak, maka kumpulan suatu relasi yang ada diantara entitas yang terdapat pada entity set - entity set yang berbeda akan membentuk relationship set (sekumpulan atau himpunan relasi). 4. Tingkat Relasi Tingkat relasi menunjukkan adanya batas jumlah maksimum entitas dapat berelasi dengan entitas yang terdapat pada entity set yang lain. Dari sejumlah kemungkinan relasi antar entitas, tingkat relasi merujuk pada jumlah maksimum relasi yang mungkin terjadi di antara entity set - entity set yang bersangkutan. Berikut ini adalah kemungkinan-kemungkinan tingkat relasi yang terdapat pada entity set, untuk setiap tingkat relasi akan dijelaskan oleh diagram ER-nya masing-masing : i. Tingkat relasi satu ke satu (one to one). Yaitu satu entitas dalam A dihubungkan dengan maksimum satu entitas dalam sejumlah entitas dalam B (gambar 2.1). Relasi satu ke satu dibedakan menjadi dua macam yaitu obligatory (gambar 2.1 a ) dan non-obligatory (gambar 2.1 b).
7
Entity set A
Entity set B
Entity set A
Entity set B
Entitas 1
Entitas 1
Entitas 1
Entitas 1
Entitas 2
Entitas 2
Entitas 2
Entitas 2
Entitas 3
Entitas 3
Entitas 3
Entitas 3
Entitas 4
Entitas 4
Entitas 4
Entitas 4
Entity set A
1
1
Entity set B
Entity set B
(a) Obligatory
1
1 Entity set B
(b) Non-Obligatory
Gambar 2.1 Tingkat relasi satu ke satu ii. Tingkat relasi satu ke banyak (one to many). Yaitu satu entitas dalam A dihubungkan dengan sejumlah entitas dalam B. Satu entitas dalam B dihubungkan dengan maksimum satu entitas dalam A (gambar 2.2). Relasi satu ke banyak dibedakan menjadi dua macam yaitu obligatory (gambar 2.2 a) dan non-obligatory (gambar 2.2 b). Entity set A
Entity set B
Entity set A
Entity set B
Entitas 1
Entitas 1 Entitas 1
Entitas 2
Entitas 1
Entitas 2
Entitas 2
Entitas 3
Entitas 2
Entitas 3 Entitas 4
Entitas 4 Entity set A
m
1
(a) Obligatory
Entity set B
Entity set B
m
1 Entity set B
(b) Non-Obligatory
Gambar 2.2 Tingkat relasi satu ke banyak iii. Tingkat relasi banyak ke satu (many to one). Yaitu satu entitas dalam A dihubungkan dengan maksimum satu entitas dalam B. Satu entitas dalam B dapat dihubungkan dengan sejumlah entitas dalam A (gambar
8
2.3). Relasi banyak ke satu dibedakan menjadi dua macam yaitu obligatory (gambar 2.3 a) dan non-obligatory (gambar 2.3 b). Entity set A
Entity set B
Entitas 1
Entity set A
Entity set B
Entitas 1
Entitas 2
Entitas 1
Entitas 2
Entitas 1
Entitas 3
Entitas 2
Entitas 3
Entitas 2
Entitas 4
Entitas 4 1
Entity set A
m
Entity set B
1
Entity set B
(a) Obligatory
m Entity set B
(b) Non-Obligatory
Gambar 2.3 Tingkat relasi banyak ke satu iv. Tingkat relasi banyak ke banyak (many to many). Satu entitas dalam A dihubungkan dengan sejumlah entitas dalam B, dan satu entitas dalam B dihubungkan dengan sejumlah entitas dalam A (Gambar 2.4). Relasi banyak ke banyak dibedakan menjadi dua macam yaitu obligatory (gambar 2.4 a) dan non-obligatory (gambar 2.4 b). Entity set A
Entity set B
Entity set A
Entity set B
Entitas 1
Entitas 1
Entitas 1
Entitas 1
Entitas 2
Entitas 2
Entitas 2
Entitas 2
Entitas 3
Entitas 3
Entitas 3
Entitas 3
Entitas 4
Entitas 4
Entitas 4
Entitas 4
Entity set A
1
m
(a) Obligatory
Entity set B
Entity set B
1
m Entity set B
(b) Non-Obligatory
Gambar 2.4 Tingkat relasi banyak ke banyak
9
2.1.2
Diagram Entity Relationship (ER)
Model ER yang berisi komponen-komponen entity set dan relationship set yang masing-masing dilengkapi dengan atribut-atribut yang merepresentasikan seluruh fakta dari sebagian dunia nyata dapat digambarkan secara sitematis dengan menggunakan diagram ER. Simbol-simbol dan notasi yang digunakan dalam penulisan diagram ER dapat dilihat pada tabel 2.1 berikut ini. Tabel 2.1 Notasi atau simbol yang digunakan dalam diagram ER Notasi / Simbol
Keterangan
Persegi panjang
(Obligatoy)
Merepresentasikan entity set. Persegi panjang (Non-Obligatoy)
Belah Ketupat
Menggambarkan relationship set.
Menghubungkan antara entity set dengan relationship set-nya.
2.2 Pengenalan Peta Dijital Peta dijital adalah representasi fenomena geografik yang disimpan untuk ditampilkan dan dianalisis oleh komputer dijital. Setiap objek pada peta dijital disimpan sebagai sebuah atau sekumpulan koordinat. Sebagai contoh, objek berupa lokasi sebuah titik akan disimpan sebagai sebuah koordinat, sedangkan objek berupa wilayah akan disimpan sebagai sekumpulan koordinat. Peta dijital dapat direpresentasikan dalam dua model: model raster dan model vektor. Pada tugas akhir ini, akan dibahas mengenai model vektor.
10
2.2.1
Model Data Vektor
Model data vektor menampilkan, menempatkan, dan menyimpan data spasial dengan menggunakan titik-titik, garis-garis atau kurva, poligon beserta atributatributnya. Pada model data ini, poligon, garis atau kurva merupakan kumpulan titik-titik terurut yang dihubungkan. Pada poligon, titik awal dan titik akhir memiliki nilai koordinat yang sama, sehingga bentuknya menjadi tertutup sempurna [Prahasta, 2001]. 1. Entity titik Titik adalah representasi grafis yang paling sederhana untuk suatu objek. Representasi ini tidak memiliki dimensi tetapi dapat diidentifikasi di atas peta dan dapat ditampilkan pada layar monitor dengan menggunakan simbolsimbol. Sudut property suatu batas (poligon) juga merupakan titik. 2. Entity garis Garis adalah bentuk linier yang akan menghubungkan paling sedikit dua titik dan digunakan untuk merepresentasikan objek-objek satu dimensi. Batas-batas poligon merupakan garis-garis, demikian pula dengan jaringan jalan, listrik, pipa dan utilitas lain-lain. 3. Entity poligon Poligon digunakan untuk merepresentasikan objek-objek dua dimensi. Suatu danau, batas propinsi, batas kota adalah tipe entitas yang pada umumnya direpresentasikan sebagai poligon. Suatu poligon paling sedikit dibatasi oleh tiga garis yang saling terhung diantara ketiga titik tersebut. Di dalam basis data, semua bentuk area (luasan) dua dimensi akan direpresentasiakn oleh bentuk poligon. 2.2.1.1 Model Data Spaghetti Pada model ini, lembar peta kertas ditranslasikan garis demi garis ke dalam list koordinat (x,y) dalam format dijital. Sebuah titik dikodekan sebagai pasangan koordinat (x,y) tunggal, sebuah garis dikodekan sebagai list atau string pasanganpasangan koordinat (x,y), sementara area atau luasan dikodekan sebagai poligon dan direkam sebagai pasangan-pasangan koordinat tertutup yang mendefinisikan
11
batas-batasnya. Garis-garis yang menjadi batas-batas bersama di antara poligonpoligon yang bersebelahan di-trace dan direkam dua kali (sekali untuk poligon pertama, dan sekali lagi untuk poligon yang terletak di sebelahnya).
Struktur model data ini sangat sederhana dan sangat mudah dimengerti. Model data ini benar-benar merupakan ekspresi peta di dalam sistem koordinat kartesian. File data koordinat-koordinat (x,y) merupakan struktur data yang sebenarnya dalam sistem komputer. Dalam struktur model data ini, semua unsur-unsur spasialnya (spatial features) tersimpan/terekam, namun hubungan spasial yang ada diantara unsur-unsur tersebut tidak tersimpan. Sebagai contoh, informasi mengenai unsur-unsur yang berada tepat di sebelah suatu poligon tidak disimpan. Informasi ini dapat dibuat dengan cara melakukan proses pencarian ke semua unsur-unsur spasial yang terdapat di dalam file data, dan kemudian melakukan analisis atau hitungan untuk memutuskan apakah poligon yang bersangkutan memiliki tetangga atau tidak.
Model vektor spaghetti ini sangat tidak efisien untuk kebanyakan tipe-tipe analisis spasial yang diperlukan dalam SIG. hal ini disebabkan karena hampir semua tipe analisis spasial di dalam SIG berikut hubungan spasialnya harus diturunkan dengan menggunakan proses komputasi. Model spaghetti ini sangat efisien untuk reproduksi peta-peta secara dijital karena informasi-informasi yang tidak berhubungan dengan masalah proses plotting dan reproduksi, misalkan hubungan spasial dan topologi, tidak ikut tersimpan. 2.2.1.2 Model Data Vektor Dengan Topologi Topologi adalah konsep atau metode matematis yang digunakan didalam mendefinisikan hubungan spasial di antara unsur-unsurnya. Hubungan topologi merupakan properties inherent yang dimiliki oleh setiap objek atau entitas geometri, atau spasial.
12
Topologi merupakan salah satu dari sejumlah hubungan terpenting didalam basis data spasial. Struktur datanya menentukan bagaimana dan dimana titik-titik dan garis-garis berhubungan satu dengan yang lainnya pada suatu node. Selain itu, urutan koneksi atau keterhubungan juga menentukan bentuk dari suatu arc (merupakan sekumpulan titik / pasangan koordinat yang dimalai dari suatu titik yang didefinisikan sebagai node awal dan diakhiri pada suatu titik yang didefinisikan sebagai node akhir). Informasi mengenai hubungan topologi ini biasanya disimpan dalam beberapa tabel pada struktur basis data spasial. Berikut ini adalah contoh hubungan unsur-unsur spasial di dalam basis data [Prahasta, 2001] : 1. Menyimpan semua node yang merupakan titik-titik (endpoints) dan perpotongan-perpotongan garis-garis (arcs) dan batas-batas (boundaries atau polygons) terlihat pada gambar 2.5. Node
X
Y
1.
25
82
2.
30
78
3.
21
76
4.
26
79
5.
27
75
Node 2 Node 5 Node 4 Node 1
Node 3
Gambar 2.5 Koordinat dan Posisi-posisi Nodes 2. Berdasarkan node tersebut, kemudian didefinisikan arcs dengan menggunakan informasi-informasi : endpoints (node), direction (arah yang dimuali dari from node ke dengan tujuan to node), orientasi vektor yang direpresentasikan oleh direction-nya terlihat pada gambar 2.6.
13
Arc 2
To Node
A.
1
2
B.
3
2
C.
3
1
D.
1
4
E.
3
4
F.
5
5
G.
4
2
4 Arc D
Arc F
Arc C
Arc B
5
Arc E
1
Ar c
G
Arc A
From Node
3
Gambar 2.6 Arcs dan nodes Arcs ini tersusun dari garis-garis lurus yang dibentuk oleh vertex yang memungkinkan untuk melakukan perubahan-perubahan arah (derection) sehingga bentuk arcs menyerupai kurva yang halus (smooth). Selain itu, dengan orientasi arcs, pembuatan rute-rute dari suatu node ke node yang ditentukan atau dari suatu tempat ke tempat lain yang ditentukan menjadi memungkinkan. 3. Poligon-poligon didefinisikan dengan menggunakan arcs: sebuah poligon didefinisikan dengan melakukan tracing batas-batasnya seara h dengan perputaran jarum jam (clockwise), komponen-komponen arcs beserta orientasinya
direkam,
tanda
negatif
diberikan
kepada
arcs
yang
mendefinisikan batas-batas internal, dan untuk setiap arc, poligon-poligon yang terletak di sebelah kiri dan kanan arah orientasinya, juga direkam. Terlihat pada gambar 2.7 2
Arc A
Poly
B
Arc C
5
Arc E
1
Arc D
C Arc F D
Arc B
4
Ar c
G
A
Jumlah arc
Arc list
A.
3
A,D,G
B.
3
C,D,E
C.
1
F
D.
4
B,E,G,F
3
Gambar 2.7 Topologi poligon
14
4. jika sebuah arc merupakan salah satu sisi (pinggiran) study area, arc tersebut dibatasi oleh universe atau outer world (dunia luar). Dengan contiguity (keterhubungan dengan unsur-unsur geometri yang bersebelahan) ini, SIG dapat menjawab pertanyaan-pertanyaan mengenai konektivitas dan lokasi seperti: poligon-poligon mana yang berdampingan atau bersebelahan (adjoin) dengan poligon A, rute terpendek mana yang menghubungkan dari node 3 ke node 2, poligon mana yang dilalui secara langsung dari poligon B di sepanjang arc D. Terlihat pada gambar 2.8 Left Poly
Right Poly
A.
Universe
A
B.
D
Universe
C.
Universe
B
D.
A
B
E.
B
D
F.
D
C
G.
A
D
Arc D
Arc C
Arc E
B
5
3
C Arc F D
Arc B
4
Ar c
G
A
1
Arc
2
Arc A
Gambar 2.8 Contiguity
2.3 Teori Graf Graf adalah struktur diskrit yang terdiri dari simpul (vertex) dan sisi (edge), atau dengan kata lain, graf adalah pasangan himpunan (V,E) di mana V adalah himpunan tidak kosong dari vertex dan E adalah himpunan sisi yang menghubungkan sepasang simpul dalam graf tersebut. Graf dapat ditulis dengan notasi G=(V,E). Pada gambar 2.9 menggambarkan suatu graf dengan 6 node dan 7 edge [Rinaldi Munir 2003].
15
Gambar 2.9 Graf dengan 6 node dan 7 edge 2.3.1
Jenis Graf
Graf digunakan untuk merepresentasikan objek diskrit dan hubungan antara objek. Representasi visual graf adalah dengan menyatakan objek sebagai noktah, bulatan, atau titik. Sedangkan hubungan antara objek dinyatakan dengan garis.Berdasarkan vertex (simpul) dan edge (sisi), graf terbagi menjadi tiga bagian antara lain [Rinaldi Munir 2003]: 1. Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graf, maka graf digolongkan menjadi dua jenis: a. Graf sederhana (simple graph) Graf yang tidak mengandung gelang maupun sisi-ganda dinamakan graf sederhana. G1 pada Gambar 2.2 adalah contoh graf sederhana. b. Graf tak-sederhana (unsimple-graph) Graf yang mengandung sisi ganda atau gelang dinamakan graf taksederhana (unsimple graph). G2 dan G3 pada Gambar 2.2 adalah contoh graf tak-sederhana. 2. Berdasarkan jumlah simpul pada suatu graf, maka secara umum graf dapat digolongkan menjadi dua jenis: a. Graf berhingga (limited graph) Graf berhingga adalah graf yang jumlah simpulnya, n, berhingga. b. Graf tak-berhingga (unlimited graph) Graf yang jumlah simpulnya, n, tidak berhingga banyaknya disebut graf tak-berhingga. 3. Berdasarkan orientasi arah pada sisi, maka secara umum graf dibedakan atas dua jenis: 16
a. Graf tak-berarah (undirected graph) Graf yang sisinya tidak mempunyai orientasi arah disebut graf takberarah. Tiga buah graf pada Gambar 2.10 adalah graf tak-berarah. b. Graf berarah (directed graph atau digraph) Graf yang setiap sisinya diberikan orientasi arah disebut sebagai graf berarah. Dua buah graf pada Gambar 2.11 adalah graf berarah.
G1
G2
G3
Gambar 2.10 Graf berdasarkan ada tidaknya sisi gelang atau sisi ganda, (a). Graf Sederhana, (b). Graf ganda, (c). Graf semu 1
2
1
3
4
2
3
4
(a) (b) G4 G5 Gambar 2.11 (a) graf berarah, (b) graf-ganda berarah Dalam penggambaran graf dalam bidang datar, graf dibagi menjadi dua yaitu: 1. Graf Planar (Planar Graph) Yaitu graf yang dapat digambarkan pada bidang datar dengan sisi-sisi yang tidak saling memotong (bersilangan). Tiga buah graf pada gambar 2.12 termasuk graf planar.
17
2. Graf Bidang (Plane Graph) Yaitu Graf planar yang digambarkan dengan sisi-sisi yang tidak saling berpotongan. Graf (b) dan (c) pada gambar 2.12 termasuk graf bidang.
(a)
(b)
(c)
Gambar 2.12 Tiga buah graf planar. Graf (b) dan (c) adalah graf bidang
2.3.2
Representasi Graf
Untuk pemrosesan graf dengan program komputer, graf harus direpresentasikan ke dalam memori. Terdapat beberapa representasi untuk graf, antara lain matriks ketetanggaan, matriks bersisian, dan senarai ketetanggaan [Rinaldi Munir 2003]. 1. Matriks Ketetanggaan (adjacency matrix) Untuk mempermudah perhitungan pada program komputer, graf dapat direpresentasikan dengan menggunakan
matriks. Salah satunya adalah
matriks ketetanggaan. Misalkan G = (V, E) adalah sebuah graf sederhana dimana |V| = n, n > 1. Misalkan simpul dari G adalah v1, v2, … vn. Maka, matriks ketetanggaan A dari G adalah n x n matriks dimana: A = [aij], 1, jika simpul i dan j bertetangga 0, jika simpul i dan j tidak bertetangga Matrks ketetanggaan nol-satu tidak dapat digunakan untuk merepresentasikan graf yang mempunyai sisi ganda. Untuk mengatasinya, maka elemen a[ij] pada matiks ketetanggaan sama dengan jumlah yang berasosiasi dengan (vi,vj), matriks ketetanggaannya bukan lagi matriks nol-satu. Untuk graf semu, gelang pada simpul vi dinyatakan dengan nilai satu pada posisi (i,j) di matriks ketetanggaannya.
18
Keuntungan representasi dengan matriks adalah elemen matriksnya dapat diakses langsung melalui indeks. Selain itu, kita dapat mengetahui secara langsung apakah simpul
i dan simpul j bertetangga. Contoh matriks
ketetanggaan ada pada gambar 2.13 1
1 2 3 4
2
3
1 0 2 1 3 1 4 0
1 1 0 0 1 1 1 0 1 1 1 0
4
Gambar 2.13 Contoh Matriks Ketetanggaan 2. Matriks Bersisian (incidency matrix) A = [aij], 1,
jika simpul i bersisian dengan sisi j
0, jika simpul i tidak bersisian dengan sisi j Matriks bersisian menyatakan kebersisian simpul dengan sisi. Misalkan G=(V, E) adalah graf dengan n simpul dan m buah sisi, maka matriks kebersisian A dari graf G adalah matriks yang berukuran m x n. Baris menunjukkan label simpul, sementara kolom
menunjukkan label sisinya. Gambar 2.14
menunjukkan representasi graf dalam bentuk matriks bersisian. e1 e2 e3 e4 e5
e1 1
2 e4
e2
e3 3
e5
1 1 2 1 3 0 4 0
1 0 1 0 1 1 0 0 0 1 1 1 0 0 0 1
4
Gambar 2.14 Contoh Matriks Besisian
19
3. Senarai Ketetanggaan (adjacency list) Kelemahan matriks ketetanggaan adalah bila graf memiliki jumlah sisi relatif sedikit, karena matriksnya bersifat jarang, yaitu banyak mengadung elemen nol, sedangkan elemen yang bukan nol sedikit. Ditinjau dari segi implementasi, kebutuhan ruang memory untuk matriks jarang, boros, karena komputer menyimpan banyak elemen nol yang tidak perlu. Untuk mengatasi masalah
ini,
senarai
ketetanggaan
digunakan.
Senarai
ketetanggaan
mengenumerasi simpul-simpul yang bertetangga dengan setiap simpul di dalam graf. Contoh dari senarai ketetanggaan dapat dilihat dari Gambar 2.15. 1
2
3
Simpul Simpul Tetangga 1 2, 3 2 1, 3, 4 3 1, 2, 4 4 2, 3
4
Gambar 2.15 Contoh Senarai Ketetanggaan
2.4 Algoritma Pencarian Lintasan Terpendek Penelusuran jalur pada SIG secara konseptual memiliki prinsip dasar yang sama, yaitu menerapkan teori Graf kedalam jaringan jalan. Sebuah struktur graf dapat dikembangkan dengan memberi bobot pada setiap edge. Graf berbobot dapat digunakan untuk melambangkan banyak konsep berbeda. Jika suatu graf melambangkan jaringan jalan, maka bobotnya dapat berarti panjang jalan maupun batas kecepatan pada batas tertentu. Ekstensi lain pada graf adalah dengan membuat edgenya bearah, atau secara teknis disebut graf berarah atau digraph (directed graf). Graf berbobot inilah yang digunakan untuk mencari lintasan terpendek. Terdapat dua metoda pencarian dalam graf yaitu : Depth First Search (DFS): pada setiap pencabangan, penelusuran verteksverteks yang belum dikunjungi dilakukan selengkapnya pada pencabangan pertama, kemudian selengkapnya pada pencabangan kedua, dan seterusnya secara rekursif.
20
Breadth First Search (BFS): pada setiap pencabangan penelusuran verteksverteks yang belum dikunjungi dilakukan pada verteks-verteks adjacent, kemudian berturut-turut selengkapnya pada masing-masing pencabangan dari setiap verteks adjacent tersebut secara rekursif. Pencarian lintasan terpendek (Shortest Path) yaitu pencarian lintasan yang memiliki bobot minimum. Untuk memecahkan permasalahan lintasan terpendek, ada beberapa algoritma yang sering digunakan antara lain : 2.4.1
Algoritma Dijkstra
Algoritma ini diberi nama sesuai nama penemunya, Edsger Wybe Dijkstra. Algoritma Dijkstra mencari lintasan terpendek dalam sejumlah langkah. Algoritma ini pada setiap langkah akan memilih sisi yang berbobot minimum dan memasukkannya ke dalam himpunan solusi. Algoritma Djikstra menggunakan strategi Greedy dalam mencari lintasan terpendek. Strategi Greedy adalah strategi yang memecahkan masalah langkah demi langkah, pada setiap langkah mengambil pilihan yang terbaik yang dapat diperoleh dengan berharap bahwa pemilihan solusi optimum lokal pada setiap langkah akan mencapai solusi optimum global. Dengan demikian algoritma Dijkstra adalah sebagai berikut : “Pada setiap langkah, ambil sisi yang berbobot minimum yang menghubungkan sebuah simpul yang sudah terpilih dengan sebuah simpul lain yang belum terpilih. Lintasan dari simpul asal ke simpul yang baru haruslah merupakan lintasan terpendek diantara semua lintasannya ke simpul-simpul yang berlum terpilih”.
Input algoritma ini adalah sebuah graf berarah yang berbobot (weighted directed graph) G dan sebuah sumber vertex s dalam G dan V adalah himpunan semua vertices dalam graph G. Algoritma Dijkstra dimulai dari sebuah simpul asal dan dalam setiap iterasinya menambahkan sebuah verteks lain ke lintasan terpendek pohon merentang. Verteks ini merupakan titik terdekat ke akar namun masih di luar bagian pohon. Dalam algoritma Dijkstra, yang dicari adalah sisi yang menghubungkan ke suatu verteks di (Vi-Vn) sehingga jarak dari verteks asal Vs ke verteks tersebut adalah minimal.
21
Algoritma Dijkstra akan membuat label untuk menunjukkan simpul-simpul. Label-label ini melambangkan jarak dari simpul asal ke suatu simpul lain. Dalam graf, terdapat dua macam label, sementara dan permanen. Label sementara diberikan untuk simpul-simpul yang belum dicapai. Nilai yang diberikan untuk label sementara ini dapat beragam. Label permanen diberikan untuk simpulsimpul
yang sudah dicapai dan jarak ke simpul asal diketahui. Nilai yang
diberikan untuk label ini ialah jarak dari suatu simpul ke simpul asal. Suatu simpul pasti memiliki label permanen atau label sementara, tetapi tidak keduanya terlihat pada gambar 2.16. 0
7
A
B
(a)
(b)
Gambar 2.16 : (a). Simpul A berlabel sementara dengan jarak 0, (b). Simpul B berlabel permanen dengan jarak 7 Algoritma dimulai dengan menginisialisasi simpul awal di dalam graf (misalkan simpul A) dengan label permanen bernilai 0 dan simpul-simpul sisanya dengan label sementara bernilai 0 terlihat pada gambar 2.17. Label permanen dengan nilai 0
0
Label sementara dengan nilai 0
A 5
0
7
B
C 6
0
8
D
0
Gambar 2.17 Inisialisasi awal
22
Algoritma ini kemudian memilih nilai sisi yang menghubungkan simpul dengan label permanen (dalam hal ini simpul A) ke sebuah simpul lain yang berlabel sementara (misalkan simpul B). Kemudian label simpul B berubah dari label sementara menjadi label permanen. Nilai simpul B merupakan penjumlahan nilai sisi AB dan nilai simpul A terlihat pada gambar 2.18. 0
Label berubah menjadi permanen dengan nilai 0+5 = 5
A 5
5
7
B
C 6
0
8
D
0
Gambar 2.18 Nilai simpul B menjadi permanen Langkah selanjutnya ialah menemukan nilai sisi berikutnya yang menghubungkan simpul awal (simpul A) ke simpul berikutnya (simpul C). Kemudian label simpul C berubah menjadi label permanen, Nilai simpul C merupakan penjumlahan nilai sisi AC dan nilai simpul A terlihat pada gambar 2.19.
0 Label berubah menjadi permanen dengan nilai 0+7 = 7
A 5
5
7
B
C 6
7
8
D
0
Gambar 2.19 Nilai simpul C berubah
23
Proses ini berulang hingga semua label simpul menjadi permanen kemudian mencari nilai yang paling kecil. Proses ini menggunakan metode Depth First Search (DFS), yang melakukan penelusuran simpul pada setiap pencabangan, penelusuran simpul-simpul yang belum dikunjungi dilakukan selengkapnya pada pencabangan pertama, kemudian selengkapnya pada pencabangan kedua, dan seterusnya secara rekursif terlihat pada gambar 2.20. 0
A 5
5
7
B Label berubah menjadi permanen dengan nilai 5+6 = 11
C 6
7
8
D 11
Gambar 2.20 Semua Nilai Simpul Menjadi Permanen 2.4.2
Algoritma A*
Algoritma A* adalah suatu algoritma pencarian untuk graf. Ciri dari algoritma ini adalah dengan adanya fungsi heuristik (h(x)) yang mempertimbangkan jarak untuk menentukan urutan di mana pencarian mengunjungi simpul dalam graf. Jalur x yang diberi notasi f(x) merupakan penjumlahan dari dua fungsi yaitu fungsi penghitungan biaya suatu jalur (g(x)) dan fungsi perkiraan heuristik yang memperkirakan jarak dari simpul saat ini ke simpul tujuan (h(x)). Pada algoritma A* pencarian dilakukan secara inkremen pada semua rute yang mengarah ke simpul mulai sampai berhasil ditemukan jalur tujuan yang terdekat. Untuk itu, algoritma ini pertama memulai dengan memeriksa rute yang „keliatannya‟ paling mungkin mengarah ke tujuan. Algoritma A* dimulai dengan menginisialisasi simpul awal dalam graf (misalkan simpul A) terlihat pada gambar 2.21.
24
Nilai sisi
A
Nilai Heuristik 1
2
B 1
C 2
3
4
5
D 3
E 4
F 5
8
6
G 6
9
7
10
H 7
Gambar 2.21 Inisialisasi Awal Algoritma ini kemudian akan memilih simpul yang kelihatannya yang paling mungkin ke tujuan (dalam hal ini simpul H). Algoritma A* menggunakan Breadth First Search (BFS) yang pada setiap pencabangan penelusuran simpul-simpul yang belum dikunjungi dilakukan pada simpul-simpul adjacent, kemudian berturut-turut selengkapnya pada masing-masing pencabangan dari setiap verteks adjacent tersebut secara rekursif. Pemeriksaan nilai dilakukan dengan menghitung nilain sisi (g(x)) dengan nilai heuristic (h(x)). Dari gambar didapat bahwa nilai dari simpul A B adalah 2, dan simpul A C adalah 4. Terlihat pada gambar 2.22. 0
Nilai sisi+nilai Heuristik=1+1=2
Nilai sisi+nilai Heuristik=2+2=4
A 1
2
4
2
B 1
C 2
3
4
5
D 3
E 4
F 5
8 7
9
6
G 6 10
H 7
Gambar 2.22 Pencarian Nilai dari Simpul A
25
Proses selanjutnya adalah memilih nilai yang paling kecil (dalam hal ini adalah dari A B). Proses ini dilakukan sampai menemukan simpul tujuan (dalam hal ini simpul H) sehingga akan didapat nilai penelusuran yang terkecil. Terlihat pada gambar 2.23. 0
A 1
2
4
2
B 1
Nilai sisi+nilai Heuristik=3+3=6 3
6
C 2 4
5
E 4
F 5
6
8
D 3
8
G 6
9
7
10
H 7
Nilai sisi+nilai Heuristik=4+4=8
Nilai sisi+nilai Heuristik=7+7=14
14
Gambar 2.23 Pencarian Nilai dari Simpul B 2.4.3
Algoritma Shooting*
Algoritma Shooting* adalah algoritma pencarian dalam graf. Algoritma ini hampir sama dengan algoritma A*, yang membedakannya adalah dalam setiap pencarian algoritma shooting* akan mencari sisi yang terdekat bukan simpul. Algoritma Shooting * dimulai dengan menginisialisasi sisi awal dalam graf (misalkan sisi A) terlihat pada gambar 2.24.
0
0
B 2
1
C 3
D 4
E 5
3
4
5
G 7 0
Nilai sisi
0
A 1
Nilai Heuristik
I 9
H 8 7
2
F 6 6
J 10
Gambar 2.24 Inisialisasi Awal 26
Algoritma ini kemudian akan memilih sisi yang kelihatannya yang paling mungkin ke tujuan (dalam hal ini sisi G). Algoritma Shooting* menggunakan Breadth First Search (BFS. Pemeriksaan nilai dilakukan dengan menghitung nilai sisi (g(x)) dengan nilai heuristic (h(x)). Dari gambar didapat bahwa nilai dari sisi A C adalah 4, dan sisi A D adalah 5. Terlihat pada gambar 2.25. 0
Nilai sisi+nilai Heuristik=1+3=6
A 1
0
B 2
1 4
C 3
5
3 Nilai sisi+nilai Heuristik=1+4=5
D 4
E 5
4
5
2
F 6 6
I 9
H 8
G 7
0
J 10
7
Gambar 2.25 Pencarian Nilai dari Sisi A Proses selanjutnya adalah memilih nilai yang paling kecil (dalam hal ini adalah dari sisi A C). Proses ini dilakukan sampai menemukan sisi tujuan (dalam hal ini sisi G) sehingga akan didapat nilai penelusuran yang terkecil. Terlihat pada gambar 2.26. 0
A 1
0
B 2
1
C 3
D 4
E 5
3
4
5
12
Nilai sisi+nilai Heuristik=4+8=12 10
G 7
I 9
H 8 7
0
2
F 6 6
J 10
Nilai sisi+nilai Heuristik=3+7=10
Gambar 2.26 Pencarian Nilai dari Sisi C
27
