Q: can we copy and paste the previous assignment's simpletest framework in our project or do we have to make our own testing mechanism
A1: yeah thats fine
A2: You can use the blank project from the course website (Qt Creator link), too, and it has the testing framework built-in
Q: all the fields in a struct are automatiically public, right?
A1: yes, essentially
Q: fields and functions
Q: does it compute this path on your computer, or it it done on google servers?
A1: On their servers
A2: Most likedly on googles servers (https://developers.google.com/maps/documentation/directions/overview)
Q: Is there a mathematical way of seeing when the greedy algorithm fails? (at least in terms of coins?)
A1: For coins, whether the greedy algorithm is globally optimal is dictated by divisibility of the coin values
Q: In an implementation of dijkstra’s would we put INT_MAX for infinity?
A1: Sure, that woudl be a good choice
Q: when this is implemented in practice in maps, how does it restrict the nodes to find the distance of so that its not searching over a really large number?
A1: live answered
Q: do ride-sharing apps and shipping companies just use this or are there other optimizations / heuristics that would make this more efficient
A1: There are some clever optimzations (I believe Chris will talk about A-star) but Dijkstra all on its own is quite efficient way to do this
Q: Do we mark each node as visited after or before enqueuing its neighbors?
A1: I don’t belive it should matter
Q: idk if he already mentioned this, i stepped away for a hot sec, but can this end up being a recursive call to continue to repeat the process and backtrack to explore the option? or is that too memory consuming
A1: Yes, he did discuss depth-first search as an option, but the problem with that going deep on the wrong path can be wasteful…
Q: How do we determine who to look at next, again? Chris mentions that it’s not always the first one…
A1: live answered
A2: The unvisited node with shortest distance
Q: Why did we not update F from D or E?
A1: He is about to do it right now, stay tuned
Q: WHy haven’t we visited D? It says previous there
A1: the previous doesn’t indicate it is visited, just that we have enqueued it
Q: Why didn’t we consider going from G to C, just because C has already been visited? Couldn’t the path SJ->B->G->C be quicker than SJ->B->C (the existing path)?
A1: We have not yet procesed from G, hang on…!
Q: what if two paths to a node had the same length
A1: live answered
Q: how do you make sure you’re not doing circles back to the starting point?
A1: You keep a set of visited nodes
Q: what’s the big O of this? Is it O(n) where n is the number of nodes, because you’re only visiting each node once, but you must visit every node?
A1: Graph algorithms often depend on both number of vertexes and number of edges, for each node for all edges = O(VE)
Q: if you find two paths with the same value, which path would it return? Or I guess, I am just curious if there’s an order in which it would return or if it would be random?
A1: Probalby would come down to on how your priority queue handled tie-breaking among entries with same priority
Q: sorry, i meant to ask how would you update the previous node if two different nodes have paths with the same distance to it
A1: It would be valid to use either.
Q: but in real life where there’s billions of node, does it check every single one it hasn’t visited yet??
A1: live answered
Q: does this also store the previous paths possible under different conditions? for instance, if you wanted to avoid tolls the path would be longer
A1: live answered
Q: Is the Big O here O(E log V) because we go over each edge once and for each edge we enqueue into a priority queue of length max V?
A1: live answered
Q: Why is the maximum length of the priority queue V?
A1: In Chris’s version, he is storing only one entry per node, other approach store all the paths which can get very large
Q: if there’s a path between H and J with weight 0.5, would A* miss it
A1: No
Q: that’s pixels as the crow flies?
A1: yes
Q: How do you initialize the distances to inf?
A1: live answered
Q: this only works if your nodes also exist in some space with a distance function right, like if all nodes are associated with a position or latitude longitude on google maps
A1: live answered
Q: why does overestimating the cheapest path cause sub-optimal solutions?
A1: live answered
Q: because pixel distances are being used, does the graph always have to be drawn out by the computer?
A1: “pixel distance” is not really a thing here, it is proxy for crows-flies distance (i.e. GPS coords)
Q: For this path finding algorithm, is the heurustic "direction" recalculated at each step for the direction from the current location to the end?
A1: live answered
Q: can there be multiple heuristics?
A1: live answered
Q: how do pathfinding algorithms work in video games where the end point (usually the player) changes position frequently? do they follow the current path as they look for a new one?
A1: live answered
Q: With A*, is it possible that you need to revisit an already seen node?
A1: No, nodes are still marked as visitied under the same constraints
Q: Could you go over how to calculate the heuristic again?
A1: live answered
Q: Does google consider each residential address as a new node, or is each street considered a new node with a certain weight?
A1: live answered
A2: In general, the nodes are intersections
Q: how would you include multiple goals within your route? Like how Teslas give you routes that stop at charging stations. Do they break up the trip into chunks and then just calculate it independetly?
A1: live answered
Q: how do different heuristic algorithms influence A*?
A1: Better, more accurate heuristics will cause the algorithm to terminate more quickly. If you use an inadmissible (overestimating) heuristic then its also possible for A* to be unable to find the hsortest path
Q: What is the big O for BFS?
A1: live answered
Q: are there rare cases where A* and Dijkstra's do not find the abosulte shortest path?
A1: live answered
A2: Dijkstra’s wil lalways find the shortest path. A* will as well as long as you have an admissible (underestimating) heuristic
Q: what if your graph isnt configured nicely and doing a pixel distance hueristic gives an illusion that some nodes will be more optimal when they don't help at all
A1: live answered
Q: what is IDA* and why is it freezing every time I try to run it
A1: live answered
Q: how do you mathematically find out when a heuristic is overestimating?
A1: live answered
Q: on similar terms, how do you determine how much the hueristic contributes to the final "cost"?
A1: live answered
Q: What if we wanted to find the shortest paths from any node to any other node? Would we run Dijkstra’s Algorithm for each node?
A1: live answered
A2: Look up floyd-warshall all-pair shortest path — neat stuff!