6

Given the following problem (a slightly simplified description of trading in the computer game Escape Velocity: Nova (system map)):

  • Given a set of (solar) systems.
  • Each system is connected by hyperspace travel route to one or more other systems; each route connects two systems.
  • Making a hyperspace jump has a cost in dollars (covering fuel costs). The cost is the same no matter which jump you're making.
  • Each system has a trading center with various commodities (food, metal, equipment, etc.) available for trade at a given price. The price varies between systems.
  • To keep it simple we'll say you can only hold a single unit of a single commodity at any given time.
  • A trade route is a series of hyperspace jumps that start and end in the same system (a loop), buying and selling commodities along the way.
  • The profit of a trade route is defined as profit made by buying and selling commodities along the way minus the total cost of the hyperspace jumps made.

I want to be able to answer questions like the following:

  1. What's the most profitable trade route?
  2. What's the most profitable trade route starting and ending in a specific system?
  3. What's the most profitable trade route involving fewer than X jumps?
  4. What's the most profitable trade route involving fewer than X jumps starting and ending in a specific system?

I plan to model this as a digraph:

  1. Each system is a vertex.
  2. For each hyperspace travel route add two edges (one in each direction) connecting the two vertexes with a weight equal to the cost of making a hyperspace jump.
  3. For each system
    • for each commodity available in that system
      • for each system where the price of the commodity is lower than in the current system (we'll never make a profit if the cost at the destination is higher so we omit those edges)
        • add an edge from the current system to that system with weight of (number of jumps to reach that system) * (cost per jump) - (difference in price of the commodity) (i.e. profit to be made by buying in the current system and selling in the destination system)

I believe the technical description of what I'm after is (for question 1): given the above digraph what's the negative cycle with the lowest average cost per edge.

I realize I can use a breadth-first search to answer questions 3 and 4 as long as the maximum number of jumps is small enough that I don't run out of memory, but I suspect it won't be practical to answer 1 or 2 this way.

I've read though the Solving Problems by Searching chapter in AI: A Modern Approach but as far as I can tell the algorithms there require positive edge weights.

A bit of Googling found me the Bellman–Ford algorithm and while that supports negative edge weights my understanding is that it doesn't give accurate costs when negative cycles are involved.

Are there any algorithms I can use to solve this problem more efficiently?

Improve this question
3
  • With no limit to jumps the answer in presence of a negative cycle always is 'enter the cycle and never leave'.
    – Patrick
    Commented Jun 23, 2015 at 12:11
  • @Patrick I actually don't think it is in this case, because I want the cycle with the lowest average cost per edge, which will not change however many times you do a given cycle. If you make $1000 in profit and the cycle takes 10 jumps, that's $100/jump. If you do the cycle twice that's $2000 and 20 jumps, that's still $100/jump, so they're equivalent from a profit perspective.
    – Redwood
    Commented Jun 23, 2015 at 17:25
  • 2
    In the case when start or end of the route are not part of the cycle the infinite solution is the only optimal one. I'd suggest that you focus on the case with a limited number of jumps. It yield solutions that can be applied, not just theoretical results.
    – Patrick
    Commented Jun 23, 2015 at 20:53

2 Answers 2

Reset to default
4

This is not a traveling salesman problem if there is no prohibition on revisiting a system.

The problem for Question 1 is canonically referred to as the minimum mean cycle problem, which has polynomial-time algorithms. This is a subroutine in some min-cost flow algorithms.

Question 2 is sort of ill-defined because there won't be a best route in general; you'll want to fly to the best loop, do it a bunch of times (the more the better), and fly back.

Questions 3 and 4 can be addressed by expanding the digraph with a time dimension (where one unit of "time" is one jump) and then computing shortest paths on the resulting acyclic digraph.

Improve this answer
1
  • Thanks for the answer, that would definitely send me down a different road. I'll have to do some research into those algorithems. I'll accept this for now until somebody else comes along and makes a convincing argument for something else:).
    – Redwood
    Commented Jun 24, 2015 at 23:26
4

Look into Traveling Salesperson Problems and optimization.

You are basically optimizing a TSP for all your four questions.

The specific details will vary based on your problem size (if you have 10 nodes you can just brute force it, if you have 1000 you will have to be more efficient).

The wikipedia site on TSPs suggests a large number of algorithms to use. It looks like you could use a modified Ant Colony Optimization method based on the total value of the entire trip (ie your first and second questions).

Improve this answer
1
  • Unaccepting for now because according to @David Eisenstat it's not the TSP and there are polynomial-time algorithems. Even if that's true Ant Colony Optimization does sound like an interesting approach so you've still got my upvote.
    – Redwood
    Commented Jun 24, 2015 at 23:29

Not the answer you're looking for? Browse other questions tagged or ask your own question.