7

I am trying to solve the following kind of problem. I do not know if there is already a name for this, or a solution; however, I'm willing to bet there is. I was hoping someone could point me in the direction of implementing a solution for it, or at least tell me the name of the problem?

Suppose a traveler has a certain amount of Gold coins, and some Bronze coins. He must start a city A, and go to city B, then city C, and finally city D.

There are two (or more) roads that pass from A to B, labeled AB1, and AB2 (etc.). Road AB1 has a toll of 5 gold coins, and AB2 has a toll of 5 bronze coins.

Roads from city B to C: BC1 has a toll of 10 coins, which can be either currency. BC2 requires 8 gold coins.

Roads from C to D have some sort of similar setup.

Assuming that we know how much money the traveler has, and that there is no possible exchange between bronze and gold coins: is there a method to determine if the traveler has enough money to pass through from A to B, to C, and finally to D?

This is the kind of problem I need a solution to... Is there a name for this problem? Is there a solution to this problem (other than brute force)? I'm assuming this is a similar problem to flow problems, but I don't know quite how to approach it.

Serge
  • 173
  • 5
  • Also, sorry about the "school problem" style explanation. It was the only way I could think of, to explain the problem in simplistic terms. – Serge Jul 29 '13 at 17:40
  • in my opinion, bruteforce is enough for this problem (if there are only 4 cities). Call n the maximum number of routes between 2 cities, then the number of all possibilities are n * n * n * n = n^4. For a more optimized solution, you may consider back-tracking. – Hoàng Long Jul 30 '13 at 03:33
  • Random suggestion: If gold and bronze are really impossible to exchange, I'd suggest choosing names for them which are mentally equivalent, such as "Blue coins" and "Red coins". Gold has the connotation of being more valuable than bronze, so there's a bit of cognitive disconnect that some roads won't accept it instead of bronze. – Bobson Jul 30 '13 at 13:32

4 Answers4

3

I'm not sure it could be related to a flow algorithm, because a flow problem would allow you to go partially down road AB1 and partially down road AB2, for example.

I think you're pretty much stuck with depth first search, but you have opportunities for pruning. For example, if one road requires 8 gold coins and another between the same two cities requires 10 gold coins, you don't need to bother traversing the latter. That leaves you with one gold, one bronze, and one "either" path between each city. Also, keep in mind that the order you visit the cities doesn't matter from the algorithm's point of view. If the CD roads are all higher cost than the AB ones, you might be able to speed things up by moving them first.

Karl Bielefeldt
  • 146,727
  • 38
  • 279
  • 479
3

If I'm reading your question correctly, your problem has a two interesting properties:

  1. The graph is connected sequentially, A->B->C->D. There may be multiple edges between nodes, but there are never edges that "skip" nodes (A->C, B->D) or loop back (C->A).
  2. The ultimate goal is feasibility versus optimality. That is, you want to know if a traveler has enough money versus which path costs the absolute least.

Is that correct? If so, there are a few tricks available.

First, calculate the expected value in both gold and bronze between each city. The expected value would be the minimum you would expect to pay. Given AB1 = 5 gold, AB2 = 5 bronze, and AB3 = 10 gold or bronze (I'm adding the road to illustrate a point), you would never select AB3. AB1 or AB2 give you a better solution regardless of the coin you use. Therefore, the expected value between A and B is 5 gold and 5 bronze. The expected value between B and C is 8 gold and 10 bronze. Again, we would never select BC1 (10 gold or bronze) when spending gold as BC2 (8 gold) is always cheaper. Continue calculating the expected values for the rest of your path.

Next, total your expected values for each coin. You're basically acting as if you paid all tolls using one coin type, but you're doing it for both types in one pass. If your expected values are:

  • A->B 5 gold, 5 bronze
  • B->C 8 gold, 10 bronze
  • C->D 10 gold, 7 bronze

Your totals are 23 gold and 22 bronze. If you started with 23 or more gold and 22 or more bronze, you're done. You know that a feasible solution exists. More likely, your expected totals will be greater than your coins available.

In that case, make a choice between expected value pairs versus considering both options. If you're short on gold, spend bronze where it returns the most gold. For example, if I start with 13 gold, I can select the bronze payment option between C->D to create a feasible solution. If I start with 5 bronze, I can select the gold payment option between B->C and C->D to create a feasible solution.

Again, that's probably wishful thinking. It's likely you'll be short both gold and bronze. If that's the case, start with a heuristic to resolve expected values: if you have a larger gold deficit, select expected values that yield the greatest savings in gold before resolving bronze, try to make up the deficit with the fewest "choices" possible, etc... In the end, you may still have to try every combination of expected values to prove a feasible solution does or does not exist.

Note that this doesn't account for tolls that involve both currencies. A toll of 2 gold and 5 bronze ruins my expected value trick.

Corbin March
  • 8,104
  • 3
  • 37
  • 39
1

If your traveler had to return to the start it would be a variation on the http://en.wikipedia.org/wiki/Travelling_salesman_problem. As is, it's just a path optimization problem. I'd tackle it using Depth First Search, but that's because it's one of only two or three graph traversal algorithms I remember from grad school.

Dan Pichelman
  • 13,773
  • 8
  • 42
  • 73
1

It's just a shortest/minimum-cost path problem stated as a decision problem. But with a 2 dimensional cost. Is there a path that costs less than x gold coins and less than y bronze coins?

That makes the problem a lot harder to solve in the general case, as there can be a huge number of potential optimal (gold, bronze)-cost pairs per node. The real challenge in this is dealing with the 2-dimensional cost, the graph search is part is just there to tell the story. It could be any kind of optimization.

Patrick
  • 1,873
  • 11
  • 14