Class conducted on: 04-08-2024
and 11-08-2024
by Yash Shah
Basic Terminologies
Search problems involve an agent that is given an initial state and a goal state, and it returns a solution of how to get from the former to the latter. A navigator app uses a typical search process, where the agent (the thinking part of the program) receives as input your current location and your desired destination, and, based on a search algorithm, returns a suggested path. However, there are many other forms of search problems, like puzzles or mazes.
- Agent: An entity that perceives its environment and acts upon it. For example, in a navigation app, the agent represents a car deciding on actions to reach its destination.
- State: A configuration of an agent in its environment. In a 15 puzzle, a state represents a specific arrangement of the numbers on the board.
- Initial State: The starting point of the search algorithm. In a navigation app, this is the current location.
- Actions: The set of choices available in a state. In the 15 puzzle, actions consist of possible movements of squares in the current configuration.
- Transition Model: Describes the result of performing an action in a state. In the 15 puzzle, moving a square to a new position results in a new configuration.
- State Space: All states reachable from the initial state through any sequence of actions. In a 15 puzzle, this includes all possible configurations of the board.
- Goal Test: Determines whether a state is the goal state. In a navigation app, the goal test checks if the current location matches the destination.
- Path Cost: The numerical cost of a path. In a navigation app, this involves finding the fastest or most efficient route to the destination.
For more details check out:
https://cs50.harvard.edu/ai/2024/notes/0/
Solving Search Problems
Solution: A series of steps that moves from the starting point to the goal.
Optimal Solution: The solution with the lowest cost among all possible solutions.
In search problems, we use nodes to store important information:
- State: The current condition or situation.
- Parent Node: The previous node from which this node was reached.
- Action: The step taken to get from the parent node to this node.
- Path Cost: The total cost to reach this node from the starting point.