Travelling salesman problem

[pepperman35]

Anyone see a practical application of the travelling salesman problem (TSP) to FO4?

If you are not familiar with the TSP you can find out more here: travelling salesman problem

[aurreth]

Not so much.

 

For those of you who are not mathematicians: you have X number of settlements, what is the shortest route a Minuteman patrol can take to visit each of those settlements exactly once and return to their starting point.

 

Thing is there isn't really any reason for that difficult of a solution (this is a rather hard math problem to solve). We don't really care if patrols retrace their steps, or pass through a settlement they've already visited on their way someplace else. In fact given the need to navigate around obstacles and across bridges it is likely more efficient, from a game point of view, that the patrol does backtrack a bit, even if it means a second visit to one of the settlements.

 

AND, that assumes one patrol, rather than the game just spawning one somewhere and having it cover one leg of the route before despawning it.

 

In the end TSP is high level mathematics, with specific solutions to it being applied to various fields such as economics. If you wanted to use it in the game you'd have to find a mathematician to solve it for your specific use case. It would cost you a fortune, and Fallout 5 would already be out by the time you had an answer.

 

Oh, and yes, I actually am a mathematician, but that kind of things is way above my pay grade. I can follow the linked paper for the most part, but even my eyes start to cross after a certain point :wacko:

[pepperman35]

Actually, you could set it up in Microsoft Excel and use Solver to get the solution. Bit of work mind you, but doable. I used it for a certain problem in Star Trek Online.

[aurreth]

Actually, you could set it up in Microsoft Excel and use Solver to get the solution. Bit of work mind you, but doable. I used it for a certain problem in Star Trek Online.

 

I may be looking too deep. TSP is one of those problems with a great deal of depth and application beyond just "A to (B or C) to (C or B) to A".

 

STO is a different beast. You aren't constrained by rivers and the bridges across them. Or big ass rocks that are conveniently placed to keep you from going in a straight line. If patrols would swim it would be a different matter. Or if they rode goats. Big, mutant, unicorn goats.

 

Note to self, add goat lab to the Institute, where scientists do nothing but stare at them.

Edited June 23, 2021 by aurreth

[pepperman35]

Yes, much less obstacles in STO, and because of said obstacles TSP probably isn't practical. A good exercise in thought nonetheless.

[DocClox]

TSP would make sense here if the provisioners were physically carrying goods, and supplies didn't arrive until the provisoners did. As it stands though, all you need is connectivity. It doesn't matter where the provisioner is, or how often he visits his settlements, just so long as he works the route, So TSP doesn't really apply.

 

The only case where you are actually interested in where your provisioners are, is if you're using them to flush out hostile spawns and keep the area around the route pacified. But if that's the intention, then what you really want is redundancy. Instead of a minimum connectivity tree, set up a mesh with each settlement having a route to all its near neighbours. That maximises the provisioners in the fiel, and again TSP doesn't really apply.