tugas ai 1- searching

Laporan

Penerapan Algoritma UCS dan A*

Disusun untuk memenuhi tugas pada mata kuliah Kecerdasan Buatan

Oleh

Ufra Neshia 1107124177

Ivan Rekyan Fitrayana 1107090021

Adyo Subhodo 1107100014

Program Studi Ilmu Komputasi

Fakultas Teknik

Telkom University

2014

A. Menentukan Peta

Peta yang digunakan dalam laporan ini adalah peta pulau Jawa yang diambil dari Google Map dan digambarkan dalam bentuk graf untuk memudahkan pencarian rute.

Gambar 1: Peta Asli

Gambar 2: Graf

Graf terdiri atas 19 simpul berupa kota-kota yang terletak di daerah jawa, dengan simpul awal (start) adalah Depok dan simpul akhir (Goal) adalah Klaten.

B. Menghitung Nilai Heuristik

Dalam sebagian algoritma pencarian perlu diketahui nilai heuristik, yaitu jarak berupa garis lurus suatu simpul ke simpul akhir, yang didapatkan dengan rumus:

dab=√¿¿¿Dalam laporan ini, nilai heuristik dicari dengan memanfaatkan koordinat bujur

dan lintang (Longitude dan Latitude) kota yang disediakan oleh Google Maps. Nilai heuristik dihitung dengan menjadikan garis lintang sebagai y dan bujur sebagai x, nilai lintang dan bujur kemudian dikonversi ke dalam satuan kilometer dengan mengalikan sebesar 111 km, lalu dihitung nilai d dengan rumus di atas.

KotaLatitude

(x)Longitude

(y) Xb-Xa Yb-YaXb-Xa (KM)

Yb-Ya (KM) h(n) dalam KM

Cilegon 106.034 -5.992 4.557 -1.704 505.857 -189.104 540.047Serang 106.150 -6.106 4.442 -1.589 493.052 -176.370 523.648Jakarta 106.847 -6.194 3.744 -1.502 415.615 -166.671 447.789Depok 106.831 -6.379 3.761 -1.316 417.476 -146.064 442.291Sukabumi 106.922 -6.918 3.670 -0.777 407.339 -86.257 416.372Bandung 107.609 -6.907 2.982 -0.789 331.045 -87.544 342.425Pamanukan 107.821 -6.283 2.771 -1.413 307.589 -156.816 345.257Subang 107.762 -6.318 2.830 -1.377 314.105 -152.882 349.335Indramayu 108.325 -6.302 2.267 -1.394 251.606 -154.700 295.360Cirebon 108.551 -6.730 2.041 -0.965 226.513 -107.107 250.559Babakan Gerbang 108.717 -6.864 1.875 -0.831 208.092 -92.230 227.615Brebes 109.049 -6.866 1.542 -0.829 171.185 -92.008 194.344Garut 107.909 -7.227 2.683 -0.469 297.814 -52.012 302.322Tasik 108.213 -7.311 2.379 -0.384 264.018 -42.619 267.436Purwokerto 109.248 -7.428 1.344 -0.267 149.168 -29.655 152.087Kebumen 109.653 -7.656 0.939 -0.039 104.190 -4.381 104.282Klaten 110.592 -7.695 0.000 0.000 0.000 0.000 0.000Semarang 110.417 -6.954 0.175 -0.742 19.436 -82.323 84.586Salatiga 110.473 -7.294 0.118 -0.401 13.142 -44.546 46.444

C. Menentukan Rute Menggunakan Algoritma UCS

Keterangan:

Node : Best Node

Frontier : Open Node

Explored : Closed Node

Cost : Jarak

n : Suksesor

procedure UniformCostSearch(Graph, root, goal)

node := root, cost = 0

frontier := priority queue containing node only

explored := empty set

do

if frontier is empty

return failure

node := frontier.pop()

if node is goal

return solution

explored.add(node)

for each of node's neighbors n

if n is not in explored

if n is not in frontier

frontier.add(n)

else if n is in frontier with higher cost

replace existing node with n

Langkah penelusuran dengan metode UCS

IterasiOpen

Closed Best NodeUbah

ParentAsal Node Jarak/Cost (km)

0 - Depok 0 - - -

1 Depok

Jakarta 132

Depok Sukabumi -Serang 104

Sukabumi 92,4Subang 144

2Depok

Jakarta 132Depok,

SukabumiSerang -

Serang 104Subang 144

Sukabumi Bandung 186,8

3Depok

Jakarta 132Depok,

Sukabumi, Serang

CilegonSubang 129,5

Sukabumi Bandung 144Serang Cilegon 186,8

4Depok

Jakarta 132 Depok, Sukabumi,

Serang, Cilegon

JakartaSubang 144

Sukabumi Bandung 186,8

5

Depok Subang 144 Depok, Sukabumi,

Serang, Cilegon, Jakarta

SubangSukabumi Bandung 186,8

Jakarta Pamanukan 153,8

6

Sukabumi Bandung 186,8 Depok, Sukabumi,

Serang, Cilegon, Jakarta, Subang

Bandung

Jakarta Pamanukan 153,8

Subang Indramayu 224,3

7

Jakarta Pamanukan 153,8 Depok, Sukabumi,

Serang, Cilegon, Jakarta, Subang, Bandung

Pamanukan

Subang Indramayu 224,3

Bandung

Cirebon 324,8

Garut 252,3

8

BandungGarut 252,3 Depok,

Sukabumi, Serang, Cilegon, Jakarta, Subang,

Bandung, Pamanukan

Indramayu

Cirebon 324,8

Pamanukan Indramayu 219,3

9 Bandung Garut 252,3 Depok, Garut


Bandung, Pamanukan, Indramayu

Indramayu Cirebon 274,2

10

Indramayu Cirebon 274,2 Depok, Sukabumi,

Serang, Cilegon, Jakarta, Subang,

Bandung, Pamanukan, Indramayu,

Garut

CirebonGarut

Babakan 400,3

Tasikmalaya 305,6

11

Bandung Tasikmalaya 400,3 Depok, Sukabumi,



Garut, Cirebon

BabakanCirebon

Babakan 304,9

Brebes 346,5

12

Garut Tasikmalaya 400,3 Depok, Sukabumi,



Garut, Cirebon, Babakan

BrebesCirebon Brebes 346,5

13 Garut Tasikmalaya 400,3 Depok, Sukabumi,



Garut,

TasikmalayaBrebes Semarang 519,5

Salatiga 565,5

Cirebon, Babakan,

14

BrebesSemarang 519,5 Depok,



Garut, Cirebon, Babakan, Brebes,

Tasikmalaya

Semarang

Salatiga 565,5

Tasikmalaya Purwokerto 540,3

15

Brebes Salatiga 565,5 Depok, Sukabumi,




Tasikmalaya, Semarang

PurwokertoTasikmalaya Purwokerto 540,3

16

Brebes Salatiga 565,3 Depok, Sukabumi,




Tasikmalaya, Semarang,

Purwokerto

SalatigaPurwokerto Kebumen 738,3

17 Purwokerto Kebumen 738,3 Depok, Sukabumi,

Serang,

KlatenSalatiga Klaten 623,5

Cilegon, Jakarta, Subang,


Garut,

18 - - -

Depok, Sukabumi,




Tasikmalaya, Semarang,

Purwokerto, Salatiga, Klaten

- -

Jadi rute yang dipilih sesuai algoritma di atas adalah

Depok Jakarta Pamanukan Indramayu Cirebon Brebes Salatiga Klaten

dengan total jarak 623,7 km.

D. Menentukan Rute Menggunakan Algoritma A*

Algoritma A* adalah algoritma pencarian yang menggabungkan kelebihan Greedy Search (operasi yang lebih ringkas, namun tidak komplit dan tidak optimal) serta Uniform Cost Search (komplit dan optimal namun waktu operasi lama). Hal ini didapatkan dengan menggunakan f(n)=h(n)+g(n), di mana h(n) adalah nilai heuristik yang digunakan dalam pencarian Greedy dan g(n) adalah nilai asli dari suatu node ke goal yang digunakan dalam Uniform Cost.

Langkah pencarian: 1. Dari starting point/initial node, akan dibentuk suatu himpunan simpul2 yang akan

diperiksa nilainya (open).2. Dari simpul-simpul open akan diambil yang nilai f(x) terkecil dan dipindahkan ke

himpunan simpul closed, simpul yang dipindahkan ini disebut best node.3. Tetangga-tetangga best node kemudian akan dibangkitkan, dimasukkan ke open

node untuk diperiksa nilai f(x). 4. Nilai f(x) di bagian open selalu diupdate setiap kali Best Node dipindah ke closed5. Pencarian berhenti saat f dan g goal node bernilai paling kecil.

function A*(start,goal) closedset := the empty set // Simpul yang sudah diperiksa (closed) openset := {start} //simpul-simpul yang hendak diperiks (open) came_from := the empty map // peta/jalur suatu node g_score[start] := 0 // Biaya jalur terbaik //Estimasi biaya dari awal ke akhir melalui y f_score[start] := g_score[start] + heuristic_cost_estimate(start, goal) while openset is not empty current := the node in openset having the lowest f_score[] value if current = goal return reconstruct_path(came_from, goal) remove current from openset add current to closedset for each neighbor in neighbor_nodes(current) if neighbor in closedset continue tentative_g_score := g_score[current] + dist_between(current,neighbor) if neighbor not in openset or tentative_g_score < g_score[neighbor] came_from[neighbor] := current g_score[neighbor] := tentative_g_score f_score[neighbor] := g_score[neighbor] + heuristic_cost_estimate(neighbor, goal) if neighbor not in openset add neighbor to openset return failure function reconstruct_path(came_from, current_node) if current_node in came_from p := reconstruct_path(came_from, came_from[current_node]) return (p + current_node) else return current_node

Tabel Tracing:

i BN Closed Suksesor Open Ubah Parent?

1 Depok DepokJakarta, Serang, Sukabumi, Subang

Jakarta Serang Sukabumi Subang

-

2 Jakarta Depok,JakartaCilegon, Pamanukan

Serang Sukabumi Subang Cilegon Pamanukan

-

3 PamanukanDepok,Jakarta,Pamanukan

Subang , Indramayu

Serang Sukabumi Subang Cilegon Pamanukan Indramayu

Subang tidak diubah parent karena jarak Subang via Pamanukan lebih besar daripada via Depok

4 SubangDepok,Jakarta,Pamanukan,Subang

Pamanukan,Indramayu,Bandung

Serang Sukabumi Subang Cilegon Indramayu Bandung

Indramayu: Tidak, karena jarak Indramayu via Pamanukan lebih kecil daripada dari Subang

5 IndramayuDepok,Jakarta,Pamanukan,Subang,Indramayu

Subang,CirebonSerang Sukabumi Subang Cilegon Bandung Cirebon

Subang: Tidak karena jarak dari Depok lebih kecil daripada dari Indramayu

6 CirebonDepok,Jakarta,Pamanukan,Subang,Indramayu,Cirebon

Bandung,Babakan,Brebes

Serang Sukabumi Subang Cilegon Bandung Babakan Brebes

Bandung: Tidak karena jarak dari Subang lebih kecil daripada bila parent Bandung diganti menjadi Cirebon

7 Babakan

Depok,Jakarta,Pamanukan,Subang,Indramayu,Cirebon,Babakan

Garut, Brebes

Serang Sukabumi Subang Cilegon Bandung Brebes Garut

Brebes: Tidak, karena jarak Brebes lebih kecil bila parentnya tetap Cirebon daripada Babakan

8 Brebes

Depok,Jakarta,Pamanukan,Subang,Indramayu,Cirebon,Babakan,Brebes

Babakan ,Tasik,Semarang,Salatiga

Serang Sukabumi Subang Cilegon Bandung Garut Tasik Semarang Salatiga

Babakan: Tidak karena jaraknya akan lebih kecil bila parent tetap Cirebon daripada Brebes

9 Semarang

Depok,Jakarta,Pamanukan,Subang,Indramayu,Cirebon,Babakan,Brebes,Semarang,Salatiga

Salatiga

Serang Sukabumi Subang Cilegon Bandung Garut Tasik Salatiga

Salatiga: Tidak karena jaraknya akan lebih kecil bila parent tetap Brebes daripada Semarang

10 Salatiga

Depok,Jakarta,Pamanukan,Subang,Indramayu,Cirebon,Babakan,Brebes,Semarang

Purwokerto,Klaten

Serang Sukabumi Subang Cilegon Bandung Garut Tasik Purwokerto Klaten

-

11 Klaten

Didapati rute Depok ke Klaten:

DepokJakartaPamanukanIndramayuCirebonBrebesSalatigaKlaten

Total Jarak = 623.7 KM

E. Perbandingan Kedua Rute yang Didapat

Jumlah Iterasi Nilai Solusi Waktu Complete OptimalUCS 14 623.7 Lebih lama Ya YaA* 11 623.7 Lebih cepat Ya Ya

F. Kesimpulan

Pencarian dengan menggunakan algoritma UCS dan A* akan menghasilkan solusi yang komplit dan optimal. Namun algoritma UCS memiliki waktu komputasi yang lebih tinggi dikarenakan jumlah iterasi yang lebih besar. Karena optimal, maka kedua algoritma menghasilkan solusi yang sama yaitu rute Depok-Jakarta-Pamanukan-Indramayu-Cirebon-Brebes-Salatiga-Klaten dengan jarak tempuh terpendek dibandingkan jalur lain yaitu 627.7 KM.

tugas ai 1- searching

Documents