Great observation. The solution to the update problem is relatively simple. It doesn't do a search again on update. Instead everytime it encounters an update in what it knows, it just changes the data stored in memory. All it is doing is updating its learned representation. After this it still knows what the other obstacles are without having to do DFS or BFS again. If the solution was a graph, it just deleted a edge it still knows what all the other edges are. If it encounters another change it updates the state of the graph again.
With regards to Neural Networks, if they are given a reward function, which can be dynamically evaluated (in this case did I reach the end or not) they are pretty good at learning without feedback.
You make it sound simple, but from my point of view the ability to update one's
learned representation requires a representation that can withstand being
updated. I mentioned John McCarthy's concept of "elaboration tolerance" in
another comment, i.e. the ability of a representation to be modified easily.
This was not a solved problem in McCarthy's time and it's not a solved problem
today either (see my sibling comment about "catastrophic forgetting" in neural
nets). For shannon's time it was definitely not a solved problem, perhaps not
even a recognised problem. That's the 1950's we're talking about, yes? :)
Sorry, I didn't get what you mean about the dynamically evaluated reward
function.
With regards to Neural Networks, if they are given a reward function, which can be dynamically evaluated (in this case did I reach the end or not) they are pretty good at learning without feedback.