# City exploration algorithm

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.

• 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, 2014 at 1:32
• @Snowman Can you elaborate, what you do understand? Aug 15, 2014 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, 2014 at 1:49
• @Snowman I updated my question. What is backtracking? Aug 15, 2014 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, 2014 at 2:02

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.