 DL"o2
LANDAS1N TEORI
2.1
Simulasi
2.1.1
Pengertian Simubs!
Simuiasi
adalac'1
tek:nik untuk
menggambarkan dan mempeiajari
perilake
sebuah siste1r: der:g t-'1 bantuan
suatu
model dad
sistem
te:sebut.
2.1.2
Kompm:um
S!mu!&si
Siml!'asi terdiri
dari
berbagai
jeris
komponePyaitu:
l. Sisten1
Sistem
adalah
sekurr:pu!an
e!emen-elemen
seperti
orang-orang
atau
mesin-mesin
ym'g saling
beraksi
dan
berhubungan satu
S<Una
la:!l
untak
penyeiesai<:n dm-i
beberapa
tujuan
legis f ]- Sed
t-igkan
state
dari
sistem
adalah
kumpulan
dari
beberapa
variabel yang
dibuturkan
um:uk
menggambarkan
sistem
pada
suatu
waktu
te1tentu, yang
berhubungan
der:gan tujuan
dari suatu
bahan pe¹ajarar:.
Sistem dapat
dibedakan
menjadi
dua
yaitu sistem diskrit dan sistem
kon:L11yu.
Ya11g dimaksud de: gan
sistem disk:.rit ada!ah
sistem
yang nilai
elemen-elemennya
Sedangkan
siste:n
oerubah-ubah
seca.ra
diskrit
(terputus-putus)
adal
l)
sistem
yang
nilai elemen-elemennya
terns berubah setiap saat menurut wakta.
6
|
 7
Sistern
terdirl
dari :
"'
Ko:ntJonen
atau sub sistem.
Q
rnteraksi
antar eiemen
I
sub
sistem.
2.
l\Jlodel
Model
adala.l-t
gambaran I
representasi dari suacu
sistem
dengan
ciri-
"
Memiliki karakteristik
sempa
dengar: sistem aslinya.
Proporsional
dengan
sistem
aslinya.
3.
Komputer
(bersifat optional),
t::mumn.ya untuk
model matematika.
::u.s
Mmiel
Simulasi
Jenis-jenis
model
simulasi
adalah:
1
.
Model fisik
yaitu: representasi bentuk fisik
dari
suatu sistem,
yang
tergolong
dalam
berbagai
jeni s, antara
lain:
!vfode!
ikonik,
yang
biasanya
disebut der;gan
simulator,
sepe11i
suatu
sistem
yG..<g
sesungguhr:ya.
Model
berusaha
untuk
menggarnbarkan
seperti
apa
bentuk
dari sistem.
Contohr:.ya adalah
maket
banguna.1.
danjlight
simulator.
"
Model
analog
berusaha
mrtuk
menggambarkan
bagaimana sistem
bekelja. Contol:mya adalah alat peraga,
2.
Model
simbolik
yaitu:
gambaran
dari sw.atu sistem dalam
bentuk
angka
a' au sL.'l:lbol.
Model L."li
l::iasa.nya
dijalanka11 pada
komputer.
|
 8
L:u1gkah··LangJ.mb da!am
Peml:mabm. Siumla:s!
.:>m"'"a"
dibuat
berdasarkan urutan
langkaJ1-!a11gklLh
Focrrrlul::tsi masalah
yaitu
mendefinisikan
<ei''""'h
rrmsatan
untuk
memperoleh
aldlir
yang
akan
dicapai.
Jlka
masalail
dengan
baik,
pertan1a-tan1a
hams mengetahui
masalail.
yang
c::,adap
misalnya
dengan mengumpulkan data dan
informasi secukupnya,
bam
kemu:Ean
""'""ill'
solu.sinya.
data-daa
yaitt:
diperlu.kan dalanl
sebuah
dan
mengumpulkan
data
1:1isalnya waktu proses yang
dibutuhkan, waktu rata-rata
"'
Definisikan
mocel
yaitt.1
pendefu.Jisian
sL:atu
sistem
keabsahan suatu
data.
yang
dapat digunakan.
pada
c<rra
kerja
sistem
sesungguhnya.
Mengidentifikas!kan
karakteristik
sebt:a.h
sistem sebagai
obyek
kemudian
menspesifikasikan
hasil
akhimya,
diawa!i dengan
mengidentifikasikan komponen yang
akan.
digunal,an
lalu
menentukan
ko::nponen ya.:1g
2lau: ke dalam sebual1
model.
<>
Validesi
yaitu
meyakinkan
(debugging)
da.:1 hasil
akhir
model
dilair.1kaa
dengan
analisis
model dapat
dipercaya
da1. digan1barkan
ke
&'am sistem
y< Lg
se!:ungg;Jhrtya.
Jika
model
akan
digunakan
pe:iode
\vak::u, r
1aka
lmLlS
dikaji
u!ang
secara
berkaia
untuk
memastikan ketelitiannya.
e
T11lis
program
yaitu
mernncang
sebuah
simulasi
ke
|
 9
pemrograrnan,
misalnya: C,
FORTRAN, PASCAL dare lain-lain.
"
Test
menguji setiap
modul pada prograrr: apaka."'J
S;Jdah
bekerja sesuai
dengan yang dih:;;:-apka::1.
Rancang percobaan yaitu 'nempersiapkan input ur.tu.k
dijalankan oieh sistern
dengan output
sudah diketahui.
"
Jalankan simulasi
yaitu menjalankan
sistel::l. sehingga capat
rne1:ghasilkan
in:fo:nasi.
"
A.nalisa
hasil
simulasi
yaitu
menganalisa dan
menatik
kesimpulan dazi
data
yang terbentuk mela!ui simulasi.
Impleme etasi yaitu pengf:,'1.maar simulasi dan mendokumentasikan la..ngka.
langkah dalam proses pembuatan simulasi [1].
Keuntungan
Keru.gilm dari
SimC kasi
Keunt:mgan dari uji coba dengan
menggurrakan simc;!asi adalall:
®
rv1engarrtisi;Jasi
kemungkinan
ada.nya
kesalal:an ata..1 kegagala."l sebeium
dilakukan implementas' ke dala;n sistem yang sesungguhnya.
,.
Simulasi dapat
memberikat: gambanm
ya..'lg
je!as tentang sistem
yang akan
<>
Dengan simulasi, dapat
dilakukan evaluasi
sistem
dalarn jangka waktu
yang
singkat.
Sedangkan kerugian dari
coba dengan menggunakan
simulasi adalah:
"'
Membutuhkan keablian khusus untuk meobuat simulasi.
|
 10
@
Hasil dar! simuh:si kadang-kadang tidak
sepenuhnya
sesuai dengan keadaan
yang
sesunggurEJYl'-
@
Untc;k
mel.akukan simulasi, dibutuhkan biaya
yang besa::
dan
waktu yang
1&"113..
l
Graph adalah hinpunan
titik-ga.is-titik-garis-
..
-
titik
denga11
memiliki
unsur-unst.;r
sebagai berikut
:
Vertex
me=-upakan
persnnpanga.rt
I
poto::1g I
titik
pertemuan dari
oeberapa
garis.
-
Edge mempak&'1 jalan I garis yang menghubungkan antara 2
vertex.
Edge
memiliki
dapat
c.enyajikan
jarak
waktu pe:jai&"lan.
Edge
te arah:
::,eberapa
jalan
satu
arah,
beberapa
jalan
merdliki
walctu perjalana.<l
yang
berbeda pada setiap
arah.
-
Degree
suatu
vertex
adalah
bar.:y-aknya
edge
yang
be1tern1; pada
vertex
tersebut.
Beberapa istila\1. yang rr:engglffilbarkan
hul:mnga:c anta.;-a
edge
can
vertex:
Walk
yaitu iirrtasan dari suatu
vertex
ke suatu
vertex
yang lain.
Path
yaitu
walk
yang semua
vertex-nya
berlaina..>..
(
vcle (close
path)
yaitoc
path
yang
di:nlllai
dan diakbi pada
vertex
yang
|
 ll
S!ll1'Jl.
Sedang.l,:an
yang dimaksud
dengan
directed
graph
(digraph)
adalah
graph
yang memperhatikan arah
yang ditunjukkal'l oleh edgenya.
Dalam
digraph,
edge
serir:g disebut
arc. Vertex
degree
pada
digraph
ada 2 yaitu:
-
lndegree
yaitu jumlah
edge
yang datang
I
masuk
-
Outdegre
yaitu
jumlah
edge
yar:g pergi I ke!uar.
Tree
adalah suatu
graph
yang banyak
vertex-nya
n
(n> ). Disebut
l ). Disebut
tree
jika
mempunyai
ci.1i-ciri
sebagai
berikut:
-
Graph
tersebut
tidak
men:punyai
ling'mran
(cycle
tree)
dan
ba!lyak::Jya
edge
(n-1).
Graph
tersebut terhubung.
Ada beberapa me ode ?encaria.'l dalam
tree
yaitu:
l. Breadth-First
Search
Pencaria11dalam
tree
yang dilakukac> dengan cara
melebar atau ke samping
kanan terlebih dahulu.
2. Depth-First
Search
Pencarian
dalam.
tree
ya.11g
dilakukan
dengan
nenggu:mkan
backtracking
yaitc
d!mulai
dengan
yang
Jeri dan mendalam
atau
ke bawah
dahuk.
Jumlah
backtracking
itu sama
dengan
jumlab
leaf
tree,
sampai
solusi
belwn ditemukan.
|
 12
3.
BestFirst Search
Merupakan
gabungan dari
Depth-First
Search dan
Breadth-First
Search.
Search
mengg:ma.kan
look-ahead yaitu
me:ihat i
memprediksi
jauh ke depan dan akan
melak:ukan baclgumping apabila
sasa:-ar: taci<
tercapaL
2.2,3
Heil!p
Heap adala!1
binary tree
yrug mewilik key eli setiap node,
dengan ketentuan
sebagai berikut .
I. Semua
leaves
da::i
tree
ada pada dua level yang berdampbgan dan semua
level kecuali yang paling bawal1 tela.terisL
2. Semua
leaves
di level yang lebLJ.: rendah berada di kiri.
3.
Key
pada
root setidak-tidaknya
sebesar
key pada children, left
dan
right
children-nya juga
heap.
4.
Minimum
heap:
jika
nilai parent-nya
selalu
lebih kecil
dadpada kedua
chilclren-nya
(lihat gambar 2.1).
Ru.mus : r[i]
<
r[2i] dan r[i]
<
r[2i+ l]
Gam.bar 2.1
Minimum Heap
|
 5. Mal.csimal heap
jika nilai
parent-nya
selalt:
lebih
besar
da:ripada kedua
children-nya
(lib.at gambar 2.2).
Ru'llUS:
r[i]
>
r[2iJ
dan r[i] > r[2Fl]
Gamba:r 2.2
Maksimal
Heap
Heap
bukan
search
tree
sebab
b:asanya
ya:g
dibutt:hkan
m:tuk
mendapatkan
ni:ai
terbesar
atau
terkecil
dari
tree
ad.a!ah
root
sehingga tidak
perlu
menelusuri
subtree
children-nya.
gan:bar
2.3
untul< contoh
heap.
Gambar 2.3
RepresentasiHecv
dalamArray
|
 14
Heap
disebtit
juga
complete
bina1y tree
kar;;:na
jika
suatu
node
menpunyai
child
maim jurrJah
child-nya
ha:us
sama
dengan
dua.
Q::eue
Queue
adalah
suatu
tipe
data
yang
berpola
HFO
(First
In
Out)
yang be arti
elemen
yz.ag
niasuk pertama
kali
adaiah
elemen
yang
dikeluarkan
pertama ka!i pu!.a
[2].
Hal
jpj
dapat
dilmtaka'l
sebagal
Queue
apabiia
terjadi
suatu
antrian,
dan
a.11tri ;1
yang
telja.di dikarenakan banyalmya
yang berdatangan secara
berurutan.
memilild
dua
je:is
operasi
dasar,
yaltu:
,,
enQueue
untuk
menambahkan
suatu
elemen pad<.
akhir dari
Queue.
deQueue
untuk
menghapus elemen
pada
awal
dari
Queue.
Gambar 2.4
mem;;erlihatkan
gambarl4'1 a.bstrak
dari
Queue.
Queue
Gambar 2.4
Model
Queue
CTffillbar
2.5
me!l'perlihatkan cara
kerja
dari fungsi
enQueue
dan
fungsi
deQueue
pads.
Queue
|
 15
Start
Add litem
Add6
Remove 1
item
Remove ³ items
Add2
items
Rernove 3 items
Add
1
it£m
back
back
back
front
I
I
back
back
back
front
back
|
 15
|
 16
Add6
items
Remove
7
items
back
front
back
Gambar
2.5
Contoh
ell\:JU<?Ue
darr
deQueue
pada
Queue
Konsep
dari Queue
atau
dalam
bahasa
Indonesia
iebih dikenal
antrian, banyak
pertoncton
membeli
tiket,
ant1::an pas1er;
kehidap&-'1 sehari-ha
antrian
ruang
tunggu
dokter,
antrian
pembaya
an
di
casar
swalayarr
da.c"11ain-1ain.
2J:.5
Priority Queue
Priority
Queue
adafah
Queue
berpola
HPIFO (Highest
Priority
In
Out)
Be:::-beda deng&t
Queue
sangat
berganrung kepada walo:u
eJerner:
yang
pertama
kali datar.g
diamb:il
atau
dihapus
pertarna
kali
pula),
pada
Frioritv
Queue
elemen
yang
n:e:miliki
prioritas
tertinggi
aka.'l
dian1hil
atau
dihz.pus
terl'ehih
dar'tulu (jika
waktu
kedatangan
prio:itas
maka
Priority
Queue
berfungsi
""'''"'rti
Queue).
Priority
Queue dibedakan merrjadi
yair:. :
"'
Ascending
Priority
Queue,
yang
menaik,
yaitu
prioritas
tertinggi.
Qu•eue
yang
diurutkan
dengan
nrimit
s
memiliki
prioritas
teremlih
sampai
|
 17
"
Descending
Priority
meue
yaitu
Queue
yang
diurutkan
dengan
plioritas
yang
menumn,
yaitu dari
elcme:n
yang
memiliki
prioritas
'"''m.l:>!!'
sar'lp::ri
prioritas
terendah.
Untuk
menyajikan
Priority
Queue
dilakukan dalam dua cara,
"
Set
data
dimasukkan ke
dalam Qu.eue
berdasarkan
waktu
ke:iat:mg:a:r,.
sedangkan pengambilannya
dari
pengguna"n
Set
adalah
enQueue sangat cepat dan
se<:ierha11a,
te:api
operasi
deQueue
menjadi sangat kompleks karena
pencarian
elemen
dengan
prioritas
tertinggi.
2.2.6
kcnsep
""j''"'" struktur
data yac"lg disebut :Ur1:p1uk:m
(stack) me palan salah satu
sangat
berg;.u:ca
dalam
ilmu
komputer.
pernrograman
backtracking,
stack ini
akan banyak
digunal<:an
baik
secara
sederhana
stack
y&ng
diletakkan di atas data
yang lain
[2].
Satu
nu""'""
berupa
linked list, Secara
yang seolal:-olah ada
data
per!u diingat
adalah
ballwa
dapat
ditambaJ!Llc<m
atau
disisipkru>
data
dan
mengambil
data
lewat
ujung
yang
sama,
yang
disebut
set•ag;J.i
atas
tumpukan (top of
stack),
Stack
w!;rupalem suatu
list
yang
mempunya
sifat
(Last In
First
Out)
yang
be:-CL-ti
elemen
yang
terakhir
ka!i
masuk
adalah
elemen
yang pertama
kaE
dikeluarkan,
Ada
dua
operasi dalam
stack, yaitu:
|
 18
"
Push
yaitu
operasi
untuk memasukkan
atau
menambah
suatu
data ke
dalam
tumpukan
(stack)
sampai batas-batas
tertentu.
"
Pop
yaitu
operasi
untuk mengelua.rkan data
tersebut dari
stack
sa.mpai
stack
tersebut
kosong.
Dan
masing-masing
cara
kerja
operasi
push
dan
pop dapat dilihat
pada
gambar
2.6 (Santosa,
1992,
p71-74)
[2].
Start
Push
"A"
Push
"B"
Push
"C"
6d
I
-=
I
A
Pop
|
 19
.
A
Pop
Gambar
2.6
Ilustrasi Cara
Kelja
Stack
Penjelasan
gambar 2.5
adaiah
sebagai ber'rkut:
,.
Operasi push
pada
stack:
Pert
Ina-tama.
diircisialisasikan
ter:ebih
dalmlu
sehingga stack
tersebut
lwsong.
Stack
dapaberupa array
mauplh"l
linkEd list,
kemadian
data
dimasukkan
ke
daiam
stack
yang
kosong
sehingga
menempati
urutan pertam.a pada
stack
yang
tadinya
kosong.
Lab ada cata
yang iuga
akar. dimasukki:4'1
daia:n
slack
&ehingga
stack
yang tadinya
h
'1ya data
"A''
kini berisi
data
d<m "B",
dengan
ketertuan data
"A''
menempati
urutan
pertama
sedangkan
data
"B" menempati
umt 'l kedua.
Kemudizn data
"C"
d
masukkan
lagi
daia:n
stack
sebingga
stack
tetsebut akhimya
berisi
"A'',
"B"
mene:npati
urutan pertama,
diikuti
ciengan
data
me:: empati
urutan kedua
dan
cata
"C"
mene:npati
umtan terakhir yaitu
urutaJl
ketiga.
"
Operasi
pop pada stack:
Stack
yang
telah berisi
data
"A",
"B"
cengan
ketentuan
data
"A" menempati urutan perta.ma,
data "B"
:nenemp<,t1
urutan
kedtia da11
data
"C"
rr:e;,ernpati
urutan
terakhir yaitu
urutan
ketiga
setelah
Gilak:t:;_l,:an operasi
pop
maka
operasi
|
 20
pop
pertama kali mengeluarkan
data
"C" yaita
data
yang
terakhir
dimasukkan ke
stack oleh operasi push tadi, kemudiar: berturL.t-
turut
operasi
pop
rnengeluarkan data
"B"
dan
kemudian data
"A:'.
2.3
Pen<::arian
Shorte.st Patil
Tujuan
pencarian
shortest
path
adaiah
untuk
menemukan jaian
terpendek
yang
d2ri
vertex awal
ke
vertex akhir.
Jika
edge
tidai<
me:niliki
nilai,
shortest path
adz.lai1
path
dengan
jumlah
edge
yang
;::aling sedikit.
Jika edge memiliki
nilai,
shortest path
adai O.
palh
dengan totai
minimum
dari
semua
edge
pada
path.
2.3.1
A!gorEtma Dijkstnt
Algoritma
Dijkstra
merr:pakar1
pengembangan
dari Breadth-First
Search.
Per")edaa!" yang
utama
terleta.lc pada d2ri
edge.
Jika
pada
Breadth-First
Search
setiap
edge mempunyai
ni1ai
sedangkar;
pada
Dijkstra
edge-rrya mempunyai r:ilai
dan
bernilai positif
merupa.lcan algo:-itrr.a
greedy
yang
berarti
jika
diba--ikan pilihan,
aitan
berope':asi
dengan
merr.ilih
pilihan
be:-r.i!ai ter'Claik
[
4l
Al.go:itma
Dijkstra
dibuat
ur.tu.i<
menemukan
path
bemilai
terendah di
antara
vertex
awal
tunggal
vertices
pada
t:fraph. Algor;tma
menja::nin
ditemukar.nya
shortest
path
semua
A.igoritma
Dijkstra
akan melihat
yang
terdeka:.:
dengan
start node
la!u
meli11at
tetangga.
node
tersebut
dan
kem:. d.ian
memperb2harui
jaraknya
dari
awal
Pada
Breadth-First
Search open list-nya
merupakan
FIFO queue
sedangkaa
open
·_,....._ merupakan
priority queue,
di
mana
node
yang
d'ambil
memiliki
|
 21
nilai
yang terbaik
yaitu path dari start
dengan
nilai
terendah
[3].
Jad
pada
algoritma
Dijkstra
hanya
dipenganJii
oleh satu faktor
nilai
dalam pengaturan
priority
queue
yaitu
berdasarkan :nilai
edge,
C
.
IR Kerja Algm:itma Dijk1tra
Algoritn:a
Dijkstra
merupaka'
[Clgoritn1l! utam.a
untuk
me;1emukan
shortest
path,
yang
secara
e5sien
menemukan
shortest
path
de.,
-
.
i
vertex
s
yang diberikan
ke
semua
V-i
vertices
lainnya
[
6]. Algoritma
Dijkstra
mulai
d<Li
s.
Pada
iterasi.,
mengidentifik:aslkan
vertex
barw
v
yang
shortest
path
dari s
ke v
diketahui.
Kumpulan
vertices
dari
yang
shortest path-nya
dati
v
diketahui
disimpa 1, cian
!n.u:tpulan
berke:nbang
satu vertex
pada
S(, tiap
iterasi. Pada setiap
i:terasi, edge
(u,v)
di
mana
u
E
v
E
V-R diidentifikasi.kan.
sedemikian
sehingga
dist(s,u}
+
weight(u,v) = min
dist(s,u')
+
weight(u',v)
di
rnana
(u', v)
E
E
Edge
(u,v)
ini
ditambahkan
ke
shortest
['A'lth
tree,
yang
root-nya
adalab
x dan
yang
mm1ggamharkan
semua
shortest
path
dari. x.
Il:putnya
e.dalah graph
G
(V,
E) dan source vertex s E V.
mana
V
adal&<t
mmpulan
vertices
sedangkan E
adalal:
kumpulac:
edge
dalam
G. Setta
mempunyai
fungsi edge
w(u,v)
2:
0,
'i
(u,v)
E
E.
Algoritma
ini
n:embagi
vertices,
V,
menjad'
dua kumpu!an yang
terp;sah,
V
=
R
u
Q.
Kumpulan tersehut,
mengar..deng
vertices
yang nilai
shortest
path
ak]ljmya
te!ah ditentukan
dan
kumpu!an
Q
=
V
-R. Ketika
vertex
dari
Q
ke
R,
vertex
te:-sebut
dikatakan "retired".
Beberapa
desk.tipsi
algoritma menyebut
Q
sebagai
"open set"
R sebagai
"closed
Cntuk
setiap
vertex,
v,
disimpan
nilai perkiraan
shortest
path
mir.imu.rn yang
sekarang
ini.
Vertex
|
 22
pendahulu
setiap
vertex
yang
telah
diku njung;
Juga akan disimparuntuk
membangun
ke:nbali
path
der,gan
backtrackir:g
tupan.
Algoritma
d?J&npseudocode,
bekerja
sebagai
berikut
[7]:
t:stre_(G,w,s)
R
=
Q
{}
for
a::..l
v
r2
V
do
g[v]
::o:.
r:
Q.:.:=r.ser{ v)
v[s)
:::;
0
wl:ile
{Q
*
[}) cio
1.<:
QuExtrac:t:Min ()
R
R
,_.,
{
u}
for
'J" G
Ne.ighbors{u}
do
(g v] >
g[ui
+ w(urv)) tl-::en
Q,DecreaseKey(v, g[uJ -T
w(u,.vj}
elf;:v] =
(u,v)
Kumpulan
Q
seharusnya
diterapkar:
sebagai priority queue
dengan
operasi
sebagai
berikut:
Q.lnsertfu)
menyisipkan
sebuah
vertex
ke
dalam queue,
Q.ExtractMinO
meminda:-,.kan elemen
v
E
Q
dengan
g[v]
terkec;l,
Q.DecreaseKey(>>,a)-
menun;n1,an g[v)
ke a,
dan
:nemperbaharui
queue.
Algoritrrirj
bekerja
dengan
mengambil
vertex
v
E
Q
dengan
perkiraan
shortest
path
n1i:rdm.urrr,
secara
beru!a.ng ulang.
Karer:a semua
nila:
edge
adalah
positif,
tida.k dapat
menemukan
shortest
path
dengan
memperpanjang
path
dali
vertices !a.innya.
Jadi
telah ditentu.ka11 shortes! perth
ke v
dan
dapat
me-retire
nya R
Kemudian
diperiksa
jika
beberapa
perpanja'lgan
da:i
path
yang
optimal
ke tetangganya
me:upaka.:a
.s Jortest
dari
perkiraan
shortest path
yang sekarang
u:1tuk tetangganya
masing
rm1s11:,g. Jika
demikian,
maka
perkiraan
shortest
path
rum
vertex
pendahulu
diperbahami
(me
refax)
untuk
tetangga
yang
sesaai
Karena
vertex
berrilai
terbaik
dipilih
berulang
ulang da.n
me relax nya,
algoritrr"'- menjadi £e!as dari
metode
'greedy· relaxation.
|
 23
Pada
!)enerapan
praktis,
Q
riapat
dibagi
merrjadi
dua subset
y&"lg
te isah, U
dar!
PQ
di
mana
dinulai,
mengandung semua
vertices
kecuali
s
dan
PQ
digunakan
sebagai
pengg&'1ti Q
di
atas.
Vertices
kemudian
dipindalikruo
dari
ke
dalam
PQ
ketika
vertices
tersebut
nertama
ka!i dikunjur:gi.
Selalu
menja.ga
priority
queue
PQ
sekecil
mungkin
dapat
me1 adi
sangat berrnanfaat
untuk
kinerja. algoritma ini.
Sekaa semua node
yang
berdekatan dengan
vertex
awal
diproses,
diiabel dan
di
enqueue, algoritma
men-dequeue
node
pertama.
Semua
node yang berdekatar:
dengan
vertex
yang
belu.cn
dikunjungi,
se
1
.az:tjutnya
r'labelkan
dan
eli-enqueue.
Sebagai
talnbata.n,
bebera!)a. node
yang
telah dikanjur:.g
tetapi
dapat
diraih
lebih
o:nuda!1
diberi
label
kembaii
da;1 di-enqueue [
"l
Proses
berlanjut
sampai
U
kosong.
Relatiamil
Database
Groff
dan
Weinberg
[8}
berpe:
dapat bahwa
relational
database
adaiah
database
di
r..mna
se'!lua
dat"
yang
terlihat
oleh
user
disus:.n
da!arn
bentuk
tabel
dari
nilai-nilai
data
dan
di
'!lar:a semua
operasi
pada
database
bekerja
pada
tabel-tabe!
tersebut.
Dalam
relational
database
terdapat
primwy
key
dan
foreign
key.
Primary key
adaJah
kandidat key yang
untuk
mengdenti:fikasilam
kclom secara u.r.ik
pada
sua:u
relasi.
Sedangkan
foreign
key
adalah
suatu
atribut
atau
lrumpulan
dari
atribut
atribut
dalam
suatu
relasi yang
sama
dengan kandidat
key
dari
beberapa
relasi
[9].
Ada
ti.ga jenis
relasi antar nlasing-1nasing
record-nya,
yai:u :
Relasi one-to-one
adalah
relasi
antara
satv. record dengan satu
record
dalam
tahel
yang
saling
bercmbungan.
Re!asi one-to-many
men:pal,a.."l
relasi
satu
record
dala.'!l tabel
yang
saling
berhtxb.it,Ul <l,1},.
|
 24
Re!asi
many-to-many
:nerupakan re[asi antara
banyak
record
dengarr iebih
drui satu
record
dalam tabel yang salirrg berhubunga11.
2.5
SQ.L
Kroenke
[1OJ
mengemukakan
bahwa SQL adatah
bal:utsa
yang
digunakarr
untuk
membuat
struktur
dan
mel ..:kan
proses
pada
relational
database.
Maka
dengan
meuggun:Lka•1 SQL dapa:t
diouat
struktur-stnktur database
dan relasi
antara tabel
tabe!nya. Selain
itu
juga
dapat
dilakukan proses
penyisipan data (insert), pengubahan
data
(update),
pengambilan
data
(select),
dan
penghapusan data
(delete).
WebSeM>er
December dan Randall [l !]
meP.genmka.1car1 bahwa web
server
adalah kon:puter
yang di
dalarnnya
terdapat
dokume1:
web
dan
ko:nputer
tersebut
menja!a11kan
software
HTTP
(HyperText
Transport
Protocolj
yang
memurrgkinkan
te:fjadir:ya
transaksi
pada
web.
'Jahulu
l''eb
server
sering
d
;alarka_Tl pada platform
U.l','IX,
sedangkarc pada
saat
sekarang
sudah banyak
platform
yang dapat
digunaka11 sebagai
web
server.
Sebagai
contolt.'tya adalah Windows
Cara
ke!ja web
server
adaiah
jika
user
mengjnginkan
S'latu
halan1an
web
maka
sebual1 koneksi IP
(Internet Protocol)
dibuat
:ntemet
antara brOH/Ser user
dengan
host
yang
menjala:1kan
web
server.
Halamc.n
web
yang diinginkarr
akan dikirim
mel<:.:ui koneksi tersebut, dan setelah sampa.i pada
user,
koneks:akan ten:mrus.
|
 2.7
WAP
WM
singkatan
da.-i
Wireless
Application
Protocol,
merupakan
sebuah
spesi±ikasi
untuk
mengembanb1Q,n
apli_1Q,si
seperti
1<eb
yang
bekerja mela!d
sebuah
jaringan tfl.lipa
k
bel [i2j. WM
telah
menjadi
standar tak
:-esmi un:u_k
komunikasi tanpa
kabel
dari
isi
Il'temet
I
Intranet.
Yang
berarti,
spesifikasi
giobal
yang
rr:eC sta.ndarisasikan
penyampaiarr isi
dari
web
ke
alat-alat
tanpa
kabel
dan
bekerja
derrgan
semua
standar
jaringan
selular.
TujuaJl
uta.ma
dari
W."J' adalah
tL'ltuk
menyediakan
jasa
!ayanan
seperti web
pada alat-alat
berukuran
kecil yang
dapat
dibawa
--
seperti
telepon selular
dan
PDA.
2.
Penentuan Posisi
deng:n1WAP
Pene:
taau:
posisi
dengan
W
AI>
tidak
dapat
di!akukan
tanpa
me:Iggunakan
beberapa
software
taml:ahan
pada
te!epon selciar
dar:
pihak
operator.
(Dan
kemungkinan
beberapa
hardware
pada
piha.ok operator,
tergantilllg
pada
solusi
yang
dipilih).
Berikat
ada!ah
peqjelasan
mengenai
software-only Location Service
[13]
:
1. Client
me:ninta
location-based service
da:i web server,
melalui WML
deck.
2.
Web
sen•er
meminta
pemeriksaan
lokzsi
umuk dilakukan
oleh
mobile
operator's
location
server
-
sebua.o'J plaiform
yang
dapat
mengkonversi
infon:nasi
cell menjadi
infiort:lasi
geografis.
3
.
Location
server
'silent
SMS
ke
telepon
selciar
(nelalui
SMS
Centre).
4.
Aplikasi
untctk
mengetahui
lokasi
yang
ada
pada telepon.
SL:vf/ROM
mengumpulkan
data
kekuatan
sinyal
dan
waktt;:
pengiriman
sel"a
mengetr4:t{llil>;an data,
server-, cengan ;silent SMS.
|
 26
5.
Location
server
kemudian
melakukan
kalkulasi
dali
setiap
kekaatatl sinyal,
perkiraa:J
posisi
dari
client
di
dalam
format
yaiJg
diset:ujui,
refererJii
grid
sebagaii'ya.
6.
Location
server mengembalikan has::perhitungan
ke web
server.
7.
Web server
rnenggur:akan hasil
perhitungan
untuk
melakukan
pencarian
lokasi
|