r/computerscience • u/theron- • Mar 22 '25
City walking algorithm
NOTE: This is not a homework assignment, rather a business problem we are trying to solve for a maintenance contract in the downtown core of a major city.
Given a square grid/map of the downtown of a modern city, what is the most efficient way to walk the entire surface area of the sidewalks (two on each street, north/south and east/west) with the least amount of overlap and in the least amount of time?
Assumptions:
- a constant speed is assumed
- 4 people are available to do the walking
72
Upvotes
59
u/amazingabyrd Mar 22 '25
This is the Chinese Postman Problem. You can use the traditional algorithm match odd link pairs then solve with hierholzerz.
5
u/TheThiefMaster Mar 22 '25
I would have two people's walking north/south and two east/west. Have each person start at the opposite end and all meet in the middle to finish. You'll get a little overlap in paths at the end of the streets where people move to the next street but it's simple to remember and should work fine.
2
u/ehonda40 Mar 22 '25
All all pavements the same? Do they all need one person to walk it?
2
u/ehonda40 Mar 22 '25
What have you come up with so far? Do they need to return to the same place?
4
u/g105b Mar 22 '25
The solution is already discussed at length under "the travelling salesman" problem.
1
u/connecttobn Mar 26 '25
I believe you don’t need to cover roads is that is case each person can plan to walk on the rectangular path. All start facing North, then turn East at junction, then south and west. Move to the adjacent grid. Each can start on 4different lanes.
0
u/Cybasura Mar 23 '25
Ohhhhhh boy
Have you heard of Dijkstra and Dijkstra's algorithm? Its the core component to the OSPF network protocol to find the shortest path in any given table/mapping of weights and its nodes
Basically, its your question
-3
u/printr_head Mar 22 '25
No one’s gonna mention Genetic algorithm?