Algorithme de Théorie des graphes?

Bonjour, Je me trouve aujourd’hui face a un problème assez complexe et j’avoue ne pas savoir par où m’y prendre. Voici sa description: dans un jeu, il y a 89 objets. Chaque objets est caractérisé par son nom, son score, et son affinité avec les autres objets. En effet chaque objet a une affinité avec chaque objet défini par un facteur compris entre 0 et 2 lorsqu’on sélectionne des objets, leurs scores et affinités se combine suivant la loi suivante:

Le score total équivaut à la somme de (chaque score multiplié par chacun des facteurs entre lui et les autres sélectionnés)

J’ai pensé a une représentation en graphe car chaque objet ayant un lien avec tous les autres on se retrouve avec un graphe complet pondéré avec une valeur pour chaque arrête et chaque sommet.

Mon probleme est le suivant : existe-t-il un algorithme ou des pistes afin de pouvoir facilement (sans prendre toutes les combinaisons) calculer le score max faisable en sélectionnant n objets parmi k (un ensemble d’objets compris entre n et 89)?

Salut,

Est-ce que $n$ reste petit ou proche de 89 ? Combien as tu de temps pour trouver ce score max ? Moins d’une seconde ? Une seconde ? Quelque secondes ? Une heure ? Un an ?…

Ton vrai problème n’est pas tellement la structure de donnée que tu utilises (à moins d’utiliser une structure avec un temps d’accès ridiculement élevé), c’est surtout qu’explorer l’arbre des possibilités commence à devenir conséquent voire impossible dès que $4<n<85$ (environ 2.5 million de possibilités avec 4 ou 85 objets, et ça explose très vite lorsqu’on se rapproche de 89/2).

Est-ce qu’il y a des doublons en terme de valeurs ? Si oui, ce sont des possibilités en moins à explorer puisque le score sera le même (et de la même façon qu’augmenter $n$ fait exploser le nombre de possibilité, diminuer l’espace à explorer le fait beaucoup rétrécir).

Est-ce qu’il y a des scores/affinités particulièrement élevé pour certains objets ? Si certains objets dominent clairement le lot, tu peux te contenter de chercher le maximum dans les branches qui les contiennent.

Si en revanche tu as des scores et affinités relativement proches mais différentes, et que $n$ est trop grand ou éloigné de $89$, tu vas être réduit à ne pouvoir avoir qu’une estimation du score max, par exemple en explorant tous les choix possibles pour les 2 ou 3 (ou un peu plus suivant le temps disponible) premiers objets, puis en ne prenant que le meilleur pour les suivants et en prenant le maximum global de cet espace réduit. SI $n$ est proche de $89$, il faut bien sûr faire l’inverse et regarder quels sont les objets à enlever pour ne jamais avoir un très gros arbre à parcourir.

merci de ta réponse

n est compris entre 1 et 6

et justement le temps est mon facteur clef, je n’ai pas vraiment de limite de temps précise mais un jour est déjà long

oui il y a des doublons en termes de valeurs mais ça restes de possibilité a explorer car leurs coefficient d’affinités sont différents. a l’inverse certains coefficients sont similaires mais leurs valeurs diffèrent

Aussi je précise qu’on ne peut pas sélectionner 2 fois le même objet Pour ce qui est des valeurs/coefficients, il n’y a pas "d’anomalie" que ce soit dans un sens ou dans l’autre

n est compris entre 1 et 6

Alors tu dois pouvoir t’en sortir avec une recherche exhaustive, ou quasiment. 6 parmi 89, ça fait presque 600 millions de possibilités. Ça fait beaucoup, mais c’est largement faisable dans un temps de l’ordre de l’heure par un ordinateur.

Affinité comprise entre 0 et 2 : ça veut dire que l’affinité entre 2 objets peut prendre 3 valeurs (soit 0, soit 1, soit 2) , c’est ça ? Ou bien , c’est n’importe quelle valeur (pas forcément réelle) entre 0 et 2 ?

"Le score total équivaut à la somme de (chaque score multiplié par chacun des facteurs entre lui et les autres sélectionnés)"

Supposons qu’on sélection 3 objets A,B et C,

ça veut dire que le score total vaut :

Score(A) x Affi(A,B) x Affi(A,C) + Score(B) x Affi(B,A) x Affi(B,C) + Score( C) x Affi(C,A) x Affi(C,B)

C’est ça ?

en effet adri1 c’est ce sur quoi je m’oriente pour le moment, mais j’avoue continuer a chercher pour le défi également autant que pour une réelle solution haha

non les affinités sont des réels et non des entiers

et oui le calcul est celui la même.

Le problème que tu décris est un problème d’optimisation non-linéaire. Il en existe un certain nombre de problèmes similaire qui sont NP-difficiles (en gros, ils n’ont pas de solution optimale qui se finissent en temps polynomial), donc le tiens est probablement aussi NP-difficile. Ça veux dire que à moins que le problème soit vraiment petit, tu n’as aucune chance de trouver un algorithme qui se fini en un temps raisonnable et qui est garanti de trouver une solution optimale.

Comme l’a dit @adri1, avec 89 objets et n compris entre 1 et 6, c’est assez petit pour tester toutes les solutions de manière exhaustive. L’estimation de moins d’une heure est assez pessimiste et je pencherais plus sur moins d’une minute avec un programme bien écrit et probablement de l’ordre de la seconde sur un bon ordinateur si tu parallélises la recherche (ce qui peut se faire de manière triviale).

Si n ou le nombre d’objet devient trop grand pour faire une recherche exhaustive, tu peut te tourner vers des algos heuristiques. D’expérience, la suggestion de @Karnaj de construire la solution de manière gloutonne ne va pas te donner un très bon résultat. Parmi la collection d’algos heuristiques, je une préférence pour utiliser un des trucs similaire au recuis simulé. Dans ton cas, tu peux simplement prendre au hasard n objets et ensuite améliorer itérativement cette solution. À chaque itération, tu choisis k éléments à remplacer, tu cherches de manière exhaustive les k nouveaux éléments qui te donnent le meilleur score. En pseudo-code, ça donne ça:

objets = liste d'objets possible
choisis = liste de n objets choisis aléatoirement parmi objets
score = score de choisis
boucle
  à_remplacer = liste de k objets choisis aléatoirement parmi choisis
  objets_stable = choisis - à_remplacer
  meilleur_score = score
  meilleur_k = à_remplacer
  pour toutes les listes l de k objets parmi (objets - objets_stable)
    nouveau_score = score de (objets_stable + l)
    si nouveau_score > meilleur_score
      meilleur_score = nouveau_score
      meilleur_k = l
  choisis = objets_stable + meilleur_k
  score = score de choisis
  afficher choisis et score

Pour que ça marche bien, il faut choisir le plus grand k qui permet à la boucle principale de s’exécuter rapidement (disons quelques dizaines/centaines de fois par secondes). Tu peux arrêter la boucle principale une fois que tu es satisfait du score obtenu.

Il reste un dernier détail important: vu qu’il est possible de diminuer ton score en ajoutant un nouvel objet, il y a de gros risques de tomber sur un optimum local qui est assez mauvais en comparaison de l’optimum global. Si tu relances l’algo décris précédemment (en t’assurant que le chois de la solution initiale est bien aléatoire) plusieurs fois, ça permet d’explorer à chaque fois des zones différentes de l’espace des solutions et donc te donne plus de chances de trouver l’optimum global (ou un bon optimum local). En allant plus loin, tu pourrais même biaiser la choix de la solution initiale pour diminuer les chances de choisir de nouveau des objets qui font parti de ta meilleur solution jusque là.

Comme Berdes, je pense que la suggestion de Karnaj ne donnera pas la meilleure solution.

A quoi ressemblent les affinités ? Si Aff(A,B) et Aff(B,C) sont toutes les 2 grandes, est-ce que Aff(A,C) va également être grande ?

Autrement dit, est-ce que les amis de mes amis sont mes amis. Si oui, il y a une vague piste, du type de ce que propose Karnaj :

• on évalue tous les triplets (A,B,C) et on garde les 500 qui ont le meilleur résultat.

• Pour chacun de ces 500 triplets, on évalue tous les quadruplets possibles, et on garde les 2000 qui ont le meilleur résultat.

etc.

Si les données sont 'sympathiques’ (c.a.d. si elles vérifient le postulat les amis de mes amis sont mes amis), tu devrais trouver ainsi la meilleure combinaison en évitant un calcul exhaustif.

Mais plus les affinités ont un caractère aléatoire, plus il faut se tourner vers une recherche exhaustive.

bonjour,

Merci pour toutes vos réponses !

Alors déjà pour elegance, non les données ne sont pas 'sympathiques’ elles ont été choisis purement arbitrairement par le créateur.

j’aime bien la solution de @Berdes je pense me diriger là dessus pour le moment et voir ce que cela me donne !

edit:

je me suis rendu compte que les objets pouvaient être classés par catégories. En effet, il y a 35 catégories d’objets différents. Les objets d’une même catégorie partagent des coefficients similaires que ce soit entre eux ou avec les autres catégories. Seul leur score change. Cela rend le calcul bien plus simple !

Les objets d’une même catégorie partagent des coefficients similaires que ce soit entre eux ou avec les autres catégories.

Voilà une information qui nous dit qu’une recherche exhaustive ne sera pas forcément nécessaire.