Skip to content

Latest commit

 

History

History
62 lines (49 loc) · 3.54 KB

README.md

File metadata and controls

62 lines (49 loc) · 3.54 KB
Raw

AI-Algorithms

Key Concepts:

  • Objective: Implement various AI search algorithms to find the best path from a start node (S) to a goal node (G).
  • Customization: The graph and heuristic values are user-defined and can be adjusted for any specific problem.

Search Algorithms and Expected Outputs

1. British Museum Search

  • Description: Brute-force approach; explores all possible paths exhaustively.
  • Use Case: Good for completeness but inefficient in large graphs.
  • Expected Output: Finds the goal by evaluating all possible paths.

2. Depth-First Search (DFS)

  • Description: Explores a branch as deeply as possible before backtracking.
  • Use Case: Works well for problems with deep solutions, but may not find the shortest path.
  • Expected Output: A path to the goal (not guaranteed to be the shortest).

3. Breadth-First Search (BFS)

  • Description: Explores nodes level by level, ensuring the shortest path in unweighted graphs.
  • Use Case: Best for unweighted graphs or problems where the shortest path is required.
  • Expected Output: Shortest path to the goal.

4. Hill Climbing

  • Description: A greedy algorithm that always expands the node with the lowest heuristic value.
  • Use Case: Fast but prone to local minima; does not guarantee an optimal solution.
  • Expected Output: A local optimum based on the heuristic values.

5. Beam Search

  • Description: Keeps track of a limited number of best nodes at each level to reduce memory usage.
  • Use Case: Useful when memory is a constraint and a heuristic is available.
  • Expected Output: A path, though not necessarily optimal due to memory limitations.

6. Oracle Search

  • Description: A hypothetical search algorithm that has perfect knowledge of the optimal path.
  • Use Case: Useful for comparison purposes or in environments with full path knowledge.
  • Expected Output: The shortest or optimal path to the goal.

7. Branch and Bound (B&B)

  • Description: Explores all paths but prunes those that are costlier than the best path found so far.
  • Use Case: Useful when we want to guarantee an optimal solution but reduce unnecessary exploration.
  • Expected Output: Optimal path with efficient pruning.

8. Branch and Bound Greedy

  • Description: Greedy version of B&B, using heuristics to guide the search.
  • Use Case: Faster than regular B&B but can miss the optimal path due to the greedy nature.
  • Expected Output: A heuristic-based path, potentially suboptimal.

9. Branch and Bound Greedy with Dead Horse Principle

  • Description: A variant of Greedy B&B that exits immediately when the goal node is found.
  • Use Case: Ideal when finding any solution quickly is more important than finding the optimal one.
  • Expected Output: First valid path to the goal.

10. Branch and Bound Greedy with Heuristics

  • Description: Combines cost and heuristic values for more aggressive pruning.
  • Use Case: Best when both cost and heuristic estimates are available for informed decisions.
  • Expected Output: More efficiently pruned path than regular B&B Greedy.

11. A Algorithm*

  • Description: Informed search using both path cost (g-value) and heuristics (h-value) to find the optimal path.
  • Use Case: Most commonly used algorithm for optimal pathfinding in graphs.
  • Expected Output: The optimal path with respect to both cost and heuristics.