jawabn no 60:

1.5. Eksplorasi dalam Masalah Kombinatorik

Dalam problem solving seringkali masalah yang diberikan bersifat kombinatorik (mendapatkan setiap kemungkinan kombinasi/permutasi jawaban). Untuk memecahkannya terkadang seluruh kemungkinan tersebut harus diperiksa untuk mendapatkan pemecahan yang umum.

Contoh:
Jika diketahui dalam perkalian matriks A (mxn) dengan B (nxp) diperlukan biaya mnp. Sementara untuk perkalian tiga matriks A.B.C dengan A(mxn), B(nxp) dan C(pxq) ternyata terdapat dua kemungkinan biaya yang bergantung pada urutannya:
• urutan (A.B).C (yaitu A dikali B dahulu kemudian dikali C), dan
• urutan A.(B.C) (yaitu B dikali C dahulu kemudian dikali A).
Urutan (A.B).C memerlukan harga mnp + mpq sementara urutan A.(B.C)
memerlukan harga npq + mnq. Kedua harga bisa berbeda sesuai dengan
harga-harga m, n, p, q tsb. Pertanyaannya, untuk perkalian empat matriks
A.B.C.D dengan A(10x4), B(4x15), C(15x2), dan D(2x20) manakah urutan
dengan biaya minimum?

Kemungkinan-kemungkinan urutan adalah (diperoleh dengan permutasi
ketiga tanda perkalian “.”):

• urutan (((A.B).C).D), biaya 10x4x15+10x15x2+10x2x20 = 1300
• urutan ((A.B).(C.D)), biaya10x4x15+15x2x20+10x15x20 = 4200
• urutan ((A.(B.C)).D), biaya 4x15x2+10x5x2+10x2x20 = 600
• urutan (A.((B.C).D)), biaya 4x15x2+4x2x20+10x4x20 = 1080
• urutan ((A.B).(C.D)), biaya 15x2x20+10x4x15+10x15x20 = 4200
• urutan (A.(B.(C.D))), biaya 15x2x20 + 4x15x20+10x4x20 = 4200