machine_learning::aystar_search::AyStarSearch< Puzzle > Class Template Reference

A class defining A* search algorithm. for some initial state and final state. More...

Collaboration diagram for machine_learning::aystar_search::AyStarSearch< Puzzle >:

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

Detailed Description

template<typename Puzzle>
class machine_learning::aystar_search::AyStarSearch< Puzzle >

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

Template Parameters

Puzzle

denotes the puzzle or problem involving initial state and final state to be solved by A* search.

Note

1. The algorithm is referred from pesudocode from Wikipedia page as is.

1. For AyStarSearch to work, the definitions for template Puzzle is compulsory. a. Comparison operator for template Puzzle (<, ==, and <=) b. generate_possible_moves()

Definition at line 290 of file a_star_search.cpp.

Member Typedef Documentation

MapOfPuzzleInfoWithInteger

template<typename Puzzle>

using machine_learning::aystar_search::AyStarSearch< Puzzle >::MapOfPuzzleInfoWithInteger

Initial value:

 
        std::map<std::shared_ptr<Info>, uint32_t, comparison_operator>

Definition at line 384 of file a_star_search.cpp.

MapOfPuzzleInfoWithPuzzleInfo

template<typename Puzzle>

using machine_learning::aystar_search::AyStarSearch< Puzzle >::MapOfPuzzleInfoWithPuzzleInfo

Initial value:

 
        std::map<std::shared_ptr<Info>, std::shared_ptr<Info>,
                 comparison_operator>

Definition at line 380 of file a_star_search.cpp.

SetOfPuzzleInfo

template<typename Puzzle>

using machine_learning::aystar_search::AyStarSearch< Puzzle >::SetOfPuzzleInfo

Initial value:

 
        std::set<std::shared_ptr<Info>, comparison_operator>

Definition at line 387 of file a_star_search.cpp.

Constructor & Destructor Documentation

AyStarSearch()

template<typename Puzzle>

machine_learning::aystar_search::AyStarSearch< Puzzle >::AyStarSearch ( const Puzzle & initial, const Puzzle & final )

inline

Parameterized constructor for AyStarSearch.

Parameters

initial	denoting initial state of the puzzle
final	denoting final state of the puzzle

Definition at line 394 of file a_star_search.cpp.

                                                             {
        Initial = std::make_shared<Info>(initial);
        Final = std::make_shared<Info>(final);
    }

Member Function Documentation

a_star_search()

template<typename Puzzle>

std::vector< Puzzle > machine_learning::aystar_search::AyStarSearch< Puzzle >::a_star_search ( const std::function< uint32_t(const Puzzle &, const Puzzle &)> & dist, const uint32_t permissible_depth = 30 )

inline

Main algorithm for finding FinalState, given the InitialState

Parameters

dist	the heuristic finction, defined by the user
permissible_depth	the depth at which the A* search discards searching for solution

Returns

List of moves from Final state to initial state, if evaluated, else returns an empty array

Stores the parent of the states

Stores the g_score

Stores the list to explore

Stores the list that are explored

Definition at line 431 of file a_star_search.cpp.

                                               {
        MapOfPuzzleInfoWithPuzzleInfo
            parent_of;                       
        MapOfPuzzleInfoWithInteger g_score;  
        SetOfPuzzleInfo open_list;           
        SetOfPuzzleInfo closed_list;  
 
        // Before starting the AyStartSearch, initialize the set and maps
        open_list.emplace(Initial);
        parent_of[Initial] = nullptr;
        g_score[Initial] = 0;
 
        while (!open_list.empty()) {
            // Iterator for state having having lowest f_score.
            typename SetOfPuzzleInfo::iterator it_low_f_score;
            uint32_t min_f_score = 1e9;
            for (auto iter = open_list.begin(); iter != open_list.end();
                 ++iter) {
                // f score here is evaluated by g score (depth) and h score
                // (distance between current state and final state)
                uint32_t f_score = (*iter)->heuristic_value + (*iter)->depth;
                if (f_score < min_f_score) {
                    min_f_score = f_score;
                    it_low_f_score = iter;
                }
            }
 
            // current_state, stores lowest f score so far for this state.
            std::shared_ptr<Info> current_state = *it_low_f_score;
 
            // if this current state is equal to final, return
            if (*(current_state->state) == *(Final->state)) {
                return Solution(current_state, parent_of);
            }
            // else remove from open list as visited.
            open_list.erase(it_low_f_score);
            // if current_state has exceeded the allowed depth, skip
            // neighbor checking
            if (current_state->depth >= permissible_depth) {
                continue;
            }
            // Generate all possible moves (neighbors) given the current
            // state
            std::vector<Puzzle> total_possible_moves =
                current_state->state->generate_possible_moves();
 
            for (Puzzle &neighbor : total_possible_moves) {
                // calculate score of neighbors with respect to
                // current_state
                std::shared_ptr<Info> Neighbor = std::make_shared<Info>(
                    neighbor, dist(neighbor, *(Final->state)),
                    current_state->depth + 1U);
                uint32_t temp_g_score = Neighbor->depth;
 
                // Check whether this state is explored.
                // If this state is discovered at greater depth, then discard,
                // else remove from closed list and explore the node
                auto closed_list_iter = closed_list.find(Neighbor);
                if (closed_list_iter != closed_list.end()) {
                    // 1. If state in closed list has higher depth, then remove
                    // from list since we have found better option,
                    // 2. Else don't explore this state.
                    if (Neighbor->depth < (*closed_list_iter)->depth) {
                        closed_list.erase(closed_list_iter);
                    } else {
                        continue;
                    }
                }
                auto neighbor_g_score_iter = g_score.find(Neighbor);
                // if the neighbor is already created and has minimum
                // g_score, then update g_score and f_score else insert new
                if (neighbor_g_score_iter != g_score.end()) {
                    if (neighbor_g_score_iter->second > temp_g_score) {
                        neighbor_g_score_iter->second = temp_g_score;
                        parent_of[Neighbor] = current_state;
                    }
                } else {
                    g_score[Neighbor] = temp_g_score;
                    parent_of[Neighbor] = current_state;
                }
                // If this is a new state, insert into open_list
                // else update if the this state has better g score than
                // existing one.
                auto iter = open_list.find(Neighbor);
                if (iter == open_list.end()) {
                    open_list.emplace(Neighbor);
                } else if ((*iter)->depth > Neighbor->depth) {
                    (*iter)->depth = Neighbor->depth;
                }
            }
            closed_list.emplace(current_state);
        }
        // Cannot find the solution, return empty vector
        return std::vector<Puzzle>(0);
    }

Solution()

template<typename Puzzle>

std::vector< Puzzle > machine_learning::aystar_search::AyStarSearch< Puzzle >::Solution ( std::shared_ptr< Info > FinalState, const MapOfPuzzleInfoWithPuzzleInfo & parent_of )

inline

A helper solution: launches when a solution for AyStarSearch is found.

Parameters

FinalState	the pointer to the obtained final state
parent_of	the list of all parents of nodes stored during A* search

Returns

the list of moves denoting moves from final state to initial state (in reverse)

Definition at line 407 of file a_star_search.cpp.

                                                        {
        //  Useful for traversing from final state to current state.
        auto current_state = FinalState;
        /*
         * For storing the solution tree starting from initial state to
         * final state
         */
        std::vector<Puzzle> answer;
        while (current_state != nullptr) {
            answer.emplace_back(*current_state->state);
            current_state = parent_of.find(current_state)->second;
        }
        return answer;
    }

Member Data Documentation

Final

template<typename Puzzle>

std::shared_ptr<Info> machine_learning::aystar_search::AyStarSearch< Puzzle >::Final

private

Definition at line 368 of file a_star_search.cpp.

Initial

template<typename Puzzle>

std::shared_ptr<Info> machine_learning::aystar_search::AyStarSearch< Puzzle >::Initial

private

Definition at line 367 of file a_star_search.cpp.

---

The documentation for this class was generated from the following file:

• machine_learning/a_star_search.cpp