UAS Analisis dan Strategi Algoritma 2026

UAS Analisis dan Strategi Algoritma 2025/2026

Kamis, 11 Juni 2026 · 10.00–11.30 WIB (90 menit) · Buku tertutup. Tuliskan NIM dan nama pada setiap lembar. Dilarang plagiasi, kerja sama, saling pinjam, dan komunikasi; pelanggaran bernilai 0.

1. Navigasi kampus (10%)

Simpul adalah gedung, sisi adalah jalan, dan bobot adalah estimasi waktu tempuh. Sistem menyediakan BFS, DFS, UCS, Greedy Best-First Search, dan A*. a. (5%) Jelaskan algoritma paling tepat untuk mencari waktu minimum. Bandingkan dengan minimal dua algoritma lain yang kurang tepat. b. (5%) Jelaskan kondisi agar algoritma pilihan tetap menghasilkan solusi optimal.

2. Heuristic (10%)

Aplikasi menggunakan A* dengan $f(n)=g(n)+h(n)$ , tetapi heuristic terkadang lebih besar daripada jarak sebenarnya menuju goal. a. (5%) Analisis dampaknya terhadap hasil pencarian. b. (5%) Bedakan heuristic admissible, tidak admissible, dan terlalu kecil. Apakah heuristic terlalu kecil selalu buruk?

3. Pemangkasan (10%)

Backtracking dan Branch and Bound membentuk pohon ruang status dan dapat memangkas simpul, tetapi penggunaannya tidak selalu sama. a. (5%) Bandingkan tujuan, cara pemangkasan, dan jenis persoalan yang cocok. b. (5%) Berikan contoh kasus yang lebih cocok untuk masing-masing algoritma.

4. Program Dinamis (10%)

Persoalan dapat dibagi menjadi beberapa tahap; tiap tahap mempunyai keputusan, dan keputusan sebelumnya memengaruhi keadaan berikutnya. a. (5%) Kapan layak diselesaikan dengan Program Dinamis? Gunakan stage, state, decision, dan prinsip optimalitas. b. (5%) Berikan contoh persoalan yang cocok dan tidak cocok menggunakan Program Dinamis.

5. Tradeoff algoritma (10%)

Dua algoritma dapat optimal tetapi berbeda kebutuhan memori dan waktu, misalnya UCS, A*, Branch and Bound, dan Program Dinamis. a. (5%) Mengapa algoritma optimal belum tentu praktis untuk semua ukuran masalah? b. (5%) Pilih dua algoritma tersebut dan analisis tradeoff optimalitas, waktu, memori, serta kualitas informasi tambahan yang dibutuhkan.

6. Kurir (25%)

Kurir mengunjungi empat pelanggan lalu kembali ke gudang awal (simpul 1).

Dari/Ke	1	2	3	4	5
1	∞	10	8	9	7
2	10	∞	10	5	6
3	8	10	∞	8	9
4	9	5	8	∞	6
5	7	6	9	6	∞

Gunakan Branch and Bound dengan pendekatan bobot tur lengkap: a. (10%) Buat pohon ruang status bertahap. b. (3%) Tentukan fungsi bound. c. (10%) Hitung bound simpul-simpul yang dibangkitkan. d. (2%) Tentukan tur optimal dan total jaraknya.

7. Alokasi anggaran (25%)

FSM Undip memiliki 6 miliar untuk digitalisasi layanan, pelatihan SDM, dan promosi internasional.

Alternatif	Biaya digitalisasi	Manfaat	Biaya SDM	Manfaat	Biaya promosi	Manfaat
1	0	0	0	0	0	0
2	2	30	1	15	2	25
3	3	40	3	45	4	55
4	5	65	4	60	—	—

Gunakan program dinamis maju agar manfaat total maksimum: a. (3%) Jelaskan tahap, state, dan alternatif keputusan. b. (15%) Hitung tabel tiap tahap. c. (4%) Rekonstruksi solusi optimal dari tabel akhir. d. (3%) Tentukan total biaya dan manfaat.

Pencarian optimal, heuristik, backtracking, branch and bound, dan program dinamis.

1. Rute minimum

UCS memilih simpul dengan biaya tempuh $g$ terkecil dan tepat untuk bobot waktu yang tidak negatif. Pada graf hingga, dengan pembaruan jarak ketika ditemukan jalur lebih murah, ia optimal. BFS hanya meminimalkan jumlah sisi (optimal bila biaya sisi sama), DFS tidak menjamin jarak minimum, dan greedy best-first hanya melihat estimasi jarak ke tujuan. A* juga tepat dengan heuristik yang memenuhi syarat optimalitas.

2. Heuristik A*

Heuristik yang melebihi jarak sebenarnya dapat membuat A* menunda jalur optimal dan mengembalikan jalur lebih mahal. Admissible berarti $h(n)\le h^*(n)$ ; tidak admissible melanggar batas ini pada setidaknya satu simpul. Heuristik terlalu kecil masih admissible: ia biasanya memperluas lebih banyak simpul, tetapi tidak salah. $h=0$ membuat A* setara UCS. Untuk graph search tanpa membuka ulang simpul tertutup, gunakan heuristik konsisten; dengan admissible tak konsisten, izinkan reopening dan terapkan kriteria terminasi yang benar.

3. Dua metode pencarian

Backtracking umumnya mencari solusi layak dan memotong pilihan parsial yang sudah melanggar kendala; N-Queens cocok. Branch and bound mencari nilai optimum dan memotong cabang bila bound-nya tidak dapat memperbaiki solusi terbaik; TSP berbobot cocok. Keduanya dapat memakai pohon status dan pruning, dan backtracking juga dapat dimodifikasi untuk optimasi.

4. Program dinamis

Tahap adalah urutan keputusan, state merangkum informasi yang memengaruhi masa depan, dan decision mengubah state dan nilai. Gunakan DP bila berlaku prinsip optimalitas (solusi optimal tersusun dari subsolusi optimal untuk state yang memadai) dan submasalah berulang. Contoh alokasi anggaran pada soal 7. Pencarian dengan semua riwayat unik dan tanpa submasalah berulang biasanya tidak diuntungkan memoization; state yang membuang informasi penting juga tidak valid.

5. Optimal belum tentu praktis

UCS dan A* dapat menyimpan banyak frontier dan memerlukan waktu/ruang eksponensial dalam ukuran deskripsi masalah. UCS tidak membutuhkan heuristik tetapi bisa mengeksplorasi banyak simpul. A* memerlukan heuristik admissible dan, dalam implementasi tertentu, konsisten; heuristik yang informatif dapat mengurangi ekspansi, tetapi frontier tetap dapat sangat besar. Keduanya optimal pada syarat masing-masing; optimalitas tidak menjamin biaya komputasi terjangkau.

6. TSP lima simpul

Gunakan bound bobot tur lengkap: untuk prefix, enumerasikan semua penyelesaian dan ambil total paling kecil. Ini bound tepat namun mahal; setiap total memasukkan kembali ke 1. Pohon berikut menunjukkan bound prefix; untuk menghemat ruang, setelah memperoleh incumbent 34, prefix dengan bound ≥34 boleh dipangkas jika hanya satu solusi diperlukan.

Prefix	Bound	Prefix	Bound	Prefix	Bound	Prefix	Bound
1–2	38	1–3	34	1–4	37	1–5	34
1–2–3	41	1–3–2	36	1–4–2	37	1–5–2	34
1–2–4	38	1–3–4	34	1–4–3	40	1–5–3	39
1–2–5	38	1–3–5	37	1–4–5	39	1–5–4	36

Contoh ekspansi 1→3→4→2→5→1 memiliki bobot $8+8+5+6+7=34$ ; kebalikannya 1→5→2→4→3→1 juga 34. Karena bound akar 34, 34 adalah optimum. Menghitung exact bound melalui semua penyelesaian sendiri melakukan kerja eksponensial; ini sesuai pendekatan bobot tur lengkap, bukan klaim efisiensi.

7. Alokasi anggaran

Tahap: digitalisasi, pelatihan, promosi. State $b$ adalah anggaran tersedia (miliar), keputusan memilih satu alternatif program; $F_i(b)=\max_{(c,v):c\le b}[F_{i-1}(b-c)+v]$ dengan $F_0(b)=0$ . Tabel menyatakan manfaat maksimum dengan biaya paling banyak b.

Tahap / b	1	2	3	4	5	6
Digitalisasi	0	30	40	40	65	65
+ Pelatihan	15	30	45	60	75	90
+ Promosi	15	30	45	60	75	90

Dari $F_3(6)=90$ , pilih promosi biaya 0; $F_2(6)=90$ diperoleh dari pelatihan biaya 4 manfaat 60 dan $F_1(2)=30$ , yakni digitalisasi biaya 2 manfaat 30. Total 6 miliar, manfaat 90.

1 / 3

Digitalisasi

Nilai terbaik untuk setiap batas anggaran 0 sampai 6.

b	0	1	2	3	4	5	6
Digitalisasi	0	0	30	40	40	65	65

Langkah

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