Seorang pengantar pizza mendapatkan tugas untuk mengantarkan pizza kepada pemesan pizza di rumahnya. Ada beberapa cara yang bisa ditempuh untuk sampai kepada rumah si pemesan, dengan gambaran seperti di atas.
Pengantar pizza ingin sampai tujuan dengan jalur terpendek, dengan titik A sebagai titik awal dan titik I sebagai titik akhir atau tujuannya dan angka-angka yang tertera pada panah merupakan jarak dari satu tempat ke tempat lainnya (dalam kilometer).
Jawab:
Untuk menyelesaikan permasalahan di atas, teknik yang digunakan adalah Dynami Programming dengan metode Backward. Dengan analisa sebagai berikut:
b Cost (2,B) = c(A,B) = 3
b Cost (3,C) = min{c(B,C) + b Cost (2,B)}
min{ 4 + 3 } = 7
b Cost (3,D) = min{c(B,D) + b Cost (2,B)}
min{ 3 + 3 } = 6
b Cost (3,E) = min{c(B,E) + b Cost (2,B)}
min{ 5 + 3 } = 8
b Cost (4,F) = min{c(C,F) + b Cost (3,C) | c(D,F) + b Cost (3,D)}
min { 7 + 7 | 5 + 6 } = 11
b Cost (4,G) = min{c(D,G) + b Cost (3,D) | c(E,G) + b Cost (3,E)}
min { 4 + 6 | 4 + 8 } = 10
b Cost (4,H) = min{c(D,H) + b Cost (3,D) | c(E,H) + b Cost (3,E)}
min { 6 + 6 | 5 + 8 } = 13
b Cost (5,I) = min{c(F,I) + b Cost (4,F) | c(G,I) + b Cost (4,G) | c(H,I) + b Cost (4,H)}
min{ 5 + 11 | 4 + 10 | 3 + 13 } = 14
# jadi jalur terpendek yang bisa diambil adalah :
A – B – D – G – I
Tidak ada komentar:
Posting Komentar