{"id":1970,"date":"2023-12-20T13:19:56","date_gmt":"2023-12-20T13:19:56","guid":{"rendered":"http:\/\/write.muthu.co\/?p=1970"},"modified":"2023-12-20T13:19:56","modified_gmt":"2023-12-20T13:19:56","slug":"beam-search","status":"publish","type":"post","link":"http:\/\/write.muthu.co\/beam-search\/","title":{"rendered":"Beam search"},"content":{"rendered":"\n

Beam search is a heuristic search algorithm, a variant of breadth first search designed in such a way that it only explores a limited set of promising paths or solutions in a search space instead of all possible paths, which is often computationally expensive. It is used in the field of artificial intelligence, particularly in the context of search and optimization problems. The main difference between BEAM search and breadth-first search is that at every level of the search tree, only the top\u00a0\\(\\beta\\)\u00a0candidates are chosen for further exploration. Here,\u00a0\\(\\beta\\)\u00a0\u00a0is known as the beam width. The reasoning behind this is that a path from source to destination is likely to pass through some top number of most promising nodes. This leads to an algorithm that is fast and memory-efficient because it can disregard many nodes that may appear to be too far from the goal. An evaluation function is used to evaluate the candidacy of nodes for further exploration.<\/p>\n\n\n\n

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

Here is an analogy that may help you better understand beam search:<\/p>\n\n\n\n

Imagine trying to find the shortest path from your house to a grocery store. You start by walking in the direction you think will lead you there, keeping track of different paths as you walk. At each intersection, you consider the available options and choose the one most likely to lead you to the store. Beam search is a search algorithm that works similarly. It only keeps track of a limited number of paths at each iteration.<\/p>\n\n\n\n

If the beam width is too small, the algorithm may not find the best path. Conversely, if the beam width is too large, the algorithm may use too much memory. This renders the algorithm incomplete, meaning that finding the shortest path is not guaranteed. Beam search is suitable for problems where an exact solution is not required, and a good approximation is sufficient.<\/p>\n\n\n\n

The trade-off between beam width and solution quality is crucial in beam search. A narrower beam focuses on the best candidates but may miss global optima. A wider beam explores a larger portion of the search space but may spend more time on unpromising paths. The choice of beam width depends on the specific problem and the desired trade-off between speed and solution quality.<\/p>\n\n\n\n

How it works<\/h2>\n\n\n\n

Beam search uses an open set prioritized based on the total cost and a closed set to keep track of visited nodes. The algorithm begins with a start node S, which also serves as the root node for the search tree.<\/p>\n\n\n\n

    \n
  1. Initialize a search tree with the root node being the start node S.<\/li>\n\n\n\n
  2. Add S to the closed set and evaluate all successors of node S.<\/li>\n\n\n\n
  3. Select the top\u00a0$latex<\/strong> \\beta$\u00a0(beam width) nodes and add them as children to S in the tree. Ignore all other nodes.<\/li>\n\n\n\n
  4. Add the selected nodes to the open set for further exploration.<\/li>\n\n\n\n
  5. Remove all nodes in the open set. Once a node is removed for exploration, add it to the closed set.<\/li>\n\n\n\n
  6. Evaluate all adjacent nodes and sort them according to the evaluation function.<\/li>\n\n\n\n
  7. Select the top $latex<\/strong> \\beta$\u00a0nodes and add them to the tree, adding them as children of their respective parent nodes.<\/li>\n\n\n\n
  8. Repeat this process until the goal node G is found in the open set, indicating that a path has been found.<\/li>\n<\/ol>\n\n\n\n

    Implementation<\/h2>\n\n\n\n

    Below is a Python program that demonstrates the Beam Search algorithm to find the shortest path in a weighted graph from a start node to a goal node with a specified beam width.<\/p>\n\n\n\n

    import queue\n\ndef beam_search(graph, start, goal, beam_width):\n    open_set = queue.PriorityQueue()\n    open_set.put((0, start))\n    closed_set = set()\n    # A dictionary to represent the search tree\n    search_tree = {start: None}\n\n    while not open_set.empty():\n        print(open_set.queue, closed_set)\n        current_cost, current_node = open_set.get()\n\n        if current_node == goal:\n            # Goal reached, reconstruct and return the path\n            path = []\n            while current_node is not None:\n                path.insert(0, current_node)\n                current_node = search_tree[current_node]\n            return path\n\n        closed_set.add(current_node)\n        successors = graph[current_node]\n        successors.sort(key=lambda x: x[1])  # Sort successors by cost\n\n        for successor, cost in successors[:beam_width]:\n            if successor not in closed_set:\n                open_set.put((current_cost + cost, successor))\n                search_tree[successor] = current_node\n\n    # If goal not reached\n    return None\n\n# Example graph represented as an adjacency list with costs\ngraph = {\n    'A': [('E', 4), ('C', 2), ('I', 4)],\n    'B': [],\n    'C': [('F', 1), ('G', 2), ('H', 8)],\n    'D': [('B', 2)],\n    'E': [('F', 2), ('C', 2), ('H', 5)],\n    'F': [('H', 4), ('G', 1)],\n    'G': [('D', 3)],\n    'H': [('B', 6)],\n    'I': [('H', 3)]\n}\nstart_node = 'A'\ngoal_node = 'B'\nbeam_width = 2  # Adjust the beam width as needed\n\npath = beam_search(graph, start_node, goal_node, beam_width)\nif path:\n    print(\"Shortest Path:\", ' -> '.join(path))\nelse:\n    print(\"No path found.\")\n<\/code><\/pre>\n\n\n\n
    Time Complexity Analysis<\/h2>\n\n\n\n
    The time complexity of Beam Search depends on several factors, including the size of the search space, the characteristics of the problem, and the chosen beam width. Let\u2019s break down the time complexity analysis:<\/p>\n\n\n\n
      \n
    1. Search Space Size \\(N\\):<\/strong>\n