la meilleure suite de transactions

[kizakoo]

Bonsoir, étant donné un ensemble de transactions qui peuvent engendrer des pertes (gain négatif) ou des gains (gain positif). On peut modéliser cette situation par le graph suivant:


Chaque sommet désigne une transaction et le passage d'un sommet A à un sommet B désigne que l'on a généré un gain équivalent au poids de l'arête.

Comment déterminer la meilleure suite de transactions (sans exploser la complexité) ? Sachant que le jeu s'arrete après un nombre N de tour.
J'ai pensé à un parcours en profondeur mais c'est très cher en termes de complexité je cherche alors à implémenter une stratégie qui soit optimale (meilleur rapport gain/complexité)

Merci de m'éclairer
-----

[pm42]

En 1ère analyse, si tu limites à N coup ce qui revient à mettre un point de sortie avec coût nul, tu dois calculer un plus long chemin entre l'entrée et la sortie.

Vu que tu as des poids positifs et négatifs, tu peux essayer l'algo de Bellman-Ford :

https://fr.wikipedia.org/wiki/Problè...s_court_chemin
https://fr.wikipedia.org/wiki/Algori...e_Bellman-Ford

adapté pour trouver un plus long chemin : https://ics.utc.fr/~led/co/anx_reche...ng_chemin.html

ou peut-être tout simplement en mode plus court mais en changeant le signe de chaque poids (à vérifier, je n'ai pas tous mes neurones le matin).

[CM63]

La transaction B->D n'est pas chiffrée. C'est 0?

[pm42]

Vu que tu as des poids positifs et négatifs, tu peux essayer l'algo de Bellman-Ford :

J'ai oublié de préciser qu'il faut que tu vérifies tes contraintes (voir le 1er lien). Si comme cela semble possible à la vue de ton graphe tu es dans le cas général avec des boucles et des circuits absorbants, etc, tu risques de tomber sur du NP-difficile.

[A voir en vidéo sur Futura]

[invite73192618]

Perso j'irai avec une variante de :
https://fr.m.wikipedia.org/wiki/Algo...ies_de_fourmis

[pm42]

Perso j'irai avec une variante de :
https://fr.m.wikipedia.org/wiki/Algo...ies_de_fourmis

C'est intéressant. Je connaissais le comportement des colonies mais pas l'adaptation en algo et c'est une bonne idée vu l'efficacité dans la nature.
Merci.