Skip to content

Latest commit

 

History

History
78 lines (66 loc) · 4.3 KB

README.md

File metadata and controls

78 lines (66 loc) · 4.3 KB
Raw

State Space Search

Student: Michael Nugent
Course Number: CSCI 164
Course Name: Artificial Intelligence
Term: Spring 2022
Course Professor: David Ruby
College: CSU, Fresno
Description: This is a C++ implementation of various state space search algorithms within a puzzle slider domain. A JavaScript attempt was made, but proved too slow in the algorithms' infancy. Perhaps now in maturity, it might handle them better since imlemented heuristics, and achieved optimality decreased run-time. Since JavaScript is 7-10 times slower than C++, its advantage is the visualization of and interaction with the puzzle slider, whereas C++ is better for difficult problems.

Provided Project Instructions

In this assignment you will explore State-Space Search with the 8-Puzzle and 15-Puzzle. You will need to implement and provide code for the following algorithms:

  • Breadth-First Search
  • Depth-First Search
  • Iterative-Deepening Depth-First Search
  • A* w/ Out-Of-Place, and Manhattan Distance Heuristics
  • Iterative Deepening A* w/ Out-Of-Place, and Manhattan Distance Heuristics

Develop search code with requirements:

  • Input puzzle as a two strings, initial state and goal state.
  • Produce the solution as a string of "udlr" representing the move "up", "down", "left", and "right" for the movement of the blank.
  • Produce the number of expanded nodes required to find solution.

In addition, develop code to test a solution with requirements:

  • Input initial puzzle state as string.
  • Input move sequence as string.
  • Produce output state from applying move sequence to initial state.

Provide link to Github repository with all code, and submit final report as PDF with requirements:

  • Provide overview of your code.
  • Provide results for the following problems:

8 Puzzle

Start State Algorithm Nodes Expanded Clock Time Solution Solution Length
160273485 IDA* 735 0.006 seconds DDLUURDLLDRRUULDRD 18
462301587 IDA* 2139 0.008 seconds RDLURULLDRDLURULDRRULDDR 24
821574360 IDA* 9863 0.029 seconds LURULLDRRDLLURDRULULDDRUURDD 28
840156372 IDA* 1340 0.004 seconds DLLURDLDRRULLURDDRUULDDR 24
530478126 IDA* 4265 0.011 seconds DLDLURDRUULLDRDRULULDDRR 24
068314257 IDA* 276 0.001 seconds DRRULLDRDLURDRUULDLDRR 22
453207186 IDA* 161 0.001 seconds RDLUULDDRUULDRDR 16
128307645 IDA* 330 0.001 seconds LURDRULLDRDLURRDLURD 20
035684712 IDA* 3301 0.01 seconds RDLDRURDLULDRUULDDRURULDRD 26
684317025 IDA* 640 0.002 seconds RURULLDRDLURRULLDRDRUULDDR 26
028514637 IDA* 982 0.003 seconds DRRDLURULLDRDLURRDLUURDD 24
618273540 IDA* 1612 0.006 seconds LUULDRRULDDRUULLDRDLURDR 24
042385671 IDA* 2429 0.011 seconds RRDLLDRRULLURRDLDLURULDDRR 26
420385716 IDA* 736 0.002 seconds DLLURDDLURRULLDDRURD 20
054672813 IDA* 585 0.002 seconds DRDLURURDDLUULDRURDLDR 22
314572680 IDA* 1728 0.007 seconds LULDRUULDRURDLULDRURDLDR 24
637218045 IDA* 271 0.001 seconds RRUULLDRRDLUULDDRRULDR 22
430621875 IDA* 526 0.003 seconds LDRULDLDRULURRDDLURD 20
158274036 IDA* 2676 0.014 seconds URDRUULDDRULDLURDRUULDRD 24
130458726 IDA* 167 0.002 seconds DLDRUULDRDLURD 14

15 Puzzle - Easy

Start State Algorithm Nodes Expanded Clock Time Solution Solution Length
16235A749C08DEBF IDA* 10 0 seconds LUURRDDLDR 10
0634217859ABDEFC IDA* 10 0 seconds DRULDDRRRD 10
012456379BC8DAEF IDA* 10 0 seconds RRDRDLLDRR 10
51246A38097BDEFC IDA* 10 0 seconds RULURRDDRD 10
12345678D9CFEBA0 IDA* 11 0 seconds ULDLLURRDR 10

15 Puzzle - Difficult

Start State Algorithm Nodes Expanded Clock Time Solution Solution Length
71A92CE03DB4658F IDA* 1044282 6.326 seconds LLLDDRURURDLDRULLULURRRDDLUULDDRUULDLDDRURULLDRRRD 50
02348697DF5A1EBC IDA* 281477 1.636 seconds RDDRDLULDRUURDLULDDRRURULLULDDRRRULDRD 38
39A1D0EC7BF86452 IDA* 44472096 249.976 seconds DLUURRRDDLLDRRULULDDRUULURDLLURDDDLUURDDRUURULLDDRRULDDR 56
EAB480FC19D56237 IDA* 26420007 215.994 seconds LDRRUULLDDRDRURULLDRULDDLUURURDDLDRRUULDLUURDDDLUURDRD 54
7DB13C52F46E80A9 IDA* 8370351 78.836 seconds RULLDRRRULLUULDRRURDDLLLURDDRRULULULDRURRDLLLURRDLDDLURDRR 58

You can work in groups, but each person needs to submit assignment, and assignment report should list all team member names. Groups are generally limited to 5.