Week 3

This week we learned about Informed Search(Best First Search, Greedy Search, & A* Search) and Local Search(Hill Climbing, Simulated Annealing, & Genetic Algorithm).

Informed searches uses domain knowledge to guide selection of the best path to continue searching. Informed Searches use heuristics, which are informed guesses.

Best First Search tries to expand most desirable unexpanded nodes. Greedy Search selects the node to expand that is believed to be the closest to goal. A* Search is a searching algorithm that searches for the shortest path between the initial and the final state.

Local Search is a heuristic method for solving computationally hard optimisation problems. Local search algorithms move from solution to solution in the space of candidate solutions (the search space) by applying local changes, until a solution deemed optimal is found or a time bound is elapsed.

We also did exercises to find the path from Arad to Bucharest using Greedy Best First Search and A* Search. The other exercise is to perform Genetic Algorithm to find the word ‘bad’ from the population of the first 5 alphabet ‘abcde’. Today, the lessons were quite confusing and it is quite difficult to absorb all the knowledge in one session.