Cerita
Indiana Jones sedang menjelajahi sebuah gua di mana harta karun berharga berada. Tiba-tiba, gempa bumi terjadi.
Ketika gempa berakhir, ia memperhatikan bahwa beberapa batu yang jatuh dari langit-langit menghalangi jalan menuju harta karun itu. Dia juga memperhatikan bahwa dia bisa mendorong batu, tetapi karena batu sangat berat, dia tidak bisa mendorong dua batu berturut-turut .
Tujuan Anda adalah membantu Indiana Jones mendapatkan harta karun itu. Karena sangat sulit untuk mendorong bahkan satu batu pun, jumlah dorongan sangat penting.
Masalah
Temukan cara terbaik (di mana Indiana Jones mendorong batu sesedikit mungkin), untuk menemukan harta karun itu.
Peta (masukan)
Peta ini adalah m
oleh n
(keduanya lebih besar dari 1) matriks yang dapat berisi lima jenis sel:
0
yang berarti sel kosong,1
yang berarti dinding,2
di mana Indiana Jones berada (hanya satu yang ada),3
di mana harta itu berada (hanya ada satu),- dan
4
, yang berarti batu.
Di baris pertama peta, dimensi peta ditentukan seperti 4 6
, dan dari baris kedua ke baris terakhir peta, struktur gua ditentukan seperti ini.
110131
104040
100101
200000
Karena itu, peta lengkapnya adalah:
4 6
110131
104040
100101
200000
yang berarti
Peta diberikan oleh stdin, file (Anda dapat menentukan nama file), atau array dalam kode yang hanya berisi informasi di atas.
Keluaran
Jumlah minimum yang harus ditekan oleh Indiana Jones. Jika tidak ada cara seperti itu, output X
.
Dalam kasus di atas , dia bisa mendorong batu ke kiri ke atas, lalu dia bisa mendorong batu ke kanan ke kanan untuk mendapatkan harta. Oleh karena itu, output dalam hal ini adalah 2
.
Namun. pada kasus ini :
4 6
111131
104040
100101
200000
(lihat bagian di bawah) dia tidak bisa mendorong batu kanan karena akan menghancurkan harta karun. Juga, mendorong batu kiri ke kanan tidak mengubah apa pun. Oleh karena itu, outputnya adalah X
.
Aturan
- Dia dapat bergerak hanya dalam empat arah, atas, bawah, kiri, dan kanan.
- Dia tidak bisa mendorong dua batu berturut-turut .
- Dia tidak bisa menarik batu apa pun, dan dia bisa mendorong batu hanya dalam satu arah ('maju').
- Dia tidak bisa menembus tembok. Hanya tempat dia bisa pergi adalah sel kosong dan sel harta.
- Batu itu tidak bisa diletakkan di atas harta karun itu. Itu akan menghancurkan harta karun itu. :(
- Dia tidak bisa keluar dari peta.
Tujuan
Program yang dapat menangani sebagian besar peta (disediakan di bagian 'Contoh' + lainnya) dalam waktu yang wajar (khususnya, 10 detik) dan menghasilkan jawaban yang benar akan menang.
Di sini 'yang lain' berarti contoh input yang disediakan dalam jawaban. Ini berarti Anda harus membuat algoritma yang cerdas sehingga program lain tidak dapat menyelesaikan peta yang dapat dipecahkan oleh program Anda, dan peta yang dipecahkan oleh program lain dapat diselesaikan oleh program Anda. Namun, memasukkan solusi ke dalam kode tidak akan dianggap valid.
Catatan
Awalnya ini adalah proyek jangka menengah dari kelas AI yang saya dengarkan, hanya satu hal yang berbeda: dikatakan bahwa hanya ada dua batu.
Dikatakan bahwa masalah ini adalah NP, tetapi juga dikatakan bahwa algoritma heuristik yang baik dapat menyelesaikan masalah dengan cukup efisien. Saya menggunakan beberapa ide dan heuristik untuk menyelesaikan masalah secara efisien, dan kode saya dapat menemukan semua solusi sampel dengan sangat cepat (kurang dari satu detik).
Namun, ketika ada lebih dari dua batu, ada beberapa kasus di mana kode tidak dapat menemukan jawabannya dalam waktu yang wajar. Saya punya beberapa ide, tetapi beberapa di antaranya 'salah', dan saya tidak bisa mengungkapkan ide lain ke kode. Saya ingin melihat algoritma pintar apa yang ada untuk menyelesaikan masalah ini, jadi saya menulis ini.
Karena saya sudah menyelesaikan proyek (btw, gambar bukan milik saya - saya googled itu), Anda tidak perlu khawatir tentang itu.
Contohnya
Contohnya bisa dilihat di sini. Anda juga dapat melihat contoh, dan menguji hasil Anda di sini (ini harus bekerja di browser modern). Anda bisa mendapatkan peta dalam format yang dijelaskan di atas, dengan mengetik whatisthis()
di konsol JS.
http://bit.sparcs.org/~differ/sokoban/#0 ~ http://bit.sparcs.org/~differ/sokoban/#19 berisi contoh-contoh yang aslinya merupakan kelas yang disediakan.
Hasil
Maaf, saya terlambat .. sebenarnya cukup banyak. : P (Saya terlalu malas untuk mencetak gol. Maaf.)
Di bawah ini hasilnya. (X: salah, O: benar,?: Membutuhkan setidaknya 10 detik, dihentikan)
Map#: 0 1 2 3 4 5 12 15 19 T1 T2 T3 T4 T5 T6 T7
Ruby: X O O ? O O O X ? ? O ? ? ? ? ?
Java: O O X O X X O O ? ? O O O X O O
(Java 19: mengambil 25s, hasilnya benar.) (Saya menggunakan ruby 1.9.3 dan javac 1.7.0_13)
Tampaknya algoritma Java memang lebih baik. (Omong-omong, saya memikirkan metode yang sama, tetapi saya menyadari bahwa peta seperti peta uji 5 ada.)
sumber
Jawaban:
Java - Sedikit lebih pintar / lebih cepat
Cukup banyak kode di sana. Saya berusaha untuk lebih cepat dengan mengevaluasi dorongan dalam urutan "seberapa besar kemungkinan ini membebaskan jalan ke harta karun", yang itu sendiri didasarkan pada dua lintasan Dijkstra (satu berhenti ketika bertemu batu, yang lain mengabaikan batu). Ini bekerja dengan cukup baik, dan satu contoh dari pastebin yang tampaknya menyusahkan bagi penulis diselesaikan dalam waktu sekitar 2 detik oleh implementasi ini. Beberapa contoh lain memakan waktu hingga 30-40 detik, yang menurut saya masih terlalu lama, tetapi saya tidak dapat menemukan cara untuk memperbaikinya tanpa merusaknya :)
Saya telah membagi barang-barang saya menjadi beberapa file untuk mendapatkan struktur yang lebih baik (juga mengapa saya beralih ke Jawa dari ruby):
Titik masuk:
Petunjuk penolong:
Kelas abstrak untuk mewakili bagian yang terletak dari "maze":
Dan akhirnya, labirin itu sendiri:
sumber
Ruby - Besar & bloster
Agak naif implementasi yang brute-force itu jalan menembus labirin. Ini tidak super cepat dalam beberapa (tidak begitu) kasus aneh. Ini dapat ditingkatkan dengan menemukan heuristik yang lebih baik daripada hanya "jika lebih dekat dengan harta, kita akan ingin menyelidiki dulu", tetapi ide-ide umum ada di sana.
Ini juga akan menunjukkan kepada Anda bagaimana Indiana mendapatkan harta karun itu jika ia bisa, itu bonus.
Sunting: Saya memikirkan cara untuk meningkatkan kinerja ini dalam situasi yang tidak jelas (saat ini menghisap telur hijau) dengan menjatuhkan evaluasi gerakan sederhana (misalnya hanya peduli ketika indy mendorong batu dan / atau sampai ke harta karun). Saya mungkin akan memperbarui kode nanti, setelah saya punya waktu untuk mengimplementasikan.
sumber
C ++ 14 dari 16
Algoritma tidak efisien dan haus memori. Selain itu saya tidak dapat menyediakan waktu untuk merapikannya, tetapi saya akan melakukannya ketika saya memiliki lebih banyak waktu;) Satu hal yang menarik adalah bahwa algoritma saya gagal pada peta pengujian yang sama dengan si penanya. Di notebook kuno saya proses mulai bertukar untuk peta T4 dan T6. Peta 3 membutuhkan waktu cukup lama, tetapi diselesaikan tepat waktu. Semua lainnya diselesaikan hampir instan. Jadi saya harus mencari cara untuk menyelesaikan T4 dan T6 dan mencoba algoritma pada mesin dengan lebih banyak memori. Akhirnya saya bisa menyelesaikan T4 dan T6 di sana. Saya akan terus memperbarui pos ...
Di bawah ini hasilnya. (X: salah, O: benar,?: Membutuhkan setidaknya 10 detik, dihentikan)
Karena kode sumbernya cukup panjang dan tidak terlalu bagus untuk dibaca ... Pada dasarnya hanya mencari semua batu yang dapat dijangkau oleh Indiana Jones. Untuk bebatuan yang dapat dijangkau, ia menyimpan informasi ke arah mana ia dapat dipindahkan. Jadi daftar kemungkinan langkah untuk peta saat ini dibuat. Untuk setiap kemungkinan perpindahan ini, salinan peta dibuat dan langkah tersebut diterapkan. Untuk peta yang baru dibuat, algoritme akan memeriksa lagi gerakan mana yang dapat diterapkan ... Ini dilakukan hingga tidak ada gerakan lebih lanjut yang memungkinkan atau cara untuk menemukan peti harta karun. Ketika algoritma pertama kali mencoba semua gerakan yang hanya akan mengambil satu gerakan untuk mencapai dada, maka semua yang akan mengambil dua, dan seterusnya ... cara pertama yang ditemukan juga secara otomatis terpendek. Untuk mencegah loop, algoritma mengingat untuk setiap peta gerakan apa yang bisa diterapkan. Jika peta lain dibuat yang menghasilkan daftar gerakan yang sudah ditemukan sebelumnya, maka mereka diam-diam dijatuhkan, karena mereka sudah diproses. Sayangnya tidak mungkin untuk mengeksekusi setiap gerakan hanya satu kali, karena mungkin ada peta yang membutuhkan batu untuk dipindahkan ke bidang yang sama beberapa kali. Kalau tidak, saya bisa menghemat banyak memori. Selain itu untuk menyelesaikan peta seperti peta 3 pada waktunya, algoritme mengabaikan semua batu yang dapat digerakkan ... Jadi pada peta 3, batu di tengah antah berantah akan dipindahkan, tetapi hanya sampai tidak ada lagi tembok di sekitarnya. Kode dapat dikompilasi dengan g ++ --std = c ++ 0x dengan g ++ versi 4.4.3 atau lebih baru. Anda tidak dapat melakukan setiap gerakan hanya satu kali, karena mungkin ada peta yang memerlukan batu untuk dipindahkan ke bidang yang sama beberapa kali. Kalau tidak, saya bisa menghemat banyak memori. Selain itu untuk menyelesaikan peta seperti peta 3 pada waktunya, algoritme mengabaikan semua batu yang dapat digerakkan ... Jadi pada peta 3, batu di tengah antah berantah akan dipindahkan, tetapi hanya sampai tidak ada lagi tembok di sekitarnya. Kode dapat dikompilasi dengan g ++ --std = c ++ 0x dengan g ++ versi 4.4.3 atau lebih baru. Anda tidak dapat melakukan setiap gerakan hanya satu kali, karena mungkin ada peta yang memerlukan batu untuk dipindahkan ke bidang yang sama beberapa kali. Kalau tidak, saya bisa menghemat banyak memori. Selain itu untuk menyelesaikan peta seperti peta 3 pada waktunya, algoritme mengabaikan semua batu yang dapat digerakkan ... Jadi pada peta 3, batu di tengah antah berantah akan dipindahkan, tetapi hanya sampai tidak ada lagi tembok di sekitarnya. Kode dapat dikompilasi dengan g ++ --std = c ++ 0x dengan g ++ versi 4.4.3 atau lebih baru. tetapi hanya sampai tidak ada lagi tembok di sekitarnya. Kode dapat dikompilasi dengan g ++ --std = c ++ 0x dengan g ++ versi 4.4.3 atau lebih baru. tetapi hanya sampai tidak ada lagi tembok di sekitarnya. Kode dapat dikompilasi dengan g ++ --std = c ++ 0x dengan g ++ versi 4.4.3 atau lebih baru.
Sunting: Program ini mengambil input dari stdin dan mengabaikan baris pertama yang berisi ukuran peta. Ia memeriksa apakah hanya karakter yang diizinkan dalam peta yang digunakan, tetapi tidak memverifikasi bahwa hanya ada satu Indiana Jones dan satu peti harta karun. Jadi dimungkinkan untuk menempatkan lebih dari satu dan gerakan paling tidak diperlukan untuk mencapai salah satu peti dicetak ke stdout. Setiap karakter yang tidak valid di peta dilewati dan program akan mencoba menghitung jumlah gerakan paling sedikit untuk peta yang dihasilkan. Perhitungan akan dimulai ketika stdin ditutup (pada sistem saya ctrl + d).
sumber