{"id":5129,"date":"2019-04-30T01:57:23","date_gmt":"2019-04-30T08:57:23","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=5129"},"modified":"2019-05-01T21:47:07","modified_gmt":"2019-05-02T04:47:07","slug":"8-puzzles-bidirectional-astar-vs-bidirectional-bfs","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/searching\/8-puzzles-bidirectional-astar-vs-bidirectional-bfs\/","title":{"rendered":"\u82b1\u82b1\u9171 8 Puzzles – Bidirectional A* vs Bidirectional BFS"},"content":{"rendered":"\n
\"\"<\/figure>\n\n\n\n

8 Puzzles # nodes expended of 1000 solvable instances<\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

Conclusion: <\/p>\n\n\n\n

Nodes expended: BiDirectional A* << A* (Manhattan) <= Bidirectional BFS < A* Hamming << BFS
Running time: BiDirectional A* < Bidirectional BFS <= A* (Manhattan) < A* Hamming << BFS <\/p>\n\n\n\n

Code:<\/p>\n\n\n\n

\n# Author: Huahua\n\nfrom collections import deque\nimport heapq\nimport numpy as np\nimport random\nimport sys\n\nN = 3\n\ndef Manhattan(s1, s2):\n  dist = 0\n  for i1, d in enumerate(s1):\n    i2 = s2.index(d)\n    x1 = i1 % N\n    y1 = i1 \/\/ N\n    x2 = i2 % N\n    y2 = i2 \/\/ N\n    dist += abs(x1 - x2) + abs(y1 - y2)\n  return dist\n\ndef Hamming(s1, s2):\n  return sum(x != y for x, y in zip(s1, s2))\n\nclass Node:\n  dirs = [0, -1, 0, 1, 0]\n  def __init__(self, state, parent = None, h = 0):\n    self.state = state\n    self.parent = parent\n    self.g = parent.g + 1 if parent else 0\n    self.h = h\n    self.f = self.g + self.h\n\n  def getMoves(self):\n    moves = []\n    index = self.state.index(0)\n    x = index % N\n    y = index \/\/ N\n    for i in range(4):\n      tx = x + Node.dirs[i]\n      ty = y + Node.dirs[i + 1]\n      if tx < 0 or ty < 0 or tx == N or ty == N:\n        continue\n      i = ty * N + tx\n      move = list(self.state)\n      move[index] = move[i]\n      move[i] = 0\n      moves.append(tuple(move))\n    return moves\n\n  def print(self):\n    print(np.reshape(self.state, (N, N)))\n\n  def __lt__(self, other):\n    return self.f < other.f\n\ndef AStarSearch(start_state, end_state, heuristic):\n  def h(s):\n    return heuristic(s, end_state)\n  q = []\n  s = Node(start_state, h=h(start_state))\n  heapq.heappush(q, s)\n  opened = {s.state : s.f}\n  closed = dict()\n  while q:\n    n = heapq.heappop(q)\n    if n.state == end_state:\n      return n, len(opened), len(closed)\n    if n.state in closed: continue\n    closed[n.state] = n.f\n    for move in n.getMoves():\n      node = Node(move, n, h(move))\n      if move in opened and opened[move] <= node.f: continue\n      opened[node.state] = node.f\n      heapq.heappush(q, node)\n  return None, len(opened), len(closed)\n\ndef BFS(start_state, end_state):\n  q = deque()\n  q.append(Node(start_state))\n  opened = set(start_state)\n  closed = 0\n  while q:\n    n = q.popleft()\n    if n.state == end_state:\n      return n, len(opened), closed\n    closed += 1\n    for move in n.getMoves():\n      if move in opened: continue\n      opened.add(move)\n      q.append(Node(move, n))\n  return None, len(opened), closed\n\ndef getRootNode(n):\n  return getRootNode(n.parent) if n.parent else n\n\ndef BidirectionalBFS(start_state, end_state):\n  def constructPath(p, o):\n    while o: \n      t = o.parent\n      o.parent = p\n      p, o = o, t\n    return p\n  ns = Node(start_state)\n  ne = Node(end_state)\n  q = [deque([ns]), deque([ne])]\n  opened = [{start_state : ns}, {end_state: ne}]\n  closed = [0, 0]\n  while q[0]:\n    l = len(q[0])\n    while l > 0:\n      p = q[0].popleft()\n      closed[0] += 1\n      for move in p.getMoves():\n        n = Node(move, p)\n        if move in opened[1]:\n          o = opened[1][move]\n          if getRootNode(n).state == end_state:\n            o, n = n, o\n          n = constructPath(n, o.parent)\n          return n, len(opened[0]) + len(opened[1]), closed[0] + closed[1]\n        if move in opened[0]: continue\n        opened[0][move] = n\n        q[0].append(n)\n      l -= 1\n    q.reverse()\n    opened.reverse()\n    closed.reverse()\n  return None, len(opened[0]) + len(opened[1]), closed[0] + closed[1]\n\n\ndef print_path(n):\n  if not n: return\n  print_path(n.parent)\n  n.print()\n\ndef solvable(state):\n  inv = 0\n  for i in range(N*N):\n    for j in range(i + 1, N*N):\n      if all((state[i] > 0, state[j] > 0, state[i] > state[j])):\n        inv += 1\n  return inv % 2 == 0\n\nif __name__ == '__main__':\n  s = [1, 2, 3, 4, 5, 6, 7, 8, 0]\n  e = [1, 2, 3, 4, 5, 6, 7, 8, 0]\n  i = 0\n  while True:\n    random.shuffle(s)\n    if not solvable(s): continue\n    n1, opened1, closed1 = AStarSearch(tuple(s), tuple(e), heuristic=Manhattan)\n    n2, opened2, closed2 = AStarSearch(tuple(s), tuple(e), heuristic=Hamming)\n    n3, opened3, closed3 = BFS(tuple(s), tuple(e))\n    n4, opened4, closed4 = BidirectionalBFS(tuple(s), tuple(e))\n    print(\"%d\\t%d\\t%d\\t%d\" % (closed1, closed2, closed3, closed4))\n    sys.stdout.flush()\n\n    # print(\"A*\")\n    # print_path(n1)\n    # print('---------------')\n    # print(\"BFS\")\n    # print_path(n3)\n    # print('---------------')\n    # print(\"Bi-BFS\")\n    # print_path(n4)\n    # print('---------------')\n\n    i += 1\n    if i == 1000: break\n<\/pre>\n\n\n\n
C++ Version<\/p>\n\n\n\n
\n#include \n#include \n#include \n#include \n#include \n#include \n#include \n#include \n#include \n#include \n#include \n\nusing namespace std;\nusing chrono::high_resolution_clock;\n\nconstexpr int N = 3;\nconstexpr int dirs[] = {0, 1, 0, -1, 0};\n\nstruct Node;\ntypedef string State;\ntypedef shared_ptr NodePtr;\ntypedef function Heuristic;\n\nstruct Node {\n  Node(State s, NodePtr p = nullptr, int h = 0)\n      : s(s), p(p), h(h), g(p ? p->g + 1 : 0), f(this->h + g) {}\n\n  vector GetNextStates() const {\n    vector states;\n    int index = find(s.begin(), s.end(), '0') - s.begin();\n    int x = index % N;\n    int y = index \/ N;\n    for (int i = 0; i < 4; ++i) {\n      int tx = x + dirs[i];\n      int ty = y + dirs[i + 1];\n      if (tx < 0 || ty < 0 || tx == N || ty == N) continue;\n      int new_index = ty * N + tx;\n      State next(s);\n      next[index] = s[new_index];\n      next[new_index] = '0';\n      states.push_back(move(next));\n    }\n    return states;\n  }\n\n  NodePtr p;\n  int h;\n  int g;\n  int f;\n  State s;\n};\n\nbool Sovlable(const State& s) {\n  int inv_count = 0;\n  for (int i = 0; i < N * N; ++i) {\n    for (int j = i + 1; j < N * N; ++j) {\n      if (s[i] != '0' && s[j] != '0' && s[i] > s[j]) {\n        ++inv_count;\n      }\n    }\n  }\n  return inv_count % 2 == 0;\n}\n\nNodePtr GetRoot(NodePtr n) { return n->p ? GetRoot(n->p) : n; }\nNodePtr WirePath(NodePtr p, NodePtr n) {\n  while (n) {\n    NodePtr t = n->p;\n    n->p = p;\n    p = n;\n    n = t;\n  }\n  return p;\n}\n\nvoid ConstructPath(NodePtr node, vector* path) {\n  while (node) {\n    path->push_back(node->s);\n    node = node->p;\n  }\n  reverse(path->begin(), path->end());\n}\n\nclass Solver {\n public:\n  virtual bool Solve(State start, State target, vector* path,\n                     int* opened, int* closed) = 0;\n};\n\nclass BFSSolver : public Solver {\n public:\n  bool Solve(State start, State target, vector* path, int* opened,\n             int* closed) override {\n    int expended = 0;\n    unordered_set seen;\n    deque q{make_shared(start)};\n    while (!q.empty()) {\n      auto cur = q.front();\n      q.pop_front();\n      ++expended;\n      if (cur->s == target) {\n        ConstructPath(cur, path);\n        *opened = seen.size();\n        *closed = expended;\n        return true;\n      }\n      for (const auto& s : cur->GetNextStates()) {\n        auto r = seen.insert(s);\n        if (!r.second) continue;\n        q.push_back(make_shared(s, cur));\n      }\n    }\n    return false;\n  }\n};\n\nclass BidirectionalBFSSolver : public Solver {\n public:\n  bool Solve(State start, State target, vector* path, int* opened,\n             int* closed) override {\n    auto start_node = make_shared(start);\n    auto target_node = make_shared(target);\n    unordered_map seen0{{start, start_node}};\n    unordered_map seen1{{target, target_node}};\n    deque q0{start_node};\n    deque q1{target_node};\n    int expended = 0;\n    while (!q0.empty()) {\n      size_t size = q0.size();\n      while (size--) {\n        auto cur = q0.front();\n        q0.pop_front();\n        ++expended;\n\n        for (const auto& s : cur->GetNextStates()) {\n          auto n = make_shared(s, cur);\n          auto it = seen1.find(s);\n          if (it != seen1.end()) {\n            auto p = it->second;\n            if (GetRoot(n)->s == target) swap(n, p);\n            n = WirePath(n, p->p);\n            ConstructPath(n, path);\n            *opened = seen0.size() + seen1.size();\n            *closed = expended;\n            return true;\n          }\n\n          if (seen0.count(s)) continue;\n          seen0[s] = n;\n          q0.push_back(n);\n        }\n      }\n\n      if (q1.size() < q0.size()) {\n        swap(q0, q1);\n        swap(seen0, seen1);\n      }\n    }\n    return false;\n  }\n\n private:\n};\n\nstruct NodeCompare : public binary_function {\n  bool operator()(const NodePtr& x, const NodePtr& y) const {\n    return x->f > y->f;\n  }\n};\n\nint ManhattanDistance(const State& s, const State& t) {\n  int h = 0;\n  for (int i1 = 0; i1 < N * N; ++i1) {\n    int i2 = t.find(s[i1]);\n    int x1 = i1 % N;\n    int y1 = i1 \/ N;\n    int x2 = i2 % N;\n    int y2 = i2 \/ N;\n    h += abs(x1 - x2) + abs(y1 - y2);\n  }\n  return h;\n}\n\nint HammingDistance(const State& s, const State& t) {\n  int h = 0;\n  for (size_t i = 0; i < s.size(); ++i) {\n    if (s[i] != t[i]) ++h;\n  }\n  return h;\n}\n\nclass AStarSolver : public Solver {\n public:\n  explicit AStarSolver(Heuristic heuristic) : heuristic_(heuristic) {}\n  bool Solve(State start, State target, vector* path, int* opened,\n             int* closed) override {\n    unordered_map o;\n    unordered_set c;\n    priority_queue, NodeCompare> q;\n    q.emplace(new Node(start, nullptr, heuristic_(start, target)));\n    while (!q.empty()) {\n      auto cur = q.top();\n      q.pop();\n      if (cur->s == target) {\n        ConstructPath(cur, path);\n        *opened = o.size();\n        *closed = c.size();\n        return true;\n      }\n      if (!c.insert(cur->s).second) continue;\n      for (const auto& s : cur->GetNextStates()) {\n        auto it = o.find(s);\n        auto n = make_shared(s, cur, heuristic_(s, target));\n        if (it != o.end() && n->f >= it->second->f) continue;\n        o[s] = n;\n        q.push(n);\n      }\n    }\n    return false;\n  }\n\n private:\n  Heuristic heuristic_;\n};\n\nclass BiAStarSolver : public Solver {\n public:\n  explicit BiAStarSolver(Heuristic heuristic) : heuristic_(heuristic) {}\n  bool Solve(State start, State target, vector* path, int* opened,\n             int* closed) override {\n    unordered_map o0, o1;\n    unordered_map c0, c1;\n    priority_queue, NodeCompare> q0, q1;\n    q0.emplace(new Node(start, nullptr, heuristic_(start, target)));\n    q1.emplace(new Node(target, nullptr, heuristic_(target, start)));\n    bool farward = true;\n    while (!q0.empty()) {\n      auto size = q0.size();\n      while (size--) {\n        auto cur = q0.top();\n        q0.pop();\n        if (c0.count(cur->s)) continue;\n        c0[cur->s] = cur;\n        if (c1.count(cur->s)) {\n          auto p = c1[cur->s];\n          if (GetRoot(cur)->s == target) swap(cur, p);\n          cur = WirePath(cur, p->p);\n          ConstructPath(cur, path);\n          *opened = o0.size() + o1.size();\n          *closed = c0.size() + c1.size();\n          return true;\n        }\n        for (const auto& s : cur->GetNextStates()) {\n          auto it = o0.find(s);\n          auto n = make_shared(s, cur,\n                                     heuristic_(s, farward ? target : start));\n          if (it != o0.end() && n->f >= it->second->f) continue;\n          o0[s] = n;\n          q0.push(n);\n        }\n      }\n      if (q1.size() < q0.size()) {\n        swap(q0, q1);\n        swap(c0, c1);\n        swap(o0, o1);\n        farward = !farward;\n      }\n    }\n    return false;\n  }\n\n private:\n  Heuristic heuristic_;\n};\n\nbool VerifyPath(const vector& path, const State& s, const State& t) {\n  if (path.empty()) return false;\n  if (path.front() != s || path.back() != t) return false;\n  for (size_t i = 1; i < path.size(); ++i) {\n    Node n(path[i - 1]);\n    auto states = n.GetNextStates();\n    if (find(begin(states), end(states), path[i]) == end(states)) {\n      return false;\n    }\n  }\n  return true;\n}\n\nvoid StatisticsMode() {\n  State s{\"123456780\"};\n  State t{\"123456780\"};\n\n  vector> solvers;\n  solvers.emplace_back(new BFSSolver);\n  solvers.emplace_back(new AStarSolver(HammingDistance));\n  solvers.emplace_back(new AStarSolver(ManhattanDistance));\n  solvers.emplace_back(new BidirectionalBFSSolver);\n  solvers.emplace_back(new BiAStarSolver(ManhattanDistance));\n\n  for (int i = 0; i < 1000;) {\n    random_shuffle(s.begin(), s.end());\n    if (!Sovlable(s)) continue;\n    ++i;\n    for (auto& solver : solvers) {\n      vector path;\n      int opened;\n      int closed;\n      auto t0 = high_resolution_clock::now();\n      bool sovlable = solver->Solve(s, t, &path, &opened, &closed);\n      auto t1 = high_resolution_clock::now();\n\n      if (!VerifyPath(path, s, t)) {\n        cerr << \"Invalid path!\" << endl;\n        return;\n      }\n\n      auto time_span = chrono::duration_cast>(t1 - t0);\n\n      cout << closed << \"\\t\" << time_span.count() * 1000 << \"\\t\";\n    }\n    cout << endl;\n  }\n}\n\nint main() { StatisticsMode(); }\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
8 Puzzles # nodes expended of 1000 solvable instances Conclusion: Nodes expended: BiDirectional A* << A* (Manhattan) <= Bidirectional BFS < A* Hamming << BFSRunning…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[44],"tags":[473,474,34,110,42],"class_list":["post-5129","post","type-post","status-publish","format-standard","hentry","category-searching","tag-a","tag-astar","tag-bfs","tag-bidirectional-bfs","tag-search","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5129","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=5129"}],"version-history":[{"count":4,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5129\/revisions"}],"predecessor-version":[{"id":5136,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5129\/revisions\/5136"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=5129"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=5129"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=5129"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}