CAP4630 Introduction to Artificial Intelligence Homework 4 (7 pts, Due Oct 3 201

Question

CAP4630 Introduction to Artificial Intelligence Homework 4 (7 pts, Due Oct 3 2018) Homework solutions must be submitted through Canvas. No email submission is accepted. Please include all your answers in one file (pdf or word file). If you have multiple pictures, please include all pictures in one Word/pdf file. If you have to submit multiple files, please include all files as one zip file, and submit zip file online. You can always update your submissions before due date, but only the latest version will be graded.] [0.5 pt] Given two admissible heuristics h1 (n) and h2(n), which of the following heuristic are admissible? 1. a. h(n)-min(h(n),h2(n)) b. h(n)w hi(n) (1wh2(n), where 0 Sw 1

Explanation / Answer

1. h(n) = min{h1(n), h2(n)} is not admissible since an admissible heuristic never overestimates the cost of reaching the goal state. That is, its estimate will be lower than the actual cost or exactly the actual cost, but never higher.

Clearly, either h1(n) > h(n) or h2(n) > h(n). Hence, it is not admissible.

2. h(n) = w*h1(n) + (1-w) * h2(n) is admissible.

We know that h1(n) h(n) and h2(n) h(n),

thus w*h1(n) + (1-w) * h2(n) <= w*h(n) + (1-w) * h(n) <= h(n)

3. h(n) = max{h1(n), h2(n)} is admissible since an admissible heuristic never overestimates the cost of reaching the goal state. That is, its estimate will be lower than the actual cost or exactly the actual cost, but never higher.

Clearly, either h1(n) <= max{h1(n), h2(n)} and h2(n) <= max{h1(n), h2(n)}, thus, h1(n) <= h(n) and h2(n) <= h(n).

Hence, it is not admissible.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.