8 Puzzle Problem using Manhattan Distance in Artificial Intelligence
ฝัง
- เผยแพร่เมื่อ 24 ก.ย. 2020
- The 8-puzzle problem is a puzzle invented and popularized by Noyes Palmer Chapman in the 1870s. It is played on a 3-by-3 grid with 8 square blocks labeled 1 through 8 and a blank square. Your goal is to rearrange the blocks so that they are in order. You are permitted to slide blocks horizontally or vertically into the blank square. We can use any one of the following Heuristic Functions: Hamming priority function: The number of blocks in the wrong position, plus the number of moves made so far to get to the state. Intuitively, a state with a small number of blocks in the wrong position is close to the goal state, and we prefer a state that has been reached using a small number of moves. Manhattan priority function: The sum of the distances (sum of the vertical and horizontal distance) from the blocks to their goal positions, plus the number of moves made so far to get to the state. A critical optimization: To prevent unnecessary exploration of states, when considering the neighbors of a state, don't explore the neighbor if its board position is the same as the previous state.🔗Important Playlists:
Artificial Intelligence: th-cam.com/users/playlist?list... Learning: • Machine Learning
🌐Join our community:
Android App(Notes+Videos): play.google.com/store/apps/de... Facebook: / thinkxacademy Twitter: / thinkxacademy Instagram: thinkxacade... #artificialintelligence #heuristics
can i ask? what would i choose if i have the same M Values?
If you get the same manhattan distance which is highest among all the paths, calculate the manhattan distance for the next state of the paths with same manhattan distance and then choose the minimum. Another way is to merge the paths of same manhattan value into one and proceed with the algo.
@@ThinkXAcademy Thank You!
Awesome tutorial, thank you!
Welcome sir😄
Thank you so much
This really helped me when I was working on an assignment. Thanks!!
That's great! Share our content with others to help this channel grow💯
What happen when all possible node value is equal the where to go?
well explained !, thank you!
Share with other students also💫
You save my day! THX bro
Keep Learning 🌟
thanks a lot bro
Nice explanation sir tq sir 👍 😊
Good video, thank you.
Thanks😃
brilliant explanation
Thank you😄 Keep Learning ✔️
Thank you.
Keep Learning 💯
Suggestion - Go a bit faster, it's great but I had to watch it at 1.5x speed
Could you generalize this technique to play any game optimally that would lend itself well to various states where an m distance calculating function could be used?
I will create a separate video for that soon✔️👍🏻
@@ThinkXAcademy That would be great, thank you very much!
I have a doubt regarding the code implementation of this. What should I do when all the possible branches were already visited but the solution hasn't been found yet? Should I try a different heuristic?
No, try a different source to start the algo.
Hey nice explanation there! Quick q, why is this heuristic preffered to the missing tiles one?
manhattan distance
Sear how we implement this algo , what can of data structure used ?
Priority Queues
I used the same methods but just using the manhattan distance causes the program to go into infinite loops for certain cases. Will like to hear the solution for this.
you will have to learn on how to write conditions that stops the loop and return the result
Made my task easy❤🎉
ThankYou very much 👌👌
Please share our videos to help this channel grow🌟
thank u soo much but there is notice u have said that the first box has only 3 new possibility and the forth one will return us to the same original box so it should be eliminated but u forgot to do it for the remaining boxes ,
with the same implemented method there should be only one new possibility for each of the 2 remaining boxes
yes we can avoid repititive boxes
Thanks
Keep Learning ✨
thanks alot
keep Learning 💯👍🏻
slowest pace to the point I have ever seen in a video. consider using a heuristic to get to the goal point faster
Helpful
Thanks😄
Hello doctor, can I communicate with you?
yes doctor
thanks
Share and Subscribe🌟
there is so much lag in is there in you tutorial try to avoid it
I am sorry i didn't have a good smartphone back then so there was lag, i have upgraded now and content is also improving👍🏻
you are taking non solvable example bro
This example can not have solution
Can you say "Pubg mobile" for me?
Pubg Mobile