From: Scott Worley Date: Sun, 10 Jan 2016 06:58:21 +0000 (-0800) Subject: Bound the frontier. I.e., do beam search. X-Git-Url: http://git.scottworley.com/slidingtile/commitdiff_plain/8e3c9cff3a9dbe44519dcea244d528809cc45821?hp=dfc82124a67c1721299a1db521b457b99191b384 Bound the frontier. I.e., do beam search. This works now. --- diff --git a/sliding_tile.cc b/sliding_tile.cc index cfa7425..2b7f31a 100644 --- a/sliding_tile.cc +++ b/sliding_tile.cc @@ -5,8 +5,9 @@ DEFINE_string(start, "", "The starting tile positions. 0 is the hole."); DEFINE_string(goal, "1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0", "The desired tile positions. 0 is the hole."); +DEFINE_int32(max_frontier, 100000, "The maximum frontier size. Larger values run longer and give shorter paths."); int main(int argc, char** argv) { gflags::ParseCommandLineFlags(&argc, &argv, false); - std::cout << *find_path(FLAGS_start, FLAGS_goal); + std::cout << *find_path(FLAGS_start, FLAGS_goal, FLAGS_max_frontier); } diff --git a/sliding_tile_lib.cc b/sliding_tile_lib.cc index 551bc1f..5a4114b 100644 --- a/sliding_tile_lib.cc +++ b/sliding_tile_lib.cc @@ -189,7 +189,7 @@ std::ostream& operator<<(std::ostream& os, const Step& step) { return os; } -std::shared_ptr find_path(const std::string& start, const std::string& goal) { +std::shared_ptr find_path(const std::string& start, const std::string& goal, unsigned max_frontier) { std::istringstream iss_start{start}, iss_goal{goal}; Board board_start, board_goal; iss_start >> board_start; @@ -200,10 +200,10 @@ std::shared_ptr find_path(const std::string& start, const std::string& goa if (iss_goal.fail() || !iss_goal.eof()) { throw std::runtime_error("Could not parse the goal board: " + goal); } - return find_path(board_start, board_goal); + return find_path(board_start, board_goal, max_frontier); } -std::shared_ptr find_path(const Board& start, const Board& goal) { +std::shared_ptr find_path(const Board& start, const Board& goal, unsigned max_frontier) { InvertedBoard invgoal = goal.invert(); std::multimap> todo; std::set seen; @@ -230,6 +230,9 @@ std::shared_ptr find_path(const Board& start, const Board& goal) { } } } + while (todo.size() > max_frontier) { + todo.erase(--todo.end()); + } } throw std::runtime_error("No path from start to goal"); } diff --git a/sliding_tile_lib.h b/sliding_tile_lib.h index 11d9de3..f0753fc 100644 --- a/sliding_tile_lib.h +++ b/sliding_tile_lib.h @@ -44,7 +44,7 @@ struct Step { }; std::ostream& operator<<(std::ostream& os, const Step& step); -std::shared_ptr find_path(const std::string& start, const std::string& goal); -std::shared_ptr find_path(const Board& start, const Board& goal); +std::shared_ptr find_path(const std::string& start, const std::string& goal, unsigned max_frontier); +std::shared_ptr find_path(const Board& start, const Board& goal, unsigned max_frontier); #endif /* _SLIDING_TILE_LIB_H */