En jouant aux jeux 18xx (créer des itinéraires pour les trains et essayer d'obtenir le plus d'argent avec vos trains), il faut parfois beaucoup de temps pour trouver l'itinéraire optimal pour les trains.
Quelqu'un sait-il s'il existe un logiciel pour résoudre ce problème ?
Pas à ma connaissance.
Une chose que j'ai faite pour résoudre ce problème est d'utiliser une pile de D6 de deux couleurs différentes.
Placez un D6 sur chaque ville d'une couleur pour représenter votre plus petit train, puis remontez jusqu'au plus grand.
Lorsque vous avez terminé, ramassez les D6 en générant votre bénéfice total au fur et à mesure.
Vers la fin du jeu, nous nous entraidons généralement, car les courses de diesel peuvent devenir assez dramatiques, comme vous le savez certainement ! Cela ne fait qu'accélérer le jeu, car nous ne voulons pas qu'une personne soit obsédée par sa course pendant vingt minutes pour gagner 10 $ de plus.
Voir https://www.reddit.com/r/18XX/comments/9t32gw/1846_route_finder/
Le problème de décision "Étant donné ce réseau particulier, est-ce qu'un train diesel (non limité) peut circuler pour au moins X $ ?" est NP-complet.
C'est dans NP, puisque la longueur d'une route est limitée par la taille du plateau et que sa validité et son gain sont facilement vérifiables.
C'est NP-hard par une réduction du chemin Hamiltonien sur les grilles carrées. Embarquez la grille carrée sur une carte hexagonale en inclinant un axe de 60°. Utiliser les villes X pour les sommets du graphe d'entrée et utiliser beaucoup de droites pour connecter les sommets. Placez une station dans un sommet/une ville arbitraire. Il existe une route de valeur k×n, où k est le dividende par ville et n est le nombre de villes, si et seulement s'il existe un chemin hamiltonien dans le graphe d'entrée (avec la correspondance évidente).
Je ne connais pas la dureté des trains bornés, mais en pratique, la limite des trains est O(1) et la longueur des trains est également O(1), et surtout, les nombres ont tendance à être petits.
Par exemple, avec 10 villes et un seul 6, il y a 10 choix de 6 = 210 ensembles de villes différents à essayer. Vous pouvez les trier par dividendes et la réponse est le premier itinéraire réalisable.
Avec 10 villes et un 5, il y a 252 possibilités. Avec un 5 et un 6, cela fait 210*252 = 52920. Une fois de plus, le tri par dividendes totaux et la recherche de la première correspondance possible devraient être assez rapides.
Ou bien vous trouvez les itinéraires les plus rémunérateurs, chaque train n'étant pas contraint par l'autre, puis vous recherchez dans deux listes une correspondance compatible. Supposons que vous recherchez les 6 routes par ordre décroissant ; vous devez alors dépasser la première correspondance compatible, jusqu'à ce que vous arriviez à une 6-route qui paie si peu que même la 5-route la mieux payée ne vous place pas au-dessus de la meilleure correspondance jusqu'ici. Alors, cette meilleure correspondance ne peut être dépassée et doit être la réponse.
AlleGamers est une communauté de gamers qui cherche à élargir la connaissance des jeux vidéo.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.
