Consider the problem of moving k knights from k starting squares s_1, s_2, ...,

Question

Consider the problem of moving k knights from k starting squares s_1, s_2, ..., s_k to k goal squares g_1, g_2, ..., g_k on an unbounded chess board, subject to the rate that no two knights can land on the same square at the same time. Each action allows you to move up to k knights (i.e., some may stay) simultaneously. We want to complete the maneuver with fewest actions. a) What is the maximum branching factor in this space? b) Suppose h_1 is an admissible heuristic for the problem of moving knight i to goal g_1 by itself. Which of the following heuristics is/are admissible for the k knights problem? min{h_1, ..., h_k} max{h_1, ..., h_k} sigma_i = 1^i = 1 h_i

Explanation / Answer

a ) The maximum branching factor in the space is given by 9k because there are 9 choices for the each knight for movement they are 8 choices of moves and one choice of not moving , hence there will be 9k actions .

b ) The heuristics of options 1st min{h1, . . . , hk}  and 2nd max {h1, . . . , hk} are admissible because if hi were exact the heuristic max {h1, . . . , hk}  would be exact for the relaxed problem where knights can land on the same square , and if min {h1, . . . , hk} is no larger than max {h1, . . . , hk} , then min {h1, . . . , hk} is admissible, hence options 1 and 2 are admissible.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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