Disons qu'il y a une ligne de bacs x remplis de bibelots (quantité aléatoire), en clair (vous pouvez voir combien de bibelots il y a dans chaque bac). Maintenant, il y a deux joueurs qui peuvent quand c'est leur tour choisir un bac de l'une ou l'autre extrémité. Ils ne peuvent pas renoncer à un tour. Proposer une stratégie pour un joueur pour obtenir la quantité maximale de bibelots.
x est même.
est-ce un problème complet de NP? Est-ce similaire à Boolean Sat?
4 Réponses :
Non, il est facilement satisfait de la programmation dynamique dans O (x ^ 2) . Regardez le problème 10 ici .
C'est un problème très simple et ce n'est pas complet NP. Voici une brève description de l'algorithme, elle est basée sur une programmation dynamique.
peut [i] - matrice qui stocke nombre de bibelots.
F [I, J] - Array Déterminez ce qui est le meilleur déplacement si seulement des canettes de I à J sont disponibles. 0 signifie prendre du côté gauche, 1 signifie prendre du côté droit.
G [I, J] - Array où "bonté" du mouvement est stocké. P>
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;
}
Ce problème semble être parfait pour l'alpha-bêta-élagage, car il est facile de dériver une liaison inférieure pour vos points. Supposons que le joueur est confronté à un nombre pair de bacs. Ensuite, il peut jouer de manière à obtenir toutes les bacs sur des positions impaires:
dire que nous avons 1 0 1 0 1 0, puis il peut prendre le 1 à gauche, et quel que soit l'adversaire, il continue de ramasser les 1.
Donc, une limite inférieure facile à calculer est le maximum de la somme de toutes les bacs sur des positions même et la somme de toutes les bacs sur des positions impaires.
Pour le joueur "impair", vous pouvez simplement prendre la somme des plus petites valeurs (longueur + 1) / 2, qui n'est pas aussi bonne que la liaison du joueur "Même", mais aussi facile à calculer. < / p>
Je pense que avec ces limites, l'arbre de recherche sera clairsemé pour les applications pratiques (je suppose que vous pouvez toujours trouver des contre-exemples "pathologiques" pour ce type de problème, si la solution doit donc être assez rapide.
Il est clair que le premier joueur a une stratégie de cravate / gagnant. Tout ce qu'il a à faire est de vérifier si les bacs de position impairs ou les bacs de position pair ont un total plus grand, puis il peut facilement jouer de telle sorte qu'il oblige l'adversaire à ramasser les bacs de la parité «Perdre».
Par exemple:
2,6,11,4,7,3
Ici, les positions impaires sont meilleures (20 vs 13), le lecteur 1 devrait donc choisir 2. Le joueur 2 doit ensuite choisir soit 6 ou 3, qui sont même des positions. Si 3 est choisi, le joueur 1 devrait choisir 7, et ainsi de suite. En fait, le joueur 1 devrait toujours choisir la position à côté de celle choisie par son adversaire et garantit une cravate ou une victoire.
Voulez-vous vraiment créer une stratégie, qui peut concurrencer des adversaires arbitraires ou souhaitez-vous créer une ligne de bibelotte donnée la séquence des mouvements (du joueur un et joueur deux), tel que le joueur Obtient la quantité maximale possible de bibelots?
@Phimuemue - essentiellement si j'étais joueur1, quelle est la stratégie que je dois suivre pour gagner. Le joueur donné 2 fait une sorte de mouvement. Très probablement, même s'il va jouer à son avantage aussi. Je pense que vous devez énumérer tous les chemins possibles et trouver la récompense de ce chemin. Et le joueur continue de prendre ce chemin.
Il n'a pas vraiment significatif de demander si un jeu (dans le sens du jeu théorique, lequel c'est) est NP-complet. Vous pouvez demander si une stratégie particulière est NP-complète, cependant.
Il convient également de demander si un jeu est complet. Cela pourrait signifier: Compte tenu d'un état de jeu, pouvez-vous décider en polynôme de temps si le premier joueur gagne sûrement / il y a un tirage au sort, etc. et que devrait-il être le bouge qui maximise vos chances de gagner. Je crois que les gens parlent des jeux étant NP-complet tout le temps.