La flemme de remettre en place mes algos d'optimisation (un bon Branch and Bound ferait le travail en un centième de seconde ^^), désolé

Cela ressemble au problème du voyageur de commerce.

Je trouve un itinéraire :

Lille Paris (200) Rennes (300) Nantes (100) Bordeaux (300) Auch (150) Toulouse (100) Marseille (300) Lyon(250) Strasbourg (350)

qui relie toutes les villes en investissant 2.050 milliards

Mais les Lillois vont devoir faire le tour de la France pour aller à Strasbourg !!

Bonjour,
Si l'on se moque totalement des Conditions de voyage et surtout des temps de trajet, j'arrive à une efficacité financière de 2,05 Milliards d'euros. Cependant, il risque de n'y avoir plus grand monde entre lille et strasbourg (Lille -> Paris -> Rennes -> Nantes -> Bordeaux -> Auch -> Toulouse -> Marseille -> Lyon -> Strasbourg). En rajoutant 400 millions, on boucle entre Lille et Strasbourg avec un maximum de 5 correspondances. Perso, je continue à prendre l'avion. trop marre de ces pauvres qui font attention à leurs sous sans prendre en compte que le temps c'est de l'argent.

Ca ressemble au pb du voyageur de commerce, mais c'est pas ça tout à fait car le but n'ai pas de définir le trajet optimal, mais le réseau optimal (en coût de construction) même si il faut passer par Strasbourg pour aller à Pau en venant de Paris... Chevallier et Laspallès avaient donc raison !

Il y a 45 bouts de réseau possible que l'on va activer ou pas, soient 2^45 solutions envisageables.
Parmis ces solutions envisageables, les solutions fonctionnelles sont celles qui relient toutes les villes.
La solutions recherchée est la moins chère des fonctionnelles.

La méthode que je propose est la suivante :
Je cherche le réseaux le moins cher : j'en trouve 2 Toulouse - Auch et Rennes - Nantes a 100, comme ils sont distincts, je les prends tous les 2 et reconstruit un tableau de coût avec les 2 pôles Toulouse-Auch et Rennes-Nantes et les 6 autres villes.

    Par    Lyo    Mar    Str    T-A    Bor    Lil    R-N
Paris__                               
Lyon__    390                           
Marseill    660    250                       
Strasbo    400    350    600                   
Tou-Auc    600    350    300    700               
Bordeau    500    450    450    700    150           
Lille___    200    550    800    400    750    700       
Ren-Nan    300    500    650    650    450    300    400

Je recommence à chercher le cout le plus bas : la liaison Bordeaux pôle Toulouse - Auch 150, je crée donc un nouveau pôle Toulouse-Auch-Bordeaux et reconstruit mon tableau.

Puis Paris - Lille : 200 puis Lyon - Marseille : 250

    Par-Lil    Ly-Ma    Str    T-A-B    R-N
Pa-Lil                   
Ly-Ma    390               
Strasb    400    350           
T-A-B    500    300    700       
Re-Na    300    500    650    300

Ensuite 3 à 300 qui me font créer le megapôle de toutes les villes sauf Strasbourg, que je relie enfin au mégapôle avec 350 (i.e via Lyon).

le coût total est donc de 100+100+150+200+250+3*300+350 = 2,05 Milliards.

Evidemment, avec de telles économies d'investissement, pour aller de Strasbourg à Lille, on passe par Lyon, Marseille, Toulouse, Auch, Bordeaux, Nantes, Rennes, et Paris, ce qui risque de dégouter les voyageurs... et de limiter les recettes d'exploitation.

rem 1 : Je pense que cette solution est optimale mais je ne l'ai pas montré !
rem 2 : Le réseau étant sans fourche (que l'on aurait eu en rajoutant Brest en cul-de-sac depuis Rennes), cette solution s'applique en fait aussi au problème du voyageur de commerce correspondant.

Pour aller de Paris a Lyon il faudra passer par Rennes, Nantes, Bordeaux, Auch, Toulouse et Marseilles. ^^

La bonne réponse a été donnée par pas mal de gens, c'est en effet:
Lille-Paris              200
Paris-Rennes             300
Rennes-Nantes            100
Nantes-Bordeaux          300
Bordeaux-Auch            150
Auch-Toulouse            100
Toulouse-Marseille      300
Marseille-Lyon          250
Lyon-Strasbourg          350

pour un total de 2.05 milliards.

Comme certains l'on remarqué (et comme d'autres se sont fait avoir), il ne s'agit pas du tout d'un problème de type voyageur de commerce.
En effet, on ne cherche pas un parcours passant par toutes les villes mais un réseau de poids minimal.
La méthode pour obtenir un tel réseau est simple.
On prend une ville au hasard: le réseau qui relie cette ville à rien du tout est minimal
On prend la ligne à moindre cout qui part de cette ville, le réseau qui relie nos deux villes a encore un cout minimal.
Et ainsi de suite, on prend à chaque fois la ligne à moindre cout qui part d'une des villes de notre réseau vers une ville qui n'y appartient pas encore, pour obtenir un réseau plus grand d'une ville, mais toujours minimal.

Petite note tout de même: si quelque soient les villes A, B et C, on a AB + BC > AC, alors ce problème est équivalent à celui du voyageur de commerce (c'est assez simple à démontrer, si ça intéresse certains). Ici, c'est le cas, le prix des lignes étant un arrondi de la distance en km qui les séparent. En faisant tourner notre voyageur de commerce, on trouve un cycle qui relie toutes nos villes, il suffit de couper la ligne la plus couteuse du cycle (en l'occurrence Lille-Strasbourg) pour obtenir le réseau de poids minimal