Konsep dan

Fungsi
Heuristik
disusun oleh

Nurfahmi Hidayat
230209501023
 KONSEP HEURISTIK
Heuristik digunakan untuk menyelesaikan masalah kompleks yang tidak dapat
diselesaikan secara optimal dalam waktu singkat. Dengan mengandalkan aturan
praktis, intuisi, dan pengalaman, heuristik mempercepat pencarian solusi meskipun
tidak selalu menghasilkan hasil terbaik. Di Indonesia, heuristik diterapkan dalam sistem
transportasi, pendidikan, dan teknologi AI, seperti pada aplikasi navigasi Gojek atau
Grab yang mencari rute tercepat berdasarkan kondisi lalu lintas. Heuristik beroperasi
dengan prinsip-prinsip berikut:
1. Mengurangi Kompleksitas: Menyederhanakan masalah dan mengeliminasi pilihan
yang kurang relevan.
2. Efisiensi Pencarian: Membimbing pencarian ke arah solusi yang lebih baik.
3. Berbasis Intuisi dan Pengalaman: Memanfaatkan pola atau informasi dari kasus
serupa di masa lalu.
 FUNGSI HEURISTIK
Fungsi heuristik adalah komponen utama dalam algoritma pencarian dan pengambilan
keputusan, yang digunakan untuk mengestimasi kualitas suatu langkah atau simpul
dalam ruang masalah. Fungsi ini membantu memilih jalur yang paling menjanjikan
menuju solusi. Peran fungsi heuristik meliputi:
1. Mempercepat Proses Penyelesaian: Mengarahkan pencarian dengan
mempersempit ruang langkah yang perlu dievaluasi, seperti dalam algoritma A*
yang memprioritaskan langkah dengan nilai estimasi terendah.
2. Mengurangi Kompleksitas Komputasi: Mengurangi jumlah perhitungan dengan
hanya mempertimbangkan langkah relevan, misalnya menghilangkan jalur jauh
dari tujuan.
3. Meningkatkan Efisiensi: Memungkinkan algoritma seperti Best-First Search atau A*
bekerja lebih cepat tanpa mengevaluasi semua langkah.
4. Mengadaptasi Keputusan dalam Ketidakpastian: Membantu membuat perkiraan
keputusan meskipun data yang tersedia tidak lengkap atau akurat.
 ALGORITMA A* DAN GREEDY
BEST-FIRST

Algoritma A*
* adalah algoritma pencarian graf atau pohon yang digunakan untuk menemukan jalur terbaik
antara dua titik (awal dan akhir). Algoritma ini menggabungkan dua nilai: g(n) (biaya dari titik awal
ke titik n) dan h(n) (perkiraan biaya dari titik n ke titik tujuan) untuk memperkirakan jalur terbaik
yang harus dilalui.
Prinsip Kerja:
A* mencari jalur terpendek dengan mempertimbangkan biaya yang telah ditempuh (g(n)) dan
perkiraan biaya yang tersisa (h(n)). Fungsi estimasi total untuk setiap simpul (node) adalah f(n) =
g(n) + h(n).
f(n): Estimasi biaya terendah untuk mencapai tujuan
g(n): Biaya dari simpul awal ke simpul n
h(n): Perkiraan biaya dari simpul n ke tujuan
A* menggunakan dua daftar:
Open list: Menyimpan simpul yang akan dibangkitkan dan dihitung heuristiknya, tetapi belum
dipilih sebagai simpul terbaik.
Closed list: Menyimpan simpul yang telah dipilih sebagai terbaik dan tidak akan diproses lagi.
 ALGORITMA A* DAN GREEDY
BEST-FIRST

Greedy Best-First Search

Metode Pencarian Greedy Best-First Search
Greedy Best-First Search adalah algoritma pencarian berbasis graf yang menggunakan fungsi heuristik untuk mencari jalur dari
titik awal ke tujuan. Algoritma ini "serakah" karena selalu memilih langkah yang dianggap paling mendekati solusi berdasarkan
nilai heuristik h(n), tanpa mempertimbangkan biaya aktual g(n).
Prinsip Kerja:
Greedy Best-First Search memprioritaskan simpul dengan nilai heuristik terkecil dan hanya memperhitungkan h(n) (perkiraan
biaya menuju tujuan). Ini membuat algoritma ini lebih cepat, tetapi sering tidak menghasilkan solusi optimal karena bisa terjebak
dalam solusi lokal.
Langkah-langkah Algoritma:
1. Mulai dari simpul awal dan tambahkan ke Open List.
2. Pilih simpul dengan h(n) terkecil dari Open List.
3. Pindahkan simpul ke Closed List.
4. Evaluasi tetangga simpul tersebut:
Jika belum ada di Open List atau Closed List, tambahkan ke Open List.
Hitung nilai h(n) untuk setiap tetangga.
5. Ulangi langkah 2 hingga:
Simpul tujuan ditemukan, atau
Open List kosong (tidak ada jalur ke tujuan).
Notasi yang Digunakan:
f(n) = h(n): Fungsi evaluasi sama dengan nilai heuristik h(n).
 EVALUASI DAN PENERAPAN
INFORMED SEARCH

Evaluasi Informed Search

Evaluasi algoritma informed search mengukur efektivitas dan efisiensi dalam menyelesaikan masalah pencarian, dengan fokus pada
beberapa aspek kunci: efisiensi, optimalitas, dan kompleksitas waktu serta ruang.
1. Efisiensi
2. Algoritma informed search, seperti A* dan Greedy Best-First Search, lebih efisien daripada pencarian buta karena menggunakan
heuristik untuk mempercepat pencarian. Heuristik membantu memilih simpul yang lebih dekat ke tujuan, mengurangi jumlah simpul
yang diperiksa dan mempercepat pencarian.
3. Optimalitas
4. Algoritma A* dapat menemukan solusi optimal jika heuristik yang digunakan admissible, sementara Greedy Best-First Search tidak
selalu optimal karena hanya mempertimbangkan heuristik tanpa memperhitungkan biaya yang telah ditempuh.
5. Kompleksitas Waktu dan Ruang
Kompleksitas Waktu: Tergantung pada ukuran ruang pencarian dan kualitas heuristik, algoritma bisa efisien atau lebih lambat jika
heuristik buruk.
Kompleksitas Ruang: Algoritma seperti A* memerlukan banyak memori untuk menyimpan informasi simpul yang telah dievaluasi,
yang dapat menjadi masalah jika ruang pencarian sangat besar.
 EVALUASI DAN PENERAPAN
INFORMED SEARCH

Penerapan Informed Search

Algoritma informed search banyak diterapkan di berbagai bidang, memanfaatkan heuristik untuk meningkatkan efisiensi dan menemukan solusi cepat dan
optimal.
Sistem Navigasi dan Perencanaan Rute
Algoritma A* digunakan dalam sistem navigasi seperti Google Maps untuk menghitung rute tercepat dengan mempertimbangkan jarak, waktu, dan
hambatan. Heuristiknya sering berupa perkiraan jarak (Euclidean atau Manhattan) antara titik yang sedang dipertimbangkan dan tujuan.
Robotika dan Kendaraan Otonom
Dalam robotika dan kendaraan otonom, A* membantu merencanakan jalur yang aman dan optimal untuk menghindari rintangan, memungkinkan robot
atau mobil untuk bergerak efisien di lingkungan dinamis.
Permainan Komputer
Algoritma seperti A* dan Greedy Best-First Search digunakan untuk merencanakan gerakan karakter komputer atau musuh dalam permainan, memilih jalur
efisien untuk mencapai tujuan.
Pencarian Informasi dan Web
Dalam pencarian informasi di web, algoritma informed search memperkirakan relevansi halaman atau dokumen berdasarkan kata kunci dan algoritma
peringkat yang memanfaatkan struktur web.
Penyelesaian Masalah Logika dan Matematika
Algoritma pencarian informed digunakan dalam penyelesaian masalah logika dan matematika yang kompleks, dengan heuristik untuk mempercepat
pencarian solusi.
STUDI KASUS OPTIMALISASI RUTE PENGIRIMAN
OLEH PERUSAHAAN LOGISTIK
Analisis:
1. Komponen AI yang Digunakan
Ruang Pencarian: Semua rute dalam jaringan transportasi (jalan raya, kereta,
pelabuhan).
Keadaan Awal: Lokasi awal pengiriman (misalnya gudang pusat atau cabang).
Keadaan Tujuan: Lokasi pelanggan atau titik distribusi.
Operator Pencarian: Pergerakan barang dari satu titik ke titik lain dalam jaringan
rute.
Fungsi Evaluasi: Kombinasi biaya transportasi (g(n)) dan estimasi biaya tambahan ke
tujuan (h(n)) seperti jarak atau waktu tempuh.
2. Manfaat
Efisiensi Biaya: Menemukan rute terpendek atau termurah untuk mengurangi
pengeluaran.
Peningkatan Layanan Pelanggan: Mempercepat pengiriman dengan rute yang lebih
efisien.
Optimasi Operasional: Memanfaatkan sumber daya logistik lebih efisien (kendaraan,
bahan bakar).
3. Tantangan
Ukuran Ruang Pencarian: Banyaknya kemungkinan rute dapat memperlambat
algoritma.
Data Dinamis: Kondisi lalu lintas, cuaca, dan penutupan jalan memerlukan
pembaruan algoritma secara real-time.
Pemilihan Heuristik yang Tepat: Heuristik yang buruk dapat menghasilkan solusi
yang tidak optimal.
 LATIHAN SOAL

1. Jelaskan apa yang dimaksud dengan heuristik secara sederhana dan

berikan satu contoh penggunaannya dalam kehidupan sehari-hari.
2. Sebutkan dua prinsip dasar dari heuristik yang membantu dalam
memecahkan masalah lebih cepat.
3. Apa perbedaan utama antara algoritma A* dan Greedy Best-First Search?
Jelaskan secara singkat.
4. Mengapa algoritma A* membutuhkan lebih banyak memori
dibandingkan dengan Greedy Best-First Search?
5. Berikan satu contoh penerapan algoritma A* dalam kehidupan sehari-
hari dan jelaskan bagaimana algoritma ini bekerja untuk menemukan solusi
terbaik.
TERIMAKASIH