TheAlgorithms/C++ 1.0.0
All the algorithms implemented in C++
Loading...
Searching...
No Matches
a_star_search.cpp
1
22#include <algorithm>
23#include <array>
24#include <cassert>
25#include <cstdint>
26#include <functional>
27#include <iostream>
28#include <map>
29#include <memory>
30#include <set>
31#include <vector>
32
37namespace machine_learning {
43namespace aystar_search {
61template <size_t N = 3>
63 std::array<std::array<uint32_t, N>, N>
64 board;
65
66 std::vector<std::pair<int8_t, int8_t>> moves = {
67 {0, 1},
68 {1, 0},
69 {0, -1},
70 {-1,
71 0}};
72
77 std::pair<uint32_t, uint32_t> find_zero() {
78 for (size_t i = 0; i < N; ++i) {
79 for (size_t j = 0; j < N; ++j) {
80 if (!board[i][j]) {
81 return {i, j};
82 }
83 }
84 }
85 return {-1, -1};
86 }
87
92 inline bool in_range(const uint32_t value) const { return value < N; }
93
94 public:
104 uint32_t get(size_t i, size_t j) const {
105 if (in_range(i) && in_range(j)) {
106 return board[i][j];
107 }
108 return -1;
109 }
110
113 std::array<std::array<uint32_t, N>, N> get_state() { return board; }
114
119 inline size_t get_size() const { return N; }
124 for (size_t i = 0; i < N; ++i) {
125 for (size_t j = 0; j < N; ++j) {
126 board[i][j] = ((i * 3 + j + 1) % (N * N));
127 }
128 }
129 }
130
134 explicit EightPuzzle(const std::array<std::array<uint32_t, N>, N> &init)
135 : board(init) {}
136
141 EightPuzzle(const EightPuzzle<N> &A) : board(A.board) {}
142
147 EightPuzzle(const EightPuzzle<N> &&A) noexcept
148 : board(std::move(A.board)) {}
149
152 ~EightPuzzle() = default;
153
159 board = A.board;
160 return *this;
161 }
162
168 board = std::move(A.board);
169 return *this;
170 }
171
178 std::vector<EightPuzzle<N>> generate_possible_moves() {
179 auto zero_pos = find_zero();
180 // vector which will contain all possible state from current state
181 std::vector<EightPuzzle<N>> NewStates;
182 for (auto &move : moves) {
183 if (in_range(zero_pos.first + move.first) &&
184 in_range(zero_pos.second + move.second)) {
185 // swap with the possible moves
186 std::array<std::array<uint32_t, N>, N> new_config = board;
187 std::swap(new_config[zero_pos.first][zero_pos.second],
188 new_config[zero_pos.first + move.first]
189 [zero_pos.second + move.second]);
190 EightPuzzle<N> new_state(new_config);
191 // Store new state and calculate heuristic value, and depth
192 NewStates.emplace_back(new_state);
193 }
194 }
195 return NewStates;
196 }
197
202 bool operator==(const EightPuzzle<N> &check) const {
203 if (check.get_size() != N) {
204 return false;
205 }
206 for (size_t i = 0; i < N; ++i) {
207 for (size_t j = 0; j < N; ++j) {
208 if (board[i][j] != check.board[i][j]) {
209 return false;
210 }
211 }
212 }
213 return true;
214 }
215
220 bool operator<(const EightPuzzle<N> &check) const {
221 for (size_t i = 0; i < N; ++i) {
222 for (size_t j = 0; j < N; ++j) {
223 if (board[i][j] != check.board[i][j]) {
224 return board[i][j] < check.board[i][j];
225 }
226 }
227 }
228 return false;
229 }
230
235 bool operator<=(const EightPuzzle<N> &check) const {
236 for (size_t i = 0; i < N; ++i) {
237 for (size_t j = 0; j < N; ++j) {
238 if (board[i][j] != check.board[i][j]) {
239 return board[i][j] < check.board[i][j];
240 }
241 }
242 }
243 return true;
244 }
245
252 friend std::ostream &operator<<(std::ostream &op,
253 const EightPuzzle<N> &SomeState) {
254 for (size_t i = 0; i < N; ++i) {
255 for (size_t j = 0; j < N; ++j) {
256 op << SomeState.board[i][j] << " ";
257 }
258 op << "\n";
259 }
260 return op;
261 }
262};
263
289template <typename Puzzle>
295 typedef struct Info {
296 std::shared_ptr<Puzzle> state;
297 size_t heuristic_value = 0;
298 size_t depth = 0;
299
303 Info() = default;
304
309 explicit Info(const Puzzle &A) : state(std::make_shared<Puzzle>(A)) {}
310
317 Info(const Puzzle &A, size_t h_value, size_t d)
318 : state(std::make_shared<Puzzle>(A)),
319 heuristic_value(h_value),
320 depth(d) {}
321
326 Info(const Info &A)
327 : state(std::make_shared<Puzzle>(A.state)),
329 depth(A.depth) {}
330
335 Info(const Info &&A) noexcept
336 : state(std::make_shared<Puzzle>(std::move(A.state))),
337 heuristic_value(std::move(A.heuristic_value)),
338 depth(std::move(A.depth)) {}
339
344 Info &operator=(const Info &A) {
345 state = A.state;
347 depth = A.depth;
348 return *this;
349 }
350
355 Info &operator=(Info &&A) noexcept {
356 state = std::move(A.state);
357 heuristic_value = std::move(A.heuristic_value);
358 depth = std::move(A.depth);
359 return *this;
360 }
361
364 ~Info() = default;
366
367 std::shared_ptr<Info> Initial; // Initial state of the AyStarSearch
368 std::shared_ptr<Info> Final; // Final state of the AyStarSearch
373 bool operator()(const std::shared_ptr<Info> &a,
374 const std::shared_ptr<Info> &b) const {
375 return *(a->state) < *(b->state);
376 }
377 };
378
379 public:
380 using MapOfPuzzleInfoWithPuzzleInfo =
381 std::map<std::shared_ptr<Info>, std::shared_ptr<Info>,
383
384 using MapOfPuzzleInfoWithInteger =
385 std::map<std::shared_ptr<Info>, uint32_t, comparison_operator>;
386
387 using SetOfPuzzleInfo =
388 std::set<std::shared_ptr<Info>, comparison_operator>;
394 AyStarSearch(const Puzzle &initial, const Puzzle &final) {
395 Initial = std::make_shared<Info>(initial);
396 Final = std::make_shared<Info>(final);
397 }
398
407 std::vector<Puzzle> Solution(
408 std::shared_ptr<Info> FinalState,
409 const MapOfPuzzleInfoWithPuzzleInfo &parent_of) {
410 // Useful for traversing from final state to current state.
411 auto current_state = FinalState;
412 /*
413 * For storing the solution tree starting from initial state to
414 * final state
415 */
416 std::vector<Puzzle> answer;
417 while (current_state != nullptr) {
418 answer.emplace_back(*current_state->state);
419 current_state = parent_of.find(current_state)->second;
420 }
421 return answer;
422 }
423
431 std::vector<Puzzle> a_star_search(
432 const std::function<uint32_t(const Puzzle &, const Puzzle &)> &dist,
433 const uint32_t permissible_depth = 30) {
434 MapOfPuzzleInfoWithPuzzleInfo
435 parent_of;
436 MapOfPuzzleInfoWithInteger g_score;
437 SetOfPuzzleInfo open_list;
438 SetOfPuzzleInfo closed_list;
439
440 // Before starting the AyStartSearch, initialize the set and maps
441 open_list.emplace(Initial);
442 parent_of[Initial] = nullptr;
443 g_score[Initial] = 0;
444
445 while (!open_list.empty()) {
446 // Iterator for state having having lowest f_score.
447 typename SetOfPuzzleInfo::iterator it_low_f_score;
448 uint32_t min_f_score = 1e9;
449 for (auto iter = open_list.begin(); iter != open_list.end();
450 ++iter) {
451 // f score here is evaluated by g score (depth) and h score
452 // (distance between current state and final state)
453 uint32_t f_score = (*iter)->heuristic_value + (*iter)->depth;
454 if (f_score < min_f_score) {
455 min_f_score = f_score;
456 it_low_f_score = iter;
457 }
458 }
459
460 // current_state, stores lowest f score so far for this state.
461 std::shared_ptr<Info> current_state = *it_low_f_score;
462
463 // if this current state is equal to final, return
464 if (*(current_state->state) == *(Final->state)) {
465 return Solution(current_state, parent_of);
466 }
467 // else remove from open list as visited.
468 open_list.erase(it_low_f_score);
469 // if current_state has exceeded the allowed depth, skip
470 // neighbor checking
471 if (current_state->depth >= permissible_depth) {
472 continue;
473 }
474 // Generate all possible moves (neighbors) given the current
475 // state
476 std::vector<Puzzle> total_possible_moves =
477 current_state->state->generate_possible_moves();
478
479 for (Puzzle &neighbor : total_possible_moves) {
480 // calculate score of neighbors with respect to
481 // current_state
482 std::shared_ptr<Info> Neighbor = std::make_shared<Info>(
483 neighbor, dist(neighbor, *(Final->state)),
484 current_state->depth + 1U);
485 uint32_t temp_g_score = Neighbor->depth;
486
487 // Check whether this state is explored.
488 // If this state is discovered at greater depth, then discard,
489 // else remove from closed list and explore the node
490 auto closed_list_iter = closed_list.find(Neighbor);
491 if (closed_list_iter != closed_list.end()) {
492 // 1. If state in closed list has higher depth, then remove
493 // from list since we have found better option,
494 // 2. Else don't explore this state.
495 if (Neighbor->depth < (*closed_list_iter)->depth) {
496 closed_list.erase(closed_list_iter);
497 } else {
498 continue;
499 }
500 }
501 auto neighbor_g_score_iter = g_score.find(Neighbor);
502 // if the neighbor is already created and has minimum
503 // g_score, then update g_score and f_score else insert new
504 if (neighbor_g_score_iter != g_score.end()) {
505 if (neighbor_g_score_iter->second > temp_g_score) {
506 neighbor_g_score_iter->second = temp_g_score;
507 parent_of[Neighbor] = current_state;
508 }
509 } else {
510 g_score[Neighbor] = temp_g_score;
511 parent_of[Neighbor] = current_state;
512 }
513 // If this is a new state, insert into open_list
514 // else update if the this state has better g score than
515 // existing one.
516 auto iter = open_list.find(Neighbor);
517 if (iter == open_list.end()) {
518 open_list.emplace(Neighbor);
519 } else if ((*iter)->depth > Neighbor->depth) {
520 (*iter)->depth = Neighbor->depth;
521 }
522 }
523 closed_list.emplace(current_state);
524 }
525 // Cannot find the solution, return empty vector
526 return std::vector<Puzzle>(0);
527 }
528};
529} // namespace aystar_search
530} // namespace machine_learning
531
536static void test() {
537 // Renaming for simplicity
538 using matrix3 = std::array<std::array<uint32_t, 3>, 3>;
539 using row3 = std::array<uint32_t, 3>;
540 using matrix4 = std::array<std::array<uint32_t, 4>, 4>;
541 using row4 = std::array<uint32_t, 4>;
542 // 1st test: A* search for simple EightPuzzle problem
543 matrix3 puzzle;
544 puzzle[0] = row3({0, 2, 3});
545 puzzle[1] = row3({1, 5, 6});
546 puzzle[2] = row3({4, 7, 8});
547
548 matrix3 ideal;
549 ideal[0] = row3({1, 2, 3});
550 ideal[1] = row3({4, 5, 6});
551 ideal[2] = row3({7, 8, 0});
552
553 /*
554 * Heuristic function: Manhattan distance
555 */
556 auto manhattan_distance =
559 uint32_t ret = 0;
560 for (size_t i = 0; i < first.get_size(); ++i) {
561 for (size_t j = 0; j < first.get_size(); ++j) {
562 uint32_t find = first.get(i, j);
563 size_t m = first.get_size(), n = first.get_size();
564 for (size_t k = 0; k < second.get_size(); ++k) {
565 for (size_t l = 0; l < second.get_size(); ++l) {
566 if (find == second.get(k, l)) {
567 std::tie(m, n) = std::make_pair(k, l);
568 break;
569 }
570 }
571 if (m != first.get_size()) {
572 break;
573 }
574 }
575 if (m != first.get_size()) {
576 ret += (std::max(m, i) - std::min(m, i)) +
577 (std::max(n, j) - std::min(n, j));
578 }
579 }
580 }
581 return ret;
582 };
583
588 search(Puzzle, Ideal);
589
590 std::vector<matrix3> answer;
591
592 answer.push_back(
593 matrix3({row3({0, 2, 3}), row3({1, 5, 6}), row3({4, 7, 8})}));
594 answer.push_back(
595 matrix3({row3({1, 2, 3}), row3({0, 5, 6}), row3({4, 7, 8})}));
596 answer.push_back(
597 matrix3({row3({1, 2, 3}), row3({4, 5, 6}), row3({0, 7, 8})}));
598 answer.push_back(
599 matrix3({row3({1, 2, 3}), row3({4, 5, 6}), row3({7, 0, 8})}));
600 answer.push_back(
601 matrix3({row3({1, 2, 3}), row3({4, 5, 6}), row3({7, 8, 0})}));
602
603 auto Solution = search.a_star_search(manhattan_distance);
604 std::cout << Solution.size() << std::endl;
605
606 assert(Solution.size() == answer.size());
607
608 uint32_t i = 0;
609 for (auto it = Solution.rbegin(); it != Solution.rend(); ++it) {
610 assert(it->get_state() == answer[i]);
611 ++i;
612 }
613
614 // 2nd test: A* search for complicated EightPuzzle problem
615 // Initial state
616 puzzle[0] = row3({5, 7, 3});
617 puzzle[1] = row3({2, 0, 6});
618 puzzle[2] = row3({1, 4, 8});
619 // Final state
620 ideal[0] = row3({1, 2, 3});
621 ideal[1] = row3({4, 5, 6});
622 ideal[2] = row3({7, 8, 0});
623
626
627 // Initialize the search object
630
631 Solution = search.a_star_search(manhattan_distance);
632 std::cout << Solution.size() << std::endl;
633 // Static assertion due to large solution
634 assert(13 == Solution.size());
635 // Check whether the final state is equal to expected one
636 assert(Solution[0].get_state() == ideal);
637 for (auto it = Solution.rbegin(); it != Solution.rend(); ++it) {
638 std::cout << *it << std::endl;
639 }
640
641 // 3rd test: A* search for 15-Puzzle
642 // Initial State of the puzzle
643 matrix4 puzzle2;
644 puzzle2[0] = row4({10, 1, 6, 2});
645 puzzle2[1] = row4({5, 8, 4, 3});
646 puzzle2[2] = row4({13, 0, 7, 11});
647 puzzle2[3] = row4({14, 9, 15, 12});
648 // Final state of the puzzle
649 matrix4 ideal2;
650 ideal2[0] = row4({1, 2, 3, 4});
651 ideal2[1] = row4({5, 6, 7, 8});
652 ideal2[2] = row4({9, 10, 11, 12});
653 ideal2[3] = row4({13, 14, 15, 0});
654
655 // Instantiate states for a*, initial state and final states
657 Ideal2(ideal2);
658 // Initialize the search object
661 search2(Puzzle2, Ideal2);
665 auto manhattan_distance2 =
668 uint32_t ret = 0;
669 for (size_t i = 0; i < first.get_size(); ++i) {
670 for (size_t j = 0; j < first.get_size(); ++j) {
671 uint32_t find = first.get(i, j);
672 size_t m = first.get_size(), n = first.get_size();
673 for (size_t k = 0; k < second.get_size(); ++k) {
674 for (size_t l = 0; l < second.get_size(); ++l) {
675 if (find == second.get(k, l)) {
676 std::tie(m, n) = std::make_pair(k, l);
677 break;
678 }
679 }
680 if (m != first.get_size()) {
681 break;
682 }
683 }
684 if (m != first.get_size()) {
685 ret += (std::max(m, i) - std::min(m, i)) +
686 (std::max(n, j) - std::min(n, j));
687 }
688 }
689 }
690 return ret;
691 };
692
693 auto sol2 = search2.a_star_search(manhattan_distance2);
694 std::cout << sol2.size() << std::endl;
695
696 // Static assertion due to large solution
697 assert(24 == sol2.size());
698 // Check whether the final state is equal to expected one
699 assert(sol2[0].get_state() == ideal2);
700
701 for (auto it = sol2.rbegin(); it != sol2.rend(); ++it) {
702 std::cout << *it << std::endl;
703 }
704}
709int main() {
710 test(); // run self-test implementations
711 return 0;
712}
A class defining A* search algorithm. for some initial state and final state.
std::vector< Puzzle > Solution(std::shared_ptr< Info > FinalState, const MapOfPuzzleInfoWithPuzzleInfo &parent_of)
A helper solution: launches when a solution for AyStarSearch is found.
struct machine_learning::aystar_search::AyStarSearch::Info Info
Struct that handles all the information related to the current state.
std::vector< Puzzle > a_star_search(const std::function< uint32_t(const Puzzle &, const Puzzle &)> &dist, const uint32_t permissible_depth=30)
AyStarSearch(const Puzzle &initial, const Puzzle &final)
Parameterized constructor for AyStarSearch.
A class defining EightPuzzle/15-Puzzle game.
EightPuzzle & operator=(EightPuzzle &&A) noexcept
Move assignment operator.
~EightPuzzle()=default
Destructor of EightPuzzle.
std::vector< EightPuzzle< N > > generate_possible_moves()
Find all possible states after processing all possible moves, given the current state of the puzzle.
EightPuzzle()
Default constructor for EightPuzzle.
EightPuzzle & operator=(const EightPuzzle &A)
Copy assignment operator.
bool in_range(const uint32_t value) const
check whether the index value is bounded within the puzzle area
bool operator<(const EightPuzzle< N > &check) const
check whether one board is lexicographically smaller
std::pair< uint32_t, uint32_t > find_zero()
A helper array to evaluate the next state from current state;.
friend std::ostream & operator<<(std::ostream &op, const EightPuzzle< N > &SomeState)
friend operator to display EightPuzzle<>
bool operator==(const EightPuzzle< N > &check) const
check whether two boards are equal
uint32_t get(size_t i, size_t j) const
get the value from i units from right and j units from left side of the board
std::vector< std::pair< int8_t, int8_t > > moves
N x N array to store the current state of the Puzzle.
EightPuzzle(const std::array< std::array< uint32_t, N >, N > &init)
Parameterized Constructor for EightPuzzle.
EightPuzzle(const EightPuzzle< N > &A)
Copy constructor.
std::array< std::array< uint32_t, N >, N > get_state()
Returns the current state of the board.
size_t get_size() const
returns the size of the EightPuzzle (number of row / column)
EightPuzzle(const EightPuzzle< N > &&A) noexcept
Move constructor.
bool operator<=(const EightPuzzle< N > &check) const
check whether one board is lexicographically smaller or equal
double k(double x)
Another test function.
double l(double x)
Another test function.
static void test()
Self-test implementations.
int main()
Main function.
Functions for A* Search implementation.
A* search algorithm
for std::assert
Info(const Puzzle &A)
constructor having Puzzle as parameter
Info(const Info &&A) noexcept
Move constructor.
Info & operator=(const Info &A)
copy assignment operator
Info(const Puzzle &A, size_t h_value, size_t d)
constructor having three parameters
Info & operator=(Info &&A) noexcept
move assignment operator