Bsc CSIT Semester 4 – Artificial Intelligence – Unit III: Problem Solving by Searching (9 Hrs.)

How is informed search different from uninformed search? Definitions - Uninformed search (also called blind search) is when the algorithm has no additional information beyond the problem definiti

How is Uniform Cost Search used to find a goal in the state space? Definition Uniform Cost Search is an uninformed search algorithm that expands nodes in order of increasing cumulative cost from

How is the minimax algorithm used in game search? The minimax algorithm is a recursive adversarial search technique used in two‑player, zero‑sum games where one player tries to maximize a value and

Definition: State Space Graph A state-space graph is a representation of all possible configurations (states) of a problem along with the transitions (actions) that take you from one state to anothe

What is Game Search? Game search is a technique in AI used to find the best possible move in a competitive game where players take turns. - Examples: Chess, Tic-Tac-Toe, Checkers. - AI evaluates p

What is a Constraint Satisfaction Problem (CSP)? A Constraint Satisfaction Problem (CSP) is a problem where: - We need to assign values to variables. - Each variable has a domain of possible values. -

Admissible Heuristic An admissible heuristic is a heuristic function that never overestimates the actual cost of reaching the goal. It always gives a value ≤ true cost, which guarantees optimality i

What is a Problem in AI? A problem in AI is a situation where an agent must move from an initial state to a goal state using a sequence of actions. It is defined clearly so that a search algorithm can

State Space Representation State space representation is a method to describe a problem using states and transitions between them. - State: A configuration of the problem - Initial State: Where th

Definition of a Game In AI, a game is a scenario where: - Two or more players take turns, - The outcome depends on moves of all players, - Goal is to maximize own benefit while minimizing opponent’s.

Answer (a) Difference between Informed and Uninformed Search (3 Marks) | Feature | Uninformed Search (Blind Search) | Informed Search (Heuristic Search) | |---------|---------------------------------

First-Order Predicate Logic Knowledge Base and Resolution Proof Step 1: Define Predicates and Knowledge Base Predicates: - T(x): x is a traffic - D(x): x is a driver - H(x): x horns - S(x): x is s

Alpha-Beta Cutoff Analysis The given tree is a Minimax tree with MAX at the root (A). We need to check if any alpha (α) or beta (β) cutoffs exist. Step 1: Leaf node values - H = 2, I = 4 - J = 6, K

Constructing State Space and Heuristic Analysis 1. State Space Construction Consider a simple graph from Start (S) to Goal (G): - Nodes: S, A, B, C, G - Local Costs (edge costs g(n)): - S -> A =

Uniform Cost Search (UCS) Algorithm Uniform Cost Search is a search algorithm used to find the least-cost path from a start node to a goal node in a state space. - It expands the node with the lowes

State Space Graph and Search Strategies 1. Definition: State Space Graph A state space graph is a graphical representation of all possible states of a problem along with the transitions (actions) bet

Game Search and Min–Max Algorithm in Game Playing 1. What is Game Search? - Definition: Game search is a technique in AI used to determine optimal moves in games where two or more players compete.

Constraint Satisfaction Problem (CSP) and Graph Coloring Example 1. What is a Constraint Satisfaction Problem (CSP)? - Definition: A CSP is a problem defined by: 1. A set of variables \(X = \{X1, X