È questo problema NP-completo?

Question

dicono che c'è una linea di x bidoni pieni di cianfrusaglie (importo casuale), in pianura vista (si può vedere il numero di gingilli ci sono in ogni bin). Ora ci sono due giocatori che possono, quando è il loro turno scegliere un bidone da entrambe le estremità. Essi non possono rinunciare ad un turno. Vieni con una strategia per un giocatore per ottenere la massima quantità di bigiotteria.

x è ancora.

E 'questo un problema NP-completo? E 'simile a booleano SAT?

Answer 1

E 'molto semplice problema, e non è NP completo. Ecco breve descrizione dell'algoritmo, si basa sulla programmazione dinamica.

Can [i] -. Matrice che memorizza il numero di gingilli
F [i, j] - matrice determinare qual è mossa migliore se solo lattine da i a j sono avaible. 0 significa prendere dal lato sinistro, 1 significa prendere dal lato destro.
G [i, j] - matrice in cui è memorizzato 'bontà' di movimento.

for (i=1 to n) F[i,i] = 0
for (i=1 to n) G[i,i] = Can[i]

for (i=1 to n-1)
   for (j=1 to n-i)
       tmp1 = Can[j] - G[j+1,j+i]
       tmp2 = Can[j+i] - G[j,j+i-1]
       if (tmp1>tmp2)
       {
             F[j,j+i] = 0;
             G[j,j+i] = tmp1;
       }
       else
       {
             F[j,j+1] = 1;
             G[j,j+i] = tmp2;
       }

Ci scusiamo per la mancanza di commenti, ma se si leggono alcuni articoli sulla dinamica programmazione Otterrete senza alcun problema.

Answer 2

No, è facilmente risolvibile con la programmazione dinamica O(x^2). Guardate problema 10 qui .

Answer 3

Questo problema sembra essere perfetto per alfa-beta-potatura, come è facile ricavare un limite inferiore per i vostri punti. Si supponga che il giocatore deve affrontare un numero pari di bidoni. Poi si può giocare in un modo sia per ottenere tutti i cassonetti su anche o tutti su posizioni dispari:

dire che abbiamo 1 0 1 0 1 0, poi si può prendere la 1 a sinistra, e qualunque sia l'avversario fa, continua a raccogliere i 1 del.

Quindi, un facile da calcolare limite inferiore è il massimo della somma di tutti i contenitori sulle posizioni anche e la somma di tutti i contenitori sulle posizioni dispari.

Per il giocatore "dispari" si può solo prendere la somma della (lunghezza + 1) / 2 valori minimi, che non è buono come il limite per il "anche" il giocatore, ma così facile da calcolare.

Credo che con questi limiti l'albero di ricerca sarà sparsa per le applicazioni pratiche (Credo che si può sempre trovare "patologiche" contro-esempi di questo tipo di problema, però) in modo che la soluzione dovrebbe essere abbastanza veloce.

Answer 4

E 'chiaro che il primo giocatore ha una strategia tie / win. Tutto quello che deve fare è controllare se i bidoni di posizione dispari o bidoni posizione anche hanno una maggiore totale, e quindi si può facilmente riprodurre tale che costringe l'avversario a prendere i bidoni della parità "perdere".

Ad esempio:

2,6,11,4,7,3

Ecco le posizioni dispari sono meglio (20 vs 13), quindi il giocatore 1 dovrebbe scegliere 2. Poi il giocatore deve scegliere 2 o 6 o 3, che sono in posizioni anche. Se 3 è scelto, il giocatore 1 dovrebbe scegliere 7, e così via. In realtà, il giocatore 1 deve sempre scegliere la posizione accanto a quello prescelto dal suo avversario, e garantisce una cravatta o una vittoria.