Melacak status yang dikunjungi di Pencarian Pertama di Breadth

Jadi saya mencoba menerapkan BFS pada teka-teki Sliding Blocks (jenis angka). Sekarang hal utama yang saya perhatikan adalah jika Anda memiliki 4*4papan, jumlah negara bagian dapat sama besar 16!sehingga saya tidak dapat menghitung semua negara bagian sebelumnya.

Jadi pertanyaan saya adalah bagaimana cara melacak negara yang sudah dikunjungi? (Saya menggunakan papan kelas setiap instance kelas berisi pola papan yang unik dan dibuat dengan menyebutkan semua langkah yang mungkin dari langkah saat ini).

Saya mencari di internet dan tampaknya mereka tidak kembali ke langkah yang baru saja selesai, TETAPI kita bisa kembali ke langkah sebelumnya dengan rute lain juga dan kemudian menghitung ulang semua langkah yang telah dikunjungi sebelumnya. Jadi bagaimana cara melacak negara yang dikunjungi ketika semua negara belum disebutkan? (Membandingkan status yang sudah ada dengan langkah saat ini akan mahal).

Anda dapat menggunakan set(dalam arti kata matematika, yaitu koleksi yang tidak dapat berisi duplikat) untuk menyimpan status yang sudah Anda lihat. Operasi yang harus Anda lakukan untuk ini adalah:

• memasukkan elemen
• menguji apakah elemen sudah ada di sana

Hampir setiap bahasa pemrograman harus sudah memiliki dukungan untuk struktur data yang dapat melakukan kedua operasi ini dalam waktu konstan ( ). Sebagai contoh:$O(1)$

• set dalam Python
• HashSet di Jawa

Pada pandangan pertama, sepertinya menambahkan semua status yang pernah Anda lihat ke perangkat seperti ini akan memakan banyak memori, tapi itu tidak terlalu buruk dibandingkan dengan memori yang sudah Anda butuhkan untuk perbatasan Anda; jika faktor percabangan Anda adalah , batas Anda akan tumbuh sebesar b - 1 elemen per simpul yang Anda kunjungi (hapus 1 simpul dari perbatasan untuk "mengunjungi" itu, tambahkan b penerus / anak baru), sedangkan set Anda hanya akan bertambah 1 tambahan simpul per simpul yang dikunjungi.$b$$b - 1$$1$$b$$1$

Dalam pseudocode, himpunan seperti itu (sebut saja closed_set, agar konsisten dengan pseudocode pada wikipedia dapat digunakan dalam Pencarian Pertama-Luas sebagai berikut:

frontier = First-In-First-Out Queue
frontier.add(initial_state)

closed_set = set()

while frontier not empty:
    current = frontier.remove_next()

    if current == goal_state:
        return something

    for each child in current.generate_children()
        if child not in closed_set:    // This operation should be supported in O(1) time regardless of closed_set's current size
            frontier.add(child)

    closed_set.add(current)    // this should also run in O(1) time

(beberapa variasi pseudocode ini mungkin bekerja juga, dan menjadi lebih atau kurang efisien tergantung pada situasinya; misalnya, Anda juga dapat mengambil closed_setuntuk memuat semua node yang telah Anda tambahkan anak-anak ke perbatasan, dan kemudian sepenuhnya menghindari generate_children()panggilan jika currentsudah ada di closed_set.)

Apa yang saya jelaskan di atas akan menjadi cara standar untuk menangani masalah ini. Secara intuitif, saya menduga "solusi" yang berbeda bisa dengan selalu mengacak urutan daftar negara penggantinya baru sebelum menambahkannya ke perbatasan. Dengan cara ini, Anda tidak terhindar dari masalah sesekali menambahkan status yang sebelumnya sudah Anda kembangkan ke perbatasan, tapi saya pikir itu seharusnya secara signifikan mengurangi risiko terjebak dalam siklus tak terbatas.

Hati-hati : Saya tidak tahu ada analisis formal dari solusi ini yang membuktikan bahwa ia selalu menghindari siklus tak terbatas. Jika saya mencoba "menjalankan" ini di kepala saya, secara intuisi, saya curiga ini seharusnya bekerja, dan tidak memerlukan memori tambahan. Mungkin ada kasus tepi yang saya tidak pikirkan sekarang, jadi itu juga mungkin tidak berfungsi, solusi standar yang dijelaskan di atas akan menjadi taruhan yang lebih aman (dengan biaya lebih banyak memori).

Jawaban Dennis Soemers benar: Anda harus menggunakan HashSet atau struktur serupa untuk melacak keadaan yang dikunjungi di BFS Graph Search.

Namun, itu tidak cukup menjawab pertanyaan Anda. Anda benar, bahwa dalam kasus terburuk, BFS akan meminta Anda untuk menyimpan 16! node. Meskipun waktu penyisipan dan periksa dalam set adalah O (1), Anda masih membutuhkan jumlah memori yang tidak masuk akal.

Untuk memperbaikinya, jangan gunakan BFS . Ini sulit untuk semua kecuali masalah yang paling sederhana, karena membutuhkan waktu dan memori yang eksponensial dalam jarak ke keadaan tujuan terdekat.

Algoritma yang jauh lebih efisien memori adalah pendalaman berulang . Ia memiliki semua sifat yang diinginkan dari BFS, tetapi hanya menggunakan memori O (n), di mana n adalah jumlah gerakan untuk mencapai solusi terdekat. Mungkin masih perlu waktu, tetapi Anda akan mencapai batas memori jauh sebelum batas yang berhubungan dengan CPU.

Lebih baik lagi, kembangkan heuristik khusus domain, dan gunakan pencarian A * . Ini akan mengharuskan Anda untuk memeriksa hanya sejumlah kecil node, dan memungkinkan pencarian untuk menyelesaikan sesuatu yang jauh lebih dekat dengan waktu linier.

Sementara jawaban yang diberikan umumnya benar, BFS dalam 15-puzzle tidak hanya cukup layak, tetapi dilakukan pada tahun 2005! Makalah yang menjelaskan pendekatan dapat ditemukan di sini:

http://www.aaai.org/Papers/AAAI/2005/AAAI05-219.pdf

Beberapa poin kunci:

• Untuk melakukan ini, diperlukan memori eksternal - yaitu BFS menggunakan hard drive untuk penyimpanan, bukan RAM.
• Sebenarnya hanya ada 15 negara / 2, karena ruang negara memiliki dua komponen yang tidak dapat dijangkau.
• Ini berfungsi dalam puzzle ubin geser karena ruang keadaan tumbuh sangat lambat dari level ke level. Ini berarti bahwa total memori yang diperlukan untuk level apa pun jauh lebih kecil daripada ukuran penuh ruang keadaan. (Ini kontras dengan ruang negara seperti Rubik's Cube, di mana ruang negara tumbuh jauh lebih cepat.)
• Karena puzzle ubin geser tidak diarahkan, Anda hanya perlu khawatir tentang duplikat di lapisan saat ini atau sebelumnya. Di ruang terarah Anda dapat membuat duplikat di setiap lapisan pencarian sebelumnya yang membuat segalanya jauh lebih rumit.
• Dalam karya asli oleh Korf (ditautkan di atas) mereka tidak benar-benar menyimpan hasil pencarian - pencarian hanya menghitung berapa banyak negara bagian di setiap level. Jika Anda ingin menyimpan hasil pertama Anda memerlukan sesuatu seperti WMBFS ( http://www.cs.du.edu/~sturtevant/papers/bfs_min_write.pdf )
• Ada tiga pendekatan utama untuk membandingkan status dari lapisan sebelumnya ketika status disimpan pada disk.
  • Yang pertama adalah berbasis penyortiran. Jika Anda mengurutkan dua file penerus, Anda dapat memindai mereka dalam urutan linier untuk menemukan duplikat.
  • Yang kedua berbasis hash. Jika Anda menggunakan fungsi hash untuk mengelompokkan penerus ke dalam file, Anda dapat memuat file yang lebih kecil dari ruang keadaan penuh untuk memeriksa duplikat. (Perhatikan bahwa ada dua fungsi hash di sini - satu untuk mengirim status ke file, dan satu untuk membedakan status dalam file itu.)
  • Yang ketiga adalah deteksi duplikat terstruktur. Ini adalah bentuk deteksi berbasis hash, tetapi dilakukan dengan cara duplikat dapat diperiksa segera ketika mereka dihasilkan alih-alih setelah mereka semua dihasilkan.

Ada banyak lagi yang bisa dikatakan di sini, tetapi makalah di atas memberikan lebih banyak detail.

Ironisnya jawabannya adalah "gunakan sistem apa pun yang Anda inginkan." HashSet adalah ide yang bagus. Namun, ternyata kekhawatiran Anda tentang penggunaan memori tidak berdasar. BFS sangat buruk dalam masalah-masalah seperti ini, sehingga menyelesaikan masalah ini untuk Anda.

Pertimbangkan bahwa BFS Anda mengharuskan Anda menyimpan setumpuk status yang tidak diproses. Ketika Anda maju ke teka-teki, keadaan yang Anda hadapi menjadi semakin berbeda, sehingga Anda cenderung melihat bahwa setiap lapis BFS Anda melipatgandakan jumlah negara untuk dilihat kira-kira 3.

Ini berarti bahwa, ketika Anda memproses lapisan terakhir BFS Anda, Anda harus memiliki setidaknya 16! / 3 status dalam memori. Pendekatan apa pun yang Anda gunakan untuk memastikan kecocokan memori akan mencukupi untuk memastikan daftar yang Anda kunjungi sebelumnya sesuai dengan memori juga.

Seperti yang telah ditunjukkan orang lain, ini bukan algoritma terbaik untuk digunakan. Gunakan algoritma yang lebih cocok untuk masalah ini.

Masalah 15-teka-teki dimainkan pada papan 4x4. Menerapkan ini dalam kode sumber dilakukan secara bertahap. Pada awalnya, mesin gim itu sendiri harus diprogram. Ini memungkinkan untuk memainkan game oleh operator manusia. Gim 15-teka-teki ini hanya memiliki satu elemen gratis dan pada elemen ini tindakannya dijalankan. Mesin permainan menerima empat perintah yang mungkin: kiri, kanan, atas dan bawah. Tindakan lain tidak diperbolehkan, dan dimungkinkan untuk mengontrol permainan hanya dengan instruksi ini.

Lapisan berikutnya untuk bermain game adalah GUI. Ini sangat penting, karena memungkinkan untuk menguji mesin permainan dan mencoba menyelesaikan permainan dengan tangan. Juga, GUI itu penting karena kita perlu mencari tahu heuristik potensial. Dan sekarang kita bisa bicara tentang AI itu sendiri. AI harus mengirim perintah ke mesin game (kiri, kanan, atas dan bawah). Pendekatan naif untuk pemecah akan menjadi algoritma pencarian brute force, yang berarti, bahwa AI mengirimkan perintah acak sampai keadaan tujuan tercapai. Ide yang lebih maju adalah untuk mengimplementasikan semacam database pola yang mengurangi ruang keadaan. Luasnya pencarian pertama tidak secara langsung heuristik, tetapi ini adalah awal. Sama dengan membuat grafik untuk menguji kemungkinan pergerakan dengan cara kronologis.

Melacak status yang ada dapat dilakukan dengan grafik. Setiap negara adalah simpul, memiliki id dan id induk. AI dapat menambah dan menghapus node dalam grafik, dan perencana dapat memecahkan grafik untuk menemukan jalur ke tujuan. Dari perspektif pemrograman, mesin-game dari 15 puzzle adalah objek dan daftar banyak objek adalah daftar susunan. Mereka disimpan dalam kelas grafik. Menyadari hal ini dalam kode sumber agak sulit, biasanya percobaan pertama akan gagal dan proyek akan menghasilkan banyak kesalahan. Untuk mengelola kerumitan, proyek semacam itu biasanya dilakukan dalam proyek akademik, itu artinya, itu adalah topik untuk menulis makalah tentang hal itu yang dapat memiliki 100 halaman dan lebih.

Pendekatan ke Game

Memang benar bahwa dewan memiliki $16!$negara yang memungkinkan. Juga benar bahwa menggunakan hash set adalah apa yang siswa pelajari dalam kursus algoritma tahun pertama untuk menghindari redundansi dan perulangan tanpa akhir ketika mencari grafik yang mungkin mengandung siklus grafik.

Namun, fakta-fakta sepele itu tidak relevan jika tujuannya adalah untuk menyelesaikan teka-teki dalam siklus komputasi paling sedikit. Pencarian pertama yang luas bukanlah cara praktis untuk menyelesaikan puzzle langkah ortogonal. Biaya pencarian pertama yang sangat luas hanya akan diperlukan jika jumlah gerakan sangat penting untuk beberapa alasan.

Keturunan sub-urutan

Sebagian besar simpul yang mewakili negara tidak akan pernah dikunjungi, dan setiap negara yang dikunjungi dapat memiliki antara dua dan empat tepi keluar. Setiap blok memiliki posisi awal dan posisi akhir dan papan simetris. Kebebasan memilih terbesar ada ketika ruang terbuka adalah salah satu dari empat posisi tengah. Paling tidak adalah ketika ruang terbuka adalah salah satu dari empat posisi sudut.

Fungsi disparitas (kesalahan) yang masuk akal adalah jumlah dari semua x disparitas ditambah jumlah dari semua disparitas y dan angka yang secara heuristik mewakili mana dari tiga tingkat kebebasan bergerak yang ada karena penempatan ruang terbuka yang dihasilkan (tengah, tepi , sudut).

Meskipun blok mungkin sementara pindah dari tujuan mereka untuk mendukung strategi menuju penyelesaian yang membutuhkan urutan langkah, jarang ada kasus di mana strategi seperti itu melebihi delapan langkah, menghasilkan, rata-rata, 5.184 permutasi yang dapat dibandingkan dengan kondisi akhir menggunakan fungsi disparitas di atas.

Jika ruang kosong dan posisi blok 1 hingga 15 dikodekan sebagai array dari camilan, hanya operasi penambahan, pengurangan, dan bit-wise yang diperlukan, membuat algoritma lebih cepat. Mengulangi strategi brute force delapan langkah dapat diulangi sampai perbedaan jatuh ke nol.

Ringkasan

Algoritma ini tidak dapat berputar karena selalu ada setidaknya satu permutasi dari delapan gerakan yang mengurangi kesenjangan, terlepas dari keadaan awal, dengan pengecualian dari keadaan awal yang sudah lengkap.