# Assignment 2: Search and Optimization

Implement all the mentioned algorithms on one of the given environments and record the performance (reward, time, point of convergence). Students are expected to submit a replicable GitHub repo and present a slide deck (maximum of six slides) on the results and explain the reasons for such performances. Slide deck should contain gifs of the implemented algorithms being executed in the environment. Also mention the heuristic function used.

*Team Size:* 1-2
*Deadline:* March 31, 2025

---

## Algorithms

- [Branch and Bound](https://en.wikipedia.org/wiki/Branch_and_bound)
- [Iterative Deepening A\](https://en.wikipedia.org/wiki/Iterative_deepening_A)
- [Hill Climbing](https://en.wikipedia.org/wiki/Hill_climbing)
- [Simulated Annealing](https://en.wikipedia.org/wiki/Simulated_annealing)

---

## Environments

### For BnB & IDA\*
- [Frozen Lake](https://gymnasium.farama.org/environments/toy_text/frozen_lake/)
- [Ant Maze](https://robotics.farama.org/envs/maze/ant_maze/)

*Instructions:*
Plot the average time taken to reach the goal state. Test for at least five runs. Terminate the run if goal state isn't reached even after some time τ has passed (Consider τ = 10 min; modify as required).

### For HC & SA
- [Traveling Salesman Problem](https://github.com/g-dendiev/gym_TSP)

*Instructions:*
Plot the average time taken to reach an optimum. Test for at least five runs. Terminate the run if goal state isn't reached even after some time τ has passed (Consider τ = 10 min; modify as required).