Nome del problema round Countdown Numbers - e soluzioni algoritmiche?

Naviga le tue risposte
9

Per i non britannici del pubblico, c'è un segmento di uno spettacolo di gioco diurno in cui i concorrenti hanno un set di 6 numeri e un numero di destinazione generato casualmente. Devono raggiungere il numero di destinazione usando qualsiasi (ma non necessariamente tutto) dei 6 numeri usando solo operatori aritmetici. Tutti i calcoli devono risultare in numeri interi positivi.

Un esempio: Youtube: Countdown - Il gioco di numeri più straordinari di sempre?

Una descrizione dettagliata è fornita su Wikipedia: Countdown (Game Show)

Ad esempio:

  • Il contentante seleziona 6 numeri - due grandi (le possibilità includono 25, 50, 75, 100) e quattro piccoli (numeri 1 .. 10, ciascuno incluso due volte nel pool).
  • I numeri selezionati sono 75 , 50 , 2 , 3 , 8 , 7 sono indicati con un numero di destinazione di 812 .
  • Un tentativo è (75 + 50 - 8) * 7 - (3 * 2) = 813 (questo segna 7 punti per una soluzione entro 5 del bersaglio)
  • Una risposta esatta sarebbe (50 + 8) * 7 * 2 = 812 (Questo avrebbe segnato 10 punti esattamente corrispondenti al bersaglio).

Ovviamente questo problema è esistito prima dell'avvento della TV, ma l'articolo di Wikipedia non gli dà un nome. Ho anche visto questo gioco in una scuola elementare a cui ho partecipato quando il gioco si chiamava "Crypto" come competizione tra le classi - ma la ricerca ora non rivela nulla.

Ne ho preso parte un paio di volte e mio padre ha scritto un foglio di calcolo Excel che ha tentato di forzare il problema, non ricordo come funzionasse (solo che non ha funzionato , cosa con limite di riga 65535 di Excel), ma sicuramente ci deve essere una soluzione algoritmica per il problema. Forse esiste una soluzione che funziona come la cognizione umana (ad esempio in parallelo per trovare i numeri "abbastanza vicini", quindi prendere candidati e eseguire operazioni "minori").

    
posta Dai 09.10.2013 - 22:07
fonte

2 risposte

2

Disclaimer: questa risposta non risponde alla domanda completamente. Ma è troppo lungo per un commento.

NP-hard? Credo che questo problema potrebbe essere NP-hard .

Considera un caso speciale del Problema dello zaino :

Given a set of positive integers and a positive integer b, does there exist a subset of the set such that the sum of all integers in that subset equals b?

Questo suona in qualche modo simile al nostro problema di Countdown, e sembra essere molto più semplice. Tuttavia, lo Zaino (e questo caso speciale di Zaino) è NP-difficile (e NP-completo, ovviamente).

Non sono riuscito a usarlo per dimostrare che Countdown è NP-hard. Non potevo liberarmi della divisione. Consideriamo che abbiamo mille 2 e b = 7. Questo non sarà mai risolvibile con lo zaino, ma sempre (?) Con Countdown, almeno in tutti i modi in cui ho provato a trasferire il problema.

Ora, se Countdown era NP-hard, potremmo dedurre che con probabilità molto alta non esiste un algoritmo che sia significativamente più efficiente della forza bruta che prova tutte le possibilità. (E se dovessimo trovare un tale algoritmo, diventeremo molto famosi).

No, non credo che debba essere un algoritmo efficiente.

Euristica. Il video di YouTube collegato nella domanda ha un bell'esempio: il concorrente ha trovato una risposta esatta 952 = ((100 + 6) * 3 * 75 - 50) / 25. Questo è completamente contro la mia intuizione, non l'avrei mai provato in quel modo nel primo tempo: produci un numero molto grande, poi dividilo e produci il risultato.

Dall'altro, noi sentiamo che non abbiamo bisogno di provare (esempio arbitrario) 50 * 75 * 100/2/3/7 per raggiungere un numero di tre cifre. Ma i computer non sentono nulla, calcolano semplicemente.

Dopo tutto, se implementiamo delle euristiche, e questa euristica non trova una soluzione esatta, dovremo comunque provare tutte le altre soluzioni per assicurarci che non ce ne siano davvero.

Ciò che il concorrente nel video di Youtube fa è, penso, per controllare molto velocemente un gran numero di possibilità e per scartare rapidamente quelli che non (o probabilmente non lo faranno) dare una soluzione.

Conclusione. Quando si implementa un algoritmo, si potrebbe fare attenzione a eseguire calcoli uguali come a / b / c = a / (b * c), ma penso che sia abbastanza difficile da fare e non so se questo migliora significativamente il tempo di esecuzione.

I computer, naturalmente, sono più veloci degli umani nel controllare un gran numero di possibilità. E oggigiorno, anche gli smartphone sono così veloci da poter risolvere questo problema, penso, in un secondo semplicemente provando tutte le possibilità. (Non ho provato questo.) Ci sono solo sei numeri, sarebbe diverso se ci fossero, ad es. 60 di loro.

    
risposta data 19.10.2013 - 11:04
fonte
1

Un algoritmo non è in realtà molto difficile.

Dati due numeri aeb, possiamo produrre i risultati a + b, abs (a - b) (non so se sono consentiti numeri negativi, nel qual caso possiamo produrre a - b e a + b ), a * b, e possibilmente a / b o b / a se il risultato è un numero intero. Quindi i risultati possibili sono un insieme di fino a cinque numeri. Chiama questo set S (a, b).

Prendi sei numeri a, b, c, d, e ed f.

Per ogni sottoinsieme di due numeri, trova i numeri che possono produrre.

Quindi per ogni sottoinsieme di tre numeri, trova i numeri che possono produrre: S (a, b, c) = S (S (a, b), c) unione S (S (a, c), b) unione S (S (b, c), a).

Quindi lo stesso per ogni sottoinsieme di 4 o 5 numeri, quindi per tutti e 6 i numeri.

    
risposta data 07.02.2016 - 20:14
fonte

Leggi altre domande sui tag

In che modo le licenze CC (0, BY, BY-SA) influenzano le applicazioni proprietarie / closed source? Si dovrebbe generalmente sviluppare una libreria client per i servizi REST per aiutare a prevenire le rotture API?