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

10

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).

Dai
źródło
1
Rozwiązałem to graficznie - użyj węzłów do przedstawienia wyników obliczeń i krawędzi do przedstawienia operacji, które można wykonać na tych liczbach, a następnie użyj algorytmu wyszukiwania wykresu, aby znaleźć żądaną ścieżkę
ell
1
Z lektury reguł wydaje się, że nie można osiągnąć idealnego rozwiązania - na przykład, jeśli wybranymi liczbami są (1, 1, 2, 2, 3, 3), a liczba docelowa to 999. Tak więc naprawdę celem dla dowolnego algorytmu byłoby znalezienie najbliższego możliwego rozwiązania.
Rich Smith
1
@ell: Czy Twoje rozwiązanie do wyszukiwania wykresów to po prostu wyszukiwanie z użyciem siły?
Martin
Właśnie użyłem głębokiego pierwszego wyszukiwania w mojej implementacji, ale nie rozumiem, dlaczego nie można użyć czegoś takiego jak Dijkstra.
ell
1
Mamy podobne programy w Stanach Zjednoczonych: przez kilka tygodni trzymamy w domu około 6 niedoświadczonych idiotów w domu i filmujemy ich rozmawiających o sobie i krzyczących na siebie. To prawie tak blisko, jak nasza telewizja osiąga coś tak intelektualnego w popularnych programach.
RBarryYoung

Odpowiedzi:

4

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.

Jaskółka oknówka
źródło
Rozwiązanie tego przykładu, choć niezwykle imponujące, nie jest tak skomplikowane, jak mogłoby się początkowo wydawać. Jego proces myślowy, pomijając bardziej oczywiste rzeczy, które mógł wypróbować, prawdopodobnie brzmiał: „Mogę dostać się do 954 za pomocą (100 + 6) * 9, co mogę zrobić przez (100 + 6) * 3 * 75/25. Zostało mi 50, a 50/25 to dwa, więc mogę zdjąć 50 (100 + 6) * 3 * 75 przed podzieleniem przez 25 ".
Tim Down
1

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.

gnasher729
źródło