Connor's Notes

⬅️ Back to portfolio

COSC 3P71: Tutorial 3

4 min read

Search Algorithms

Heuristics

a “good” way to evaluate a problem state

  • can be an approximation, an educated guess, not perfect
  • why?: many problems where performing a brute force search is not computationally feasible

Connect Four Heuristics Example

  • heuristic should rank states closer to goal higher
  • Goal: win the game
  • e.g.
    • four same coloured pieces in a row: +
    • 3 same coloured pieces in a row: +500
    • 2 same coloured pieces in a row: +100
    • piece in the middle column: +10
  • 3 same coloured pieces with an open spot at each end?

Sliding Puzzle Heuristic

  • e.g.
    • manhattan distance (number of tiles vertically+horizontally from intended tile)
    • hamming distance (number of tiles that are out of place)
      • ignoring the blank tile → adds unnecessary complexity
  • uses information gathered from the problem
  • heuristic
  • guaranteed to find the shortest path if your heuristic is admissible (never over estimates cost to reach the goal)
  • evaluates path with function: where:
  • : path cost from the root to node n
  • : heuristic cost from n to the goal state

Iterative Deepening A* Search (IDA*)

  • implementation is quite different than A*
  • only remembers current path
  • A* implementation typically uses dynamic programming while IDA* uses recursion

IDA* implementation

  • define a “cutoff” value
  • if > cutoff, stop expansion
  • increase the cutoff value based on minimum of the visited child nodes
  • commonly implemented with a stack tracking the current path, no priority queue

Pseudocode:

IDAStar(Node root)
    cutoff = h(root)
    path = Stack<Node>
    path.push(root)
    repeat
        cheapestCost = recurse(path, 0, cutoff)
        cutoff = cheapestCost


recurse(path, currentPathCost, cutoff)
    currentNode = path[-1]
    newCost = currentPathCost + h(currentNode)
    if newCost > cutoff
        return newCost

    if currentNode.state == goal_state
        // Goal found, print path, exit

    min = MAX_VALUE
    for each child in currentNode.children
        if child not in path
            path.push(child)
            childPathCost = recurse(path, currentPathCost + 1, cutoff)
                // +1 = cost from currentNode to child
            min = Math.min(childPathCost, min)
            path.pop()

    return min

Python:

def ida_star(root):
    cutoff = h(root)
    path = [root]  # use list as stack
 
    while True:
        cheapest_cost = recurse(path, 0, cutoff)
        if cheapest_cost == float("inf"):
            return None  # no solution
        if isinstance(cheapest_cost, Node):  # found goal, return path or node
            return cheapest_cost
        cutoff = cheapest_cost
 
 
def recurse(path, current_path_cost, cutoff):
    current_node = path[-1]
    new_cost = current_path_cost + h(current_node)
 
    if new_cost > cutoff:
        return new_cost
 
    if current_node.state == goal_state:
        print("Goal found:", path)
        return current_node
 
    min_cost = float("inf")
 
    for child in current_node.children:
        if child not in path:
            path.append(child)
            child_path_cost = recurse(path, current_path_cost + 1, cutoff)
            # +1 = cost from currentNode to child
 
            if isinstance(child_path_cost, Node):  # propagate solution
                return child_path_cost
 
            min_cost = min(child_path_cost, min_cost)
            path.pop()
 
    return min_cost

IDA* complexity

  • space complexity: O(bd)
    • only remembers current path (at most, b*d)
    • A*: all nodes
  • time complexity: depends on heuristic
    • worst case: O()
    • same as A*
  • repeatedly apply DFS with an iteratively increasing depth limit
  • only check for goal state when reaching max depth current iteration
  • applicable for graphs/trees

IDS implementation

boolean IDS(node, target, maxDepth)
    for depth from 0 to maxDepth
        if DFS(node, target, depth)
            return true
    return false

boolean DFS(node, target, depth)
    if depth == 0 // max depth reached
        if node == target
            return true
        return false

    for each child of node
        if DFS(child, target, depth - 1)
            return true

    return false

def ids(node, target, max_depth):
    for depth in range(max_depth + 1):
        if dfs(node, target, depth):
            return True
    return False
 
 
def dfs(node, target, depth):
    if depth == 0:  # max depth reached
        return node == target
 
    for child in node.children:  # assumes node has a .children list
        if dfs(child, target, depth - 1):
            return True
 
    return False

IDS complexity

  • time complexity: O()
    • b: branching factor (max number of children a node can have)
    • d: max depth
  • space complexity: O(bd)

IDS vs BFS

  • new nodes are visited in the same order
  • IDS requires less memory
    • useful for very large graphs/trees
    • O(bd) vs O()
  • IDS provides intermediate results
    • useful for game tree searches (checkers, chess, go, etc.)

Graph View