An cross-platform eight digit problem solution simulate program based on C/C++ and GUI is created with QT API.
Simulating the search process under different searching algorithm:
- BFS
- DFS
- A*
A* search algorithm is implemented with the Heuristic Function: f(x) = g(x) + h(x).
g(x): current searching depthh(x): the sum of coordination difference under Manhattan distance strategy
g(x) functions similar as dijkstra algorithm, which can guarenteen the current would be the most optimal state on current search depth. (dynamic programing)
h(x) makes the searching process have the ability of 'pridiction' the direction of target, which makes it possible to select with greedy algorithm.
After reaching the final target state, g(x) reaches the largest depth and h(x) becomes 0, and thus the current state can be guarenteened to be the most optimal solution by comparing with the past state.
After compiling under QT framework, execute the EightDigitProblem.exe file.
- input the initial state and the target state
- clicking the
startbutton