Kecerdasan Buatan " Graf Simetris "

Nama Mata Kuliah    : Kecerdasan Buatan

Tugas ke                      : 2

Dosen Pengampu       : Asriyanik, M.T.

 

Soal:

1.       Gambar di bawah ini adalah sebuah graf simetris tak berarah yang menggambarkan kondisi jalan raya di suatu kota. Terdapat 8 simpul yang menyatakan persimpangan jalan dengan posisi-posisi koordinat dua dimensi (x,y). Setiap busur memiliki 2 atribut, angka pertama menyatakan panjang jalan sebenarnya (dalam satuan kilo meter), dan angka yang berada dalam tanda kurung, menyatakan kecepatan maksimum yang diperbolehkan untuk setiap kendaraan yang melalui jalan tersebut (dalam satuan km/jam). Seorang pimpinan satuan pemadam kebakaran, yang berada di persimpangan S, bermaksud memadamkan api di sebuah gedung yang terletak di persimpangan G. Dia menggunakan mobil pemadam kebakaran dengan kecepatan maksimum 90 km/jam. Bantulah petugas tersebut menemukan rute jalan dengan total waktu tercepat dari S ke G dengan menggunakan Metode A*.

Penyelesaian :

Pertama kita tentukan terlebih dahulu

Titik awal : S

Simpul / titik / node terdekat : A,B,C

Tentukan F(n)

F(n)= g(n) + h(n)

F adalah titik tujuan (GOAL)

G adalah jarak antar node

H adalah perkiraan jarak garis lurus dari node ke node tujuan

Masukan A,B,C ke dalam (n)

F(A)= g(A) + h(A) = 5 + 5 = 10

F(B)= g(B) + h(B) = 10 + 3 = 13

penjelasan 3 dari mana. 3 tersebut diambil dari garis lurus B, cara mendapatkannya pertama bisa dilihat dari titik koordinat, yang kedua bisa menggunakan tripel phytagoras dari segitiga SBA. 

F(C)= g(C) + h(C) = 5 + 5 = 10

Best node : A dan C (karena sama sama bernilai 10)

Closed list : S

Opened list : A,B,C

Pertama kita coba menggunakan simpul / node A

Closed list : A

Titik tetangga : B dan D

Karena kecepatan maksimum dari mobil pemadam kebakaran hanya 90 km/jam, jadi jalur

AB dan AD tidak bisa kita lalui

Kedua menggunakan simpul / node C

Closed list : C

Titik tetangga : B dan F

Karena kecepatan maksimum dari mobil pemadam kebakaran hanya 90 km/jam, jadi jalur, CB tidak bisa kita lalui.

f (F) = SC+CF+h(F) = 5+12+(5+12) = 34

Best node : F

Closed list : F

Titik tetangga : E dan G

F(E)= SC+CF+h(E) = 5+12+4+ (5+12+4) = 42

F(G)= SC+CF+h(G) = 5+12+5+ (5+12+5) = 44

Best node : E

Akan tetapi karna EG harus dengan kecapatan km/jam, maka jalur ini tidak bisa digunakan.

 

HASIL AKHIR

Dari hasil akhir didapatkan bahwa jalur terpendek dilalui melalui titik S>C>F>G dengan nilai 44.