Senin, 18 September 2017

Algoritma untuk tur ksatria dengan Python

Solusi sains dan teknologi -- Saya telah menulis versi terbaru dari kode ini di sini.Silakan lihat.Ini menambahkan visualisasi, kemampuan untuk menyelesaikan tur tertutup dan persyaratan langkah, dan memiliki strategi keluar yang lebih baik.🙂 Di kelas Diskrit, kita telah membicarakan grafik planar dan hal-hal seperti traversal Hamilton.

Solusi sains dan teknologi -- Salah satu latihan di kelas kami melibatkan tur ksatria, dan apakah kami bisa menemukan peraturan yang memungkinkan kami memutuskan apakah tur ksatria dimungkinkan diberikan papan catur dimensi tertentu.Saya memiliki waktu yang sulit untuk memahami grafik, tapi "Knight's Tour" terdengar sangat keren sehingga saya mencarinya di Wikipedia.Masalahnya sebenarnya sangat menarik, jadi saya memutuskan untuk mencoba tangan saya dalam menerapkan algoritma untuk memecahkannya dengan Python.Dari Wikipedia: Tur ksatria adalah urutan gerakan seorang ksatria di papan catur sehingga ksatria itu mengunjungi setiap kotak hanya satu kali.

Solusi sains dan teknologi -- Jika ksatria itu berakhir di lapangan yang merupakan salah satu kesatria dari lapangan awal (sehingga bisa segera menaiki papan lagi, following jalan yang sama), tur ditutup, jika tidak terbuka.The .gif di bawah ini adalah contoh dari tur ksatria apa yang akan terlihat seperti pada papan berukuran 8 × 8.Dalam penulisan implementasi saya sendiri, saya sangat mereferensikan situs ini dan situs ini.Saya akan melakukan panduan saya di bawah ini.

Solusi sains dan teknologi -- Ini sangat masuk akal untuk menggunakan penelusuran mendalam pertama dalam penerapan kami, karena solusi untuk masalah ini cukup jauh dari akar karena ini (solusinya) memiliki pergerakan M * N-1 yang tepat.(Dimana M dan N adalah dimensi papan tulis.) Saya mewakili papan catur sebagai daftar daftar, hanya karena mudah seperti itu.Posisi papan catur diindeks seperti ini: self.board [m] [n] Dimana m adalah lokasi Y dan n adalah lokasi X.Selama setiap langkah tur, algoritma akan menemukan semua pergerakan valid berikutnya, dan secara rekursif menjalankan self.tour () dengan n (count) yang diperbarui, jalur (titik yang dilalui saat ini dari titik awal), dan to_visit (titik berikutnya ke kunjungi) variabel.

Solusi sains dan teknologi -- Panggilan rekursif ini akan berlanjut sampai menyenangkanction mencapai jalan buntu dimana tidak ada pergerakan yang valid yang bisa dilakukan, dalam hal ini akan mundur ke langkah terakhir yang dibuat dan mencoba lagi dengan nilai to_visit yang berbeda.Pengoptimalan dibuat dalam bentuk self.sort_lonely_neighbors (), dengan mengamati peraturan heuristik Warnsdorf.Karya heuristik sebagai berikut: Ksatria akan memilih langkah selanjutnya dengan berpindah ke kotak yang memiliki kemungkinan pergerakan paling sedikit berikutnya.Dengan menyortir node yang akan dikunjungi oleh berapa banyak kemungkinan pergerakan berikutnya, ksatria kita akan selalu melintasi grafik dari ujungnya.

Solusi sains dan teknologi -- Logika semacam ini masuk akal, karena lebih mudah mengunjungi lapangan kosong di tepi papan catur dekat awal tur tanpa terjebak dari kemudian hari.Secara default skrip dimulai pada posisi (0,0) pada papan catur 8 × 8.Namun, bisa dengan mudah dimodifikasi.Ini memecahkan papan catur 31 × 31 dalam waktu kurang dari satu detik, yang sangat saya banggakan.

Solusi sains dan teknologi -- Ketika saya mencoba pergi ke papan catur 50 × 50, saya mengalami kedalaman rekursi melebihi kesalahan ...yang saya takutkanSaya bisa berkeliling dengan melakukan sesuatu yang sedikit lebih rumit daripada program rekursif sederhana.Hmm ...masalah menarik untuk hari lain kurasa.

Solusi sains dan teknologi -- Terkait .

Tidak ada komentar:

Posting Komentar