Menjelaskan konsep state, operator, goal test, dan cost. Contoh: permainan 8-puzzle dan labirin. Mahasiswa memodelkan masalah ke bentuk graf (simpul & relasi).
Realisasi Materi
Mahasiswa membuat representasi graf sederhana di Python menggunakan networkx. Diskusi menekankan bagaimana formulasi masalah (pemilihan state/aksi/biaya) memengaruhi efisiensi pencarian.
State: representasi kondisi saat ini (mis. posisi agen di grid, konfigurasi ubin 8-puzzle).
Operator/Aksi: aturan transisi yang mengubah state (mis. atas/bawah/kiri/kanan).
Goal Test: fungsi yang memeriksa apakah state adalah tujuan (mis. mencapai sel kanan-bawah atau urutan ubin benar).
Cost: biaya untuk menerapkan operator/menempuh jalur (mis. 1 per langkah, atau bobot berbeda).
Contoh Hitungan Manual
Perkiraan ukuran ruang keadaan (tree search):
Jika branching factor = b dan kedalaman = d, maka total simpul ≈ 1 + b + b^2 + … + b^d.
Contoh: b=3, d=4 → 1+3+9+27+81 = 121 simpul.
Implikasi: formulasi masalah yang baik (membatasi b/d) membuat pencarian jauh lebih efisien.
# ====== Representasi Masalah: Graf Labirin ======
# Tujuan: memodelkan labirin sebagai graf (simpul=sel, sisi=langkah valid)
# Lalu cetak rute acak dari start ke goal dan visualisasikan.
import random
import math
import networkx as nx
import matplotlib.pyplot as plt
# 1) Bangun grid W x H
W, H = 8, 6
G = nx.grid_2d_graph(H, W) # node = (row,col)
start = (0,0)
goal = (H-1, W-1)
# 2) Hapus beberapa edge untuk membuat "dinding" labirin sederhana
random.seed(7)
remove_ratio = 0.18
edges = list(G.edges())
random.shuffle(edges)
for e in edges[:int(len(edges)*remove_ratio)]:
G.remove_edge(*e)
# Pastikan graf tetap terhubung antar komponen start-goal dengan menambah edge alternatif jika perlu
# (heuristik sederhana)
if not nx.has_path(G, start, goal):
# coba sambung dengan menambah kembali sebagian edge yang dihapus
for e in edges[int(len(edges)*remove_ratio)//2:]:
G.add_edge(*e)
if nx.has_path(G, start, goal):
break
# 3) Cetak rute (menggunakan shortest_path sebagai baseline)
if nx.has_path(G, start, goal):
path = nx.shortest_path(G, source=start, target=goal)
print(f"Panjang jalur: {len(path)-1} langkah")
else:
path = []
print("Belum ada jalur dari start ke goal (atur ulang remove_ratio atau seed)")
# 4) Visualisasi
pos = {(r,c):(c,-r) for r,c in G.nodes()} # tata letak grid (x=c, y=-r)
plt.figure(figsize=(6,4))
nx.draw(G, pos=pos, node_size=80, width=1, with_labels=False)
if path:
nx.draw_networkx_nodes(G, pos, nodelist=path, node_size=90)
nx.draw_networkx_edges(G, pos, edgelist=list(zip(path, path[1:])), width=3)
plt.title("Graf Labirin & Jalur Baseline")
plt.show()
Catatan: networkx biasanya tersedia di Colab. Jika tidak, jalankan !pip install networkx dahulu.
B. Kuis 2 (Cek Mandiri)
# ====== Kuis 2 (cek mandiri) ======
qs = [
("Apa itu 'state' dalam representasi masalah?",
{"a":"Aturan transformasi",
"b":"Kondisi/konfigurasi saat ini dalam ruang masalah",
"c":"Fungsi evaluasi heuristik",
"d":"Tujuan akhir"},
"b"),
("Apa itu 'operator'?",
{"a":"Pengujian apakah solusi sudah optimal",
"b":"Langkah/aksi yang mengubah satu state ke state lain",
"c":"Biaya total jalur",
"d":"Ukuran branching factor"},
"b"),
("Goal test adalah...",
{"a":"Fungsi yang memeriksa apakah state saat ini memenuhi kondisi tujuan",
"b":"Jumlah maksimum langkah",
"c":"Cara memilih node berikutnya",
"d":"Pohon keputusan"},
"a"),
]
print("Kunci jawaban:")
for i, (_, __, ans) in enumerate(qs,1):
print(f"Q{i}: {ans}")
Penugasan & Referensi
PR: Buat definisi masalah pilihan Anda (1 halaman) lengkap dengan sketsa state-space (bisa gambar tangan). Jelaskan state, operator, goal test, dan cost.
Russell & Norvig (2020), bab representasi masalah & pencarian.