Mise à jour d'une grille de "joueurs" en remplaçant les perdants par des copies du gagnant

Question

J'ai un tableau bidimensionnel d'objets. Chaque objet a, à tout moment, un certain score (variable) (c'est-à-dire que le score d'un objet au temps t n'est pas nécessairement le score de l'objet au temps t+1). Je veux trouver l'algorithme le plus efficace pour dupliquer tout objet dont le score est supérieur à celui de son voisin, et placer ce duplicata à la place du voisin. 1

Ma première impulsion a été la solution naïve :

• Créer une copie du tableau
• mettre l'indicateur "changeWasMade" à false
• parcourir toutes les positions p
  • comparer les scores avec tous les voisins n
  • si score(p) > score(n), remplacez n dans la grille copiée par une copie de p et mettez "changeWasMade" à vrai
• si "changeWasMade", alors on jette la grille originale, et on répète en utilisant la copie comme nouvel original ; sinon, on retourne la copie

Cependant, pour un tableau n x n, cela semble être O(n 4 ) (n 2 itérations possibles de n 2 ), ce qui me semble assez lent. Comme mes connaissances en algorithmique sont assez faibles, j'ai pensé qu'il serait judicieux de demander s'il existe un moyen plus rapide de procéder.

UPDATE

Je viens de penser qu'il serait peut-être plus rapide de faire une "passe" de remplacements, puis de vérifier que tous les objets nouvellement créés (c'est-à-dire clonés) ont le score le plus élevé de leurs voisins (c'est-à-dire qu'ils constituent un maximum local). Si c'est le cas, c'est parfait, la bonne chose s'est produite. Sinon, il faut les remplacer par une copie du voisin ayant le score le plus élevé. Cette méthode réduira probablement le nombre d'itérations nécessaires (mais elle nécessitera une bonne tenue de livres pour que tout soit clair !

** Notes de bas de page**

1. (Pour situer le contexte, pour ceux qui ont lu "Le voleur de quantum", il s'agit de l'installation de la prison décrite dans les premières pages).

Answer 1

A moins que je ne lise mal le problème, la solution évidente semble être :

1. Créer un tableau vide de la même taille, appeler l'ancien tableau old et le nouveau tableau new .
2. Pour chaque cellule new[i][j] dans le nouveau tableau, fixez-le au maximum des cinq valeurs possibles : old[i][j] , old[i-1][j] , old[i][j-1] , old[i+1][j] , old[i][j+1] .
3. new est maintenant le tableau mis à jour pour le pas de temps t+1.