Trouver les meilleurs chemins dans plusieurs arbres (plusieurs nœuds dans plusieurs couches)

Question

Le problème consiste à trouver les meilleurs chemins (coût min/score élevé) dans plusieurs nœuds dans plusieurs niveaux. Ou en d'autres termes, dans plusieurs arbres qui partagent certains mêmes nœuds. Par exemple comme vu in the picture; Il y a plusieurs nœuds dans chaque niveau. Ceux-ci sont reliés entre eux par des arêtes (chaque arête a également une valeur de distance, mais ne peut pas utiliser). Et chaque chemin a une valeur de score à partir des valeurs de bord. Le score est la probabilité conjointe du chemin. Donc, le but est de trouver les meilleurs chemins entre ces nœuds de couches.

les données sont vues comme suit; (premier noeud de niveau, 2 noeud de niveau, 3 noeud de niveau ...): score

(1, 1, 1): 3

(1, 2, 1): 1

(1, 2, 2): 6

(1, 2, 3): 2

(2, 2, 1): 3

(2, 2, 2): 4

(2, 2, 3): 3

(2, 3, 2): 5

(2, 3, 3): 4

.....

le résultat devrait donner 5 chemins et ces chemins devraient donner un coût min total.

Quel type d'algorithme devrait être utilisé pour ce problème?

Answer 1

Ce problème peut être modélisé comme un problème de réseau minimum cost flow. Soit m le nombre de nœuds dans chaque couche. Une source artificielle s est placée au-dessus de la première couche; s est connecté à chaque noeud de la première couche et chacun de ces bords m a sa capacité de réseau limitée par 1 et un coût de 0. De même, il existe un terminal artificiel t en dessous de la dernière couche; t est connecté à chaque nœud de la dernière couche et chacun de ces bords m a sa capacité réseau limitée par 1 et un coût de 0. Le problème peut être résolu en déterminant un flux de coût minimum avec le montant m, ce qui est possible via l'algorithme network simplex.