@@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. ua-cam.com/video/6TsL96NAZCo/v-deo.html
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.
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
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*
Great explanation, thank you! I also could relate a lot when I saw the the clock, lol. There ain't no rest for coders.
@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.
ua-cam.com/video/6TsL96NAZCo/v-deo.html
Big thanks. It's a best reference that i ever seen for my A* algorithm task
Can I get the code for implementing the tree structure
One of the best explanation i have found in internet so far
Nice video. Please upload more!!!
Great explanation ❤
Thank you. Great job
thank you so much! this was so helpful
it helps a lot, thank you very much!!
What if 2 paths have the same distance?
I think you pick the one on the left
thanks
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
good explanation. Much appreciated
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🤝
Excellent Tutorial! You saved the day :D
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
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*
Thanks Jinyue !! Thanks a lot
AttributeError: module 'time' has no attribute 'clock' Shows This Error
What is the difference between branch and bound method and A* for solving this problem?
Thank you very much. You explained it very well
thanks for the code very cool
Best explanation on UA-cam
Thanks alot , nice explanation, best Regards :)
how to set the goals?
Thanks
Goated
Great vedio
Thanks for sharing the code. It really helped me!!
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.
Excellent tutorial!
This is AWESOME!
I love Chinese Taiwanese