KECERDASAN BUATAN _ PERTEMUAN 4,5,6,7

KECERDASAN BUATAN 

informatika B 2018

PERTEMUAN 4,5,6,7 

 

Blind search yaitu algoritma paling dasar untuk searching yang bisa dibilang belum ada kcerdasan buatannya..Blind Search tidak ada informasi mengenai jarak cost dari current state ke goal state.

Untuk mengukur Performansi  metode  pencarian, terdapat 4 kriteria yang digunakan yaitu :

Completeness, apakah metode tersebut menjamin penemuan solusi jika solusinya memang ada ? 

Optimality, apakah metode tersebut menjamin menemukan solusi yang terbaik jika terdapa beberapa solusi yng berbeda ?

Time complexity, berapa lama waktu yang dibutuhkan ?

compexity, bera banyak memory yang diperlukan ?

Adapun 6 metode tang tergolong dalam Blind Search 

Breadth-First Search (BFS)

Algoritma BFS  menjelajahi node tetangga terlebih dahulu, sebelum pindah ke tingkat tetangga berikutnya dan juga algoritma BFS   menggunakan konsep first-in-first-out.BFS mengingat semua node tyang dikunjungi sebelumnya.BFS  menggunakan function (Graph,root).Perfomance dari BFS yaitu Complete dan Optimal.

Depth-First Search (DFS)

DFS  memperluas node terdalam yang belum diperluas. DFS menggunakan Algoritma  konsep last-in-first-out.DFS hanya mengingat jalur yang dikunjungi saat ini sedangkan Algoritmayang  digunakan yaitu STACK. Perfomance dari  DFS  yaitu Not complete and  Not Optimal.

 Depth-Limited Search (DLS)

Metode ini berusaha mengatasi kelemahan DFS (tidak complete) dengan membatsi kelemahan maksimum dari suatu jalur solusi. Algortima ini merupakan variasi dari DFS. Jika DFS melakukan perhitungan dengan cara menghabiskan semua tingkatan atau kedalaman dari sebuah titik, maka algoritma ini memiliki batasan dimana perhitungan pada sebuah titik hanya dihitung sampai pada kediaman tertentu. 

Uniform Cost Search (UCS)

Algoritma merupakan graph yang digunakan untuk menyelesaikan beberapa persoalan. Algoritma ini memulai pencarian dari root node, kemudian dilanjutkan ke node-node selanjutnya. Algoritma ini merupakan modifikasi dari BFS.

 Iterative-Deepening Search (IDS)

IDS merupakan metode yang menggabungkan kelebihan BFS (Complete dan Optimal) dengan kelebihan DFS (space complexityjika rendah atau membutuhkan sedikit memori).Tetapi konsekuwensinya adalah time complexitynya menjadi tinggi.

 Bi-Directional Search (BSD)

Pencarian dilakukan dari dua arah : pencarian maju (dari start ke goal) dan pencarian mundur (dari goal ke start).Ketika dua arah pencarian telah membangkitkan simpul yang sama, maka solusi telah ditemukan, yaitu dengan cara menggabungkan kedua jakur tang bertemu.