Menyelesaikan Masalah Melalui Pencarian

1.  Agent pemecah permasalahan
Dalam membangun sebuah sistem AI, perlu dipertimbangkan 4 hal, yaitu:
1)      Mendefinisikan masalah dengan tepat. Pendefinisian ini mencakup deskripsi masalah dengan baik
2)      Menganalisis masalah tersebut serta mencari beberapa teknik penyelesaian masalah yang sesuai
3)      Mempresentasikan pengetahuan yang perlu untuk menyelesaikan masalah tersebut
4)      Memilih teknik penyelesaian masalah terbaik.
Dalam menentukan teknik penyelesaian terbaik dalam AI memang tidak mudah, untuk itu ada beberapa teknik penyelesaian masalah yang perlu kita pahami, antara lain:
1. Searching
Teknik penyelesaian masalah yang mempresentasikan masalah kedalam ruang keadaan (state) dan secara sistematis melakukan pembangkitan dan pengujian state-state dari initial state sampai ditemukan suatu goal state.
2. Reasoning
Teknik penyelesaian masalah yang mempresentasikan masalah kedalam logic (Mathematical Tools yang digunakan untuk merepresentasikan dan memanipulasi fakta dan aturan)
3. Planning
Memecah masalah dalam sub-sub masalah yang lebih kecil, menyelesaikan sub-sub masalah satu demi satu, kemudian menggabungkan solusi-solusi dari sub masalah tersebut menjadi sebuah solusi lengkap.
4. Learning
Program komputer yang secara otomatis sanggup belajar dan meningkatkan performancenya  melalui pengalaman


2.  Pencarian sebagai solusi pemecahan masalah

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
Posisi Awal : Selalu sama
Aturan Legal :
Aturan – aturan sangat berguna untuk menentukan gerak suatu bidak
Untuk mempermudah,
Horisontal = Huruf (a,b,c,d,e,f,g,h)
Vertical = Angka (1,2,3,4,5,6,7,8)


3.  strategi pencarian yang tidak terbentuk

·         Breadth-first search 
Breadth-first search adalah algoritma yang melakukan pencarian secara melebar yang mengunjungi simpul secara preorder yaitu mengunjungi suatu simpul kemudian mengunjungi semua simpul yang bertetangga dengan simpul tersebut terlebih dahulu. Selanjutnya, simpul yang belum dikunjungi dan bertetangga dengan simpulsimpul yang tadi dikunjungi , demikian seterusnya. Jika graf berbentuk pohon berakar, maka semua simpul pada aras d dikunjungi lebih dahulu sebelum simpul-simpul pad aras d+1.
Algoritma ini memerlukan sebuah antrian q untuk menyimpan simpul yang telah dikunjungi. Simpulsimpul ini diperlukan sebagai acuan untuk mengunjungi simpul-simpul yang bertetanggaan dengannya. Tiap simpul yang telah dikunjungu masuk ke dalam antrian hanya satu kali. Algoritma ini juga membutuhkan table Boolean untuk menyimpan simpul yang te lah dikunjungi sehingga tidak ada simpul yang dikunjungi lebih dari satu kali.
·         Uniform Cost Search
Uniform Cost Search adalah algoritma Seach Tree (graph) yang digunakan untuk menyelesaikan beberapa persoalan . Algoritma ini memulai pencarian dari root node, kemudian dilanjutkan ke node-node selanjutnya. Dimana node tersebut dipilih yang memilki harga (cost) terkecil dari root node. Algoritma ini merupakan modifikasi dari Bread First Search (BFS).
·         Depth First Search
Algoritma DFS (Depth First Search) adalah salah satu algoritma yang digunakan untuk pencarian jalur. Contoh yang dibahas kali ini adalah mengenai pencarian jalur yang melalui semua titik. 
Algoritma ini mirip dengan Algoritma BFS (Breadth First Search) yang sudah dijelaskan sebelumnya. Jika Algoritma BFS (Breadth First Search) melakukan perhitungan secara terurut dari urutan pertama sampai urutan terakhir, maka algoritma ini melakukan kebalikannya, yaitu melakukan perhitungan secara terurut dari urutan terakhir. Setelah menghabiskan semua kemungkinan dari titik terakhir, barulah mundur ke titik-titik sebelumnya sampai pada titik pertama.

·         Depth Limited Search
Algoritma DLS (Depth Limited Search) adalah salah satu algoritma yang digunakan untuk pencarian jalur. Contoh yang dibahas kali ini adalah mengenai pencarian jalur yang melalui semua titik. 
Algoritma ini merupakan variasi dari Algoritma DFS (Depth First Search) yang sudah dijelaskan sebelumnya. Jika Algoritma DFS (Depth First Search) melakukan perhitungan (yang dimulai dengan titik terakhir) dengan cara menghabiskan semua tingkatan / kedalaman dari sebuah titik, maka algoritma ini memiliki batasan dimana perhitungan pada sebuah titik hanya dihitung sampai pada kedalaman tertentu. Setelah semua kemungkinan pada kedalaman itu sudah habis, kemudian akan dilanjutkan pada titik berikutnya.

·         iterative deepening depth-first search
Dalam ilmu komputer , pencarian pendalaman iteratif atau lebih spesifik iterative deepening depth-first search(IDS atau IDDFS) adalah strategi pencarian ruang / grafik negara di mana versi kedalaman kedalaman pencarian kedalaman pertama dijalankan berulang kali dengan kedalaman yang meningkat. batas sampai tujuan ditemukan. IDDFS setara dengan pencarian pertama , tapi menggunakan lebih sedikit memori; Pada setiap iterasi, ia mengunjungi simpul -simpul di pohon pencarian dengan urutan yang sama seperti pencarian pertama-tama , namun urutan kumulatif dimana simpul pertama kali dikunjungi secara efektif adalah keluasan-pertama.

·         Bi-Directional Search
Pencarian dengan metode bidirectional search adalah dengan menjalankan dua pencarian, 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 jalur yang bertemu.
Ada beberapa masalah sebelum memustuskan untuk menngunakan strategi Bi-directional Search, yaitu:
1.       Bagaimana kalau terdapat beberapa node tujuan yang berbeda? 
2.       Terdapat perhitungan yang tidak efisien untuk selalu mengecek apakah node baruyang dibangkitkan sudah pernah dibangkitkan oleh pencarian dari arah yang berlawanan.
3.       Bagaimana menentukan strategi pencarian untuk kedua arah tersebut? Misalnya dari arah sumber dan dari arah tujuan digunakan BFS.







sumber :
http://tiindonesia.blogspot.co.id/2013/02/teknik-pemecahan-masalah-dalam-ai.html
https://aiukswkelasekelompok4a.wordpress.com/2009/02/06/masalah-ruang-keadaan-dan-pencarian/
http://jakaseptiadi.blogspot.co.id/2015/09/bi-directional-search-bds-depth-limited.html






Komentar

Posting Komentar

Postingan populer dari blog ini

Jaka tarub dan 7 bidadari

Gambar
Di suatu desa, hiduplah seorang perempuan tua yang biasa dipanggil Nyi Randa Tarub (hidup di dusun Tarub), dia mempunyai anak angkat bernama Jaka Tarub yang telah tumbuh menjadi seorang pemuda dewasa yang tampan dan sangat senang berburu. Suatu hari ketika dia berburu seperti biasanya, dia mendengar suara wanita yang kurang jelas karena ditelan dedauanan, karena penasaran Jaka Tarub akhirnya menuju ke sumber suara secara mengendap-endap. Jaka Tarub melihat empat orang gadis cantik yang sedang mandi di telaga, hampir bersamaan dengan itu, dia juga melihat beberapa lembar selendang yang tergeletak dipinggir telaga, ada bisikan dari dalam diri Jaka Tarub untuk mengambilnya, dan secara mengendap-endap dia mengambil salah satunya. Ketika para gadis yang ternyata bidadari itu hendak kembali ke kahyangan, salah satu dari mereka panik karena tidak menemukan selendangnya, tapi ketiga bidadari lain tidak dapat berbuat apa-apa. Melihat hal tersebut...
Baca selengkapnya

Logika Orde Pertama (first-Order Logic)

1. Pengenalan logika orde pertama                 First order logic adalah sebuah bahasa formal yang digunakan di ilmu matematika, philosophy, bahasa dan ilmu computer. Disebut juga kalkulus predikat, merupakan logika yang digunakan untuk merepresentasikan masalah yang tidak dapat direpresentasikan dengan menggunakan proposisi. Logika predikat dapat memberikan representasi fakat-fakta sebagai suatu pernyataan yang mapan (well form). Kalkulus predikat bisa menganalisakan kalimat-kalimat ke dalam subjek dan argumen dalam berbagai cara yang berbeda-beda, yang pada akhirnya kalkulus predikat bisa digunakan untuk memecahkan problem of multiple generality (masalah dalam berbagai keadaan umum) yang telah membingungkan sebagian besar ahli-ahli logika abad pertengahan. Dengan menggunakan logika predikat ini, untuk pertama kalinya, para ahli-ahli logika bisa memberikan quantifier   yang cukup u...
Baca selengkapnya

Roti Buaya Lambang Kesetiaan Suku Betawi

Gambar
Asal muasal adanya roti buaya ini, konon terinspirasi perilaku buaya yang hanya kawin sekali sepanjang hidupnya.Dan masyarakat Betawi meyakini hal itu secara turun temurun. Selain terinspirasi perilaku buaya, simbol kesetiaan yang diwujudkan dalam sebuah makanan berbentuk roti itu juga memiliki makna khusus. Menurut keyakinan masyarakat Betawi, roti juga menjadi simbol kemampanan ekonomi. Dengan maksud, selain bisa saling setia, pasangan yang menikah juga memiliki masa depan yang lebih baik dan bisa hidup mapan. Roti Buaya Sebagai Simbol Pernikahan Adat Betawi Setiap acara pernikahan yang mengusung adat Betawi, pasti tak pernah meninggalkan roti buaya. Biasanya roti yang memiliki panjang sekitar 50 sentimeter ini dibawa oleh mempelai pengantin laki-laki pada acara serah-serahan. Selain roti buaya, mempelai pengantin laki-laki juga memberikan uang mahar, perhiasan, kain, baju kebaya, selop, alat kecantikan, serta beberapa peralatan rumah tangga. Dari sejumlah barang yang diserahk...
Baca selengkapnya