Implementing Memory-Bound Search

The method must be carefully designed to efficiently handle the memory resources available to implement memory-bound search. Let us go through a simple Pseudocode that illustrates the main ideas of creating memory-bound search code samples.

Pseudocode: Memory-Bounded A* Algorithm

function MemoryBoundedSearch(problem, memory_limit):
    node = InitialNode(problem)
    open_list = [node]
    closed_list = []
    
    while open_list is not empty:
        if memory_usage(open_list, closed_list) > memory_limit:
            prune_memory(open_list, closed_list)
        
        current_node = select_best_node(open_list)
        if is_goal(current_node):
            return solution(current_node)
        
        open_list.remove(current_node)
        closed_list.append(current_node)
        
        for successor in generate_successors(current_node):
            if not redundant(successor, open_list, closed_list):
                open_list.append(successor)
    
    return failure

Explanation:

The MemoryBoundedSearch function in this pseudocode accepts an issue and a memory limit as input. The nodes to be investigated and the nodes that have already been explored are stored in the open and closed lists, respectively, which are initialized. The algorithm then goes into a loop where it keeps track of whether memory use goes above the predetermined threshold. If that’s the case, memory is freed up by pruning the open and closed lists.

Based on a heuristic assessment, the select_best_node function selects the most promising node from the open list. The answer is sent back if this node is in the desired state. If not, the node is transferred from the open list to the closed list, and if its heirs have previously been investigated or are already on the open list, they are created and added to the open list.

Implemented of memory-bounded search strategy for the 8-puzzle problem

This is an example of a straightforward memory-bounded search strategy for the 8-puzzle problem implemented in Python:

code steps:

Node Class: Defines a class representing nodes in the search tree, with attributes state, parent, and action.
Heuristic Function: Calculates the Manhattan distance heuristic for a given state.
Memory Usage Function: Computes the total memory usage based on the length of the open and closed lists.
Prune Memory Function: Prunes the least promising nodes from the open list to reduce memory usage.
Select Best Node Function: Selects the node with the lowest heuristic value from the open list.
Goal State Check Function: Checks if a given node’s state matches the goal state.
Generate Successors Function: Generates successor nodes by swapping the blank space with neighboring tiles.
Redundancy Check Function: Determines if a successor node is redundant by checking if its state is already present in either the open or closed list.
Memory-Bounded Search Function: Performs a memory-bounded search using A* algorithm, considering memory limit.
Goal State Definition: Defines the goal state of the puzzle.
Possible Moves Definition: Defines the possible moves for each position on the puzzle grid.
Example Usage: Specifies an initial state of the puzzle and sets a memory limit for the search.
Solution Found Check: Checks if a solution node is found within the memory limit.
Print Solution Path: If a solution is found, prints the sequence of actions and states leading from the initial state to the goal state.
Memory Limit Exceeded Check: Prints a message if the memory limit is exceeded without finding a solution.

Python

# Define a class to represent nodes in the search tree
class Node:
    def __init__(self, state, parent=None, action=None):
        self.state = state
        self.parent = parent
        self.action = action

# Define the heuristic function (Manhattan distance)
def heuristic(state):
    distance = 0
    for i in range(9):
        if state[i] != 0:
            distance += abs(i // 3 - (state[i] - 1) // 3) + abs(i % 3 - (state[i] - 1) % 3)
    return distance

# Define the memory usage function
def memory_usage(open_list, closed_list):
    return len(open_list) + len(closed_list)

# Define the function to prune memory
def prune_memory(open_list, closed_list):
    # Prune the least promising nodes from the open list
    open_list.sort(key=lambda x: heuristic(x.state), reverse=True)
    open_list[:] = open_list[:len(open_list) // 2]  # Keep only the top half of the open list

# Define the function to select the best node
def select_best_node(open_list):
    return min(open_list, key=lambda x: heuristic(x.state))

# Define the function to check if a node is the goal state
def is_goal(node):
    return node.state == goal_state

# Define the function to generate successors
def generate_successors(node):
    successors = []
    zero_index = node.state.index(0)
    for move in moves[zero_index]:
        new_state = list(node.state)
        new_state[zero_index], new_state[move] = new_state[move], new_state[zero_index]
        successors.append(Node(tuple(new_state), parent=node, action=move))
    return successors

# Define the function to check if a successor is redundant
def redundant(successor, open_list, closed_list):
    for node in open_list + closed_list:
        if node.state == successor.state:
            return True
    return False


# Define the memory-bounded search function
def MemoryBoundedSearch(initial_state, memory_limit):
    node = Node(initial_state)
    open_list = [node]
    closed_list = []
    
    while open_list:
        if memory_usage(open_list, closed_list) > memory_limit:
            prune_memory(open_list, closed_list)

        # No solution found within memory limit
        if not open_list:
            return None  
        
        current_node = select_best_node(open_list)
        # Return the goal node
        if is_goal(current_node):
            return current_node  
        
        open_list.remove(current_node)
        closed_list.append(current_node)
        
        for successor in generate_successors(current_node):
            if not redundant(successor, open_list, closed_list):
                open_list.append(successor)
                
    # No solution found within memory limit
    return None  


# Define the goal state
goal_state = (1, 2, 3, 4, 5, 6, 7, 8, 0)

# Define the possible moves
moves = {
    0: [1, 3],
    1: [0, 2, 4],
    2: [1, 5],
    3: [0, 4, 6],
    4: [1, 3, 5, 7],
    5: [2, 4, 8],
    6: [3, 7],
    7: [4, 6, 8],
    8: [5, 7]
}

# Example usage
initial_state = (1, 2, 3, 4, 5, 6, 0, 7, 8)  # Initial state of the puzzle

print("Case 1 with Memory Limit 1")
memory_limit = 1  # Set memory limit

goal_node = MemoryBoundedSearch(initial_state, memory_limit)
if goal_node:
    print("Solution found!")
    # Print the solution path if needed
    while goal_node.parent:
        print("Action:", goal_node.action)
        print("State:")
        print(goal_node.state[:3])
        print(goal_node.state[3:6])
        print(goal_node.state[6:])
        print()
        goal_node = goal_node.parent
else:
    print("Memory limit exceeded. No solution found within the given memory limit.")

print("\nCase 1 with Memory Limit 10")
memory_limit = 10  # Set memory limit
goal_node = MemoryBoundedSearch(initial_state, memory_limit)
if goal_node:
    print("Solution found!")
    # Print the solution path if needed
    while goal_node.parent:
        print("Action:", goal_node.action)
        print("State:")
        print(goal_node.state[:3])
        print(goal_node.state[3:6])
        print(goal_node.state[6:])
        print()
        goal_node = goal_node.parent
else:
    print("Memory limit exceeded. No solution found within the given memory limit.")

Output:

Case 1 with Memory Limit 1
Memory limit exceeded. No solution found within the given memory limit.

Case 1 with Memory Limit 10
Solution found!
Action: 8
State:
(1, 2, 3)
(4, 5, 6)
(7, 8, 0)

Action: 7
State:
(1, 2, 3)
(4, 5, 6)
(7, 0, 8)

Memory-bounded search ( Memory Bounded Heuristic Search ) in AI

Search algorithms are fundamental techniques in the field of artificial intelligence (AI) that let agents or systems solve challenging issues. Memory-bounded search strategies are necessary because AI systems often encounter constrained memory resources in real-world circumstances. The notion of memory-bound search, often referred to as memory-bounded heuristic search, is examined in this article along with its importance in AI applications. We will review how AI effectively manages search jobs when memory resources are limited and provide a useful how-to manual for putting memory-bound search algorithms into practice.

Table of Content

Understanding Memory-Bound Search
Benefits of Memory-Bound Search
Implementing Memory-Bound Search

Pseudocode: Memory-Bounded A* Algorithm
Implemented of memory-bounded search strategy for the 8-puzzle problem

Applying Memory-Bound Search in AI
Conclusion
FAQs on Memory-bounded search (or Memory Bounded Heuristic Search)

Implementing Memory-Bound Search

Pseudocode: Memory-Bounded A* Algorithm

Implemented of memory-bounded search strategy for the 8-puzzle problem

Memory-bounded search ( Memory Bounded Heuristic Search ) in AI

Similar Reads