![]() |
TheAlgorithms/C++ 1.0.0
All the algorithms implemented in C++
|
A class defining A* search algorithm. for some initial state and final state. More...
Classes | |
struct | comparison_operator |
Custom comparator for open_list. More... | |
struct | Info |
Struct that handles all the information related to the current state. More... | |
Public Types | |
using | MapOfPuzzleInfoWithPuzzleInfo |
using | MapOfPuzzleInfoWithInteger |
using | SetOfPuzzleInfo |
Public Member Functions | |
AyStarSearch (const Puzzle &initial, const Puzzle &final) | |
Parameterized constructor for AyStarSearch. | |
std::vector< Puzzle > | Solution (std::shared_ptr< Info > FinalState, const MapOfPuzzleInfoWithPuzzleInfo &parent_of) |
A helper solution: launches when a solution for AyStarSearch is found. | |
std::vector< Puzzle > | a_star_search (const std::function< uint32_t(const Puzzle &, const Puzzle &)> &dist, const uint32_t permissible_depth=30) |
Private Types | |
typedef struct machine_learning::aystar_search::AyStarSearch::Info | Info |
Struct that handles all the information related to the current state. | |
Private Attributes | |
std::shared_ptr< Info > | Initial |
std::shared_ptr< Info > | Final |
A class defining A* search algorithm. for some initial state and final state.
AyStarSearch class is defined as the informed search algorithm that is formulated in terms of weighted graphs: starting from a specific starting node of a graph (initial state), it aims to find a path to the given goal node having the smallest cost (least distance travelled, shortest time, etc.) The weighted edges (or cost) is evaluated on two factors, G score (cost required from starting node or initial state to current state) and H score (cost required from current state to final state). The F(state)
, then is evaluated as: F(state) = G(state) + H(state)
. The best search would be the final state having minimum F(state)
value
Puzzle | denotes the puzzle or problem involving initial state and final state to be solved by A* search. |
AyStarSearch
to work, the definitions for template Puzzle is compulsory. a. Comparison operator for template Puzzle (<
, ==
, and <=
) b. generate_possible_moves()
Definition at line 288 of file a_star_search.cpp.
using machine_learning::aystar_search::AyStarSearch< Puzzle >::MapOfPuzzleInfoWithInteger |
Definition at line 382 of file a_star_search.cpp.
using machine_learning::aystar_search::AyStarSearch< Puzzle >::MapOfPuzzleInfoWithPuzzleInfo |
Definition at line 378 of file a_star_search.cpp.
using machine_learning::aystar_search::AyStarSearch< Puzzle >::SetOfPuzzleInfo |
Definition at line 385 of file a_star_search.cpp.
|
inline |
Parameterized constructor for AyStarSearch.
initial | denoting initial state of the puzzle |
final | denoting final state of the puzzle |
Definition at line 392 of file a_star_search.cpp.
|
inline |
Main algorithm for finding FinalState
, given the InitialState
dist | the heuristic finction, defined by the user |
permissible_depth | the depth at which the A* search discards searching for solution |
Stores the parent of the states
Stores the g_score
Stores the list to explore
Stores the list that are explored
Definition at line 429 of file a_star_search.cpp.
|
inline |
A helper solution: launches when a solution for AyStarSearch is found.
FinalState | the pointer to the obtained final state |
parent_of | the list of all parents of nodes stored during A* search |
Definition at line 405 of file a_star_search.cpp.
|
private |
Definition at line 366 of file a_star_search.cpp.
|
private |
Definition at line 365 of file a_star_search.cpp.