It basically sorts the inserted nodes with a key and when asked to retrieve a node, the node is requested with that key. I kept that history in a Sorted List structure of C#.
Otherwise, the search space unboundedly expands and solving even the easiest puzzles becomes a burden and sometimes impossible. While solving this puzzle, a history of opened states should be constructed. Although finding that two step loop is very easy, some larger loops are not trivial to detect. The smallest loop is constructed at only two steps, i.e., moving a tile forward and backward. However, sliding puzzle has a very loopy structure. In other words, it is one of the simplest problems to realize in the computer environment. It is a deterministic, episodic, and fully observable problem. Sliding puzzle requires an agent to solve the problem, which is the program written by us in that take home examination. Among these algorithms, A*, IDFS, and BFS give optimal paths, on the other hand, DFS is not optimal in the sense of detecting the shortest solution path. In this take home examination, we were asked to implement Breadth First Search (BFS), Depth First Search (DFS), Iterative Deepening Depth Limited Search DFS (IDFS), and A* algorithm with “Misplaced Tiles Heuristic” (A* Mis) and “Total Manhattan Distance Heuristic” (A* Man) on an adjustable size “Sliding Puzzle”. The very basics of almost anything related to AI can be found in the book of Steward Russell and Peter Norvig “Artificial Intelligence: A Modern Approach”. In this report I will be explaining the details of my solution algorithms, implemented programs, and the results I have concluded. So learning their concept and being able to implement them are extremely crucial to do more advanced research on AI. A* with Manhattan Distance Heuristic (A* Man)īasic search algorithms constitute the fundamentals of Artificial Intelligence (AI). A* with Misplaced Tiles Heuristic (A* Mis) Iterative Deepening Depth Limited Depth First Search (IDFS)
0 kommentar(er)
