Author : Ya Chen
Date : 2021 / 4 / 5
List :Description
Algorithms
Exercise Essentials
Reference
How to Execute
First of all, suppose there is a ( H + 2 ) x ( W + 2 ) maze with an outer wall, the grid content of * is the wall and cannot be walked into. The grid content 0 ~ 9 indicates the height of the grid, which can be walked into, but if you walk from a grid with height c to the next grid with height d, it costs the robot 10 + (c-d)2 in power cost.
The robot starts from the top left corner and can move to any of the four adjacent spaces. If it finally reaches the end point in the lower right corner, the task is completed.
Of course, it would be great to find the best solution that costs the least total power!
I will use the following three algorithms to perform the exercise:
- Uniform-cost search ( An algorithm likes Dijkstra's single-source-shortest-path algorithm )
- Iterative Deeping Depth-First Search ( IDS or IDDFS )
- Iterative Deeping A* ( IDA* )
- Bonus : Bidirectional Search
- How to display the output plate?
- How the route should be generated?
- How to implement Frontier?
- What informations to store at the node?
- How to distinguish repetition?
- Will there be infinite loops?
- Will the memory explode?
- Will the result be the best solution?
- Which heuristic result is better to use?
- How to estimate the Time complexity and Space complexity?
If your device supports the make command, this will be much easier.
You can type make in Terminal to see the output of all Python files directly.
You can also type in :
>>>make
// Output all the execution results
>>>make p1
// Output the execution result of P1_UCS
>>>make p2
// Output the execution result of P2_IDS
>>>make p3
// Output the execution result of P3_IDASTAR
>>>make bonus
// Output the execution result of BidirectiontionalSearch
If your device does not supports the make command, there will be a little inconvenience.
You can type in :
>>>python mazeMaker.py
// If you want to random the looks of maze in input.txt
>>>python P1_UCS.py
// Output the execution result of P1_UCS
>>>python P2_IDS.py
// Output the execution result of P2_IDS
>>>python P3_IDASTAR.py
// Output the execution result of P3_IDASTAR
>>>python BidirectionalSearch.py
// Output the execution result of BidirectionalSearch