aiml-lab-week5

Week5: Heuristic Search

Outcome of this week is:

Aim: To write a Python program for implementing Heuristic Search

why is it called so:

from the available dataset, the best outcome/ result is to be searched

Heuristic Search- Theory

It is a search strategy that uses a heuristic function h(n) to guide the search toward the most promising solution instead of exploring all possibilities blindly. The heuristic is a problem-specific estimate that ranks options based on how close they are to the goal. If in dataset, data doesnot appear valid, it is penalized.

Program for Heuristic Search- Example-1 (based on total marks)

# Heuristic Search (Greedy Best-First) based on student marks

students = {

"A": {"math": 78, "physics": 82, "cs": 90},

"B": {"math": 88, "physics": 76, "cs": 85},

"C": {"math": 92, "physics": 89, "cs": 91},

"D": {"math": 70, "physics": 68, "cs": 75}

}

def heuristic(student_marks):

# Heuristic function: total marks

return sum(student_marks.values())

open_list = []

# Initialize search space

for student, marks in students.items():

open_list.append((student, heuristic(marks)))

# Greedy selection based on heuristic value

open_list.sort(key=lambda x: x[1], reverse=True)

# Best student according to heuristic

best_student, best_score = open_list[0]

print("Best student:", best_student)

print("Total marks:", best_score)

Program for Heuristic Search- Example-2 (based on CGPA, backlogs, attendance)

# Heuristic Search: Scholarship Candidate Selection

students = {

"Suresh": {"CGPA": 8.8, "backlogs": 0, "attendance": 92},

"Ramesh": {"CGPA": 9.2, "backlogs": 1, "attendance": 85},

"Jagadesh": {"CGPA": 9.6, "backlogs": 2, "attendance": 80},

"Rajesh": {"CGPA": 8.5, "backlogs": 0, "attendance": 68},

"Mahesh": {"CGPA": 9.0, "backlogs": 0, "attendance": 88}

}

def heuristic(student):

penalty = 0

if student["attendance"] < 75:

penalty = 75 - student["attendance"]

return (

student["CGPA"]

- (student["backlogs"] * 40)

- penalty

)

# OPEN list (frontier)

open_list = []

for name, data in students.items():

h_value = heuristic(data)

open_list.append((name, h_value))

# Greedy Best-First Search

open_list.sort(key=lambda x: x[1], reverse=True)

best_student, best_score = open_list[0]

print("Selected Scholarship Candidate")

print("Student:", best_student)

print("Heuristic Score:", best_score)

Program for Heuristic Search- Example-3 (based on CGPA, backlogs from a csv file)

#download link for csv file ---LINK

#File --> Download OR direct download button

import pandas as pd

df = pd.read_csv(r"C:\\Users\\krish\\Desktop\\students.csv")

def heuristic(cgpa, backlogs):

# Penalize backlogs

return cgpa - (backlogs * 0.5)

open_list = []

for _, row in df.iterrows():

score = heuristic(row["CGPA"], row["Backlogs"])

open_list.append((row["Roll"], score))

# Greedy heuristic selection

open_list.sort(key=lambda x: x[1], reverse=True)

best_student, best_score = open_list[0]

print("Best student (Roll No):", best_student)

print("Heuristic Score:", best_score)

Viva-voce Questions:

What is heuristic search in AI?
Heuristic search is an informed search strategy that uses a heuristic function h(n) to guide the search toward the most promising solution rather than exhaustively exploring all possibilities.
Why is it called “heuristic” search?
It is called heuristic because it uses a rule-of-thumb estimate that ranks options based on how close they are to the goal, enabling more efficient search.
What is a heuristic function?
A heuristic function h(n) provides an estimate of the desirability or proximity of a state to the goal, guiding the search toward the best outcome.
How is a heuristic search different from uninformed search?
Heuristic search uses problem-specific information to prioritize promising paths, while uninformed search blindly explores without additional guidance.
In the student marks example, how is the heuristic computed?
The heuristic is computed as the total marks of a student by summing marks across subjects to prioritize higher scores.
What does the Python program’s open_list represent in heuristic search?
The open_list represents the frontier or candidate list of states with their heuristic scores from which the best candidate is selected.
How does the selection occur after computing heuristic values?
After computing the heuristic for each candidate, the list is sorted in descending order of heuristic scores, and the best one is chosen.
In the scholarship example, how are penalties used in the heuristic?
Penalties are applied for backlogs and low attendance, reducing the heuristic score to prefer candidates with better overall profiles.
What is a practical advantage of using heuristic search in real problems?
Heuristic search reduces the number of states explored by focusing on promising candidates, improving efficiency in large search spaces.
Why is sorting by heuristic score essential in the Python heuristic search code?
Sorting ensures that the search process prioritizes the state with the highest estimated desirability first, simulating greedy selection toward the goal.

Google Sites

Report abuse