A. FIRST ORDE LOGIC
First-order logic itu salah satu jenis sistem formal, yang digunakan untuk membuktikan kebenaran dari sebuah pernyataan.
Dalam first-order logic, setiap pernyataan dianggap memiliki predikat. Predikat itu dapat menghubungkan pernyataan yang satu dengan yang lain.
Kalimat-kalimat dalam first-order-logic dibuat dengan format P( X,  Y). P adalah predikat dan X adalah subjek. Y adalah objek, yang merupakan variabel yang opsional.
Contoh kalimatnya adalah sebagai berikut:
Kalimat asli: James makan apel.
Kalimat FOL: makan(James, apel)
Kalimat FOL dapat juga diberikan kuantor dan tanda-tanda logika lain, seperti berikut:
Kalimat asli: James suka daging dan Daisy suka sayur.
Kalimat FOL: suka(James, daging) ^ suka(Daisy, sayur)

B.SYNTAX & SEMANTIC  FIRST ORDER LOGIC
Constants: KingJohn, 2, UI,Depok,...
Predicates: Brother, >,Loves,Membenci,Mengajar,...
Functions: Sqrt, LeftLegOf,Ayah,...
Variables: x, y, a, b,...
Connectives: ∧ ∨ ¬ ⇒ ⇔
Equality: = Quantifiers: ∀∃

∀            : Semua atau Seluruh
∃             : Ada atau Sebagian atau Beberapa
→          : Implikasi ( Jika .. maka .. )
↔          : Biimplikasi ( Jika .. dan .. hanya .. jika .. )
¬            : Negasi (Tidak atau bukan)
V            : Disjungsi (Atau)
∧           : Konjungsi (Dan)


C.SEMANTIK
Sama halnya dg. PL, sebuah kalimat FOL dikatakan true terhadap sebuah model. Namun, sebuah kalimat bisa diinterpretasikan banyak cara dalam sebuah model.
Model berisi: Objects: elemen-elemen di dalam dunia (domain elements) Relations hubungan antara elemen-elemen tsb. Sebuah interpretasi mendefinisikan referent (“yang dipetakan”)
Constant symbols→objects
Predicate symbols→relations
Function symbols→functional relations

• Kemungkinan model & interpretasi
  Entailment, validity, satisfiability, dll. didefinisikan untuk semua kemungkinan interpretasi dari semua kemungkinan model! Kalau mau dijabarkan semua kemungkinannya
  Menentukan entailment berdasarkan truth-table mustahil! Biasanya ada satu interpretasi yang “dimaksudkan”→ intended interpretation.
• Kalimat Atomik
  Atomik adalah suatu pernyataan yang tidak dapat dipecah-pecah lagi.
  
  • Cristiano Ronaldo pemain bola.
    
• kalimat kompleks merupakan kalimat yang mempunyai lebih dari satu verba utama atau predikat karena mempunyai dua aksi, peristiwa, atau kejadian.
  kalimat kompleks mempunyai ciri-ciri sebagai berikut :
  
  • Kalimat kompleks mempunyai dua buah beristiwa atau lebih. 
  • Kedua struktur pada kalimat kompleks dipisahkan dengan tanda koma atau konjungsi (kata penghubung). 
  • Kalimat kompleks mempunyai dua buah subjek dan predikat.

Contoh :
Shafira menyanyi di taman, burung pun bersiul dengan sangat merdu

EQUALITY
Kalimat term1 = term2 bernilai true di bawah sebuah interpretasi jhj term1 and term2 
me-refer ke object yang sama. 
Contoh:
Ayah(Anto) = Abdul adalah satisfiable
Anto = Abdul juga satisfiable!
Anto = Anto adalah valid.
Bisa digunakan dengan negasi untuk membedakan dua term: ∃x,y Mencintai(Anto,x)∧Mencintai(Anto,y) ∧¬(x = y) (Anto mendua!)
 Definisi Sibling: ∀x,y Sibling(x,y) ⇔ (¬(x =y)∧∃m,f ¬(m=f)∧ Parent(m,x)∧Parent(f,x)∧Parent(m,y)∧Parent(f,y)) 

ASSERTION
Kalimat FOL yang ditambahkan ke KB disebut assertion.
Contohnya:
TELL(KB,King(John)) TELL(KB,∀x King(x) ⇒Person(x))

QUERY
Lalu, kita bisa memberikan query, atau bertanya, kepada KB (ASK).
Contohnya: 
ASK(KB,King(John)) jawabannya adalah true.
ASK(KB,Person(John)) jawabannya adalah true.
ASK(KB,∃x Person(x)) jawabannya adalah{x/John} 

D.Inferensi Logika Orde pertama
   Distributif : (A Ù B) Ú C = (A Ú C) Ù (B Ú C)



F. Forward Chaining
 
G. Backward Chaining
 

H. RESOULUSIResolusi merupakan suatu teknik pembuktian yang lebih efisien, sebab fakta-fakta yang akan dioperasikan terlebih dahulu dibawa ke bentuk standar yang sering disebut dengan nama klausa. Pembuktian suatu pernyataan menggunakan resolusi ini dilakukan dengan cara menegasikan pernyataan tersebut, kemudian dicari kontradiksinya dari pernyataan-pernyataan yang sudah ada.
Resolusi adalah suatu aturan untuk melakukan inferensi yang dapat berjalan secara efisien dalam suatu bentuk khusus conjunctive normal form (CNF). Pada logika proposisi, prosedur untuk membuktikan proposisi P dengan beberapa aksioma F yang telah diketahui, dengan menggunakan resolusi.
Algoritma resolusi :

• Konversikan semua proposisi F ke bentuk CNF.
• Negasikan P, dan konversikan hasil negasi tersebut ke bentuk klausa. Tambahkan ke himpunan klausa yang telah ada pada langkah 1.
• Kerjakan hingga terjadi kontradiksi atau proses tidak mengalami kemajuan :
  
  • Seleksi 2 klausa sebagai klausa parent.
  • Bandingkan (resolve) secara bersama-sama. Klausa hasil resolve tersebut dinamakan resolvent. Jika ada pasangan literal L dan ￢L, eliminir dari resolvent.
  • Jika resolvent berupa klausa kosong, maka ditemukan kontradiksi. Jika tidak, tambahkan ke himpunan klausa yang telah ada.

SUMBER :
https://www.academia.edu/960824/Analisis_Semantik_dengan_Representasi_First_Order_Logic_dalam_Sistem_Tanya_Jawab
http://randysetiawan.blog.binusian.org/2014/03/30/ai-first-order-logic/
troublemackr.blog.binusian.org/2014/03/30/first-order-logic/
http://sarahamanda12.blogspot.co.id/2017/01/inferensi-dalam-logika-order-pertama.html
http://gofagofaa.blogspot.co.id/2016/12/inferensi-dalam-logika-order-pertama.html

A.PENGETAHUAN BERBASIS AGEN

Konsep dasar dari agen berbasis pengetahuan, yakni mengetahui hal-hal tentang dunia dan dapat melakukan reasoning (berpikir, bernalar) mengenai :

• Hal-hal yang tidak diketahui sebelumnya ( imperfect/partial information )
• Tindakan yang paling baik untuk diambil ( best action ) Hal-hal yang harus dipenuhi ketika membuat agen pengetahuan, antara lain:
• Dapat merepresentasikan world, state, action.
• Dapat menerima informasi baru (dan mengupdate representasinya)
• Dapat menyimpulkan pengetahuan lain yang tidak eksplisit ( hidden property )
• Dapat menyimpulkan action apa yang perlu diambil.

B. Logika
Bahasa formal untuk merepresentasikan fakta sedemikian sehingga. kesimpulan (fakta baru, jawaban) dapat ditarik. Ada banyak metode inference yang diketahui. Kita bisa membangun agent Wumpus World dengan logika: memanfaatkan perkembangan logika oleh ahli matematika, filsafat selama ratusan tahun. 

C. Logika Proposisi 
Logika proposisi merupakan ilmu dasar untuk mempelajari algortima dan logika, yang berperan sangat penting dalam pemrograman. yaitu bertransaksi atau berhubungan dengan nilai kebenaran atau kesalahan dari sebuah peryataan atau fakta yang ada di sekitar sekeliling kita.

1. Sintaks
   Sintak sebuah bahasa berhubungan dengan struktur bahasa. Sebagai contoh, untuk membentuk sebuah kalimat yang valid dalam bahasa kita memakai struktur: [subyek] + [kata kerja] + [kata benda]. Dengan memakai struktur ini, kita bisa membentuk kalimat, sebagai contoh: Saya makan nasi. Dalam hubungannya dengan bahasa pemrograman, kita harus memenuhi sintak (baca: aturan struktur bahasa) agar program dapat berjalan. Sebagai contoh, dalam bahasa BASIC, untuk mengassign sebuah variabel dengan sebuah nilai, kita memakai operand ‘=’, tetapi kalau dalam Pascal, kita pakai ‘:=’. Contoh dalam BASIC: a=1, tapi dalam bahasa Pascal, a:=1
   Atau jika lebih spesifik lagi sintak dapat diartikan aturan-aturan peng-code-an struktur suatu bahasa pemograman, ibarat grammar dalam berbahasa Inggris. Setiap jenis bahasa pemograman mempunyai aturan sintak yang berbeda.
   
2. Semantik
   Semantik sebuah bahasa menggambarkan hubungan antara sintak dan model komputasi. Sederhananya, semantik menjelaskan arti dari program. Analoginya sebagai berikut. Apabila kita memakai sintak [subyek] + [kata kerja] + [kata benda], kita bisa menghasilkan kalimat-kalimat. Apabila kita mengasilkan kalimat Saya makan nasi, maka kalimat ini memenuhi aturan sintak. Tapi, apabila saya membuat kalimat Saya makan batu, secara sintak kalimat ini sudah benar. Namun, secara semantik, kalimat ini tidak mengandung makna yang berarti.
   
3. Inferensi
   Inferensi pada logika proposisi dapat dilakukan dengan menggunakan resolusi. Metode inferensi adalah mekanisme berfikir dan pola-pola penalaran yang digunakan oleh sistem untuk mencapai suatu kesimpulan. Metode ini akan menganalisa masalah tertentu dan selanjutnya akan mencari  jawaban atau kesimpulan yang terbaik.
   
4. Ekuivalen
   Dua atau lebih pernyataan majemuk yang mempunyai nilai kebenaran sama disebut ekuivalensi logika dengan notasi “ dua buah pernyataan majemuk dikatakan ekuivalen, jika kedua pernyataan majemuk itu mempunyai nilai kebenaran yang sama untuk semua kemungkinan nilai kebenaran pernyataan-pernyataan komponen-komponennya.
   
5. Validitas
   Validitas adalah aspek kecermatan pengukuran. Suatu alat ukur yang valid dapat menjalankan fungsi ukurnya dengan tepat, juga memiliki kecermatan tinggi. Arti kecermatan disini adalah dapat mendeteksi perbedaan-perbedaan kecil yang ada pada atribut yang diukurnya.
   Dalam pengujian validitas terhadap kuesioner, dibedakan menjadi 2, yaitu validitas faktor dan validitas item. Validitas faktor diukur bila item yang disusun menggunakan lebih dari satu faktor (antara faktor satu dengan yang lain ada kesamaan). Pengukuran validitas faktor ini dengan cara mengkorelasikan antara skor faktor (penjumlahan item dalam satu faktor) dengan skor total faktor (total keseluruhan faktor).
   Validitas item ditunjukkan dengan adanya korelasi atau dukungan terhadap item total (skor total), perhitungan dilakukan dengan cara mengkorelasikan antara skor item dengan skor total item. Bila kita menggunakan lebih dari satu faktor berarti pengujian validitas item dengan cara mengkorelasikan antara skor item dengan skor faktor, kemudian dilanjutkan mengkorelasikan antara skor item dengan skor total faktor (penjumlahan dari beberapa faktor).
   
6. Satisfiabilitas
   Sebuah proposisi majemuk dikatakan satisfiable jika ada minimal satu nilai tabel kebenarannya yang bernilai TRUE (benar), Jika proposisi majemuk tersebut tidak memiliki nilai TRUE (benar) sama sekali dalam tabel kebenarannya, maka proposisi majemuk tersebut disebut tidak satisfiable

D. Pola Penalaran Pada Logika Proses

1. RESOULUSI
   Resolusi merupakan suatu teknik pembuktian yang lebih efisien, sebab fakta-fakta yang akan dioperasikan terlebih dahulu dibawa ke bentuk standar yang sering disebut dengan nama klausa. Pembuktian suatu pernyataan menggunakan resolusi ini dilakukan dengan cara menegasikan pernyataan tersebut, kemudian dicari kontradiksinya dari pernyataan-pernyataan yang sudah ada.
   Resolusi adalah suatu aturan untuk melakukan inferensi yang dapat berjalan secara efisien dalam suatu bentuk khusus conjunctive normal form (CNF). Pada logika proposisi, prosedur untuk membuktikan proposisi P dengan beberapa aksioma F yang telah diketahui, dengan menggunakan resolusi.
   Algoritma resolusi :

• Konversikan semua proposisi F ke bentuk CNF.
• Negasikan P, dan konversikan hasil negasi tersebut ke bentuk klausa. Tambahkan ke himpunan klausa yang telah ada pada langkah 1.

1. Kerjakan hingga terjadi kontradiksi atau proses tidak mengalami kemajuan :
   
   • Seleksi 2 klausa sebagai klausa parent.
   • Bandingkan (resolve) secara bersama-sama. Klausa hasil resolve tersebut dinamakan resolvent. Jika ada pasangan literal L dan ￢L, eliminir dari resolvent.
   • Jika resolvent berupa klausa kosong, maka ditemukan kontradiksi. Jika tidak, tambahkan ke himpunan klausa yang telah ada.
2. BACKWARD CHAINING
   Merupakan kebalikan dari forward chaining dimana mulai dengan sebuah hipotesa (sebuah objek) dan meminta informasi untuk meyakinkan atau mengabaikan. Backward chaining inference engine sering disebut: ‘Object-Driven/Goal-Driven‘.
3. FORWARD CHAINING
   Kadang disebut:data-driven karena inference engine menggunakan informasi yang ditentukan oleh user untuk memindahkan ke seluruh jaringan dari logika ‘AND’ dan ‘OR’ sampai sebuah terminal ditentukan sebagai objek. Bila inference engine tidak dapat menentukan objek maka akan meminta informasi lain. Aturan (Rule) di mana menentukan objek, membentuk path (lintasan) yang mengarah ke objek. Oleh karena itu, hanya satu cara untuk mencapai satu objek adalah memenuhi semua aturan.

E. Inferensi Proposisi yang efektif

1. Backtracking
   Algoritma backtracking merupakan salah satu metode pemecahan masalah yang termasuk dalam strategi yang berbasis pencarian pada ruang status. Algoritma backtracking bekerja secara rekursif dan melakukan pencarian solusi persoalan secara sistematis pada semua kemungkinan solusi yang ada. Oleh karena algoritma ini berbasis pada algoritma Depth-First Search (DFS), maka pencarian solusi dilakukan dengan menelusuri struktur berbentuk pohon berakar secara preorder. Algoritma backtracking merupakan bentuk tipikal dari algoritma rekursif.Saat ini algoritma backtracking banyak diterapkan untuk program games (seperti permainan tic-tac-toe, menemukan jalan keluar dalam sebuah labirin, catur, dll) dan masalah-masalah pada bidang kecerdasan buatan (artificial intelligence). 

F. Agen Berbasis Logika Proposisi

• Problem Solving Agent : memilih solusi diantara kemungkinan yang ada. Apa yang ia “ketahui” tentang dunia, pengetahuannya tidak berkembang untuk mencapai problem solution.
• Knowledge-based Agent : lebih “pintar”. Ia “mengetahui hal-hal tentang dunia dan dapat melakukan reasoning (berfikir, bernalar) mengenai :
  
  • Hal-hal yang tidak diketahui sebelumnya
  • Tindakan yang paling baik untuk diambil

SUMBER :
http://kadekdimas.blogspot.co.id/2015/12/algoritma-backtraking.html
http://divtor.blogspot.co.id/2016/10/logical-agent-m3.html
http://slametgo-blog.blogspot.co.id/2016/01/resolusi-logika-proposisi.html
https://melkianusbenusu.wordpress.com/category/logika-informatika/
http://qmc.binus.ac.id/2014/11/01/u-j-i-v-a-l-i-d-i-t-a-s-d-a-n-u-j-i-r-e-l-i-a-b-i-l-i-t-a-s/
https://irfanfahmisite.wordpress.com/2016/10/09/pengertian-dan-contoh-ekuivalensi/
http://umardanny.com/pengertian-metode-forward-dan-backward-chaining-sistem-pakar/
http://dokumenkul-dodiksriyanto.blogspot.co.id/2014/01/perbedaan-sintak-semantik-dan-logika.html

A. STRATEGI PENCARIAN BERBENTUK / HEURISTIC SEARCH STRATEGY

    Pencarian dengan algoritma ini menggunakan knowledge yang spesifik kepada permasalahan yang dihadapi disamping dari definisi masalahnya itu sendiri. Metode ini mampu menemukan solusi secara lebih efisien daripada yang bisa dilakukan pada metode uninformed strategy. 

1. Greedy Best First Search
   Metode pencarian ini melakukan ekspansi node yang memiliki jarak terdekat dengan goal. Namun, ekspansi yang dilakukan pada metode ini menggunakan evaluasi node hanya dengan melihat kepada fungsi heuristiknya. Dengan kata lain, yang dibandingkan untuk penentuan ekspansi node adalah nilai estimasi/prediksinya saja.
   f(n) = h(n)
2. A* Search
   Bentuk dari Best First Search yang paling dikenal adalah algoritma pencarian A* (dibaca dengan “A-star”). Sedikit berbeda dengan Greedy yang hanya melihat kepada nilai h(n), pencarian dengan A* melihat kepada kombinasi nilai dari pathnya yaitu g(n) dengan nilai estimasi yaitu h(n).
   f(n) = g(n) + h(n)
3. SMA* atau Simplified Memory Bounded A*
   SMA* atau Simplified Memory Bounded A* adalah algoritma pencarian jalur terpendek berdasarkan dari algoritma A*. Keuntungan utama dari algo SMA* adalah dia menggunakan bounded memory, sementara algo A* mungkin membutuhkan memori exponensial. Semua karakteristik di algo SMA* diturunkan dari A*.
   
   Seperti A *, algoritma SMA* memperluas cabang yang paling menjanjikan menurut heuristik. Apa yang membuat SMA * terpisah adalah SMA* memangkas simpul yang ekspansinya telah diungkapkan kurang menjanjikan dari yang diharapkan. Pendekatan ini memungkinkan algoritma untuk mengeksplorasi cabang dan backtrack untuk mengeksplorasi cabang lain.
   
   Ekspansi dan pemangkasan simpul didorong karena SMA* menjaga dua nilai f untuk setiap simpul. Simpul x menyimpan nilai f(x) yang memperkirakan biaya mencapai tujuan dengan mengambil jalan melalui simpul tersebut. Semakin rendah nilai, semakin tinggi prioritas. Seperti di A * nilai ini diinisialisasi dengan h (x) + g (x), tetapi kemudian akan diperbarui untuk mencerminkan perubahan estimasi ketika anak-anaknya diperluas. Sebuah simpul yang sudah diperluas sepenuhnya akan memiliki nilai f setidaknya setinggi dari suksesornya. Selain itu, simpul menyimpan nilai f dari suksesor terbaik yang telah dilupakan. Nilai ini dikembalikan jika suksesor yang telah dilupakan itu dinyatakan sebagai suksesor paling menjanjikan.
   
   SMA* merupakan algoritma yang:
   
   
   1. Bekerja dengan heuristic, seperti A*
   2. Selesai jika memori yang diperbolehkan cukup tinggi untuk menyimpan solusi terdangkal
   3. Optimal jika memori yang diperbolehkan cukup tinggi untuk menyimpan solusi optimal terdangkal, jika tidak dia akan mengembalikan solusi terbaik yang ada di memori
   4. Menjauhi pernyataan yang diulang-ulang selama batas memori memperbolehkannya
   5. Menggunakan semua memori yang ada
   6. Memperbesar batas memori dari algoritma hanya akan mempercepat perhitungan
   7. Ketika memori cukup ada untuk memuat seluruh pohon pencarian, maka perhitungan mempunyai kecepatan yang optimal 
    

B. FUNGSI HEURISTIK

     Heuristik adalah sebuah teknik yang mengembangkan efisiensi dalam proses pencarian (pencarian yang lebih simple). Namun kemungkinan juga dapat mengngorbankan kelengkapan (complateness).
Fungsi Heuristic digunakan untuk mengevaluasi keadaan-keadaan problema individual dan menentukan seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan

C. ALGORITMA PENCARIAN LOKAL  DAN MASALAH OPTIMISASI

1. HILL CLIMBING SEARCHMetode ini hampir sama dengan metode pembangkitan dan pengujian, hanya saja proses pengujian dilakukan dengan menggunakan fungsi heuristic. Pembangkitan keadaan berikutnya tergantung pada feedback dari prosedur pengetesan. Tes yang berupa fungsi heuristic ini akan menunjukkan seberapa baiknya nilai terkaan yang diambil terhadap keadaan-keadaan lainnyayang mungkin.
   
   Algoritma:
   
   1. Cari operator yang belum pernah digunakan; gunakan operator ini untuk mendapatkan keadaan yang baru.
   
   a) Kerjakan langkah-langkah berikut sampai solusinya ditemukan atau sampai tidak ada operator baru yang akan diaplikasikan pada keadaan sekarang : Cari operator yang belum digunakan; gunakan operator ini untuk mendapatkan keadaan yang baru.
   
   b) Evaluasi keadaan baru tersebut :
   
   • Jika keadaan baru merupakan tujuan, keluar
   • Jika bukan tujuan, namun nilainya lebih baik daripada keadaan sekarang, maka jadikan keadaan baru tersebut menjadi keadaan sekarang.
   • Jika keadaan baru tidak lebih baik daripada keadaan sekarang, maka lanjutkan iterasi.
2. SIMULATED ANNEALING SEARCHSimulated annealing adalah salah satu algoritma untuk untuk optimisasi yang bersifat generik. Berbasiskan probabilitas dan mekanika statistik, algoritma ini dapat digunakan untuk mencari pendekatan terhadap solusi optimum global dari suatu permasalahan. Masalah yang membutuhkan pendekatan SA adalah masalah-masalah optimisasi kombinatorial,
   di mana ruang pencarian solusi yang ada terlalu besar, sehingga hampir tidak mungkin ditemukan solusi eksak terhadap permasalahan itu. Annealing adalah satu teknik yang dikenal dalam bidang metalurgi, digunakan dalam mempelajari proses pembentukan kristal dalam suatu materi. Agar dapat terbentuk susunan kristal yang sempurna, diperlukan pemanasan sampai suatu tingkat tertentu, kemudian dilanjutkan dengan pendinginan yang perlahan-lahan dan terkendali dari materi tersebut. Pemanasan materi di awal proses annealing, memberikan kesempatan pada atom-atom dalam materi itu untuk bergerak secara bebas, mengingat tingkat energi dalam kondisi panas ini cukup tinggi. Proses pendinginan yang perlahan-lahan memungkinkan atom-atom yang tadinya bergerak bebas itu, pada akhirnya menemukan tempat yang optimum, di mana energi internal yang dibutuhkan atom itu untuk mempertahankan posisinya adalah minimum.
3. LOCAL BEAM SEARCH
   Local Beam Search adalah sebuah algoritma pencarian heuristik yang mengeksplor sebuah graf dengan cara meng- expand node anak yang paling “menjanjikan” (yang paling optimal) dalam sebuah memori yang terbatas. Algoritma ini merupakan optimisasi dari algortima pencarian breadth-first search dan best-first search dalam hal penggunaan memori.
   Algoritma ini pada setiap langkahnya seakan-akan memotong/memangkas node-node anak yang dianggap “kurang menjanjikan” (kurang optimal) untuk mengurangi kebutuhan memori penyimpanan yang akan digunakan.
   Pemotongan atau pemangkasan node anak ini ditentukan berdasarkan nilai heuristik yang spesifik terhadap permasalah yang dihadapi. Node-node anak yang disimpan sebagai kandidat node untuk di- expand inilah yang disebut dengan beam.
   Local Beam Search menggunakan algoritma breadth-first search untuk menelusuri
   (men- generate ) kemungkinan node yang akan di- expand (node-node anaknya), lalu mengurutkannya berdasarkan nilai heuristik masing-masing. Algoritma local beam search ini hanya mengambil/meng- expand node-node anaknya dengan jumlah tertentu saja dilihat dari nilai heuristik yang paling optimum (disebut dengan beam width ). Node-node yang berada pada urutan kurang dari beam width inilah yang nantinya akan di- expand . Semakin banyak beam width , maka semakin sedikit node-node anak yang akan dieliminasi. Untuk kasus dengan nilai beam width sama dengan tak terhingga ( infinite ), maka algoritma ini sama saja dengan algoritma breadth-first search .
4. GENETIC ALGORITHM
   Genetic Algorithm adalah Teknik pencarian yang di dalam ilmu komputer untuk menemukan penyelesaian perkiraan untuk optimisasi dan masalah pencarian. Algoritme genetik adalah kelas khusus dari algoritme evolusioner dengan menggunakan teknik yang terinspirasi oleh biologi evolusioner seperti warisan, mutasi, seleksi alam dan rekombinasi (atau crossover)
   • Mutasi : Mencoba kombinasi proses secara acak dan mengevaluasi hasilnya. 
   • Crossover : Mengombinasi bagian dari hasil yang baik dengan harapan dapat memperoleh hasil yang lebih baik. 
   • Seleksi : memilih proses-proses yang baik dan membuang yang jelek.
   
   Algoritme Genetik pertama kali dikembangkan oleh John Holland pada tahun 1970-an di New York, Amerika Serikat. Dia beserta murid-murid dan teman kerjanya menghasilkan buku berjudul "Adaption in Natural and Artificial Systems" pada tahun 1975.
   
   Algoritme Genetik khususnya diterapkan sebagai simulasi komputer dimana sebuah populasi representasi abstrak (disebut kromosom) dari solusi-solusi calon (disebut individual) pada sebuah masalah optimisasi akan berkembang menjadi solusi-solusi yang lebih baik. Secara tradisional, solusi-solusi dilambangkan dalam biner sebagai string '0' dan '1', walaupun dimungkinkan juga penggunaan penyandian (encoding) yang berbeda. Evolusi dimulai dari sebuah populasi individual acak yang lengkap dan terjadi dalam generasi-generasi. Dalam tiap generasi, kemampuan keseluruhan populasi dievaluasi, kemudian multiple individuals dipilih dari populasi sekarang (current) tersebut secara stochastic (berdasarkan kemampuan mereka), lalu dimodifikasi (melalui mutasi atau rekombinasi) menjadi bentuk populasi baru yang menjadi populasi sekarang (current) pada iterasi berikutnya dari algoritme.

D. AGEN PENCARIAN ONLINE DAN  LINGKUNGAN YANG TIDAK DIKETAHUI 

     Agen yang berupa perangkat lunak, atau bisa disebut agen cerdas, adalah perangkat lunak yang dapat bertindak seperti orang yang mampu berinteraksi dengan lingkungan. Contoh:

1. Agen sistem operasi digunakan untuk membantu penggunaan sistem operasi digunakan untuk membantu penggunaan sistem operasi. Contoh, microsoft memiliki sejumlah agen yang dinamakan wizard pada sistem operasi yang di buatnya; misalnya Windows NT. Agen ini digunakan antara lain untuk menambah nama pemakai, mengelola grup pemakai, dan manajemen berkas.
2. Agen spreadsheet digunakan untuk membuat program spreadsheet menjadi lebih mudah digunakan oleh pemakai. Contoh, Office Assistant pada excel dapat “mengamati” pemakaidan jika terjadi sesuatu yang perlu untuk dibantu, agen cerdas akan memberikan saran. 
3. Agen untuk perdagangan elektronis digunakan untuk membantu pemakai yang akan melakukan belanja secara online.

Sumber :
http://socs.binus.ac.id/2013/04/23/uninformed-search-dan-informed-search/
http://fitribby.blogspot.co.id/2014/10/algoritma-pencarian-simplified-memory.html
https://rinnooberta.wordpress.com/2013/10/29/pencarian-heuristik/
https://www.coursehero.com/file/21999190/Local-Beam-Search/
https://id.wikipedia.org/wiki/Algoritma_genetik
http://tekomp13unpad.blogspot.co.id/2013/09/kecerdasan-buatan.html

A. AGEN PEMECAH PERMASALAHAN

Kecerdasan Buatan di ciptakan untuk memecahkan masalah di berbagai bidang yaitu :
Untuk membangun system yang mampu menyelesaikan masalah, perlu dipertimbangkan 4 hal :

1. Mendefinisikan masalah dengan tepat
   
   • Spesifikasi yang tepat mengenai keadaan awal
   • Solusi yang diharapkan 
2. Menganalisis masalah serta mencari beberapa teknik penyelesaian masalah yang sesuai 
3. Merepresentasikan pengetahuan yang perlu untuk menyelesaikan masalah 
4. Memilih teknik penyelesaian masalah yang terbaik

B. PENCARIAN SEBAGAI SOLUSI PEMECAHAN MASALAH
Searching di dalam AI (Artificial Intelligence) adalah salah satu motode penyelesaian masalah dengan pencarian solusi pada suatu permasalahan yang dihadapi.
Teknik searching sendiri terbagi menjadi dua, yaitu:

1. Blind searching
   Blind Searching adalah model pencarian buta atau pencarian yang tidak memiliki inforamasi awal, model pencarian ini memiliki tiga ciri – ciri utama yaitu:
   
   • Membangkitkan simpul berdasarkan urutan
   • Kalau ada solusi maka solusi akan ditemukan 
   • Hanya memiliki informasi tentang node yang telah dibuka (node selanjutnya tidak diketahui). Blind Searching sendiri dibagi menjadi tiga macam yaitu : 
   1. BFS (Breadth First Search) 
   2. DFS (Depth-first Search) 
   3. UCS (Uniform Cost Search) 
    
2. Heuristic searching
   Heuristic Search merupakan metode pencarian yang memperhatikan nilai heuristik (nilai perkiraan).Teknik pencarian heuristik (heuristic searching) merupakan suatu strategi untuk melakukan proses pencarian ruang keadaan (state space) suatu problema secara selektif, yang memandu proses pencarian yang kita lakukan di sepanjang jalur yang memiliki kemungkinan sukses paling besar, dan mengesampingkan usaha yang bodoh dan memboroskan waktu. Heuristik adalah sebuah teknik yang mengembangkan efisiensi dalam proses pencarian, namun dengan kemungkinan mengorbankan kelengkapan (completeness). Heuristic Search memperkirakan jarak menuju Goal (yang disebut dengan fungsi heuristik). Fungsi heuristik ini digunakan untuk mengevaluasi keadaan-keadaan problema individual dan menentukan seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan. Jenis-jenis Heuristic Searching :
   
   • Generate and Test
   • Hill Climbing
   • Best First Search
   • Alpha Beta Prunning
   • Means-End-Anlysis
   • Constraint Satisfaction

C. STRATEGI PENCARIAN YANG TIDAK BERBENTUK 

1. Breadth First Search (BFS) Pencarian dengan Breadth First Search menggunakan teknik dimana langkah pertamanya adalah root node diekspansi, setelah itu dilanjutkan semua successor dari root node juga di-expand. Hal ini terus dilakukan berulang-ulang hingga leaf (node pada level paling bawah yang sudah tidak mempunyai successor lagi).
   
2. Uniform Cost Search (UCS)
   Pencarian dengan Breadth First Search akan menjadi optimal ketika nilai pada semua path adalah sama. Dengan sedikit perluasan, dapat ditemukan sebuah algoritma yang optimal dengan melihat kepada nilai tiap path di antara node-node yang ada. Selain menjalankan fungsi algoritma BFS, Uniform Cost Search melakukan ekspansi node dengan nilai path yang paling kecil. Hal ini bisa dilakukan dengan membuat antrian pada successor yang ada berdasar kepada nilai path-nya (node disimpan dalam bentuk priority queue).
   
3. Depth First Search (DFS)
   Teknik pencarian dengan Depth First Search adalah dengan melakukan ekspansi menuju node yang paling dalam pada tree. Node paling dalam dicirikan dengan tidak adanya successor dari node itu. Setelah node itu selesai diekspansi, maka node tersebut akan ditinggalkan, dan dilakukan ke node paling dalam lainnya yang masih memiliki successor yang belum diekspansi.
   
    
4. Depth Limited Search
   Pencarian menggunakan DFS akan berlanjut terus sampai kedalaman paling terakhir dari tree. Permasalahan yang muncul pada DFS adalah ketika proses pencarian tersebut menemui infinite state space. Hal ini bisa diatasi dengan menginisiasikan batas depth pada level tertentu semenjak awal pencarian. Sehingga node pada level depth tersebut akan diperlakukan seolah-olah mereka tidak memiliki successor.
5. Iterative Deepening Depth First Search
   Iterative deepening search merupakan sebuah strategi umum yang biasanya dikombinasikan dengan depth first tree search, yang akan menemukan berapa depth limit terbaik untuk digunakan. Hal ini dilakukan dengan secara menambah limit secara bertahap, mulai dari 0,1, 2, dan seterusnya sampai goal sudah ditemukan.
   
6. Bidirectional Search
   Pencarian dengan metode bidirectional search adalah dengan menjalankan dua pencarian secara simultan, yang satu dikerjakan secara forward dari initial state menuju ke goal, sedangkan yang satu lagi dikerjakan secara backward mulai dari goal ke initial state. Yang kemudian diharapkan bahwa kedua pencarian itu akan bertemu di tengah-tengah.

SUMBER :
http://najibzot.blogspot.co.id/p/teknik-searching-kecerdasan-buatan-di.html
http://socs.binus.ac.id/2013/04/23/uninformed-search-dan-informed-search/
https://aiukswkelasekelompok4a.wordpress.com/2009/02/06/masalah-ruang-keadaan-dan-pencarian/