What is the shortest way to connect all the cities? For example, Paris, Dieppe, Brussels and Zurich could all be connected with just 6. Similar to travelling salesman, but not identical. Sorry if there's a name for this and it's easily solvable.
My best so far is 108.
>>8167079
>just 6
if you use 6 lines to connect 4 nodes, you have no more possible combinations of nodes left to connect.
how is this a problem? its fucking trivial, there is no minimization here and a 10 year old could derive the generic formula for the correct answer
>>8167102
I was just referring to those four cities as an example. See picture for acceptable solution.
>>8167112
This would be quicker if it was classic travelling salesman, my point is that the problem isn't.
>>8167079
Damn this map is wrongo
>>8167079
>My best so far is 108.
Yeah well I got 107
Is it a game or what?
>>8168974
It's the board from a game, but when playing it's not possible to link all the cities as a player doesn't have enough pieces. So it's just a problem using a network from a game.
>>8167079
I think you're looking for a minimum spanning tree.
Solution would be using primm's or kruskal's algorithm.
whats the name of this game
>>8169255
Ticket to Ride: Europe
>>8168987
Thanks, now I know the name it's easy to find a solution, and check because other people have done it.
>>8167079
>Have only played this while simulatenously drunk and hungover at 3am (multiple times)
Just looking at this game makes me sick
>>8167079
This is a minimal network problem. I think it theoretically is a bit easier than salesman, but I'm not very knowledgeable in those problems.