Analisis dan Desain Algoritma UAS

Bagaimana konsep bekerja algoritma gready ?

• Pembangkitan solusi dilakukan dengan melakukan penelusuran secara bertahap, jika suatu tahap dari solusi tidak memenuhi konstrain maka akan kembali ke tahap sebelumnya untuk mencoba kemungkinan solusi lainnya.

• Pembangkitan solusi dilakukan dengan memilih lokal optimum dari setiap kondisi pada saat itu.

• Dalam proses menemukan solusi dilakukan proses memoization sehingga dapat mengurangi proses komputasi yang tidak perlu dilakukan

• Melakukan penelusuran dengan startegi BFS dengan mempertimbangkan biaya minimal yang dibutuhkan untuk melakukan penelusuran selanjutnya

Algoritma yang menggunakan strategi memoization untuk mengurangi biaya komputasi adalah

• algoritma branch and bound

• Algoritma Greedy

• DIvide dan Conquer

• Dynamic Programming

Tahapan dalam algoritma divide and conquer yang bertujuan untuk menggabungkan solusi dari permasalahan adalah...

Strategi yang dilakukan dalam algoritma dynamic programming untuk menyimpan solusi dalam memori disebut..

Strategi penelusuran yang digunakan dalam algoritma branch and bound adalah...

Strategi penelusuran yang digunakan dalam algoritma backtracking adalah ...

Tahapan yang dilakukan untuk menyelesaikan sub permasalahan pada algoritma divide and conquer disebut...

Pilih semua syarat yang merupakan syarat mutlak bahwa sebuah masalah dapat diselesaikan secara divide and conquer

• permasalah dapat dibagi-bagi menjadi submasalah kecil

• setiap submasalah dapat diselesaikan secara terpisah

• setiap submasalah boleh berdbeda

• terdapat metode untuk dapat menggabungkan solusi dari setiap masalah

Selesaikan permasalahan pada gambar tersebut dengan menggunakan algoritma dynamic programming. Cost minimal yang dibutuhkan adalah....

Soal yang sama dengan sebelumnya dynamic programming, rute yang dilalui untuk mendapatkan nilai cost minimal adalah...(tuliskan mulai dari 0- ...-9 dst)