Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Assignment 4: Solution Heuristics
Regarding the presented heuristics in the solution. Won’t both heuristics be fooled by an initially fruitful looking subtree? Asking in terms of optimality … (see attatched image)
Attachment:
20190202_230559.jpg: https://fsi.cs.fau.de/unb-attachments/post_159366/20190202_230559.jpg
Yes. Initially. But the deeper the heuristic explores the promising path, the more it will cost. So it will start looking for cheaper paths than the ones it already traversed. E.g. at depth X+1 (at most) the heuristic will start searching the unexplored paths, because costs are the same as going deeper inside the already half-explored ones. And finally it’ll settle for the better path. Just try a test run with a small tree. When do you think will the heuristic stop exploring the right side in your example?
“Success is not final, failure is not fatal: it is the courage to continue that counts.”
– Winston Churchill
I copied that from a google search to look smarter.
3 „Gefällt mir“
Thank you for the answer - if I understand correctly, A* will start exploring the left side of my example tree as soon as it is through the cherries (level X+1). It will stop proceeding on the right side and focus solely on the left, as soon as the left side has turned up at least one cherry more than the right side has. Is my assessment accurate?
“You can’t connect the dots looking forward; you can only connect them looking backwards.”
- Steve Jobs (but probably not in the context of tree traversals … )
It depends on the exact heuristic, but if you think of cherry-nodes as free travel and all non-cherrys as costly, then the heuristic will (in your example) be done with the right side as soon as it realizes that there’s even one cherry on the left. How about the most stupid heuristic: it just knows the cost up to that node.
Let’s say the current cost we can afford is 0 (we are students after all). Then we’ll be able to traverse the beginning of the right side pro bono. Cherrys are free after all. How far do we get on the left? Well… not even one node. Capitalism is in the way. But that’s what friends are for, innit? So we borrow some cash from our best friend and see how far we can go with one money. On the right side… one node farther than we already could. Left? Just one node. That’s not helpful.
Now how about if we get a job as a TA in our favourite AI-Course. Our budget increases slowly. Now we have X money. Aww yiss. Lets search further. Right: we get to depth X+X = 2X. Left: we get to depth X, as any single step down is oh so expensive.
Assume that the left path has cherries starts at depth 2X. If we double our work-hours at the job and do some tax evasion, we might get enough… Aah we’re just one short. 2X-1. Curse these delicious cookies they sell on the way to work. Or are we?
So on the right we’re reaching as far down as 3X-1 (and we really searched every nook of that subtree down to that level). When we go one step further, our heuristic tells us we’re over budget and should stop before being engulfed in crushing debt, leading to another financi… you get the point (the real reason is that we know there MIGHT BE a better way on the left subtree as the heuristic is a very positive thinker). On the left we’re greeted with a different outcome. Upon reaching depth 2X-1, for which we had to pay at every single downwards step, we have exhausted our whole budget. Now we go one step further, because we’ll only stop when we go over budget and there’s a chance that the next stop will be free. Can’t get worse than the right subtrees cost at depth 3X, right? Now we go down a step. We didn’t go over budget… let’s try again. Same thing. And again… we reach the end without spending a single penny more than we did before reaching the first cherry.
There are of course better heuristics, which are all just cheating in a way. The heuristic is just a guy telling you the most optimistic outcome as far as he can see. The one we used is just telling us what we already know, to be precise:
We ask: “What’s the best outcome if I continue with the path from this node onwards”
Heuristic answers: “The cost it took to get here.”
If the path ahead only yields cherries, he’s right. So we trust him. This is the most “optimistic” heuristic.
We could tweak it so it considers the children of a node. That means if we ask now, he’ll return the cost up to him + the most promising child-cost. As the heuristic now knows a bit more, it can give a slightly better answer. In our example this might not help much, in fact it just saves us one deoth level of searching before finding a best path.
Now we can imagine having a heuristic that just knows the whole tree. So it can precisely determine the true cost to the end for every node. This is major cheatage. But it’s what we call h*. The most accurate heuristic.
Why even bother? For many problems there’s sweet spot between h* (whose calculation includes the problem we’re trying to solve (i.e. finding the shortest path) so that’s stupid) and the dtupid one we used. The overhead of calculating the heuristic is worth it in those cases.
I apologize, this is way longer than I expected. But explaining is also just heuristics when I think about it. Hmm…
2 „Gefällt mir“
I am amazed!
Thank you for educating and entertaining me 