UAS Analisis dan Strategi Algoritma 2025

UAS Analisis dan Strategi Algoritma 2024/2025 — Soal A

Senin, 16 Juni 2025 · 08.00–09.30 WIB (90 menit) · Buku tertutup. Tuliskan NIM, nama, dan kode soal. Sertakan asumsi/gambar bila perlu. Dilarang bekerja sama, menyontek, dan meminjam alat tulis/penghapus; pelanggaran bernilai 0.

Benar/Salah (2% per soal, total 20%)

Tentukan apakah pernyataan berikut Benar atau Salah!

BFS menjamin solusi optimal jika tiap langkah memiliki biaya yang sama.
DFS selalu lebih cepat daripada BFS dalam menemukan solusi terpendek.
Backtracking melakukan eksplorasi semua solusi secara menyeluruh tanpa pemangkasan terhadap pilihan yang tidak valid.
Backtracking dapat diterapkan pada labirin, N-Queens, pewarnaan graf, dan subset jumlah tertentu.
Dalam Branch and Bound, simpul dengan estimasi biaya terkecil dipilih untuk diekspansi berikutnya.
Semua simpul dalam pohon ruang status selalu diekspansi dalam B&B tanpa mempertimbangkan apakah lintasannya menjanjikan.
Greedy Best-First Search menggunakan $f(n)=g(n)+h(n)$ untuk memperkirakan biaya total dari awal ke tujuan.
UCS menjamin solusi optimal selama semua biaya langkah bernilai positif.
Semua persoalan dalam kelas NP dapat diselesaikan algoritma deterministik dalam waktu polinomial.
Halting Problem termasuk persoalan yang tidak dapat diselesaikan mesin Turing (unsolvable).

Uraian 1 (25%)

Tim kelautan Undip mengeksplorasi laut dalam di perairan Banda. Robot bawah laut memiliki kapasitas muatan maksimum 15 kg. Pilih kombinasi peralatan dengan nilai ilmiah tertinggi tanpa melampaui kapasitas.

No	Peralatan	Berat (kg)	Nilai ilmiah
1	Sensor Salinitas	4	12
2	Kamera Tekanan Tinggi	6	18
3	Tabung Oksigen Cadangan	5	10
4	Jaring Mikroorganisme	3	9

a. Tentukan kombinasi optimal menggunakan backtracking! b. Gambarkan pohon ruang statusnya!

Uraian 2 (25%)

Lembaga kemanusiaan mendistribusikan obat ke empat pulau P, Q, R, S menggunakan drone medis. Berangkat dari P, kunjungi semua kota tepat sekali, lalu kembali ke P dengan total jarak minimum. Jarak dalam km:

	P	Q	R	S
P	∞	12	10	19
Q	12	∞	8	14
R	10	8	∞	11
S	19	14	11	∞

a. Gunakan Branch and Bound untuk menentukan tur minimum P kembali ke P! b. Gambarkan pohon ruang statusnya!

Uraian 3 (30%)

Drone penyelamat mencari jalur tercepat dari S menuju korban G di hutan, dengan jarak antartitik dan estimasi jarak tujuan.

Graf tidak berarah dari gambar:

Sisi	Jarak
S–A	2
S–B	3
A–D	2
B–D	3
A–C	4
D–G	4
C–G	5

Node	h(n)
S	7
A	6
B	5
C	3
D	2
G	0

a. Tentukan rute minimum menggunakan A* dan Greedy BFS! b. Gunakan tabel antrean prioritas penelusuran kota lengkap dengan jarak yang sudah ditempuh!

Naskah yang tersedia berakhir pada halaman 2 dari 3, tetapi graf dan semua subpertanyaan soal uraian 3 terlihat pada halaman 2.

Benar/salah

No.	Jawaban	Alasan
1	Benar	BFS meminimalkan jumlah sisi; dengan biaya langkah sama ini juga meminimalkan biaya.
2	Salah	DFS dapat menjelajahi cabang panjang sebelum menemukan lintasan terpendek.
3	Salah	Backtracking memangkas kandidat yang melanggar kendala.
4	Benar	Keempatnya dapat dimodelkan dengan pilihan parsial dan kendala.
5	Bergantung strategi	Best-bound memilih bound terbaik, tetapi branch and bound juga dapat memakai DFS atau FIFO; pernyataan umum tanpa kualifikasi tidak selalu benar.
6	Salah	Bound yang tidak dapat memperbaiki incumbent dapat dipangkas.
7	Salah	Greedy best-first memakai $h(n)$ ; $g+h$ adalah A*.
8	Benar	UCS optimal dengan biaya positif dan kondisi pencarian standar.
9	Belum diketahui	Pernyataan ini setara dengan P = NP, persoalan terbuka; tidak dapat dibuktikan benar maupun salah berdasarkan pengetahuan saat ini.
10	Benar	Tidak ada mesin Turing yang memutuskan halting untuk seluruh masukan program.

1. Backtracking knapsack

Empat item masing-masing (berat,nilai) = (4,12), (6,18), (5,10), (3,9); kapasitas 15. Pohon biner memiliki level item 1–4 dan dua cabang ambil/tidak. Pangkas setiap cabang segera setelah berat >15. Daftar daun layak (berat,nilai): (0,0), (3,9), (4,12), (5,10), (6,18), (7,21), (8,19), (9,22), (9,27), (10,30), (11,28), (12,31), (13,39), (14,37), (15,40); kombinasi 18 kg tidak layak. Nilai optimum 40 dengan item 1, 2, 3, berat 15 kg. Pohon berikut memakai 1 untuk ambil dan 0 untuk tidak ambil; tuple adalah (berat,nilai), dan cabang melebihi kapasitas dipangkas.

akar (0,0)
├─ 1: (4,12)
│  ├─ 1: (10,30)
│  │  ├─ 1: (15,40) → 0: (15,40); 1: (18,49) pangkas
│  │  └─ 0: (10,30) → 0: (10,30); 1: (13,39)
│  └─ 0: (4,12)
│     ├─ 1: (9,22) → 0: (9,22); 1: (12,31)
│     └─ 0: (4,12) → 0: (4,12); 1: (7,21)
└─ 0: (0,0)
   ├─ 1: (6,18)
   │  ├─ 1: (11,28) → 0: (11,28); 1: (14,37)
   │  └─ 0: (6,18) → 0: (6,18); 1: (9,27)
   └─ 0: (0,0)
      ├─ 1: (5,10) → 0: (5,10); 1: (8,19)
      └─ 0: (0,0) → 0: (0,0); 1: (3,9)

2. Branch and bound TSP

Semua tur lengkap dari P: P-Q-R-S-P=50, P-Q-S-R-P=47, P-R-Q-S-P=51, P-R-S-Q-P=47, P-S-Q-R-P=51, P-S-R-Q-P=50. Maka optimum 47 km, misalnya P→Q→S→R→P atau arah sebaliknya. Pohon ruang status mempunyai akar P, tiga cabang Q/R/S, masing-masing dua cabang, lalu simpul tersisa dan kembali P. Enumerasi nilai lengkap ini juga memberi bound tepat untuk setiap prefix: P-Q = 47, P-R = 47, P-S = 50. Setelah menemukan 47, cabang P-S dapat dipangkas untuk mencari satu optimum. Bound ini sah tetapi mahal karena menghitung seluruh penyelesaian; bound relaksasi lebih murah untuk input besar.

3. Rute dan heuristik

Graf pada halaman 2 memiliki sisi S–A=2, S–B=3, A–D=2, A–C=4, B–D=3, D–G=4, dan C–G=5; heuristik S=7, A=6, B=5, C=3, D=2, G=0. Asumsikan graf tak berarah, hindari memasukkan kembali state yang sudah diproses tanpa perbaikan, dan pecahkan nilai prioritas sama menurut alfabet.

A* memakai f=g+h. Tabel menunjukkan antrean setelah simpul pada kolom pertama diekspansi; format entri adalah (simpul, g, f).

Ekspansi	Antrean prioritas
S	(A,2,8), (B,3,8)
A	(D,4,6), (B,3,8), (C,6,9)
D	(B,3,8), (G,8,8), (C,6,9)
B	(G,8,8), (C,6,9)
G	selesai

Hasil S→A→D→G, biaya 8. Rute ini juga minimum jika semua lintasan dibandingkan.

Greedy best-first memilih nilai h terkecil, namun tetap mencatat g untuk total jarak:

Ekspansi	Antrean prioritas `(simpul, g, h)`
S	(B,3,5), (A,2,6)
B	(D,6,2), (A,2,6)
D	(G,10,0), (A,2,6)
G	selesai

Hasil greedy S→B→D→G, biaya 10; ia tidak menjamin rute minimum karena tidak memakai biaya yang sudah ditempuh untuk memilih frontier. Jika urutan tie di A* berbeda, urutan ekspansi dapat berbeda namun biaya hasil tetap 8 pada contoh ini.

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