Discrete Mathsfor Engineers

1. Problem Model

We consider a search problem defined over a state space represented as a graph or tree, where each node corresponds to a configuration and edges represent valid transitions.

Each transition has an associated cost, and the objective is to find a path from an initial state to a goal state with minimum total cost.

1.1 State Space

The problem is modeled as a state space (S, E), where:

• S: set of states
• E: transitions between states

The search starts from an initial state s₀ and aims to reach a goal state s*.

1.2 Cost Function

Each path has an associated cost:

g(n) = cost from the start node to n

The goal is to minimize the total path cost.

1.3 Heuristic Function

A heuristic function estimates the remaining cost:

h(n) ≈ cost from n to goal

The evaluation function is:

f(n) = g(n) + h(n)

This function guides the search toward promising regions.

1.4 Cost-Bounded Search

Unlike A*, IDA* does not expand nodes globally using a priority queue.

Instead, it performs depth-first searches limited by a cost threshold:

f(n) ≤ threshold

Nodes exceeding the threshold are pruned.

1.5 Iterative Deepening on Cost

The algorithm runs multiple iterations, each increasing the threshold.

• Start with initial threshold = h(s₀)
• Run DFS with cost bound
• Increase threshold to next minimum exceeded value

This process continues until the goal is found.