Question 865 – Artificial-intelligence
April 14, 2024Question 867 – Artificial-intelligence
April 14, 2024Artificial-Intelligence
| Question 45 |
In heuristic search algorithms in Artificial Intelligence (AI), if a collection of admissible heuristics h1…….hm is available for a problem and none of them dominates any of the others, which should we choose ?
| h(n) = max{h1 (n), …., hm(n)} | |
| h(n) = min{h1(n), …., hm(n)} | |
| h(n) = avg{h1(n), …., hm(n)} | |
| h(n) = sum{h1(n), …., hm(n)} |
Question 45 Explanation:
Heuristic Search Strategies:
A key component of an evaluation function is a heuristic function h(n), which estimates the cost of the cheapest path from node ‘n’ to a goal node.
→ In connection of a search problem “heuristics” refers to a certain (but loose) upper or lower bound for the cost of the best solution.
→ Goal states are nevertheless identified: in a corresponding node ‘n’ it is required that h(n)=0
E.g., a certain lower bound bringing no information would be to set h(n) ≅ 0
→ Heuristic functions are the most common form in which additional knowledge is imported to the search algorithm.
Generating admissible heuristics from relaxed problems:
→ To come up with heuristic functions one can study relaxed problems from which some restrictions of the original problem have been removed.
→ The cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem (does not overestimate).
→ The optimal solution in the original problem is, by definition, also a solution in the relaxed problem.
Example:
→ Heuristic h1 for the 8-puzzle gives perfectly accurate path length for a simplified version of the puzzle, where a tile can move anywhere.
→ Similarly h2 gives an optimal solution to a relaxed 8-puzzle, where tiles can move also to occupied squares.
→ If a collection of admissible heuristics is available for a problem, and none of them dominates any of the others, we can use the composite function.
h(n) = max { h1(n), …, hm(n) }
→ The composite function dominates all of its component functions and is consistent if none of the components overestimates.
Reference:
http://www.cs.tut.fi/~elomaa/teach/AI-2011-3.pdf
A key component of an evaluation function is a heuristic function h(n), which estimates the cost of the cheapest path from node ‘n’ to a goal node.
→ In connection of a search problem “heuristics” refers to a certain (but loose) upper or lower bound for the cost of the best solution.
→ Goal states are nevertheless identified: in a corresponding node ‘n’ it is required that h(n)=0
E.g., a certain lower bound bringing no information would be to set h(n) ≅ 0
→ Heuristic functions are the most common form in which additional knowledge is imported to the search algorithm.
Generating admissible heuristics from relaxed problems:
→ To come up with heuristic functions one can study relaxed problems from which some restrictions of the original problem have been removed.
→ The cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem (does not overestimate).
→ The optimal solution in the original problem is, by definition, also a solution in the relaxed problem.
Example:
→ Heuristic h1 for the 8-puzzle gives perfectly accurate path length for a simplified version of the puzzle, where a tile can move anywhere.
→ Similarly h2 gives an optimal solution to a relaxed 8-puzzle, where tiles can move also to occupied squares.
→ If a collection of admissible heuristics is available for a problem, and none of them dominates any of the others, we can use the composite function.
h(n) = max { h1(n), …, hm(n) }
→ The composite function dominates all of its component functions and is consistent if none of the components overestimates.
Reference:
http://www.cs.tut.fi/~elomaa/teach/AI-2011-3.pdf
Correct Answer: A
Question 45 Explanation:
Heuristic Search Strategies:
A key component of an evaluation function is a heuristic function h(n), which estimates the cost of the cheapest path from node ‘n’ to a goal node.
→ In connection of a search problem “heuristics” refers to a certain (but loose) upper or lower bound for the cost of the best solution.
→ Goal states are nevertheless identified: in a corresponding node ‘n’ it is required that h(n)=0
E.g., a certain lower bound bringing no information would be to set h(n) ≅ 0
→ Heuristic functions are the most common form in which additional knowledge is imported to the search algorithm.
Generating admissible heuristics from relaxed problems:
→ To come up with heuristic functions one can study relaxed problems from which some restrictions of the original problem have been removed.
→ The cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem (does not overestimate).
→ The optimal solution in the original problem is, by definition, also a solution in the relaxed problem.
Example:
→ Heuristic h1 for the 8-puzzle gives perfectly accurate path length for a simplified version of the puzzle, where a tile can move anywhere.
→ Similarly h2 gives an optimal solution to a relaxed 8-puzzle, where tiles can move also to occupied squares.
→ If a collection of admissible heuristics is available for a problem, and none of them dominates any of the others, we can use the composite function.
h(n) = max { h1(n), …, hm(n) }
→ The composite function dominates all of its component functions and is consistent if none of the components overestimates.
Reference:
http://www.cs.tut.fi/~elomaa/teach/AI-2011-3.pdf
A key component of an evaluation function is a heuristic function h(n), which estimates the cost of the cheapest path from node ‘n’ to a goal node.
→ In connection of a search problem “heuristics” refers to a certain (but loose) upper or lower bound for the cost of the best solution.
→ Goal states are nevertheless identified: in a corresponding node ‘n’ it is required that h(n)=0
E.g., a certain lower bound bringing no information would be to set h(n) ≅ 0
→ Heuristic functions are the most common form in which additional knowledge is imported to the search algorithm.
Generating admissible heuristics from relaxed problems:
→ To come up with heuristic functions one can study relaxed problems from which some restrictions of the original problem have been removed.
→ The cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem (does not overestimate).
→ The optimal solution in the original problem is, by definition, also a solution in the relaxed problem.
Example:
→ Heuristic h1 for the 8-puzzle gives perfectly accurate path length for a simplified version of the puzzle, where a tile can move anywhere.
→ Similarly h2 gives an optimal solution to a relaxed 8-puzzle, where tiles can move also to occupied squares.
→ If a collection of admissible heuristics is available for a problem, and none of them dominates any of the others, we can use the composite function.
h(n) = max { h1(n), …, hm(n) }
→ The composite function dominates all of its component functions and is consistent if none of the components overestimates.
Reference:
http://www.cs.tut.fi/~elomaa/teach/AI-2011-3.pdf
Subscribe
Login
0 Comments