Soal ini sudah pernah saya baca sejak tahun 2010, yaitu ketika saya bertekad untuk menyelesaikan soal-soal UVa di chapter 103. Sayangnya, berhari-hari telah saya gunakan untuk memikirkan solusinya dan tidak juga ditemukan :(. Ingin mencari diskusinya di internet pun sumbernya sangat sedikit. Akhirnya pada tahun 2013, saya kembali menantang soal ini dan setelah diskusi dengan Ashar, kami berhasil menyelesaikannya!
Untuk menyelesaikan soal ini, perlu dipahami bahwa soal ini dapat dimodelkan sebagai permainan 2 pemain: satu orang berusaha berjalan sampai pintu keluar (sebut saja A), dan satu orang berusaha memblokir jalan (sebut saja B). Terdapat perbedaan peran yang mana B hanya memiliki kesempatan satu kali memblokir dan dapat dilaksanakan kapan saja. Lalu setelah diblokir, permainan dapat dianggap berakhir karena si pemain yang satunya pasti memilih jalur terpendek. Pertanyaannya adalah: jika keduanya bermain optimal, berapa langkah minimal yang dibutuhkan oleh pemain yang berjalan?
Mari kita sederhanakan persoalannya: anggap peta yang diberikan berbentuk DAG (Directed Acyclic Graph). Untuk menyelesaikan persoalan teori game, kita akan gunakan pendekatan minimax.
Misalkan A sedang di posisi (i, j). Kemungkinan yang dapat terjadi adalah:
Selanjutnya dapat dirumuskan DP minimax dengan state (i, j), yaitu posisi dimana A berada. Nilai DP ini adalah jarak terkecil yang dibutuhkan apabila pemain A ada di (i, j), dan pemain B masih bisa memblokir jalan. Dirumuskan:
\(\displaystyle
f(i, j) = \left\{
\begin{array}{lll}
0 & &,(i, j) = finish \\
\max \big{(} & \displaystyle \min_{(ni,nj) \in adj((i,j))} 1 + f(ni,nj), & \\
& \displaystyle \max_{(ni,nj) \in adj((i,j))} g(i,j,ni,nj) \ \ \big{)} & ,(i, j) \neq finish
\end{array}
\right.
\)
dengan g(i,j,ni,nj) adalah jarak terpendek untuk pergi dari posisi (i, j) menuju ke pintu keluar, dengan petak baris ni dan kolom nj diblokir. Nilai ini bisa di-precompute pada awal eksekusi program dengan BFS. Setelah itu, jalankan DP dari pintu masuk dan persoalan selesai!
Sekarang bagaimana bila persoalannya bukan DAG, melainkan graph secara umum?
Percobaan pertama mungkin berusaha merubahnya menjadi DAG. Sayangnya, saya dan Ashar tidak menemukan caranya. Hal ini menjadi tidak sesederhana biasanya karena melewati jalan yang dekat belum tentu menghasilkan jawaban minimal, sehingga tidak ada kepastian.
Kemudian Ashar menawarkan strategi berikut:
Awali nilai f(i,j) untuk setiap i dan j sebagai tak hingga. Khusus untuk petak pintu keluar, nilainya adalah 0 (pasti benar). Setelah itu, petak-petak yang bertetanggaan dengan petak pintu keluar bernilai 1 (bagaimanapun juga si B memblokir jalan, A pasti bisa sampai pintu keluar dalam 1 langkah). Kemudian untuk petak-petak sisanya, akan diisi sesuai dengan rekurens di atas selama beberapa kali iterasi sampai hasilnya tidak berubah (konvergen). Strategi ini cukup dikenal pada game theory, ketika game state yang ada bersifat siklis (bukan DAG). Kompleksitas solusinya secara keseluruhan (prekomputasi + pencarian solusi) adalah O(R2C2 + kRC).
Setelah mencoba strategi tersebut, ternyata AC!
Dari sini saya mempelajari hal baru, yaitu pengulangan iterasi sampai konvergen dalam game theory.
Berikut ini adalah implementasinya:
Untuk menyelesaikan soal ini, perlu dipahami bahwa soal ini dapat dimodelkan sebagai permainan 2 pemain: satu orang berusaha berjalan sampai pintu keluar (sebut saja A), dan satu orang berusaha memblokir jalan (sebut saja B). Terdapat perbedaan peran yang mana B hanya memiliki kesempatan satu kali memblokir dan dapat dilaksanakan kapan saja. Lalu setelah diblokir, permainan dapat dianggap berakhir karena si pemain yang satunya pasti memilih jalur terpendek. Pertanyaannya adalah: jika keduanya bermain optimal, berapa langkah minimal yang dibutuhkan oleh pemain yang berjalan?
Mari kita sederhanakan persoalannya: anggap peta yang diberikan berbentuk DAG (Directed Acyclic Graph). Untuk menyelesaikan persoalan teori game, kita akan gunakan pendekatan minimax.
Misalkan A sedang di posisi (i, j). Kemungkinan yang dapat terjadi adalah:
- A bergerak seperti biasa, ke salah satu lokasi yang dapat dia capai.
- B memblokir salah satu lokasi yang bisa dicapai A, sehingga A harus pergi ke lokasi yang lain.
Selanjutnya dapat dirumuskan DP minimax dengan state (i, j), yaitu posisi dimana A berada. Nilai DP ini adalah jarak terkecil yang dibutuhkan apabila pemain A ada di (i, j), dan pemain B masih bisa memblokir jalan. Dirumuskan:
\(\displaystyle
f(i, j) = \left\{
\begin{array}{lll}
0 & &,(i, j) = finish \\
\max \big{(} & \displaystyle \min_{(ni,nj) \in adj((i,j))} 1 + f(ni,nj), & \\
& \displaystyle \max_{(ni,nj) \in adj((i,j))} g(i,j,ni,nj) \ \ \big{)} & ,(i, j) \neq finish
\end{array}
\right.
\)
Sekarang bagaimana bila persoalannya bukan DAG, melainkan graph secara umum?
Percobaan pertama mungkin berusaha merubahnya menjadi DAG. Sayangnya, saya dan Ashar tidak menemukan caranya. Hal ini menjadi tidak sesederhana biasanya karena melewati jalan yang dekat belum tentu menghasilkan jawaban minimal, sehingga tidak ada kepastian.
Kemudian Ashar menawarkan strategi berikut:
Awali nilai f(i,j) untuk setiap i dan j sebagai tak hingga. Khusus untuk petak pintu keluar, nilainya adalah 0 (pasti benar). Setelah itu, petak-petak yang bertetanggaan dengan petak pintu keluar bernilai 1 (bagaimanapun juga si B memblokir jalan, A pasti bisa sampai pintu keluar dalam 1 langkah). Kemudian untuk petak-petak sisanya, akan diisi sesuai dengan rekurens di atas selama beberapa kali iterasi sampai hasilnya tidak berubah (konvergen). Strategi ini cukup dikenal pada game theory, ketika game state yang ada bersifat siklis (bukan DAG). Kompleksitas solusinya secara keseluruhan (prekomputasi + pencarian solusi) adalah O(R2C2 + kRC).
Setelah mencoba strategi tersebut, ternyata AC!
Dari sini saya mempelajari hal baru, yaitu pengulangan iterasi sampai konvergen dalam game theory.
Berikut ini adalah implementasinya:
Tidak ada komentar :
Posting Komentar