Semua tentang Pencarian Informasi dalam Kecerdasan Buatan

Informed search adalah jenis algoritma pencarian yang menggunakan pengetahuan khusus domain untuk memandu pencariannya melalui ruang masalah. Dari sistem navigasi hingga bermain game, pemrosesan bahasa alami hingga manajemen rantai pasokan, dan pencarian informasi lebih lanjut dalam kecerdasan buatan telah secara signifikan mengurangi jumlah waktu dan sumber daya komputasi yang diperlukan untuk menyelesaikan berbagai masalah.

Dengan menggunakan pengetahuan khusus domain untuk memandu pencarian, algoritme pencarian yang terinformasi dapat dengan cepat menghilangkan jalur yang tidak relevan atau kurang menjanjikan, memungkinkan pencarian untuk fokus pada opsi yang paling menjanjikan. Untuk melakukannya, jenis algoritme pencarian dalam AI ini menggunakan heuristik untuk meningkatkan efisiensi dan kecepatan pencarian.

Daftar ke Kursus Pembelajaran Mesin dari Universitas top Dunia. Dapatkan Program Master, PGP Eksekutif, atau Sertifikat Lanjutan untuk mempercepat karier Anda.

Artikel ini akan membahas konsep pencarian informasi dalam kecerdasan buatan, fungsi heuristiknya, contoh algoritma, serta kelebihan dan kekurangannya.

Fungsi Heuristik

Secara sederhana, fungsi heuristik adalah pendekatan pemecahan masalah yang menggunakan aturan praktis atau “tebakan terbaik” untuk memperkirakan jarak atau biaya ke status tujuan dalam masalah pencarian. Fungsi heuristik memperkirakan seberapa jauh keadaan tujuan dari keadaan saat ini, yang dapat digunakan untuk memandu algoritme pencarian menuju tujuan.

Algoritma pencarian informasi menggunakan fungsi-fungsi ini sebagai sumber informasi tambahan untuk membuat keputusan tentang jalur mana yang harus diambil. Karena alasan ini, fungsi heuristik sangat penting dalam algoritma pencarian informasi.

Contoh kehidupan nyata dari fungsi heuristik

Untuk memahami fungsi heuristik dengan lebih baik, berikut adalah beberapa contoh kehidupan nyata:

• Dalam permainan klasik “teka-teki ubin geser”, fungsi heuristik sederhana dapat menghitung jumlah ubin yang tidak pada tempatnya dalam konfigurasi saat ini dibandingkan dengan konfigurasi tujuan. Semakin banyak petak yang tidak pada tempatnya, semakin jauh status saat ini dari status tujuan.
• Dalam catur, fungsi heuristik dapat berupa menetapkan nilai untuk setiap bidak di papan berdasarkan kekuatan dan posisi relatifnya dan menggunakan jumlah nilai tersebut untuk memperkirakan keuntungan atau kerugian pemain saat ini. Fungsi heuristik ini dapat digunakan untuk memandu algoritme pencarian menuju pergerakan yang cenderung menghasilkan posisi yang lebih baik.

Dengan itu diselesaikan, sekarang mari kita lanjutkan dan pahami beberapa contoh yang paling sering digunakan dari algoritma pencarian informasi dalam kecerdasan buatan.

Contoh Algoritma Pencarian Informasi

Dua algoritma pencarian informasi yang paling umum digunakan termasuk pencarian pertama terbaik dan pencarian A*. Mari kita pahami kedua algoritma ini beserta beberapa contoh, kelebihan, kekurangan, dan implementasi Python-nya:

1. Pencarian Pertama Terbaik

Pencarian pertama terbaik adalah algoritma pencarian yang memperluas node yang paling menjanjikan terlebih dahulu, sesuai dengan fungsi heuristik. Algoritme dimulai dari simpul awal dan memeriksa semua simpul anaknya, memilih anak dengan nilai heuristik terendah sebagai simpul berikutnya untuk dijelajahi. Proses ini berlanjut hingga node tujuan ditemukan atau semua node telah dieksplorasi.

Pencarian pertama terbaik – contoh ilustrasi

Berikut adalah contoh sederhana untuk mengilustrasikan pencarian pertama yang terbaik:

Misalkan Anda mencoba mencari rute terpendek dari rumah Anda ke toko bahan makanan terdekat. Anda tahu jarak ke toko kelontong dari beberapa lokasi terdekat, tetapi Anda tidak tahu rute persis yang harus ditempuh. Untuk mengatasi masalah ini menggunakan pencarian terbaik pertama, Anda dapat:

1. Mulai dari lokasi rumah Anda dan hitung nilai heuristik untuk setiap lokasi terdekat berdasarkan jaraknya ke toko kelontong.
2. Pilih lokasi terdekat dengan nilai heuristik terendah sebagai node berikutnya untuk dijelajahi.
3. Hitung nilai heuristik untuk setiap lokasi turunannya dari lokasi terdekat tersebut dan pilih salah satu dengan nilai heuristik terendah sebagai node berikutnya untuk dijelajahi.
4. Ulangi proses ini sampai Anda mencapai toko kelontong.

Pencarian pertama terbaik – implementasi Python

Inilah cara Anda menerapkan algoritme pencarian pertama terbaik di Python:

impor tumpukanq

def best_first_search(start_state, goal_state, heuristic_func, actions_func, cost_func):

# menginisialisasi set perbatasan dan dieksplorasi

frontier = [(heuristic_func(start_state, goal_state), start_state)]

dijelajahi = set()

# inisialisasi jalur dan biaya

jalur = {}

biaya = {}

path[start_state] = Tidak ada

biaya[start_state] = 0

sementara perbatasan:

# dapatkan node dengan nilai heuristik terendah dari frontier

(h, current_state) = heapq.heapppop(frontier)

jika current_state == goal_state:

# mengembalikan jalur jika status tujuan tercapai

jalur kembali

dieksplorasi.tambahkan(current_state)

# menghasilkan kemungkinan tindakan dari kondisi saat ini

untuk tindakan di actions_func(current_state):

next_state = tindakan(current_state)

# hitung biaya jalur baru

biaya_baru = biaya[status_saat ini] + fungsi_biaya(status_saat ini, tindakan, status_berikutnya)

jika next_state tidak dieksplorasi dan next_state tidak di [status untuk (h, status) di perbatasan]:

# tambahkan status baru ke perbatasan

heapq.heappush(frontier, (heuristic_func(next_state, goal_state), next_state))

path[next_state] = current_state

biaya[kondisi_berikutnya] = biaya_baru

# kembalikan Tidak ada jika status tujuan tidak dapat dijangkau

kembali Tidak ada

Seperti yang Anda lihat, Anda perlu menentukan fungsi-fungsi berikut:

• heuristic_func(current_state, goal_state): Fungsi ini mengambil status saat ini dan status tujuan sebagai input dan mengembalikan perkiraan biaya untuk mencapai status tujuan dari status saat ini.
• actions_func(current_state): Fungsi ini mengambil status saat ini sebagai masukan dan mengembalikan daftar tindakan yang dapat diambil dari status saat ini.
• cost_func(current_state, action, next_state): Fungsi ini mengambil status saat ini, tindakan, dan status selanjutnya sebagai input dan mengembalikan biaya pengambilan tindakan dari status saat ini ke status berikutnya.

Contoh Pencarian Pertama Terbaik

status_awal = (0, 0)

keadaan_tujuan = (4, 4)

def heuristic_func(current_state, goal_state):

kembalikan abs(current_state[0] – goal_state[0]) + abs(current_state[1] – goal_state[1])

def action_func(current_state):

tindakan = []

jika current_state[0] > 0:

tindakan.append(status lambda: (status[0]-1, status[1]))

jika current_state[0] < 4:

tindakan.append(status lambda: (status[0]+1, status[1]))

jika current_state[1] > 0:

tindakan.append(status lambda: (status[0], status[1]-1))

jika current_state[1] < 4:

tindakan.append(status lambda: (status[0], status[1]+1))

tindakan pengembalian

def cost_func(current_state, action, next_state):

kembali 1

path = best_first_search(start_state, goal_state, heuristic_func, actions_func, cost_func)

jika jalur:

# bangun jalur dari status awal ke status tujuan

current_state = goal_state

sementara current_state != start_state:

cetak(status_saat ini)

current_state = jalur[current_state]

cetak(start_state)

kalau tidak:

print(“Status tujuan tidak dapat dicapai.”)

Keuntungan Pencarian Pertama Terbaik

• Dibandingkan dengan pencarian luas-pertama, kompleksitas waktu pencarian terbaik-pertama lebih rendah.
• Pencarian pertama terbaik memperoleh dan mengimplementasikan keuntungan dari algoritma BFS dan DFS

Kerugian Pencarian Pertama Terbaik

• Kadang-kadang dapat menempuh jarak lebih dari yang dipertimbangkan.
• Kemungkinan terjebak dalam satu lingkaran sangat mungkin terjadi.

Pencarian

Pencarian A* adalah algoritme pencarian yang menggunakan biaya untuk mencapai node dari node awal dan perkiraan biaya yang tersisa untuk mencapai node tujuan untuk memandu pencariannya. Algoritme dimulai dari simpul awal dan memeriksa semua simpul anak-anaknya, memilih anak dengan biaya gabungan terendah dan perkiraan sisa biaya sebagai simpul berikutnya untuk dijelajahi. Proses ini berlanjut hingga node tujuan ditemukan atau semua node telah dieksplorasi.

Pencarian A* – contoh ilustrasi

Mari kita lihat kembali contoh sebelumnya tentang Anda yang mencoba mencari rute terpendek dari rumah Anda ke toko kelontong terdekat. Sekarang, Anda dapat:

1. Mulailah dari lokasi rumah Anda dan hitung total biaya untuk mencapai setiap lokasi terdekat sebagai jumlah jarak dari rumah Anda ke lokasi tersebut dan perkiraan sisa biaya untuk mencapai toko kelontong dari lokasi tersebut.
2. Pilih lokasi terdekat dengan total biaya terendah sebagai node berikutnya untuk dijelajahi.
3. Dari lokasi terdekat tersebut, hitung total biaya untuk setiap lokasi turunannya sebagai jumlah jarak dari lokasi tersebut ke lokasi turunannya, biaya untuk mencapai lokasi tersebut dari simpul awal, dan perkiraan sisa biaya untuk mencapai toko grosir dari lokasi anak itu. Pilih lokasi turunan dengan total biaya terendah sebagai node berikutnya untuk dijelajahi.
4. Ulangi proses ini sampai Anda mencapai toko kelontong.

Hal penting yang perlu diperhatikan di sini adalah bahwa A* Search adalah algoritme pencarian optimal yang menjamin menemukan jalur terpendek ke keadaan tujuan. Ini efisien dalam masalah dengan ruang pencarian yang besar dan banyak digunakan dalam video game, robotika, dan perencanaan rute. Namun, itu membutuhkan fungsi heuristik yang terdefinisi dengan baik agar efektif. Karena alasan ini, algoritme dapat menjadi intensif memori dan melambat dalam masalah kompleks dengan banyak node.

A* search – Implementasi Python

Inilah cara Anda dapat mengimplementasikan algoritme pencarian A* menggunakan pemrograman Python:

impor tumpukanq

def astar_search(start_state, goal_state, heuristic_func, actions_func, cost_func):

# menginisialisasi set perbatasan dan dieksplorasi

frontier = [(heuristic_func(start_state, goal_state), start_state)]

dijelajahi = set()

# inisialisasi jalur dan biaya

jalur = {}

biaya = {}

path[start_state] = Tidak ada

biaya[start_state] = 0

sementara perbatasan:

# dapatkan node dengan nilai f terendah dari frontier

(f, current_state) = heapq.heapppop(frontier)

jika current_state == goal_state:

# mengembalikan jalur jika status tujuan tercapai

jalur kembali

dieksplorasi.tambahkan(current_state)

# menghasilkan kemungkinan tindakan dari kondisi saat ini

untuk tindakan di actions_func(current_state):

next_state = tindakan(current_state)

# hitung biaya jalur baru

biaya_baru = biaya[status_saat ini] + fungsi_biaya(status_saat ini, tindakan, status_berikutnya)

jika next_state tidak dieksplorasi dan next_state tidak di [state for (f, state) in frontier]:

# tambahkan status baru ke perbatasan

heapq.heappush(frontier, (new_cost + heuristic_func(next_state, goal_state), next_state))

path[next_state] = current_state

biaya[kondisi_berikutnya] = biaya_baru

elif next_state di [state for (f, state) in frontier] dan new_cost < cost[next_state]:

# perbarui biaya negara bagian yang ada di perbatasan

index = [i for (i, (f, state)) in enumerate(frontier) if state == next_state][0]

frontier[indeks] = (biaya_baru + fungsi_heuristik(status_berikutnya, status_tujuan), status_berikutnya)

path[next_state] = current_state

biaya[kondisi_berikutnya] = biaya_baru

# kembalikan Tidak ada jika status tujuan tidak dapat dijangkau

kembali Tidak ada

Kursus Pembelajaran Mesin Teratas & Kursus AI Online

Contoh Pencarian A*

Berikut adalah contoh bagaimana Anda dapat menggunakan fungsi astar_search dengan fungsi-fungsi ini:

status_awal = (0, 0)

keadaan_tujuan = (4, 4)

def heuristic_func(current_state, goal_state):

kembalikan abs(current_state[0] – goal_state[0]) + abs(current_state[1] – goal_state[1])

def action_func(current_state):

tindakan = []

jika current_state[0] > 0:

tindakan.append(status lambda: (status[0]-1, status[1]))

jika current_state[0] < 4:

tindakan.append(status lambda: (status[0]+1, status[1]))

jika current_state[1] > 0:

tindakan.append(status lambda: (status[0], status[1]-1))

jika current_state[1] < 4:

tindakan.append(status lambda: (status[0], status[1]+1))

tindakan pengembalian

def cost_func(current_state, action, next_state):

kembali 1

path = astar_search(start_state, goal_state, fungsi_heuristik, fungsi_tindakan, fungsi_biaya)

jika jalur:

# bangun jalur dari status awal ke status tujuan

current_state = goal_state

sementara current_state != start_state:

cetak(status_saat ini)

current_state = jalur[current_state]

cetak(start_state)

kalau tidak:

print(“Status tujuan tidak dapat dicapai.”)

Keuntungan Pencarian A*

• Ini adalah salah satu teknik heuristik terkemuka.
• Pencarian A* dapat dimanfaatkan untuk memecahkan masalah pencarian yang rumit

Keterampilan Pembelajaran Mesin yang Sedang Tren

Kerugian Pencarian A*

• Performa pencarian A* sangat bergantung pada keakuratan algoritme heuristik.
• Memiliki efisiensi pencarian yang rendah.

Blog AI dan ML Populer & Kursus Gratis

Membawa pergi

Algoritma pencarian yang diinformasikan sangat penting dalam kecerdasan buatan karena memungkinkan komputer untuk mencari keadaan tujuan secara efisien dan efektif. Algoritme ini menggunakan fungsi heuristik untuk memperkirakan biaya setiap langkah yang memungkinkan dan memandu proses pencarian menuju keadaan tujuan. Best First Search dan A* Search adalah contoh algoritma pencarian informasi yang banyak digunakan di berbagai bidang. Namun, fungsi heuristik yang terdefinisi dengan baik sangat penting untuk keberhasilan algoritma pencarian informasi.

Jika Anda tertarik untuk mempelajari lebih lanjut tentang kecerdasan buatan dan pembelajaran mesin, lihat program Magister Pembelajaran Mesin & Kecerdasan Buatan upGrad yang ditawarkan oleh Universitas John Moores Liverpool . Program ini mencakup berbagai pembelajaran mesin dan topik AI, termasuk algoritme seperti pencarian informasi. Dengan mengikuti program ini, Anda dapat memperoleh keterampilan dan pengetahuan yang Anda butuhkan untuk berhasil dalam berbagai karier terkait AI.

Anda juga dapat melihatkursus gratis kamiyang ditawarkan oleh upGrad dalam Manajemen, Ilmu Data, Pembelajaran Mesin, Pemasaran Digital, dan Teknologi.Semua kursus ini memiliki sumber belajar terbaik, kuliah langsung mingguan, tugas industri, dan sertifikat penyelesaian kursus – semuanya gratis!