Questo problema è np-complete?

Question

Diciamo che c'è una riga di x bidoni pieni di bigiotteria (quantità casuale), in chiaro (si vede quanti gingilli ci sono in ogni cestino). Ora ci sono due giocatori che possono, quando è il loro turno, scegliere un bin da entrambe le estremità. Non possono rinunciare a una svolta. Vieni con una strategia per un giocatore per ottenere la quantità massima di bigiotteria.

x è pari.

Si tratta di un problema np-completo? È simile al SAT booleano?

Answer 1

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

Può [i] - array che memorizza il numero di ninnoli.
F [i, j] - array che determina quale è la migliore mossa se sono disponibili solo lattine da i a j. 0 significa prendere dal lato sinistro, 1 significa prendere dal lato destro.
G [i, j] - array in cui è memorizzata la "bontà" dello spostamento.

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 mancanza di commenti, ma se leggete alcuni articoli sulla programmazione dinamica lo otterrete senza alcun problema.

Answer 2

No, è facilmente risolvibile con programmazione dinamica in O(x^2). Guarda il problema 10 here.

Answer 3

Questo problema sembra essere perfetto per l'alfa-beta-potatura, in quanto è facile ricavare un limite inferiore per i punti. Supponi che il giocatore abbia un numero pari di bidoni. Poi può giocare in modo da ottenere tutti i buchi in pareggio o tutti su posizioni dispari:

Diciamo che abbiamo 1 0 1 0 1 0, quindi può prendere il 1 a sinistra, e qualunque cosa faccia l'avversario, continua a raccogliere gli 1.

Quindi un limite inferiore facile da calcolare è il massimo della somma di tutti i raccoglitori in posizioni pari e la somma di tutti i raccoglitori in posizioni dispari.

Per il giocatore "dispari" puoi semplicemente prendere la somma dei (più lunghi + 1)/2 valori più piccoli, che non è buono come il limite per il giocatore "pari", ma anche facile da calcolare.

Penso che con questi limiti l'albero di ricerca sarà scarso per applicazioni pratiche (suppongo che si possano sempre trovare contro-esempi "patologici" per questo tipo di problema), quindi la soluzione dovrebbe essere abbastanza veloce.

Answer 4

È chiaro che il primo giocatore ha una strategia di pareggio/vincita. Tutto quello che deve fare è controllare se i bin di posizione dispari o quelli di posizione pari hanno un totale maggiore, e quindi può facilmente giocare in modo che costringa l'avversario a raccogliere i cassonetti della parità "perdente".

Ad esempio:

2,6,11,4,7,3

Qui le posizioni dispari sono meglio (20 vs 13), quindi il giocatore 1 dovrebbe scegliere 2. Quindi il giocatore deve scegliere 2 6 o 3, che sono in posizioni pari. Se si sceglie 3, il giocatore 1 dovrebbe scegliere 7, e così via. In realtà, il giocatore 1 dovrebbe sempre scegliere la posizione accanto a quella scelta dal suo avversario e garantisce un pareggio o una vittoria.