Nazwa okrągłego problemu odliczania - i rozwiązania algorytmiczne?

Dla nie-Brytyjczyków na widowni jest odcinek teleturnieju w ciągu dnia, w którym zawodnicy mają zestaw 6 liczb i losowo generowaną liczbę docelową. Muszą osiągnąć liczbę docelową przy użyciu dowolnej (ale niekoniecznie wszystkich) z 6 liczb przy użyciu tylko operatorów arytmetycznych. Wszystkie obliczenia muszą dawać dodatnie liczby całkowite.

Przykład: Youtube: Countdown - najbardziej niezwykła gra liczbowa w historii?

Szczegółowy opis znajduje się na Wikipedii: Countdown (Game Show)

Na przykład:

• Contentant wybiera 6 liczb - dwie duże (możliwości obejmują 25, 50, 75, 100) i cztery małe (liczby 1 .. 10, każda zawarta dwukrotnie w puli).
• Liczby są zbierane 75, 50, 2, 3, 8, 7podane są z liczbą docelową 812.
• Jedna próba to (75 + 50 - 8) * 7 - (3 * 2) = 813 (Daje to 7 punktów za rozwiązanie w odległości 5 od celu)
• Dokładna odpowiedź to (50 + 8) * 7 * 2 = 812 (uzyskałoby to 10 punktów dokładnie odpowiadających celowi).

Oczywiście ten problem istniał przed pojawieniem się telewizji, ale artykuł w Wikipedii nie nadaje mu nazwy. Widziałem też tę grę w szkole podstawowej, do której uczęszczałem, gdzie gra nazywała się „Crypto” jako konkurs międzyklasowy - ale wyszukiwanie jej teraz nic nie ujawnia.

Brałem w nim udział kilka razy i mój tata napisał arkusz kalkulacyjny Excel, który próbował brutalnie wymusić problem, nie pamiętam, jak to działało (tylko, że to nie działało, co z limitem wierszy Excela 65535), ale z pewnością musi istnieć algorytmiczne rozwiązanie problemu. Być może istnieje rozwiązanie, które działa tak, jak działa ludzkie poznanie (np. Równolegle, aby znaleźć liczby „wystarczająco blisko”, a następnie przyjmować kandydatów i wykonywać „mniejsze” operacje).

Zastrzeżenie: Ta odpowiedź nie odpowiada na to pytanie całkowicie. Ale to za długo na komentarz.

NP-twardy? Uważam, że ten problem może być trudny do rozwiązania .

Rozważ szczególny przypadek problemu z plecakiem :

Biorąc pod uwagę zbiór dodatnich liczb całkowitych i dodatnich liczb całkowitych b , czy istnieje podzbiór zbioru taki, że suma wszystkich liczb całkowitych w tym podzestawie wynosi b ?

Brzmi to nieco podobnie do naszego problemu z odliczaniem i wydaje się znacznie prostsze. Jednak Plecak (i ​​ten specjalny przypadek Plecaka) jest trudny do NP (i oczywiście do NP).

Nie udało mi się użyć tego jako dowodu, że odliczanie jest trudne. Nie mogłem się pozbyć podziału. Rozważmy, że mamy tysiąc 2 ib = 7. To nigdy nie będzie możliwe do rozwiązania z Knapsack, ale zawsze (?) Z Countdown, przynajmniej na wszystkie sposoby, w jakie próbowałem przenieść problem.

Teraz, jeśli odliczanie naprawdę było trudne NP, moglibyśmy wywnioskować, że z bardzo dużym prawdopodobieństwem nie ma algorytmu, który byłby znacznie bardziej wydajny niż brutalna siła wypróbowująca wszystkie możliwości. (A jeśli znajdziemy taki algorytm, staniemy się bardzo sławni.)

Nie, nie sądzę, nie musi być wydajny algorytm.

Heurystyka. Film na Youtube, do którego link znajduje się w pytaniu, ma ładny przykład: uczestnik znalazł dokładną odpowiedź 952 = ((100 + 6) * 3 * 75 - 50) / 25. To całkowicie wbrew mojej intuicji, nigdy bym tego nie spróbował po raz pierwszy: Wytwórz bardzo dużą liczbę, a następnie podziel ją i uzyskaj wynik.

Z drugiej strony my ludzie czujemy , że nie musimy próbować (przykład arbitralny) 50 * 75 * 100/2/3/7, aby osiągnąć trzycyfrową liczbę. Ale komputery nic nie czują , po prostu obliczają.

W końcu, jeśli zaimplementujemy pewne heurystyki, a ta heurystyka nie znajdzie dokładnego rozwiązania, nadal będziemy musieli wypróbować wszystkie inne rozwiązania, aby upewnić się, że naprawdę ich nie ma.

Myślę, że to, co robi uczestnik wideo na Youtube, to bardzo szybkie sprawdzenie dużej liczby możliwości i szybkie odrzucenie tych, które nie dadzą (lub prawdopodobnie nie dadzą) rozwiązania.

Wniosek. Wdrażając algorytm, można zadbać o usunięcie równych obliczeń, takich jak a / b / c = a / (b * c), ale myślę, że jest to dość trudne i nie wiem, czy to znacząco poprawia czas działania.

Komputery oczywiście szybciej niż ludzie sprawdzają wiele możliwości. W dzisiejszych czasach nawet smartfony są tak szybkie, że mogą rozwiązać ten problem w ciągu sekundy, po prostu wypróbowując wszystkie możliwości. (Nie testowałem tego.) Jest tylko sześć liczb, byłoby inaczej, gdyby było ich np. 60.

Algorytm nie jest tak naprawdę bardzo trudny.

Biorąc pod uwagę dwie liczby aib, możemy uzyskać wyniki a + b, abs (a - b) (nie wiem, czy dopuszczalne są liczby ujemne, w którym to przypadku możemy uzyskać a - b i a + b), a * b i ewentualnie a / b lub b / a, jeśli wynikiem jest liczba całkowita. Możliwe wyniki to zestaw do pięciu liczb. Nazwij ten zestaw S (a, b).

Weź sześć liczb a, b, c, d, e i f.

Dla każdego podzbioru dwóch liczb znajdź liczby, które mogą wytworzyć.

Następnie dla każdego podzbioru trzech liczb znajdź liczby, które mogą wytworzyć: S (a, b, c) = S (S (a, b), c) połączenie S (S (a, c), b) połączenie S ( S (b, c), a).

Następnie to samo dla każdego podzbioru 4 lub 5 liczb, a następnie dla wszystkich 6 liczb.