bab 2 teori dasar - digilib.itb.ac.id er yang berisi komponen-komponen entity set dan relationship...
TRANSCRIPT
6
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 Entity-Relationship (ER)
Model 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 :
7
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).
8
Entitas 1
Entitas 2
Entitas 3
Entitas 4
Entitas 1
Entitas 2
Entitas 3
Entitas 4
Entity set A Entity set B
Entitas 1
Entitas 2
Entitas 3
Entitas 4
Entitas 1
Entitas 2
Entitas 3
Entitas 4
Entity set A Entity set B
Entity set A Entity set B Entity set BEntity set B1 1 1 1
(a) (b)Obligatory 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).
Entitas 1
Entitas 2
Entitas 1
Entitas 2
Entitas 3
Entitas 4
Entity set A Entity set B
Entitas 1
Entitas 2
Entitas 1
Entitas 2
Entitas 3
Entitas 4
Entity set A Entity set B
Entity set A Entity set B Entity set BEntity set Bm 1 m 1
(a) (b)Obligatory 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
9
2.3). Relasi banyak ke satu dibedakan menjadi dua macam yaitu
obligatory (gambar 2.3 a) dan non-obligatory (gambar 2.3 b).
Entitas 1
Entitas 2
Entitas 3
Entitas 4
Entitas 1
Entitas 2
Entity set A Entity set B
Entity set A Entity set B Entity set BEntity set B1 m 1 m
(a) (b)Obligatory Non-Obligatory
Entitas 1
Entitas 2
Entitas 3
Entitas 4
Entitas 1
Entitas 2
Entity set A Entity set B
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).
Entitas 1
Entitas 2
Entitas 3
Entitas 4
Entitas 1
Entitas 2
Entitas 3
Entitas 4
Entity set A Entity set B
Entity set A Entity set B Entity set BEntity set B1 m 1 m
(a) (b)Obligatory Non-Obligatory
Entitas 1
Entitas 2
Entitas 3
Entitas 4
Entitas 1
Entitas 2
Entitas 3
Entitas 4
Entity set A Entity set B
Gambar 2.4 Tingkat relasi banyak ke banyak
10
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
Merepresentasikan entity set.
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.
Persegi panjang
(Obligatoy)
Belah
Ketupat
Persegi panjang
(Non-Obligatoy)
11
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 atribut-
atributnya. 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 simbol-
simbol. 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 pasangan-
pasangan koordinat (x,y), sementara area atau luasan dikodekan sebagai poligon
dan direkam sebagai pasangan-pasangan koordinat tertutup yang mendefinisikan
12
batas-batasnya. Garis-garis yang menjadi batas-batas bersama di antara poligon-
poligon 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.
13
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.
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.
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 1Node 3
14
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
Gambar 2.7 Topologi poligon
Arc From Node To Node
A. 1 2
B. 3 2
C. 3 1
D. 1 4
E. 3 4
F. 5 5
G. 4 2
Poly Jumlah arc Arc list
A. 3 A,D,G
B. 3 C,D,E
C. 1 F
D. 4 B,E,G,F
Arc A
Arc DArc
G
Arc F
Arc
E
Arc C
Arc
B
1
3
4
2
5
Arc A
Arc DArc
G
Arc F
Arc
E
Arc C
Arc
B
A
BD
C1
3
4
2
5
15
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
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].
Arc 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 A
Arc DArc
G
Arc F
Arc
E
Arc C
Arc
B
A
BD
C1
3
4
2
5
16
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 tak-
sederhana (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:
17
a. Graf tak-berarah (undirected graph)
Graf yang sisinya tidak mempunyai orientasi arah disebut graf tak-
berarah. 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
(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.
1 1
2 3
4
2 3
4
18
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.
19
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
4321
4
3
2
1
0110
1011
1101
0110
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
4
3
2
1
10000
11100
00111
01011
Gambar 2.14
Contoh
Matriks
Besisian
1 2
3
4
e1
e2e3e4
e5
1
32
4
20
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.
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 verteks-
verteks yang belum dikunjungi dilakukan selengkapnya pada pencabangan
pertama, kemudian selengkapnya pada pencabangan kedua, dan seterusnya
secara rekursif.
Simpul Simpul
Tetangga
1 2, 3
2 1, 3, 4
3 1, 2, 4
4 2, 3
1
32
4
21
Breadth First Search (BFS): pada setiap pencabangan penelusuran verteks-
verteks 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.
22
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 simpul-
simpul 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.
A
7
B
0
(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.
0
A
B C
D
5 7
86
0
0
0
Label permanen
dengan nilai 0
Label sementara
dengan nilai 0
Gambar 2.17 Inisialisasi awal
23
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.
A
B C
D
5 7
86
0
0
0
Label berubah
menjadi permanen
dengan nilai 0+5 = 5
5
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.
A
B C
D
5 7
86
0
0
Label berubah
menjadi permanen
dengan nilai 0+7 = 7
5
7
Gambar 2.19 Nilai simpul C berubah
24
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.
A
B C
D
5 7
86
0
Label berubah
menjadi permanen
dengan nilai 5+6 = 11
5
7
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.
25
A
B
1
C
2
D
3
1 2
Nilai sisi
E
4
F
5
G
6
H
7
6
1078 9
543
Nilai Heuristik
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.
A
B
1
C
2
D
3
1 2
E
4
F
5
G
6
H
7
6
1078 9
543
Nilai sisi+nilai
Heuristik=1+1=2
Nilai sisi+nilai
Heuristik=2+2=4
2
0
4
Gambar 2.22 Pencarian Nilai dari Simpul A
26
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.
A
B
1
C
2
D
3
1 2
E
4
F
5
G
6
H
7
6
1078 9
543
Nilai sisi+nilai
Heuristik=3+3=6
Nilai sisi+nilai
Heuristik=4+4=8
2
0
4
6 8
14
Nilai sisi+nilai
Heuristik=7+7=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
1 2
3
A
1B
2
Nilai sisi
4 5 6
7
F
6
J
10
G
7
H
8
I
9
E
5D
4
C
3
Nilai Heuristik
0
0
0
Gambar 2.24 Inisialisasi Awal
27
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
1 2
3
A
1B
2
4 5 6
7
F
6
J
10
G
7
H
8
I
9
E
5D
4
C
3
0
Nilai sisi+nilai
Heuristik=1+3=6
0
4
5
Nilai sisi+nilai
Heuristik=1+4=5
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
1 2
3
A
1B
2
4 5 6
7
F
6
J
10
G
7
H
8
I
9
E
5D
4
C
3
0
Nilai sisi+nilai
Heuristik=4+8=12
0
10
12
Nilai sisi+nilai
Heuristik=3+7=10
Gambar 2.26 Pencarian Nilai dari Sisi C