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()

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>

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>

SetOfPuzzleInfo

template<typename Puzzle >

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

Initial value:

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

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

                                                             {
        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

                                               {
        MapOfPuzzleInfoWithPuzzleInfo
            parent_of;                       /// Stores the parent of the states
        MapOfPuzzleInfoWithInteger g_score;  /// Stores the g_score
        SetOfPuzzleInfo open_list;           /// Stores the list to explore
        SetOfPuzzleInfo closed_list;  /// Stores the list that are explored
 
        // 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);
    }

Here is the call graph for this function:

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)

                                                        {
        //  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;
    }

Here is the call graph for this function:

---

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

• machine_learning/a_star_search.cpp