Artificial Intelligence Search Algorithms Project

This project is a university Artificial Intelligence assignment that demonstrates classic graph search algorithms. The program loads a state-space graph from a text file, then searches from a configurable initial state to a configurable goal state.

Implemented Algorithms

Uninformed search:

1. Breadth-First Search (BFS)
2. Depth-First Search (DFS)
3. Uniform Cost Search (UCS)
4. Depth-Limited Search (DLS)
5. Iterative Deepening Depth-First Search (IDDFS)

Informed search:

6. Greedy Best-First Search
7. A* Search

Algorithm Comparison

Algorithm	Priority / Strategy	Uses edge cost?	Uses heuristic?	Typical guarantee / note
BFS	FIFO frontier, level by level	Not for priority	No	Finds a path with the fewest edges
DFS	LIFO frontier, depth first	Not for priority	No	Finds a reachable path, but not necessarily an optimal one
UCS	Lowest g(n)	Yes	No	Finds a lowest-cost path when step costs are non-negative
DLS	DFS up to a fixed depth	Not for priority	No	Success depends on the chosen depth limit
IDDFS	Repeated DLS with increasing limits	Not for priority	No	Finds shallow solutions by increasing the depth limit
Greedy Best-First	Lowest h(n)	No	Yes	Often goal-directed, but not generally optimal
A*	Lowest g(n) + h(n)	Yes	Yes	Finds a lowest-cost path under the usual cost and heuristic assumptions

On graph_simple1.txt, the algorithms illustrate why the search strategy matters:

Algorithm	Path	Cost
BFS	A -> C	10
Greedy Best-First	A -> C	10
UCS	A -> B -> C	7
A*	A -> B -> C	7

Correctness Notes

• BFS minimizes the number of edges, not weighted path cost.
• DFS does not guarantee an optimal path.
• UCS has its normal lowest-cost guarantee when step costs are non-negative.
• DLS depends on the selected depth limit; IDDFS repeatedly increases that limit.
• Greedy Best-First Search follows h(n) and is not generally optimal.
• A* follows g(n) + h(n). Its weighted-cost guarantee depends on the usual non-negative-cost and admissible-heuristic assumptions.
• When A* discovers a cheaper g(n) for an expanded state, it reopens that state. The automated regression suite covers an admissible but inconsistent heuristic case.

How To Run

Run from the project root:

python src/main.py

You can also run non-interactively:

python src/main.py data_test/graph_simple1.txt 1
python src/main.py data_test/graph_simple1.txt 3
python src/main.py data_test/graph_simple1.txt 7

Override the start or goal state:

python src/main.py data_test/graph_usa_cities.txt 7 --start NewYork --goal LosAngeles

Set depth limits:

python src/main.py data_test/graph_simple2.txt 4 --depth-limit 2
python src/main.py data_test/graph_iran_cities.txt 5 --max-depth 6

Install the development dependency and run the automated tests:

python -m pip install -r requirements-dev.txt
pytest -q

Data File Format

Each graph file uses this format:

InitialState GoalState
State1 State2 Cost
State2 State3 Cost
SLD
State1 GoalState HeuristicValue
State2 GoalState HeuristicValue
GoalState GoalState 0

The first line defines the default initial and goal states. Lines before SLD define undirected weighted graph edges. Lines after SLD define heuristic values used by Greedy Best-First Search and A* Search.

Example:

A C
A B 5
B C 2
A C 10
SLD
A C 8
B C 2
C C 0

Example Output

Running: A* Search

===== Step 1 =====
Selected node: A
Depth: 0
Path cost: 0
g(n): 0
h(n): 8.0
f(n) = g(n) + h(n): 8.0
Generated child nodes: [B(g=5.0, h=2.0, f=7.0), C(g=10.0, h=0, f=10.0)]
Current frontier: [B(g=5.0, h=2.0, f=7.0), C(g=10.0, h=0, f=10.0)]
Explored/expanded nodes: ['A']

At the end, the program prints the final path, total path cost, expanded node count, and generated child node count.