Episode 149: CityStrides.com, Graph Algorithms and More! #40
Replies: 2 comments 1 reply
-
I think CityStrides is the Clustered Orienteering Problem FWIW |
Beta Was this translation helpful? Give feedback.
-
You also might want to do a preprocessing where you contract one of the edges that are connected to a degree 2 vertex. Ie for a vertex that has only one "in" edge and one "out" edge, then the first or second edge is contacted. As you mentioned, these edges complicate the algorithm but don't have any additional meaning. Additionally, you told Bryce that the weight idea doesn't make sense because of these extra edges. I would argue once you contract these extra edges, you could add weights to the edges that encode the distance. And then you could the do a greed optimizing based on these weight. Cheers |
Beta Was this translation helpful? Give feedback.
-
Episode Link: https://adspthepodcast.com/2023/09/29/Episode-149.html
Feel free to write comments or ask questions 🙂
Beta Was this translation helpful? Give feedback.
All reactions