5. METODE PENCARIAN DAN PELACAKAN 2 (HEURISTIK)

Heuristikadalahsebuahteknikyang mengembangkanefisiensidalamprosespencarian, namumdengankemungkinanmengorbankankelengkapan(completeness).Fungsiheuristikdigunakanuntukmengevaluasikeadaan-keadaanproblemaindividual danmenentukanseberapajauhhaltersebutdapatdigunakanuntukmendapatkansolusiyang diinginkan.

5.1 Best First Search

Metodeinimerupakankombinasidarimetodedepth-first searchdanbreadth-first search. Padametodebest-first search, pencariandiperbolehkanmengunjunginode yang adadilevel yang lebihrendah, jikaternyatanode padalevel yang lebihtinggiternyata memilikinilaiheuristic yang lebihburuk.

FungsiHeuristikyang digunakanmerupakanprakiraan(estimasi) cost dariinitial statekegoal state, yang dinyatakandengan:

f’(n) = g(n) + h’(n)

dimanaf’= Fungsievaluasi

g = cost dariinitial statekecurrent state

h’= prakiraancost daricurrent stateke goal state

Contoh: Node M merupakan keadaan awal dan noda T merupakan tujuannya. Biaya edge yang menghubungkan node M dengan node A adalah biaya yang dikeluarkan untuk bergerak dari kota M ke kota A. Nilai g diperoleh berdasarkan biaya edge minimal. Sedangkan nilai h’ di node A merupakan hasil perkiraan terhadap biaya yang diperlukan dari node A untuk sampai ke tujuan. h’(n) bernilai ~ jika sudah jelas tidak ada hubungan antara node n dengan node tujuan (jalan buntu). Kita bisa merunut nilai untuk setiap node. 

Terdapat dua jenis algoritma Best First Search, yaitu:

Greddy Best yang hanya memperhitungkan biaya perkiraan saja.

Greedy Best First Search hanya memperhitungkan biaya perkiraan (estimated cost) saja, yakni:

f(n) = h(n)
Dimana : h(n)= perkiraan biaya dari simpul n ke goal.

Biaya yang sebenarnya (actual cost) tidak diperhitungkan. Dengan hanya memperhitungkan biaya perkiraan yang belum tentu kebenarannya maka algoritma ini menjadi tidak optimal.

Algoritma greddy best ini membentuk solusi langkah per langkah (step by step). Pada setiap langkah, terdapat banyak pilihan yang perlu dieksplorasi. Oleh karena itu, pada setiap langkah harus dibuat keputusan yang terbaik dalam menentukan pilihan.

A* yang memperhitungkan gabungan dua biaya, biaya sebenarnya dan biaya perkiraan.

Algoritma ini merupakan algoritma Best First Search yang menggabungkan Uniform Cost Search dan Greddy Best First Search. Algoritma ini memperhitungkan biaya dari biaya sebenarnya ditambah dengan biaya perkiraan. Dalam notasi matematika dituliskan sebagai:

f(n) = g(n) + h(n)dimana : g(n) = biaya sebenarnya untuk mencapai simpul n,

h(n) = perkiraan biaya dari simpul n ke goal,

f(n) = perkiraan total biaya jalur yang melalui simpul n ke goal.

Dengan perhitungan biaya seperti ini, algoritma A* adalah complete dan optimal.

5.2 Problem Reduction

Dalam teori komputabilitas dan teori kompleksitas komputasi , pengurangan adalah transformasi dari satu masalah ke masalah lain. Tergantung pada transformasi yang digunakan ini dapat digunakan untuk mendefinisikan kelas kompleksitas pada serangkaian masalah.

Problem reduction atau yang biasa dikenal dengan constraint, intinya adalah berusaha mengurangi masalah dengan harapan masalah yang bersangkutan menjadi lebih mudah diselesaikan. Sekarang ini sudah diketahui teknik konsistensi ini sangat penting dalam penyelesaian constraint satisfactionproblem yang sangat berat sehingga semua aplikasi komersial penyelesaian constraint satisfactionproblem menggunakan teknik konsistensi ini sebagai langkah dasar.

Sejarah konsistensi constraint dapat ditlusuri dari peningkatan efisiensi program pengenalan gambar oleh peneliti di intelejensi semu. Pegenalan gambar melibatkan pemberian label kepada semua garis pada gambar dengan cara yang konsisten. Jumlah kombinasi pemberian label pada garis yang memungkinkan dapat menjadi sangat besar, sementara hanya sedikit yang konsisten pada tahap awal. Dengan demikian memperpendek pencarian untuk pembeian nilai yang konsisten.Untuk mengilustrasikan teknik konsistensi ini akan diberikan sebuah contoh constraint satisfaction problem yang sangat sederhana.

Anggap A < B adalah constraint antara variabel A dengan domainDA = { 3..7} dan variabel B dengan domain DB = { 1..5}. dengan jelas tampak bahwa bahwa untuk sebagian nilai pada DA tidak ada nilai yang konsisten di DB yang memenuhi constraint A < B dan sebaliknya. Niai yang demikian dapat dibuang dari domain yang berkaitan tanpa kehilangan solusi apapun. Reduksi itu aman. Didapatkan domain yang tereduksi DA = {3,4} dan DB = {4,5}.

Perhatikan bahwa reduksi ini tidak membuang semua pasangan yang tidak konsisten. Sebagai contoh kumpulan label (<A, 4>, <B, 4>) masihh dapat dihasilkan dari domain, tetapi untuk setiap nilai A dari DA adalah mungkin untuk mencari nilai B yang konsisten dan sebaliknya.

Walaupun teknik konsistensi ini jarang digunakan sendirian untuk menghasilkan solusi, teknik konsistensi ini membantu menyelesaikan constraint satisfactionproblemdalam beberapa cara. Teknik konsistensi ini dapat dipakai sebelum pencarian maupun pada saat pencarian.

Constraint sering direpresentasikan dengan gambar graf (gambar 1) di mana setiap verteks mewakili variabel dan busur antar verteks mewakili constraint binari yang mengikat variabel-variabel yan dihubungkan dengan busur tersebut. Constraint unari diwakilkan dengan busur melingkar. Kebanyakan solusi menggunakan pohonOR,dimana lintasan dari awal sampai tujuan tidak terletak pada satu cabang. Bila lintasan dari keadaan awal sampai tujuan dapat terletak pada satu cabang, maka kita akan dapat menemukan tujuan lebih cepat.
 

5.3 Constraint Satisfaction

Problem search standard :

·  state adalah "black box“

·  setiap struktur data yang mendukung fungsi successor, fungsi heuristik dan tes goal.

   CSP:

· state didefinisikan sebagai variabel Xi dengan nilai dari domain Di – Tes goal adalah sekumpulan constraint yang menspesifikasikan kombinasi dari nilai subset variabel.

Contoh sederhana adalah bahasa representasi formal.

CSP ini merupakan algoritma general-purpose dengan kekuatan lebih daripada algoritma pencarian standar.

Contoh : Pewarnaan Peta 

                                 

Ø  Variabel WA, NT, Q, NSW, V, SA, T

Ø  Domain Di = {red,green,blue}

Ø  Constraints : daerah yang bertetangga dekat harus memiliki warna yang berbeda.

Ø  Contoh WA ≠ NT, atau (WA,NT) {(red,green),(red,blue),(green,red), (green,blue),(blue,red),(blue,green)}

Ø  Solusi lengkap dan konsisten, contoh : WA = red, NT = green,Q = red,NSW = green,V = red,SA = blue,T = green

Constraint Graf

Binary CSP biner : setiap constraint merelasikan dua variabel

Graf Constraint : node adalah variabel, arc adalah constraint

5.4 Means End Analysis

MEA adalah strategi penyelesaian masalah yang diperkenalkan pertama kali dalam GPS (General Problem Solver). Proses pencariannya berdasarkan ruang masalah yang menggabungkan aspek penalaran forward dan backward. Perbedaan antara state current dan goal digunakan untuk mengusulkan operator yang mengurangi perbedaan itu. Keterhubungan antara operator dan perbedaan tsb disajikan sebagai pengetahuan dalam sistem (pada GPS dikenal dengan Table of Connections). Contoh OPERATOR first-order predicate calculus dan operator tertentu mengijinkan perbedaan korelasi task-independent terhadap operator yang menguranginya. MEA meningkatkan metode pencarian heuristik lain (di rata-rata kasus) dengan pemusatan pemecahan masalah pada perbedaan yang nyata antara current state dengan goal-nya.

REFERENSI :

·         http://ichaajja212.blogspot.co.id/2012/10/heuristic-search-techniques-problem.html

·         http://shabri-prayogi.blogspot.co.id/2013/08/teknik-pencarian-heuristik-heuristic.html

·         lutfiatulm.blogspot.com/2013/03/representasi-pengetahuan.html

Pengenalan Teknologi Sistem Cerdas

Materi Minggu 1

PENGENALAN INTELEGENSI BUATAN

 PENGERTIAN INTELEGENSI BUATAN

Kecerdasan Buatan ( Artificial Intelligence ) adalah salah satu cabang Ilmu pengetahuan berhubungan dengan pemanfaatan mesin untuk memecahkan persoalan yang rumit dengan cara yang lebih manusiawi. Hal Ini biasanya dilakukan dengan mengikuti/mencontoh karakteristik dan analogi berpikir dari kecerdasan/Inteligensia manusia, dan menerapkannya sebagai algoritma yang dikenal oleh komputer.
      Pengertian lain dari kecerdasan buatan adalah salah satu cabang ilmu computer yang mempelajari bagaimana cara membuat sebuah mesin cerdas, yaitu mesin yang mempunyai kemampuan untuk belajar dan beradaptasi terhadap sesuatu.

SEJARAH INTELEGENSI BUATAN

Teori-teori yang mengarah ke KB sudah muncul sejak tahun 1941. Berikut ini tahap-tahap sejarah perkembangan KB :

A.Era Komputer Elektronik (1941)

·         Ditemukannya pertama kali alat penyim-panan dan pemprosesan informasi yang disebut komputer elektronik. Penemuan ini menjadi dasar pengembangan program yang mengarah ke KB.

B. Masa Persiapan KB (1943 – 1956)

·         Tahun 1943, Warren McCulloch dan Walter Pitts 

mengemukakan tiga hal, yaitu :

a. pengetahuan fisiologi dasar dan fungsi sel syaraf

dalam otak

b. analisis formal tentang logika proposisi (propositional logic)

c.teori komputasi Turing

·         Tahun 1950, Norbert Wiener membuat penelitian mengenai prinsip-prinsip teori feedback. Contoh yang terkenal adalah thermostat. Penemuan ini juga merupakan awal dari perkembangan KB.

·         Tahun 1956, John McCarthy meyakinkan Minsky, Claude Shannon dan Nathaniel Rochester untuk membantunya melakukan penelitian dalam bidang Automata, Jaringan Syaraf dan pembelajaran intelijensia. 

Mereka kerjakan projek ini selama dua tahun di Dartmouth. Hasilnya adalah program yang mampu berpikir non-numerik dan menyelesaikan masalah pemikiran yang dinamakan Principia Mathematica. Hal ini menjadikan McCarthy disebut sebagai ”Bapak Kecerdasan Buatan”.

 LINGKUP INTELEGENSI BUATAN

Sistem pakar : Komputer digunakan sebagai saran untuk menyimpan pengetahuan para pakar. Dengan demikian komputer akan memiliki keahlian untuk menyelesaikan masalah dengan meniru keahlian yang dimiliki para pakar.

Pengolahan bahasa alami : Dengan pengolahan bahasa alami ini diharapkan user mampu berkomunikasi dengan komputer dengan menggunakan bahasa sehari-hari.

Pengenalan ucapan : Melalui pengenalan ucapan diharapkan manusia mampu berkomunikasi dengan komputer dengan menggunakan suara.

Robotika dan Sistem sensor.

Computer vision, mencoba untuk dapat mengintrepetasikan gambar atau objek-objek tampak melalui komputer.

Intelligent Computer aid Instruction : Komputer dapat digunakan sebagai tutor yang dapat melatih dan mengajar.

Materi Minggu 2

PENGENALAN INTELEGENSI AGENTS

Kecerdasan buatan atau dalam bahasa inggrisnya Artificial Intelligence sering disingkat dengan AI yang merupakan cabang terpenting dalam dunia komputer. Akhir-akhir ini, teknologi AI telah begitu banyak mempengaruhi kehidupan manusia. AI kini berada disekeliling kita, di dalam kehidupan sehari-hari kita, boleh dikatakan tidak ada satu pun peralatan yang tidak menggunakan teknologi AI. Di rumah, radio, mesin cuci, kulkas, ponsel, dll dilengkapi dengan Integrated Circuit komputer yang mempunyai AI. Dengan kata lain AI ialah ilmu dan rekayasa yang membuat mesin mempunyai intelligensi tertentu khususnya program komputer yang ‘cerdas’ (John McCarthy, 1956).

Pengertian sebuah AGENT adalah segala sesuatu yang dipandang sebagaimana mengamati lingkungannya melalui sensor dan bertindak atas lingkungan yang melalui efektor. Agen manusia memiliki mata, telinga, dan organ lain untuk sensor, dan tangan, kaki, mulut, dan bagian tubuh lainnya untuk efektor. Sebuah pengganti agen robot kamera dan berbagai pencari inframerah untuk sensor dan berbagai motor untuk efektor.

Agen dan Lingkungannya

Agen Intelligent sering digambarkan secara skematis sebagai sistem fungsional abstrak mirip dengan program komputer. Untuk alasan ini, agen cerdas kadang-kadang disebut agen cerdas abstrak s (AIA) Untuk membedakan mereka dari dunia nyata implementasinya sebagai sistem komputer, sistem biologis, atau organisasi. Beberapa definisi dari agen cerdas mereka menekankan otonomi , sehingga lebih memilih cerdas agen otonom jangka s. Yang lain (terutama Russell & Norvig (2003) ) perilaku goal-directed dianggap sebagai inti dari kecerdasan dan sebagainya lebih suka istilah yang dipinjam dari ekonomi , ” agen rasional “.

Agen Cerdas dalam kecerdasan buatan berhubungan erat dengan agen di ekonomi , dan versi dari paradigma agen cerdas yang dipelajari dalam ilmu kognitif , etika , filsafat alasan praktis , serta di banyak interdisiplinersosio-kognitif pemodelan dan sosial simulasi komputer.

Intelligent agen juga berhubungan erat dengan agen perangkat lunak (program perangkat lunak otonom yang melaksanakan tugas atas nama pengguna). Dalam ilmu komputer , agen cerdas istilah dapat digunakan untuk merujuk kepada agen perangkat lunak yang memiliki kecerdasan tertentu, terlepas jika tidak agen rasional oleh dan Norvig Definisi Russell. Sebagai contoh, program otonom digunakan untuk bantuan operator atau data mining (kadang-kadang disebut sebagai bot).

Lingkungan Tugas Agen, merupakan definisi dari pemasalahan yang akan diselesaikan oleh agen.antara lain :

1. Performance Measure

karakteristik apa yang menjadi tujuan dari agen ?

contoh : motor - tiba ditujuan dengan cepat dan hemat bahan bakar 

2. Environment

bagaimana karakterisitik lingkungan yang akan dihadapi ?

contoh : motor - tipe jalan, tingkat kemacetan

3. Actuators

perangkat apa yang dibutuhkan agen untuk mencapai tujuan ?

contoh : motor - steering, klakson dll 

4. Sensors

perangkat apa yang dibutuhkan agen untuk mengetahui kondisi lingkungan ?

contoh : motor – speedometer

RASIONALITAS

Rational Agent merupakan suatu agent yang selalu bertindak memaksimalkan ukuran kinerja, mengingat apa yang ia amati tentang lingkungan dan pengetahuan lain yang dimilikinya. Mengevaluasi kinerja sangat penting. Kita harus berhati-hati untuk membedakan antara rasionalitas dan omniscience (kemahatahuan). Rasionalitas bahwa agen tahu hasil dari sebuah tindakan yang dilakukan secara rasional. Sedangkan omniscience adalah sebuah kemustahilan dari kenyataan yang sebenarnya telah terjadi. Faktor yang mempengaruhi rasionalitas :

-          Pengukuran kinarja (Performance Measure)

-          Percept Sequence (persepsi urutan)

-          Knowledge from Environment

-          Possible Actions

TIPE-TIPE LINGKUNGAN AGEN

·        Fully observable (vs. Partially observable): sensor-sensor sebuah agen memberinya akses ke keadaan lengkap lingkungannya pada setiap jangka waktu.

·        Deterministic (vs. Stochastic): keadaan lingkungan berikutnya sepenuhnya ditentukan oleh keadaan sekarang dan tindakan yang dilaksanakan oleh agen. (Jika lingkungan itu deterministik kecuali untuk tindakan agen-agen lain, maka lingkugannya adalah strategic)

·        Episodic (vs. Sequential): pengalaman agen dibagi ke dalam “episode-episode” atomik (setiapepisode terdiri dari si agen) memahami (perceiving) dan kemudian melaksanakan satu tindakan, dan pilihan tindakan dalam tiap episode hanya tergantung pada episode itu sendiri.

·        Static (vs. Dynamic): lingkungan tidak berubah selagi agen direncanakan (deliberating). (Lingkungan adalah semidynamic jika lingkungan itu sendiri tidak berubah dengan berjalannya waktu tetapi skor performa agen berubah)

·        Discrete (vs. Continuous): sejumlah terbatas persepsi dan tindakan yang khas dan terdefinisi baik.

·        Single agent (vs. Multiagent): sebuah agen yang mengoperasikan dirinya sendiri dalam sebuah lingkungan

·        Jenis lingkungan sangat menentukan rancangan agen

·        Dunia nyata (tentu saja) partially observable, stochastic, sequentil, dynamic, continuous, multi-agent.

Tipe-tipe Agen

·        Autonomy: Agent dapat melakukan tugas secara mandiri dan tidak dipengaruhi secara langsung oleh user, agent lain ataupun oleh lingkungan (environment). Untuk mencapai tujuan dalam melakukan tugasnya secara mandiri, agent harus memiliki kemampuan kontrol terhadap setiap aksi yang mereka perbuat, baik aksi keluar maupun kedalam [Woolridge et. al.,1995].

·        Intelligence, Reasoning, dan Learning: Setiap agent harus mempunyai standar minimum untuk bisa disebut agent, yaitu intelegensi (intelligence). Dalam konsep intelligence, ada tiga komponen yang harus dimiliki: internal knowledge base, kemampuan reasoning berdasar pada knowledge base yang dimiliki, dan kemampuan learning untuk beradaptasi dalam perubahan lingkungan.

·        Mobility dan Stationary: Khusus untuk mobile agent, dia harus memiliki kemampuan yang merupakan karakteristik tertinggi yang dia miliki yaitu mobilitas. Berkebalikan dari hal tersebut adalah stationary agent. Bagaimanapun juga keduanya tetap harus memiliki kemampuan untuk mengirim pesan dan berkomunikasi dengan agent lain.

·        Delegation: Sesuai dengan namanya dan seperti yang sudah kita bahas pada bagian definisi, agent bergerak dalam kerangka menjalankan tugas yang diperintahkan oleh user. Fenomena pendelegasian (delegation) ini adalah karakteristik utama suatu program disebut agent.

·        Reactivity: Karakteristik agent yang lain adalah kemampuan untuk bisa cepat beradaptasi dengan adanya perubahan informasi yang ada dalam suatu lingkungan (enviornment). Lingkungan itu bisa mencakup: agent lain, user, adanya informasi dari luar, dsb [Brenner et. al., 1998].

·        Proactivity dan Goal-Oriented: Sifat proactivity boleh dikata adalah kelanjutan dari sifat reactivity. Agent tidak hanya dituntut bisa beradaptasi terhadap perubahan lingkungan, tetapi juga harus mengambil inisiatif langkah penyelesaian apa yang harus diambil [Brenner et. al., 1998]. Untuk itu agent harus didesain memiliki tujuan (goal) yang jelas, dan selalu berorientasi kepada tujuan yang diembannya (goal-oriented).

·        Communication and Coordination Capability: Agent harus memiliki kemampuan berkomunikasi dengan user dan juga agent lain. Masalah komunikasi dengan user adalah masuk ke masalah user interface dan perangkatnya,sedangkan masalah komunikasi, koordinasi, dan kolaborasi dengan agent lain adalah masalah sentral penelitian Multi Agent System (MAS). Bagaimanapun juga untuk bisa berkoordinasi dengan agent lain dalam menjalankan tugas,perlu bahasa standard untuk berkomunikasi. Tim Finin [Finin et al., 1993] [Finin et al., 1994] [Finin et al., 1995] [Finin et al., 1997]dan Yannis Labrou [Labrou et al., 1994] [Labrou et al., 1997] adalah peneliti software agent yang banyak berkecimpung dalam riset mengenai bahasa dan protokol komunikasi antar agent. Salah satu produk mereka adalah Knowledge Query and Manipulation Language (KQML). Kemudian masih berhubungan dengan ini komunikasi antar agent adalah Knowledge Interchange Format (KIF).

Materi Minggu 3

PENGENALAN LOGICAL AGENTS

Logic merupakan jantung dari program, para pemrogram mempunyai keyakinan bahwa sebuah computer dapat dibuat mengerti logika, maka computer dapat dibuat untuk berfikir, karena logika kelihatannya menjadi inti dari kecerdasan.

1  Problem solving agent hanya bisa menyelesaikan masalah yang lingkungannya accessible

2  Kita membutuhkan agen yang dapat menambah pengetahuan dan menyimpulkan keadaan

3  Agent yang akan membantu seperti ini kita beri nama knowledge based agent

Knowledge based agent

Komponen utama dari knowledge based agent adalah knowledge basenya. Knowledge base (KB) adalah kumpulan representasi fakta tentang lingkungan atau dunia yang berhubungan atau menjadi daerah bekerjanya agen. Setiap representasi dalam KB disebut sebagai sebuah sentence yang diekspresikan dalam sebuah bahasa yakni knowledge representation language

Propositional Logic.

Proposional logic berupa kalimat-kalimat lengkap dari fakta atau kenyataan, atau bisa dikatakan sebuah propositional logic bisa merupakan sebuah proposisi adalah kalimat yang berbentuk dengan sendirinya, apakah kalimat itu bernar atau kalimat itu salah. Propositional logic merupakan operator-operator untuk menghubungkan proposisi-proposisi dalam bentuk, ungkapan dan ekspresi, sebagai kata penyambung logika.

 Beberapa Jenis Logical Agents

Agen teknologi Logika membedakan dirinya dengan kesederhanaan, fleksibilitas dan kemampuan memperingatkan terintegrasi. Dengan fasilitas layanan mandiri yang sederhana, Agen Logic “RulePoint” dirancang untuk pengguna bisnis untuk menentukan aturan untuk peristiwa dan tindakan terkait. Dengan sifatnya yang fleksibel, Agen Logic “RuleCast” memungkinkan pengembang untuk membuat acara aturan Pengolahan Streaming untuk satu set beragam sumber data seperti antrian pesan, database, feed telemetri dan sistem kontrol. Selain itu, dengan kemampuan memperingatkan terintegrasi, Agen Logic ”Real-Time” memberikan intelijen tepat waktu mengenai peluang dan ancaman yang diidentifikasi oleh RulePoint.

 Bersama-sama, dengan arsitektur-event, portofolio produk Logic Agen memungkinkan organisasi untuk meraih kelincahan yang lebih besar.

Kombinasi Agen Logika dan Informatika akan memajukan teknologi kepemimpinan Informatika dalam dua cara yang mendasar. Pertama, kombinasi Agen Logic Kompleks Event Pengolahan dan Platform Informatika memungkinkan jenis lain dari proyek integrasi data yang lebih luas.

Kedua, kombinasi dari Agen Logic Kompleks Event Pengolahan dan Informatica Identitas Resolusi mendukung identitas sadar pengolahan acara. Integrasi data aktif dan identitas-sadar pengolahan acara akan memungkinkan berbagai aplikasi di bidang jasa keuangan, kesehatan dan, khususnya, sektor publik.

Materi Minggu 4

Metode Pencarian dan Pelacakan

Pencarian dan pelacakan merupakan suatu hal penting dalam suatu sistem. Karena pencarian dan pelacakan ini adalah hal yang menentukan keberhasilan sistem tersebut. Pada dasarnya, metode pencarian dan pelacakan dibagi dua, yaitu pencarian buta (blind search) dan pencarian tersusun (heuristic search).

Pencarian Melebar Pertama (breadth-search first)

Pencarian melebar pertama dilakukan dengan melakukan pencarian dengan cara mencari yang dilakukan dengan cara melebar dari node pertama hingga berlanjut kepada node di level selanjutnya. Dimulai pada node n, dan dilanjutkan n+1. Pencarian akan terus dilakukan dari akar kiri ke kanan hingga hasil ditemukan.

Metode ini memiliki keuntungan dan kekurangan, yaitu :

Keuntungan

Tidak akan menemui jalan buntu

Jika ada satu solusi, maka breadth first akan menemukannya. Dan jika ada lebih dari satu solusi, maka solusi minimum akan ditemukan.

Kekurangan

Membutuhkan memori yang cukup banyak, karena menyimpan semua node dalam satu pohon.

Membutuhkan waktu yang cukup lama karena akan menguji n level untuk mendapatkan solusi pada level yang ke-(n+1)

Pencarian Mendalam Pertama (depth-search first)

Pencarian metode ini melakukan pencarian pada semua node "anaknya" sebelum dilakukan pencarian ke node-node lain yang selevel. Pencarian dimulai dari node akar ke level yang lebih tinggi, dan proses terus diulang hingga solusi ditemukan.

Keuntungan dari metode ini adalah menggunakan memori yang relatif kecil, dan jika pencarian tepat, akan menemukan solusi tanpa harus menguji lebih banyak node. Namun, metode ini tetap memiliki kelemahan, yaitu memungkinkan hasil tidak ditemukan, dan setiap 1 kali pencarian hanya akan menghasilkan satu solusi.

Pencarian Tersusun (Heuristik)

Pencarian tersusun atau pencarian heuristik merupakan suatu teknik yang digunakan untuk meningkatkan efisiensi dalam proses pencarian. Metode heuristik menggunakan suatu fungsi yang menghitung biaya perkiraan dari suatu simpul tertentu menuju ke simpul tujuan.

Dalam pencarian state space, heuristik adalah aturan untuk memilih cabang-cabang yang paling mungkin menyebabkan penyelesaian permasalahan dapat diterima.

Generate and test

Ini adalah gabungan dari pencarian depth first dengan pelacakan mundur. Nilai dari pengujian ini berupa "ya" atau "tidak". Pencarian ini memiliki beberapa algoritma, yaitu :

Bangkitkan suatu kemungkinan solusi (membangkitkan suatu titik tertentu atau lintasan tertendu dari keadaan awal).

Uji untuk melihat apakah node tersebut benar-benar merupakan solusinya dengancara membandingkan node tersebut atau node akhir dari suatu lintasan yang dipilih merupakan tujuan yang diharapkan.

Kelemahan dari generate and test adalah perlunya membangkitkan semua kemungkinan sebelum dilakukan pengujian, serta membutuhkan waktu yang cukup lama dalam pencarian.

Hill climbing

        Metode ini hampir sama dengan generate and test, perbedaannya ada pada feedback dari prosedur test untuk pembangkitan keadaan berikutnya. Tes yang dilakukan berupa fungsi heuristik akan menunjukkan seberapa baik nilai terkaan yang diambil terhadap keadaan lain yang memungkinkan. Algoritma dari pencarian ini adalah :

Mulai dari keadaan awal, jika merupakan tujuan, maka berhenti; tapi jika tidak, lanjutkan dengan keadaan sekarang sebagai keadaan awal.

Kerjakan langkah-langkah berikut hingga solusinya ditemukan, atau hingga tidak ada lagi operator baru yang diaplikasikan pada keadaan sekarang :

Cari operator yang belum pernah digunakan sebagai operator untuk keadaan baru

evaluasi keadaan baru tersebut

jika keadaan baru adalah tujuan, keluar.

jika bukan tujuan namun nilai lebih baik, keadaan baru akan digunakan sebagai keadaan sekarang.

jika  keadaan baru tidak lebih baik, maka lanjutkan interasi.

          Kelemahan pada sistem ini adalah algoritma akan berhenti ketika mencapai optimum local, urutan penggunaan operator akan sangat berpengaruh, dan tidak diijinkan untuk melihat langkah sebelumnya.

Sumber : 

http://citrarhmdn.blogspot.co.id/2016/10/pengenalan-intelegensi-buatan-kb-minggu.html

http://sarahamanda12.blogspot.co.id/2016/10/pengenalan-intelligent-agents.html

https://rinnooberta.wordpress.com/2013/10/18/2-logical-agents/

http://citrarhmdn.blogspot.co.id/2016/10/metode-pencarian-dan-pelacakan-1-minggu.html