From: Scott Worley Date: Sun, 10 Jan 2016 06:35:20 +0000 (-0800) Subject: Switch from priority_queue to multimap X-Git-Url: http://git.scottworley.com/slidingtile/commitdiff_plain/dfc82124a67c1721299a1db521b457b99191b384?hp=ab51c07a99c1927c95a123e6912925adba83714f Switch from priority_queue to multimap --- diff --git a/sliding_tile_lib.cc b/sliding_tile_lib.cc index 9ac0217..551bc1f 100644 --- a/sliding_tile_lib.cc +++ b/sliding_tile_lib.cc @@ -2,6 +2,7 @@ #include #include +#include #include #include #include @@ -204,34 +205,31 @@ std::shared_ptr find_path(const std::string& start, const std::string& goa std::shared_ptr find_path(const Board& start, const Board& goal) { InvertedBoard invgoal = goal.invert(); - auto heap_greater = [invgoal](const std::shared_ptr& a, const std::shared_ptr& b) { - return a->cost(invgoal) > b->cost(invgoal); - }; - std::priority_queue, - std::vector>, - decltype(heap_greater)> todo(heap_greater); + std::multimap> todo; std::set seen; - seen.emplace(start); - todo.push(std::make_shared(start, nullptr)); + seen.insert(start); + auto start_step = std::make_shared(start, nullptr); + todo.emplace(start_step->cost(invgoal), start_step); while (!todo.empty()) { - if (todo.top()->board == goal) { - return todo.top(); + auto cur = todo.begin()->second; + todo.erase(todo.begin()); + if (cur->board == goal) { + return cur; } - std::vector> successors = todo.top()->successors(todo.top()); + std::vector> successors = cur->successors(cur); for (const std::shared_ptr& s : successors) { if (seen.find(s->board) == seen.end()) { - seen.emplace(s->board); - todo.push(s); + seen.insert(s->board); + todo.emplace(s->cost(invgoal), s); if (seen.size() % 10000 == 0) { std::cerr << "Examined " << seen.size() << " boards. Tracking " << Step::count << " steps. " << todo.size() << " waiting. Considering paths of length " - << todo.top()->cost(invgoal) << std::endl; + << cur->cost(invgoal) << std::endl; } } } - todo.pop(); } throw std::runtime_error("No path from start to goal"); }