Olimpiade Sains Provinsi (OSP) 2018 - Komputer, Nomor 9
Diberikan peta rumah-rumah di kota Pak Dengklek tinggal seperti berikut:
Setiap rumah memiliki nomor dari 1 sampai 9. Dua buah rumah dihubungkan dengan sebuah jalan yang memiliki panjang tertentu. Pak Dengklek sedang berada di rumah no. 1 dan ingin berkunjung ke rumah no. 9. Ada berapa banyak rute berbeda yang dapat Pak Dengklek tempuh dengan total lintasan sependek mungkin? Dua buah rute dikatakan berbeda jika terdapat setidaknya satu jalan berbeda yang dipilih dari satu rute, tetapi tidak pada rute lainnya.
Jawaban: ……………. {tuliskan jawaban dalam bentuk angka saja}
3 jawaban
Noya Aldiputera7 tahun lalu
Jika ingin mendownvote, jangan lupa juga untuk komen tentang kesalahannya. That'll be helpful for everyone, don't let that be a habit.
2
Sangat terlalu keterlaluan dan menyebalkan sekali jikalau kita mengenumerasikan semua kemungkinan hidup ini (Hehe). Pertama-tama kita cari dulu mana rute yang terpendek untuk sampai ke rumah nomor 9, algoritma apapun boleh. Kita temukan bahwa 26 adalah rute yang terpendek. Perhatikan bahwa edge dan
tidak mungkin dilewati karena untuk setiap rute apapun, jika kita lewati edge/jalan ini maka kita akan menempuh jarak 26 lebih.
Perhatikan bahwa terdapat 5 kemungkinan rute dari rumah ke-1 sampai ke-5 dengan panjang terpendek, yaitu panjang 15 (enumerasi heuristik, bottom-up). Lalu perhatikan juga bahwa terdapat 1 kemungkinan rute saja untuk sampai ke rumah ke-4. Jadi, banyaknya cara untuk menempuh rumah ke-7 dalam rute terpendek yaitu . Banyaknya cara untuk menempuh rumah ke-8 pun lima, karena diikuti dari rute terpendek rumah ke-1 sampai ke-5 yang dimana terdapat 5 kemungkinan saja, sementara banyaknya cara untuk menempuh rumah ke-8 hanya satu saja.
Jadi, banyaknya cara untuk menempuh rumah ke-9 dengan rute terpendek adalah .
Masuk untuk menulis jawaban