UTS Kecerdasan Buatan 2025

UTS Sistem Cerdas 2024/2025

Rabu, 9 April 2025 · 10.00–11.40 WIB (100 menit) · Buku tertutup. Tuliskan NIM dan nama pada setiap lembar; sertakan asumsi/gambar bila perlu.

1. Informed Search (30%)

Graf berarah dari initial state S ke goal G. Daftar sisi dari gambar:

S→A, S→C, S→D
A→K
C→K, C→E, C→G
D→E
K→B, K→J
B→H
H→G, J→G
E→F, E→I
F→G, I→G

Tentukan cost aktual dan estimasi cost yang disesuaikan (customized) dengan preferensi masing-masing. a. (20%) Tentukan rute pencarian A*. b. (10%) Jelaskan poin kunci algoritma A*.

2. 8-puzzle (30%)

Initial     Goal
1 3 2       1 2 3
5 _ 4       4 _ 5
8 6 7       6 7 8

Operator: geser kanan, kiri, atas, bawah. a. (20%) Tentukan pemetaan graf kasus tersebut. b. (10%) Tentukan rute pencarian BFS. Boleh memberi nama pada setiap state.

3. Iterative Search (40%)

Gambar menunjukkan fungsi objektif f(x) dengan beberapa puncak dan lembah pada x sekitar −3 hingga 3. Search path ditandai lingkaran; final solution bertanda silang berada pada puncak lokal sekitar x=−2.1, f(x)≈1. Puncak lebih tinggi ada dekat x≈0.25, f(x)≈1.65; puncak lain dekat x≈2.1, f(x)≈1.05. Nilai ini hanya pembacaan perkiraan gambar, bukan data numerik yang diberikan soal.

a. (10%) Jelaskan alur kerja Simulated Annealing (SA) mencari global optimum. b. (10%) Jelaskan alur kerja Hill Climbing (HC) mencari global optimum. c. (10%) Jika SA terjebak local optimum pada gambar, bagaimana agar dapat menemukan global optimum? d. (10%) Mengapa HC dapat terjebak dan tidak bisa lolos dari local optimum?

1. A* dengan biaya yang dipilih

Soal membebaskan pemilihan biaya. Pilih semua sisi berarah pada gambar berbobot 1 dan $h(n)=0$ untuk setiap simpul. Ini admissible dan konsisten. Dari S, masukkan A,C,D dengan $g=f=1$ . Ambil C (jika tie memilih alfabet, A boleh diproses lebih dahulu); C memiliki sisi langsung ke G, sehingga G masuk dengan $g=f=2$ . Setelah semua simpul dengan prioritas lebih kecil diproses, G dikeluarkan. Rute S→C→G, biaya 2. Pilihan biaya/heuristik lain dapat menghasilkan rute berbeda.

A* mengurutkan frontier berdasarkan $f=g+h$ , dengan $g$ biaya dari awal dan $h$ estimasi sisa. Simpan jarak terbaik dan parent; perbarui jika jalur yang lebih murah ditemukan. Dengan biaya tak negatif dan heuristik admissible (serta reopening bila diperlukan), solusi goal yang dipilih sesuai kriteria terminasi adalah optimal.

2. Pemetaan dan BFS 8-puzzle

State adalah susunan sembilan sel; sisi menggeser sel kosong satu langkah legal kanan/kiri/atas/bawah. Awal 132/5_4/867, tujuan 123/4_5/678. BFS menyimpan queue dan visited, membangkitkan seluruh tetangga legal per level lalu merekonstruksi parent saat goal ditemukan; biaya tiap gerakan satu. Satu lintasan minimum hasil BFS, dengan urutan operator kanan, kiri, atas, bawah, terdiri dari 22 gerakan:

132/5_4/867 → 132/_54/867 → 132/854/_67 → 132/854/6_7
→ 132/8_4/657 → 132/_84/657 → _32/184/657 → 3_2/184/657
→ 382/1_4/657 → 382/14_/657 → 38_/142/657 → 3_8/142/657
→ _38/142/657 → 138/_42/657 → 138/4_2/657 → 138/42_/657
→ 13_/428/657 → 1_3/428/657 → 123/4_8/657 → 123/458/6_7
→ 123/458/67_ → 123/45_/678 → 123/4_5/678

Garis miring memisahkan baris dan _ menandakan kosong. Pada papan ganjil, kedua state memiliki paritas inversi genap (4 dan 0), sehingga tidak terhalang paritas. BFS menemukan rute terpendek dalam jumlah gerakan; pemetaan graf tidak perlu menggambar semua state untuk menjelaskan aturan pembangkitannya.

1 / 3

State awal

Ruang kosong berada di tengah.

1	2	3
1	3	2
5	_	4
8	6	7

Langkah

Jejak ini menampilkan awal dan akhir dari lintasan BFS 22 langkah di atas.

3. SA dan hill climbing

Simulated annealing memilih tetangga, menerima perbaikan, dan untuk minimisasi menerima pemburukan $\Delta>0$ dengan probabilitas $e^{-\Delta/T}$ ; suhu diturunkan bertahap dan solusi terbaik disimpan. Untuk maksimum balik tanda definisi perubahan. Pada suhu cukup tinggi ia dapat menerima langkah memburuk untuk menyeberangi lembah menuju optimum global; pendinginan lebih lambat, reheating, atau restart dapat meningkatkan peluang, tetapi run terbatas tidak menjamin optimum global.

Hill climbing memilih langkah yang memperbaiki nilai secara lokal sampai tidak ada perbaikan. Ia berhenti di optimum lokal karena tiap tetangga langsung lebih buruk atau sama meski optimum global di tempat lain; varian dengan sideways moves atau restart dapat mengatasi beberapa plateau, tetapi tetap tanpa jaminan umum.

Pembahasan ditulis independen oleh belajar.myudak, bukan kunci jawaban resmi. Soal asli tetap milik pengampu mata kuliah dan ditampilkan langsung dari arsip Google Drive.