Unformatted text preview:

Hill-climbing SearchSome Hill-Climbing Algo’sLocal (Iterative) ImprovingTSP NotesUncross ProblemHill-climbing Search•Goal: Optimizing an objective function.•Can be applied to “goal” predicate type of problems.–BSAT with objective function number of clauses satisfied.•Intuition: Always move to a better stateSome Hill-Climbing Algo’s•Start State = empty state or random state or special state •Until (no improvement)–Steepest Ascent: find best successor–OR (greedy): select first improving successor–Go to that successor•Repeat the above process some number of times (Restarts).•Can be done with partial solutions or full solutions.Local (Iterative) Improving•Initial state = full candidate solution–Random or “nearest neighbor selection”•Greedy hill-climbing: –if up, do it–if flat, probabilistically decide to accept move•Not necessary for homework•Otherwise need to limit number of flat moves–if down, don’t do it•We are gradually expanding the possible moves.TSP Notes•Only use “up” moves•It is not necessary to compute the entire tour lengths after an operator applies. Instead compute change in length- most of the path length stays the same.•You keep applying the operators until no improvement occurs.Uncross


View Full Document

UCI ICS 171 - Hill-climbing Search

Documents in this Course
Prolog

Prolog

16 pages

PROJECT

PROJECT

3 pages

Quiz 6

Quiz 6

9 pages

Load more
Download Hill-climbing Search
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Hill-climbing Search and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Hill-climbing Search 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?