Please enable JavaScript.
Coggle requires JavaScript to display documents.
AI Week 8, A heuristic is consistent (monotone) if the estimate is always…
AI Week 8
A* search uses the cost function f(n) = g(n) + h(n) where g(n) is the cost to reach the node and h(n) is the heuristic function. This attempts to overcome a greedy search
We expand the node in the frontier with the lowest cost; don't add children to the frontier if already in the frontier or list of visited nodes (if the state is already in the frontier, we use the one with a smaller g(n)); stop when we reach a goal node
TIME COMPLEXITY: O(b^(đťś–d)) where đťś–= (h"-h)/h" (this is the relative error) and h" is the actual cost from root to goal node
SPACE COMPLEXITY: O(b^d) as we keep all the expanded nodes and those in the frontier stored in memory
-
Optimisation problems are those where we attempt to find a solution that either minimises or maximises one or more pre-defined objectives
They maintain whole candidate solutions from the beginning (rather than step by step paths) - these could be feasible or infeasible (e.g. may not take paths with viable connections)
Just because they're feasible, doesn't mean they're optimal
As many search problems have associated cost, we can formulate them as optimisation problems
Advantages: Usually more space efficient (as we don't maintain alternative candidate solutions, frequently require the same amount of space from beginning to end) ; Potentially more time efficient (depending on the algorithm) ; Don't necessarily require problem-specific heuristics
Disadvantages: Not guaranteed to find the optimal solution in reasonable time ; Not guaranteed to be complete (depending on operators and problem formulation)
Hill-Climbing
-
-
2) We repeatedly: generate neighbour solutions - these differ from the candidate solution by one element; find the best of the neighbour solutions; return the best between the best neighbour and the initial current solution (if the current solution is better, break out of the loop)
-
A heuristic is consistent (monotone) if the estimate is always no greater than the estimated distance from any neighbouring vertex to the goal plus the cost of reaching that neighbour h(n) <= cost(n,n') + h(n')
If this is true, A* is complete and optimal
-
-