Untuk pertanyaan Wirth dan rantai

Algoritma + struktur data = program - Virt N.

“Kami memiliki kesempatan luar biasa untuk melakukan latihan taktis kecil tapi sangat instruktif”

Meskipun epigraf pertama untuk posting ini, saya membiarkan diri saya tidak setuju dengan penulis dan mencoba untuk menunjukkan bahwa dalam beberapa kasus pilihan struktur data yang tepat mungkin lebih signifikan daripada pilihan algoritma yang tepat. Untuk mengilustrasikan tesis yang penuh hasutan, mari kita pertimbangkan tugas yang sederhana namun menjanjikan untuk mempelajari game "Chain".

Pertama, tentang aturan permainan - dua pemain bermain, posisi awal terdiri dari N objek yang terletak di dekatnya. Langkah selanjutnya adalah menghapus satu atau dua objek yang berada di dekatnya (Anda dapat mencoba memberikan definisi formal tentang "lokasi terdekat", tetapi dapat dipahami pada tingkat intuitif). Pemain yang menghilangkan objek terakhir menang - permainan langsung, atau orang yang harus (Anda tidak dapat melewati langkah) mengambil objek terakhir - permainan terbalik menang. Karena dalam versi peraturan ini, permainan langsung tidak akan menarik (lebih lanjut tentang itu nanti), pembatasan tambahan diperkenalkan - hanya satu objek yang dapat dihapus pada langkah pertama.

Pertama-tama, kami menentukan bahwa permainan ini terbatas, karena dengan setiap gerakan jumlah objek berkurang secara ketat dan permainan berakhir ketika jumlah objek yang dihitung dengan nol tercapai, oleh karena itu kami memiliki hak untuk mengandalkan keberhasilan dalam mempelajari permainan ini. Selain itu, jelas bahwa permainan tidak dapat bertahan lebih dari N gerakan, mari kita ingat fakta ini.

Studi permainan terdiri dalam menentukan apakah untuk jumlah awal objek tertentu pemain membuat langkah pertama menang (karena ini adalah permainan dengan jumlah nol, jika tidak ia kalah) dengan permainan yang optimal di kedua sisi dan berapa jumlah gerakan minimum yang diperoleh (atau dengan berapa jumlah maksimum gerakan yang hilang hilang).

Untuk beberapa H, jawabannya jelas - dengan satu objek, yang pertama memenangkan permainan langsung dalam satu giliran dan juga kehilangan satu permainan terbalik (P1 = 1, I1 = -1). Dengan dua objek, pemain pertama kalah dalam dua gerakan dalam pertandingan langsung dan menang dalam dua gerakan terbalik (P2 = -2, I2 = 2), yang dapat menimbulkan hipotesis tentang kesederhanaan mengevaluasi permainan ini, yang dikonfirmasi oleh kasus tiga objek (P2 = 3, I3 = -3). Untungnya (kalau tidak, posting ini tidak akan dipublikasikan) permainan dengan empat objek sedikit mengubah gambar (P4 = -4, tapi I4 = -3), jadi meneliti permainan itu benar-benar diperlukan.

Untuk beberapa H dan untuk jenis permainan tertentu, ada algoritma heuristik yang memberikan hasil yang dijamin. Misalnya, untuk permainan langsung dengan inisial H yang aneh, Anda dapat dijamin menang jika Anda menghapus objek sentral dengan gerakan pertama dan kemudian mengulangi gerakan lawan menggunakan tempat sentral sebagai sumbu simetri, maka kami dijamin untuk mengambil objek terakhir dan menang. Strategi yang sama akan bekerja dengan sejumlah objek, jika bukan karena pembatasan pada langkah pertama, yang membuat permainan tidak begitu sepele. Secara umum, penggunaan strategi simetris cukup umum terjadi dalam menghitung game, tetapi bukan obat mujarab, karena, misalnya, dalam permainan invers kami strategi ini gagal. Perlu dicatat bahwa heuristik memberikan algoritma kemenangan tetapi tidak memberikan estimasi posisi yang akurat, karena mungkin ada strategi yang mengarah pada kemenangan yang lebih cepat (ini adalah kasus untuk permainan khusus ini).

Bagaimana kami dapat memberikan penilaian terhadap permainan - persis seperti yang saya terima pada perkiraan sebelumnya untuk 1-4 objek - metode ini disebut pencarian lengkap dari atas ke bawah - kita harus mempertimbangkan pohon lengkap permainan, yaitu, semua kemungkinan pergerakan untuk kedua sisi dan mengevaluasi setiap posisi, termasuk sumber, sesuai aturan tertentu. Perlu dicatat bahwa keberadaan heuristik yang sukses tidak menjamin kami penilaian yang akurat, karena hanya menjawab setengah dari pertanyaan pertama - siapa yang menang, tetapi tidak memberikan jumlah minimum yang diperlukan.

Ini berarti bahwa kita harus membangun pohon permainan yang lengkap, tetapi sebelum melanjutkan konstruksi, kita harus membuat model objek yang sedang dipelajari, dalam kasus kita, permainan.

Mengapa saya fokus pada tahap ini - karena kita tidak dapat menjelajahi objek dalam perwujudan materialnya. Tidak, murni secara teori ini mungkin ("sedikit yang mungkin di dunia secara umum murni secara teoritis") dan saya dapat membayangkan gambar di mana sejumlah besar robot memainkan banyak game di dunia nyata, tetapi biaya material untuk solusi untuk masalah mengevaluasi permainan melebihi kuantitas, jadi kami terpaksa memulai jalur pemodelan objek nyata dengan rekan perangkat lunak mereka. Dan di sini sangat penting untuk mengikuti garis yang halus, menggabungkan tingkat kecukupan model yang memadai dan penyederhanaan yang diperlukan.

Tapi pertama-tama, sedikit matematika untuk menilai kompleksitas tugas - kita perlu memilah-milah semua gerakan yang mungkin dalam permainan (perhatian tidak semua posisi mungkin, ini adalah topik dari metode lain, yaitu bergerak) dan kami ingin mengevaluasi jumlah sumber daya yang diperlukan sebelum memulai pekerjaan - untuk menentukan urutan tugas. Pada langkah pertama, kami memiliki kesempatan untuk mengeluarkan chip apa pun (saya akan terus memanggil objek) dari H yang tersedia, pada langkah berikutnya - salah satu dari chip H-1 atau dua chip yang tersisa di dekatnya (tidak akan ada lebih dari pasangan seperti itu daripada H-2), yang memberikan jumlah total opsi Hx (H-1 + H-2). Sangat mudah untuk melihat bahwa setelah langkah ketiga kita memiliki Hx (H-1 + H-2) x (H-2 + H-3 + Δ) dan seterusnya.

Jika kita membatasi diri kita di setiap braket hanya syarat pertama penjumlahan, maka kita mendapatkan perkiraan jumlah gerakan sebagai H !, yang memberi kita perkiraan dalam kuadratur H ^ H.

Ini adalah hasil yang sangat tidak menyenangkan, yang mengklaim bahwa kita akan memiliki masalah yang sangat besar dengan H yang signifikan, sehingga kemungkinan besar pemodelan "langsung" akan memerlukan biaya komputasi yang signifikan. Sebagai contoh, untuk 16 chip di posisi awal, kita perlu mempertimbangkan kira-kira 16! = 1013 gerakan, dan jika satu gerakan adalah 10E-9 detik (perkiraan cukup optimis), maka total waktu akan menjadi sekitar 10E4 detik atau hampir 3 jam, yang agak banyak , tetapi dapat diterima, tetapi hanya untuk 20 chip, waktu perhitungan yang diharapkan adalah 77 tahun, yang jelas tidak dapat diterima. Faktorial tumbuh sangat cepat dan tidak ada yang bisa dilakukan untuk itu.

Kami menarik perhatian pada fakta bahwa jumlah gerakan secara signifikan melebihi jumlah posisi yang mungkin, yaitu hanya 2 ^ N, dan jelas bahwa kami akan jatuh ke posisi terpisah untuk 16 chip 10E (13-5) = 10E7 kali, yang merupakan kejadian sehari-hari yang cukup untuk mencari tugas. Ingat fakta ini, itu akan berguna bagi kita nanti.

Namun demikian, kami akan mulai menulis sebuah program, untuk itu kami akan menentukan modelnya. Pertama, kita beri nomor chip dari 1 hingga H, kemudian buat sebuah array dengan jumlah elemen H, dan tentukan bahwa angka 1 dalam elemen array dengan indeks n berarti keberadaan nomor chip n, dan angka 0 - tidak adanya pada posisi tertentu. Model seperti itu memadai, sederhana, intuitif, dan memungkinkan Anda untuk membuat operasi penghilangan chip efektif, serta menentukan kondisi "kedekatan".

Sekarang kita memiliki model (struktur data), kita dapat mulai menarik (burung hantu di dunia) algoritma pada model ini. Algoritma enumerasi lengkap dengan pengembalian sederhana dalam diagram blok dan terdiri dari dua bagian independen - enumerasi aktual dan evaluasi posisi, untuk permulaan kita akan mengimplementasikan bagian pertama. Perhatikan bahwa algoritma ini tidak terbaik diimplementasikan dalam kerangka paradigma pemrograman struktural dan akan lebih efektif jika kita membiarkan diri kita menggunakan transisi atau mengulangi kode, tetapi bahkan tanpa penyimpangan dari gaya, implementasi sama sekali tidak megah (kompleksitas siklomatik cukup dapat diterima) . Karena kami belum memperkenalkan penilaian, dan kami ingin mendapatkan hasil dari program, kami hanya mengambil posisi yang dipertimbangkan dan melihat melalui mereka dengan mata kami untuk mengevaluasi implementasi yang benar dan memastikan bahwa hasilnya sesuai dengan yang diharapkan.

Sekarang mari kita tambahkan perkiraan posisi - tentu saja, kode yang ditulis dengan baik mendokumentasikan diri sendiri (walaupun ada pendapat berbeda tentang pernyataan ini), tetapi bagian ini paling baik dijelaskan dengan kata-kata. Idenya adalah bahwa kami memberikan penilaian yang jelas tentang posisi akhir (dalam kasus kami unik dan terdiri dari nol chip), berdasarkan aturan permainan, dan untuk semua posisi lain kami memberikan penilaian netral awal, dan kemudian kami mulai memperbaikinya dengan menggerakkan perkiraan naik pohon . Ketika bergerak mundur, perkiraan posisi saat ini berubah satu arah dari nol, kemudian terbalik dan dipindahkan ke posisi sebelumnya, di mana ia dikombinasikan dengan perkiraan sebelumnya sesuai dengan aturan berikut:

1. penilaian penilaian netral berubah menjadi yang baru,
2. peringkat positif berubah menjadi positif lebih kecil,
3. penilaian negatif berubah menjadi negatif besar atau positif.

Setelah kami benar-benar melewati semua gerakan, penilaian posisi awal adalah final.

Kami menambahkan perkiraan pada prosedur kami untuk menghasilkan semua posisi dan kami dapat mengagumi hasil analisis, yang ditampilkan dalam tabel, menambahkan penghitung kemajuan dan pengukur waktu untuk analisis. Pada kompiler gcc (dalam mode optimasi -O2) pada mesin dengan prosesor, saya mendapatkan tabel yang sepenuhnya mengkonfirmasi asumsi awal kami tentang urutan faktorial dari kompleksitas tugas. Dari tabel yang sama, kita melihat bahwa saya berhenti mengharapkan hasil dengan H melebihi 11, karena waktu perhitungan menjadi tidak dapat diterima (bagi saya, mungkin Anda siap menunggu setengah jam) dan asumsi kami tentang kursus dan nanodetik tidak sesuai dengan kenyataan (waktu rata-rata) pertimbangan posisi adalah 100 nsec). Muncul pertanyaan - apa yang harus kita lakukan jika kita ingin memiliki perkiraan untuk lebih dari 11 chip di posisi awal.

Kita dapat mengambil jalur optimasi kecil, bermain dengan transisi dan bendera, masuk ke insert assembler, menerapkan operasi vektor yang rumit dari sistem instruksi prosesor kami, dan dengan cara ini Anda dapat menang dalam kecepatan secara tidak ambigu pada suatu waktu, dengan urutan besar - mungkin dua urutan besarnya - ini sangat tidak mungkin, tetapi kita perlu mendapatkan banyak pesanan besar, karena pesanan (dan bahkan lebih) kita akan makan kenaikan H satu per sepuluh. Ngomong-ngomong, jika Anda mengaktifkan optimisasi kompiler, itu akan melakukan sesuatu untuk kami dan waktu eksekusi akan berkurang Saya memiliki 4 kali - tidak buruk sama sekali dan sesuai dengan harapan kita.

Oleh karena itu, pertama-tama kita harus mencoba meningkatkan algoritma yang diterapkan, dan yang pertama dari peningkatan ini (dan yang utama) adalah metode cut-off brute force atau "prosedur alpha-beta". Gagasan utamanya terlihat cukup kuat dan terdiri dari kenyataan bahwa jika kita memberi peringkat pada posisi tertentu sebagai yang menang, kita berhenti meningkatkan peringkat untuk yang ini dan kembali ke pohon. Pendekatan ini dapat sangat meningkatkan kecepatan algoritma, terutama jika kita menyelidiki langkah-langkah sukses (mengarah ke kemenangan). Tetapi ini juga dapat menambah waktu, karena verifikasi penilaian saat ini ditambahkan dan prosedur untuk memilih mata pelajaran ini rumit, sangat sulit untuk memperkirakan pengaruh metode ini sebelumnya, maka perlu untuk melakukan percobaan. Dan satu pertimbangan lagi - kita tidak boleh lupa bahwa dalam kasus pencarian dengan cut-off, dalam kasus posisi menang, kami memberikan perkiraan yang benar, tetapi tidak akurat, karena kami tidak mempertimbangkan bagian dari opsi, dan mereka dapat memberikan kemenangan dalam lebih sedikit gerakan. Jika penurunan akurasi seperti itu cocok untuk kita, maka mengapa tidak menggunakan metode ini, tetapi untuk penilaian yang akurat, tidak ada yang lain selain pencarian lengkap tidak bekerja.

Hasil pencacahan kliping ditunjukkan pada tabel berikut, dan kami melihat bahwa ada peningkatan kinerja, dan peningkatan yang signifikan, tetapi tidak cukup untuk mempelajari nilai-nilai besar N. Di mana arah kami akan melanjutkan penelitian kami - pertama kita akan melihat struktur data lain, baik, dan kemudian, Anda dapat menebaknya (senang berurusan dengan audiens yang licik) adalah algoritma lain.

Mari kita perhatikan fakta bahwa struktur data yang diadopsi oleh kami membuat chip unik dan, misalnya, satu chip (tidak memiliki berdekatan) di posisi tidak setara dengan chip tunggal di posisi n + 2, yang sepenuhnya salah. Kami memilih elemen kunci dari posisi permainan - kelompok chip yang terletak di sebelahnya dan menentukan karakteristik utamanya - jumlah chip dalam grup. Informasi inilah yang secara unik menentukan posisi apa pun dalam permainan, dan kami harus menyajikannya dalam bentuk yang nyaman untuk pemrograman. Kami memilih struktur data yang paling sederhana dan paling jelas - kami memulai larik elemen H dan menyimpan dalam elemen n larik jumlah grup dengan tepat n chip di dalamnya. Lalu, misalnya. Untuk posisi awal dengan 3 chip, kita akan memiliki representasi {0,0,1}. Prosedur pelaksanaan untuk presentasi yang diberikan masih sederhana dan efektif, meskipun, tentu saja, lebih rumit daripada di versi pertama. Setelah langkah pertama (yang ada dua bukannya tiga) kita mendapatkan posisi {0,1,0} dan {2,0,0}.

Mari kita coba memperkirakan keuntungan yang diharapkan dalam jumlah gerakan untuk struktur data yang diberikan. Untuk langkah pertama, kami memiliki (H-1) / 2 + 1 opsi, untuk yang kedua (kami membagi grup H menjadi m dan N-m-1) (m-1) / 2 + (N-m-1-1) / 2 (ambil 1 chip) + (m-2) / 2 + (N-m-1-2) / 2 (ambil 2 chip) = (H-3) / 2 + (H-5) / 2 dan dengan analogi , kami menyimpulkan bahwa pada setiap langkah kami menyimpan setidaknya setengah dari langkah. Maka keuntungan kita harus minimal 2 ^ H, yang sangat, sangat bagus untuk H. besar Faktanya, gain akan lebih besar, misalnya, untuk posisi {8,0 ...} dalam perwujudan pertama, Anda perlu memilah 8 gerakan, dan pada yang kedua hanya 1 dan keuntungan dalam kasus ini akan menjadi 8 kali. Jadi kita bisa mengandalkan 2 ^ H, tapi berharap lebih, yang akan kita periksa. Dan yang pasti, untuk program yang sesuai dengan representasi ini, kita mendapatkan Tabel 4, baris terakhir menunjukkan kenaikan kinerja ketika beralih ke versi kedua dari struktur data (dihitung dengan tangan). Pertumbuhan ini hanya kolosal dan kami dengan penuh percaya diri (mencapai bagian bawah) menerobos langit-langit kemungkinan analisis hingga 20 chip di posisi awal dengan biaya waktu yang wajar.

Lebih lanjut, kita dapat terlibat dalam optimasi algoritma yang halus untuk struktur data yang diberikan dan bahkan mendapatkan keuntungan dalam kinerja, tetapi kita tidak akan mendapatkan pertumbuhan dramatis (berdasarkan pesanan), yang sekali lagi menunjukkan bahwa Wirth salah. Misalnya, dalam program di atas, prosedur untuk membuat kandidat berikutnya untuk langkah itu sengaja tidak optimal dan koreksi yang jelas (mari kita serahkan kepada pembaca yang ingin tahu) akan meningkatkan kecepatan sebanyak 3 kali, tetapi ini adalah hal yang sepele, meskipun yang menyenangkan.

Mari kita perhatikan hasilnya dan melihat beberapa hal yang tidak jelas. Sebagai contoh, program ini mengklaim bahwa kemenangan dijamin dalam permainan langsung untuk 9 chip dicapai tidak dalam 9 gerakan sama sekali, sebagai berikut dari algoritma simetris heuristik, tetapi hanya dalam 7, dan langkah pertama bertepatan dengan heuristik (dan, apalagi, adalah satu-satunya posisi menang ), tetapi yang ketiga dan selanjutnya tidak boleh mengulangi gerakan lawan sama sekali, sebagai berikut dari algoritma naif, dan kuncinya di sini adalah {1,0,0,1}, yang memiliki peringkat +4. Sekarang kita telah memberikan penilaian yang akurat dari permainan, kita dapat mengajukan pertanyaan menarik mengenai keberadaan posisi dengan penilaian yang stabil (di mana kita dapat membiarkan lawan pergi untuk diri kita sendiri), keberadaan posisi kunci di pohon penghitungan, menemukan posisi dengan satu-satunya langkah yang tepat, dan seterusnya (dan bahkan mendapatkan jawaban untuk pertanyaan-pertanyaan ini, dan yang tepat).

Berikut adalah tabel nilai ringkasan

Keripik	Langsung	Umpan balik	Posisi / Waktu	Posisi / Waktu
1	1	-1	1/0	1/0
2	-2	2	4/0	2/0
3	3	-3	17/0	7/0
4	-4	-3	82/0	20/0
5	5	4	463/0	71/0
6	5	-5	3032/0	263/0
7	7	6	22693/0	1107/0
8	-8	-7	191422/0	4945/0
9	7	-7	1798427 / 0,1	24.283 / 0
10	9	8	18634228 / 0.8	125419/0
11	11	-9	211177537 / 10.4	699165 / 0,1
12	-10	-9	*** / 127	4057686 / 0.6
13	11	10		25056975 / 3.84
14	-12	-11		160643971/28
15	13	12		1082854607/213
16	-14	-13		*** / 1698

Namun demikian, kami melihat bahwa perkiraan waktu operasi tetap faktorial, meskipun dengan penurunan yang signifikan dalam tingkat pertumbuhan. Mari kita cari cara lain untuk menjelajahi pohon permainan.

Kami telah menyempurnakan algoritme top-down (yah, tentu saja, kami tidak menyelesaikannya dalam bentuk jelek yang saya sketsa di belakang amplop, Anda dapat secara signifikan meningkatkan kinerja dengan menulis ulang prosedur dasar dengan hati-hati, dan ini pasti akan dilakukan, tetapi masalahnya bukan pada dasarnya, memutuskan), jadi mari kita pergi ke arah lain - dari bawah ke atas. Ide metode ini secara intuitif sederhana dan dapat dimengerti, tetapi sangat sulit untuk digunakan manusia - kita mulai dari posisi akhir, yang diperkirakan sesuai dengan aturan permainan, dan mulai mentransfer estimasi naik pohon sesuai dengan aturan yang sama seperti untuk pencarian top-down. Tentu saja, pada saat yang sama kami mempertimbangkan untuk tidak mungkin bergerak turun dari posisi saat ini, tetapi kami sedang mempertimbangkan semua posisi dari mana kami bisa masuk ke posisi saat ini dalam satu gerakan. Kami mentransfer estimasi sesuai dengan aturan di atas. Selanjutnya, kami menerapkan prosedur ini secara iteratif dan ketika berhenti menghasilkan hasil, yaitu, di babak berikutnya, tidak ada satu posisi pun yang mengubah penilaian, tugas diselesaikan dan penilaian posisi awal benar dan akurat. Pendekatan ini memungkinkan Anda untuk sangat mengurangi waktu pencarian, terutama jika Anda melakukan beberapa perbaikan, tetapi memiliki kelemahan yang kuat (dan ini klasik - kami mengubah waktu untuk memori), secara signifikan membatasi ruang lingkupnya - persyaratan memori yang tinggi, karena kami harus menyimpan perkiraan , ( ).Dalam kasus permainan yang dimaksud, metode representasi bit untuk struktur data pertama menunjukkan dirinya, ada metode lain yang dapat mengurangi jumlah memori yang diperlukan (menyimpan hanya tiga level pohon yang dipertimbangkan dengan pengecualian lapisan bawah), tetapi, tentu saja, dengan menurunkan kinerja, karena pencarian menjadi sangat tidak sepele. Namun demikian, untuk H tidak lebih besar dari 20, jumlah total posisi tidak akan lebih dari 2 ^ 20, dan array ukuran ini dalam memori untuk elemen yang mengandung angka dari -20 hingga 20, yaitu, angka 8-bit, saya cukup bisa membayangkan dan implementasinya tidak akan sulit. Jadi sangat mungkin untuk menulis sebuah program untuk algoritma semacam itu dan mengevaluasi kinerja yang dihasilkan, tetapi jangan terburu-buru dan membuat perkiraan. Memori seperti apa yang harus kita alokasikan tidak sulit untuk ditentukan, tetapi dengan parameter sementara itu agak lebih rumit.Misalkan kita segera membuat semua posisi yang mungkin, mereka akan menjadi M, maka jumlah rata-rata bergerak dari satu posisi dapat diperkirakan tidak lebih dari 2 * N (perkiraan yang sangat kasar). Kemudian, pada setiap iterasi, kita perlu melakukan tidak lebih dari transfer estimasi M * 2 * H, dan karena dalam setiap siklus kita akan meningkatkan estimasi setidaknya satu posisi, total waktu kerja akan menjadi urutan M * 2 * H * M.

Kemudian, untuk cara pertama mempresentasikan data, kami memperoleh 2 ^ H * M * 2 ^ H = 2 ^ (2 * H) * M (kami menekankan sekali lagi bahwa perkiraan ini sangat kuat dari atas) dan, misalnya, untuk H = 20, perkiraan waktu pencarian dari atas -down akan menjadi 20! ~ 10E18, dan untuk pencarian bottom-up kami memiliki 2 ^ 40 * 20 = (2 ^ 10) ^ 4 * 40 = (10 ^ 3) ^ 4 * 40 ~ 10 ^ 14, yaitu, untuk 20 chip kami menang dalam waktu setidaknya 10E6 kali, yang sangat bagus. Kami juga akan menghitung 9 chip awal, mendapatkan 9! ~ 10E6 untuk pencarian teratas, dan 2 ^ 9 * 2 ^ 9 * 18 ~ 10E6 untuk penyaringan bottom-up, yaitu, mulai dari nomor ini, pencarian bottom-line menang. Pernyataan terakhir agak tergesa-gesa, karena prosedur untuk mengevaluasi posisi selanjutnya menjadi jauh lebih lama - kita harus mencarinya di antara yang sudah dibuat, tetapi untuk representasi khusus ini dalam bentuk bitmap, prosedur ini dilakukan di O (1).

Untuk presentasi kedua, perlu untuk mengevaluasi jumlah posisi yang berbeda, yang merupakan tugas dari bidang kombinatorik. Sebagai contoh, perhatikan gim dengan 9 chip awal, yang jumlah posisinya berbeda: 1+ (1 + 4) + (1 + 3 + 2) + (1 + 3 + 3 + 2) + (1 + 2 + 2 + 1 + 1) + (1 + 2 + 1 + 1) + (1 + 1 + 1) + (1 + 1) + 1 = 1 + 5 + 6 + 9 + 7 + 5 + 3 + 2 + 1 = 39.
Maka estimasi dengan metode yang sama akan mengarah pada nilai H * M * M = 39 * 39 * 9 ~ 10E4, yang merupakan dua urutan besarnya lebih baik dalam kecepatan dibandingkan dengan representasi pertama, dan saat H meningkat, gain hanya akan meningkat. Dibandingkan pergi ke atas untuk tampilan kedua, Anda juga harus mengharapkan peningkatan kinerja yang signifikan, tetapi lebih sulit untuk dievaluasi, sehingga lebih mudah untuk dicoba.

Oleh karena itu, jika Anda melakukan parsing program dari bawah ke atas, maka untuk presentasi kedua. Saya tidak akan memberikan programnya, saya harus meninggalkan sesuatu bagi pembaca untuk melakukan analisis di rumah. Kita harus mendapatkan hasil untuk H signifikan dalam waktu yang sangat wajar. Keuntungan lain dari penghilangan dari bawah adalah bahwa kita dapat berhemat secara signifikan dengan memperbaiki estimasi untuk bagian bawah dari posisi (yang memiliki jumlah chip lebih kecil dari N / 2), karena begitu bagian bawah yang diperkirakan diangkut tanpa perubahan untuk jumlah chip berikutnya, yang akan memberi kita kemenangan tambahan dalam 2 kali.

— , , . , , ( ) .

Kesimpulannya, penjelasan yang diperlukan bagi mereka yang menganggap posting saya terlalu serius dan terbakar dengan kemarahan (adil) - Saya benar-benar tidak yakin bahwa menentukan algoritme sebagai istilah pertama dalam rumus definisi program menegaskan pentingnya mereka yang lebih besar, saya sepenuhnya setuju bahwa dalam beberapa situasi tertentu, algoritma yang dipilih dengan benar dapat memberikan peningkatan produktivitas yang teratur, dan saya tidak akan memberatkan Dijkstra (yang saya hormati dengan hormat) karena kesalahan. Itu semua adalah ungkapan untuk menarik perhatian, dan posting adalah tentang sesuatu yang lain - bahwa struktur data juga sangat penting dalam hal kinerja dan saya ingin tidak dilupakan tentang hal ini dalam proses desain.

PS.Mereka memberi tahu saya di sini dari hadirin (hai, Max) bahwa ada metode lain untuk meneliti permainan - matematis, dan, mengingat hipotesis nama ganda bahwa sebagian besar permainan menghitung turun ke permainan Nim, jadi kita hanya perlu menghitungnya-jumlah posisi awal (menurut saya, pernyataannya meragukan), dan Anda juga dapat mengonversi game asli ke game pada grafik (tidak ada keberatan), yang untuknya Anda dapat memperkirakan perkiraan 1,878 ^ N pada saat bekerja (meskipun angka spesifiknya agak membingungkan saya). Mungkin, pertimbangan-pertimbangan ini memiliki hak untuk hidup, setidaknya artikel-artikel dari konten ini terlihat meyakinkan, tetapi saya adalah seorang praktisi murni dan meninggalkan opsi-opsi ini lagi untuk pembaca yang ingin tahu (ars longa, vita brevis).