1

The purpose of the algorithm is to create n routes on a geographical map, where n is being given, whereas all routes take no longer than t time units by foot and end where they start, while trying to have as little overlap as possible, meaning the user walking the routes walks on as few streets twice or more often as possible.

The software is to calculate closed routes (starting point = ending point) while the length of the routes should equal the time t. Another restriction is that each street should be walked along as few times as possible to always explore new areas while walking for the same time period.

Example:

You are in New York City (google maps for an example map)

  • You want to walk for 40 minutes.
  • You want to be on new roads or paths as often as possible.

Picture having a thread. The thread has a length of velocity_walking * t in a smaller scale. Now you glue the end and start to a starting point on your map, lat and lon. Then you move the thread so it is only on streets/walking paths, without being on the same street twice.

Now you take another thread and glue the end and start to a starting point on your map, lat and lon. Now you do the same thing as above, trying to not put it over the other thread.

You repeat this n times, all in all, so given the first two threads, you repeat it n-2 times.

So the steps are

  1. Enter n
  2. Enter t
  3. Enter the starting point in lat and lon
  4. Create n routes that take t time units to walk by foot, start and end in lat,lon and if possible don't contain the same streets or parts of streets twice.

My idea:

Having a circle of radius equaling walking_velocity * t / 2. Plan routes from start to point on circle to start.

Disadvantages:

  • Same streets to the circle's circumference and back.
  • Many streets are omitted.

What is the better algorithm to do this? Language does not matter, algorithm matters.

  • I am not sure I understand your algorithm. Could you please describe it in more detail? – user22815 Aug 15 '14 at 1:32
  • @Snowman Can you elaborate, what you do understand? – Timo Theobald Aug 15 '14 at 1:46
  • For one, it is not an algorithm because there are no steps. How do you plan? How do you make decisions? Backtracking, if any? – user22815 Aug 15 '14 at 1:49
  • @Snowman I updated my question. What is backtracking? – Timo Theobald Aug 15 '14 at 2:01
  • @TimoTheobald Wikipedia says: "Backtracking is a general algorithm for finding all (or some) solutions to some computational problem, that incrementally builds candidates to the solutions, and abandons each partial candidate c ("backtracks") as soon as it determines that c cannot possibly be completed to a valid solution." – user40980 Aug 15 '14 at 2:02
1

This might not be the most efficient, but it would be a good starting point. I think any better algorithm would be an optimization or simplification of this one.

Set up the problem

  1. Convert the geographical map into a graph. Intersections are nodes, streets or other footpaths are edges.
  2. Each edge has a cost which is the time required to traverse that edge.
  3. Each edge tracks the number of times it has been traversed.
  4. Pick a starting node.
  5. Choose a desired time (cost) at which a route terminates.
  6. The algorithm will have a running total of the cost accrued from traversing the previous nodes. This cost starts at zero.

Traversing the graph

  1. At any given node, evaluate the edges connected to it. If the cost of an edge plus the current accrued cost is greater than the terminating cost, that edge is removed from consideration. If the algorithm backtracked from an edge, remove that edge from consideration.
  2. If there are no edges to consider, backtrack and remove the cost of the backtracked edge. If the total cost is zero (i.e. at the start node with nothing traversed), the algorithm terminates.
  3. Of the remaining edges, pick one to traverse and repeat the algorithm.

Analysis

This is essentially a basic search tree algorithm which includes costs for each edge. Note that it also does not forbid traversing forward backwards, meaning going from node A to B and back to A without backtracking. That might actually increase the total amount of distance covered if B is a dead end and the cost is low compared to other edges.

  • I have to think about this tomorrow. – Timo Theobald Aug 15 '14 at 2:19
  • I came to the conclusion that the challenge is too high. Please give me a structure in c# I can build on. – Timo Theobald Aug 18 '14 at 19:05
  • This site is about conceptual problems in computer science, not concrete code. I gave an algorithm. – user22815 Aug 18 '14 at 19:07
  • Did you reply to help me? If yes, I found that I cannot put it into code. So if you don't share a basic frame to start from, you wrote it in vain and did not help me. – Timo Theobald Aug 18 '14 at 23:22
  • I am explaining that this site is not about working code and programs, it is about theory and design. If you need a working code example, Stack Overflow is the place to go. If you want an algorithm that could be put on a whiteboard, this is the place to be. – user22815 Aug 19 '14 at 4:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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