From 8e3c9cff3a9dbe44519dcea244d528809cc45821 Mon Sep 17 00:00:00 2001
From: Scott Worley <scottworley@scottworley.com>
Date: Sat, 9 Jan 2016 22:58:21 -0800
Subject: [PATCH] Bound the frontier.  I.e., do beam search.

This works now.
---
 sliding_tile.cc     | 3 ++-
 sliding_tile_lib.cc | 9 ++++++---
 sliding_tile_lib.h  | 4 ++--
 3 files changed, 10 insertions(+), 6 deletions(-)

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<Step> find_path(const std::string& start, const std::string& goal) {
+std::shared_ptr<Step> 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<Step> 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<Step> find_path(const Board& start, const Board& goal) {
+std::shared_ptr<Step> find_path(const Board& start, const Board& goal, unsigned max_frontier) {
   InvertedBoard invgoal = goal.invert();
   std::multimap<int, std::shared_ptr<Step>> todo;
   std::set<Board> seen;
@@ -230,6 +230,9 @@ std::shared_ptr<Step> 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<Step> find_path(const std::string& start, const std::string& goal);
-std::shared_ptr<Step> find_path(const Board& start, const Board& goal);
+std::shared_ptr<Step> find_path(const std::string& start, const std::string& goal, unsigned max_frontier);
+std::shared_ptr<Step> find_path(const Board& start, const Board& goal, unsigned max_frontier);
 
 #endif /* _SLIDING_TILE_LIB_H */
-- 
2.44.1