CODEWITHSUNDEEP
algorithmgraph-algorithm
Raj Rao
Raj Rao

Reputation: 9148

Dynamic graph algorithm shortest path

I have a problem which I am converting into a TSP kind of problem so that I can explain it here and I am looking for any existing algorithms that might help me.

  1. There are a list of places that I need to visit and I need to visit them all.
  2. There are some places that have to be visited as the first x of n (IE, they need to be first 3 or first 5 places visited). (where the number is arbitrary)
  3. There are some other places that have to be visited as the last y of n (IE, they need to be last 3 or last 5 places visited).
  4. The places are could be categorized (some may not have a category), for those in a category, they need to visited as far away from each other (ie, if 2 places are categorized as green, then I would like to visit as many other category places as possible between these green categorized places)

Here is an example list:

A: category green: last 3

B: category none: ordering none

C: category pink: first 3

D: category none: ordering none

E: category none: last 3

F: category green: ordering none

G: category pink: first 3

The order I would like to come up with is:

G(pink,first3) -> F(green,none) -> C(pink,first3) -> D(none,none) -> B(none,none) -> E(none,last3) -> A(green,last3)

Explanation: G came first, to keep it as far away from C as possible. F came next to keep it as far away from A as possible. C came next as it needed to be in first 3. C and G could be interchanged D B could be placed anywhere E came next as it had to be last 3 A came last as it had to be last 3 and by placing it at the end, it was as far as possible from F.

My idea is to evaluate each edge cost and the edge cost would be dynamically calculated. So if you tried to visit A and then F it would have a high cost, as opposed to visiting A and then some other place and then F (where the number of places in between would some how be part of the cost). Also, I would introduce a start and end place and so, if I had to visit some places as first x, I would be able to give it a low cost if start was within N places of that place. Same for the end.

I was wondering if there is a graph algorithm that can account for such dynamic weights/cost and determine the shortest path from start to end?

note: In some cases a best case may not be available, and that would be ok, as long as I can show that the cost is high because there wasnt enough category separation (eg: all places were in the same category).

Brute force algorithm Initial idea I had is: Given a list of places, come up with all combinations of place ordering and calculate the costs between each and then choose the cheapest. (but this would mean evaluating n! where for 8 that would be 362880 orders that i would have to evaluate! why 8, cause that is what I believe will be the average number of places to evaluate)

But is there an algorithm that I could potentially use to determine it without testing all orderings.

Upvotes: 0

Views: 78

Answers (1)

Stefan Haustein
Stefan Haustein

Reputation: 18813

One thing you could do:

  • Order the places as follows: first 1, ... first n, unordered, last n, ... last 1.
  • Go through the list and separate elemnts with the same color where possible without violating the previous order
  • Calculate the cost of this list and store it as the current best
  • Use this list to determine the order in which you evaluate permutations
  • While you build permutations, keep track of the cost
  • Abort building the current permutation when the cost exceeds the current best (including the theoretical minimum cost for the remaining places, if there is any)
  • Also abort when you have the theoretically possible best score.

Upvotes: 1

Related Questions