@@kimbokjay H is the distance between its current state to the goal state. so it needs to travel to bottom right. that's 3 moves. right down down. or you can go down down right. same thing. So H should be 3 here not 2 as shown on the video
the left child of the root should have a score of 4. G = 1 H = 3. the right child of the root is correct. Remember you don't count the empty space towards your heuristic because you always want your heuristic score to always be an underestimate. This guy does a pretty good video explaining why. th-cam.com/video/6TsL96NAZCo/w-d-xo.html
1:23 Two very important value Cost(number of steps taken to current state) 1:32 Estimate distance from current state to goal state 1:39 Manhatan distance 垂直距離 加上 水平距離 2:23 H value is the total Manhattan distance of all vertex except for empty vertex 2:37 A star search uses the sum of G and H as a score to determine which go next
I tested with these input values and the algorithm failed to solve: board = [[8, 5, 2],[7, 6, 4],[0, 1, 3]] Waited about 10 minutes and was not able to find a solution. But other entries less shuffled he solved quickly. Thanks for sharing, it helped to improve my college work.
late reply, but for anyone with similar question: these puzzles basically have 2 possible shuffle states: solvable and unsolvable. Basically, if you just switch 2 neighboring tiles (for example [[1, 3, 2], [4, 5, 6], [7, 8, 0]]), the puzzle becomes impossible to solve. The same applies to the example you've given. When I switched 1 and 3 (since they're neighboring), the solution was identified. Yes, it would be nice to add a feature that would prevent the program from endlessly trying to solve an impossible puzzle. But since we're practically given the whole code, I consider it a suitable challenge for everyone who wants to really understand how this program works to do that on their own.
Your code is slow and inefficient. You can solve 8-puzzles with A*, or IDA, but this approach starts to fail terribly once you want to solve bigger puzzles. Also, Manhattan distance alone is not sufficient as a heuristic when using A*
One of the best explanation i have found in internet so far
Great explanation, thank you! I also could relate a lot when I saw the the clock, lol. There ain't no rest for coders.
Big thanks. It's a best reference that i ever seen for my A* algorithm task
@2:46 I think the manhattan distance should be 3 as the empty space needs to move one to the left then two down, therefore f should be 4.
I'm still confused about this step. Shouldn't be the the H value be 1? Cause the #2 just moved once, going to the right.
Same, I was going to comment the same Oamar
@@kimbokjay H is the distance between its current state to the goal state. so it needs to travel to bottom right. that's 3 moves. right down down. or you can go down down right. same thing. So H should be 3 here not 2 as shown on the video
@@danteeep Yeah, that's where I was confused because it should be 3 and the video shows 2.
the left child of the root should have a score of 4. G = 1 H = 3. the right child of the root is correct. Remember you don't count the empty space towards your heuristic because you always want your heuristic score to always be an underestimate.
This guy does a pretty good video explaining why.
th-cam.com/video/6TsL96NAZCo/w-d-xo.html
Thanks for sharing the code. It really helped me!!
Excellent Tutorial! You saved the day :D
Nice video. Please upload more!!!
1:23
Two very important value
Cost(number of steps taken to current state)
1:32
Estimate distance from current state to goal state
1:39
Manhatan distance
垂直距離 加上 水平距離
2:23
H value is the total Manhattan distance of all vertex except for empty vertex
2:37
A star search uses the sum of G and H as a score to determine which go next
What is the difference between branch and bound method and A* for solving this problem?
Excellent tutorial!
thank you so much! this was so helpful
Thank you very much. You explained it very well
it helps a lot, thank you very much!!
I tested with these input values and the algorithm failed to solve:
board = [[8, 5, 2],[7, 6, 4],[0, 1, 3]]
Waited about 10 minutes and was not able to find a solution.
But other entries less shuffled he solved quickly.
Thanks for sharing, it helped to improve my college work.
late reply, but for anyone with similar question: these puzzles basically have 2 possible shuffle states: solvable and unsolvable. Basically, if you just switch 2 neighboring tiles (for example [[1, 3, 2], [4, 5, 6], [7, 8, 0]]), the puzzle becomes impossible to solve. The same applies to the example you've given. When I switched 1 and 3 (since they're neighboring), the solution was identified.
Yes, it would be nice to add a feature that would prevent the program from endlessly trying to solve an impossible puzzle. But since we're practically given the whole code, I consider it a suitable challenge for everyone who wants to really understand how this program works to do that on their own.
@@richardmedzihradsky7952 nice work🤝
Best explanation on TH-cam
Thanks Jinyue !! Thanks a lot
Thank you. Great job
This is AWESOME!
Great explanation ❤
thanks for the code very cool
Great vedio
Thanks alot , nice explanation, best Regards :)
how to set the goals?
What happens if the manhatten distance is same for two cases?
It will start exploring the first one, if it fails (I mean it ends up into a blind alley) then it will start rollback into past options.
thanks
Thanks
What if 2 paths have the same distance?
I think you pick the one on the left
Goated
AttributeError: module 'time' has no attribute 'clock' Shows This Error
good for just explaining the basics and nothing else
What G represent , i did not actually get it
G is the cost of the node
@@tonyli5851 I don't get it too, It seems irrelevant since it's the same for every node to be compared in each traverse.
help
Your code is slow and inefficient. You can solve 8-puzzles with A*, or IDA, but this approach starts to fail terribly once you want to solve bigger puzzles. Also, Manhattan distance alone is not sufficient as a heuristic when using A*
I love Chinese Taiwanese