search

codereport / city-strides-hacking

Python scripts that build optimal routes for node collection
MIT License
8 stars 3 forks source link

ADSP 149 #10

Open CharString opened 11 months ago

CharString commented 11 months ago

That discussion had more turns and bends than the mean output of your current algorithm. I went from "Yes Bryce, tell him to get his graph theory up to snuff." The distances, are the weights. He needs to prune the nodes that pose no choice, keep just the intersections (which naively are the vertices with exactly 2 edges, but some ways change name halfway, so some checks have to be done for Toronto, as you don't want to prune any such public way). But than Bryce failed to see the difference between the solved shortest path from A-B problem (Dijkstra or A* if you have some useful heuristic) and your NP-hard problem. And when you mentioned your first implementation was in Python I just had to point you to this Python sketch: https://www.youtube.com/watch?v=VI4q4ShXNYw

codereport commented 11 months ago

That discussion had more turns and bends than the mean output of your current algorithm. I went from "Yes Bryce, tell him to get his graph theory up to snuff." The distances, are the weights. He needs to prune the nodes that pose no choice, keep just the intersections (which naively are the vertices with exactly 2 edges, but some ways change name halfway, so some checks have to be done for Toronto, as you don't want to prune any such public way). But than Bryce failed to see the difference between the solved shortest path from A-B problem (Dijkstra or A* if you have some useful heuristic) and your NP-hard problem. And when you mentioned your first implementation was in Python I just had to point you to this Python sketch: https://www.youtube.com/watch?v=VI4q4ShXNYw

Lol, this is definitely going to be mentioned in our next recording. Note that a couple things I failed to highlight is because a "completed street" might consist of multiple segments, "weights" don't really make sense. A segment isn't worth anything unless you complete every segment in the street, so a weighted graph really doesn't make a lot of sense. Also, if I "prune" the nodes, it would have be to a bidirectional things because I need all the nodes to know how to travel the run path. It is already tricky enough with all the doubling back etc.