Nama masalah bulat Countdown Numbers - dan solusi algoritmik?

Untuk yang non-Inggris di antara hadirin, ada segmen acara permainan siang hari di mana para kontestan memiliki 6 angka dan angka target yang dibuat secara acak. Mereka harus mencapai nomor target menggunakan salah satu (tetapi tidak harus semua) dari 6 angka hanya menggunakan operator aritmatika. Semua perhitungan harus menghasilkan bilangan bulat positif.

Contoh: Youtube: Countdown - Game Angka Paling Luar Biasa Yang Pernah Ada?

Deskripsi terperinci diberikan di Wikipedia: Countdown (Game Show)

Sebagai contoh:

• Para kontestan memilih 6 angka - dua besar (kemungkinan termasuk 25, 50, 75, 100) dan empat kecil (nomor 1 .. 10, masing-masing termasuk dua kali dalam kelompok).
• Angka-angka memilih yang 75, 50, 2, 3, 8, 7diberikan dengan target jumlah 812.
• Satu upaya adalah (75 + 50 - 8) * 7 - (3 * 2) = 813 (Skor ini 7 poin untuk solusi dalam 5 target)
• Jawaban yang tepat adalah (50 + 8) * 7 * 2 = 812 (Ini akan mencetak 10 poin tepat sesuai dengan target).

Jelas masalah ini sudah ada sebelum munculnya TV, tetapi artikel Wikipedia tidak memberikan nama. Saya juga melihat permainan ini di sekolah dasar yang saya hadiri di mana permainan itu disebut "Crypto" sebagai kompetisi antar kelas - tetapi mencarinya sekarang tidak mengungkapkan apa-apa.

Saya mengambil bagian di dalamnya beberapa kali dan ayah saya menulis lembar bentang Excel yang berusaha memaksa masalah, saya tidak ingat bagaimana cara kerjanya (hanya saja itu tidak berhasil, apa dengan batas baris 65535 Excel), tetapi tentunya harus ada solusi algoritmik untuk masalah ini. Mungkin ada solusi yang berfungsi seperti halnya kognisi manusia (mis. Sejajar untuk menemukan angka 'cukup dekat', kemudian mengambil kandidat dan melakukan operasi 'lebih kecil').

Penafian: Jawaban ini tidak menjawab pertanyaan yang sepenuhnya. Tapi terlalu lama untuk berkomentar.

NP-keras? Saya percaya, masalah ini bisa jadi NP-hard .

Pertimbangkan kasus khusus masalah Knapsack :

Diberikan himpunan bilangan bulat positif dan bilangan bulat positif b , apakah ada himpunan himpunan sedemikian sehingga jumlah semua bilangan bulat dalam himpunan bagian itu sama dengan b ?

Ini terdengar agak mirip dengan masalah Countdown kami, dan tampaknya jauh lebih sederhana. Namun, Knapsack (dan case khusus Knapsack ini) NP-hard (dan NP-complete, tentu saja).

Saya tidak berhasil menggunakan ini untuk bukti bahwa Countdown adalah NP-hard. Saya tidak bisa menyingkirkan divisi itu. Anggap kita memiliki seribu 2, dan b = 7. Ini tidak akan pernah bisa dipecahkan dengan Knapsack, tetapi selalu (?) Dengan Countdown, setidaknya dalam semua cara saya mencoba untuk mentransfer masalah.

Sekarang, jika Countdown benar - benar NP-keras, kita dapat menyimpulkan bahwa di sana dengan probabilitas yang sangat tinggi tidak ada algoritma yang secara signifikan lebih efisien daripada brute-force mencoba semua kemungkinan. (Dan jika kita harus menemukan algoritma seperti itu, kita akan menjadi sangat terkenal.)

Tidak, saya tidak berpikir harus ada algoritma yang efisien.

Heuristik. Video Youtube yang ditautkan dalam pertanyaan memiliki contoh yang bagus: Kontestan menemukan jawaban yang tepat 952 = ((100 + 6) * 3 * 75 - 50) / 25. Itu sepenuhnya bertentangan dengan intuisi saya, saya tidak akan pernah mencobanya cara pertama kali: Menghasilkan angka yang sangat besar, kemudian membaginya dan menghasilkan hasilnya.

Di sisi lain, kita manusia merasa bahwa kita tidak perlu mencoba (contoh sewenang-wenang) 50 * 75 * 100/2/3/7 untuk mencapai angka tiga digit. Tetapi komputer tidak merasakan apa - apa, mereka menghitung sederhana.

Lagi pula, jika kita menerapkan beberapa heuristik, dan heuristik ini tidak menemukan solusi yang tepat, kita masih harus mencoba semua solusi lain untuk memastikan tidak ada.

Apa yang dilakukan kontestan dalam video Youtube adalah, saya pikir, dengan sangat cepat memeriksa sejumlah besar kemungkinan dan dengan cepat membuang yang tidak akan (atau kemungkinan tidak akan) memberikan solusi.

Kesimpulan. Ketika menerapkan suatu algoritma, orang dapat berhati-hati untuk menghapus perhitungan yang sama seperti a / b / c = a / (b * c), tapi saya pikir ini cukup sulit untuk dilakukan dan saya tidak tahu apakah ini meningkatkan runtime secara signifikan.

Komputer tentu saja lebih cepat daripada manusia dalam memeriksa sejumlah besar kemungkinan. Dan saat ini, bahkan smartphone sangat cepat sehingga mereka dapat menyelesaikan masalah ini, saya pikir, dalam sedetik dengan hanya mencoba semua kemungkinan. (Saya tidak menguji ini.) Hanya ada enam angka, akan berbeda jika ada misalnya 60 dari mereka.

Algoritma sebenarnya tidak terlalu sulit.

Diberi dua angka a dan b, kita dapat menghasilkan hasil a + b, abs (a - b) (Saya tidak tahu apakah angka negatif diperbolehkan, dalam hal ini kita dapat menghasilkan a - b dan a + b), sebuah * b, dan mungkin a / b atau b / a jika hasilnya bilangan bulat. Jadi hasil yang mungkin adalah satu set hingga lima angka. Sebut set ini S (a, b).

Ambil enam angka a, b, c, d, e dan f.

Untuk setiap subset dari dua angka, temukan angka yang dapat mereka hasilkan.

Kemudian untuk setiap subset dari tiga angka, temukan angka yang dapat mereka hasilkan: S (a, b, c) = S (S (a, b), c) union S (S (a, c), b) union S ( S (b, c), a).

Kemudian sama untuk setiap subset dari 4 atau 5 angka, lalu untuk semua 6 angka.