Exam (elaborations)
cs 161 Exam midterm Study Terms and Questions with Correct Verified Answers
- Course
- Institution
cs 161 Exam midterm Study Terms and Questions with Correct Verified Answers
[Show more]
Seller
Follow
Content preview
cs 161 Exam midterm Study Terms andQuestions with Correct Verified Answers
Disjoint pattern databases - ANSWER Have non-overlapping moves where adding the costs
gives a lower bound for the solution cost
Local search goal - ANSWER Solve optimization problem where it wants the best state according
to an objective function
Hill climbing - ANSWER Go in direction of steepest ascent, considered "greedy" local search
Local max, ridges, plateaus - ANSWER Hill climbing can get stuck in these places
Simulated Annealing - ANSWER Add randomness factor, combine hill climbing with
random walk to balance efficiency and completeness
Local beam search - ANSWER Have k random states, choose the best k successors
every iteration
Parts of a CSP - ANSWER Needs variables, domains, constraints
Unary constraint - ANSWER Restrict value of single var
Binary constraint - ANSWER Relates two vars together
, Global constraint - ANSWER Limits all vars
Preference constraint - ANSWER Shows which solutions are preferred
Constraint propagation - ANSWER keeps local consistency, there's node consistency, arc
consistency, path consistency, and k-consistency
Node consistency - ANSWER Iff all values in variable's domain satisfies the unary constraints
Arc consistency - ANSWER Iff every value in domain satisfies its binary constraints
AC3 Algorithm - ANSWER Checks for inconsistency, runs in O(cd^3)
Resource constraint - ANSWER Ex. "AtMost"
Bounds propagation - ANSWER Change bounds depending on constraints
Bound-consistent - ANSWER Guaranteed at least one solution for all vars
Minimum remaining values (MRV) - ANSWER Choose var w/ fewest legal vars (most
constrained), fail-first, used for variable selection
Least constraining value (LCV) - ANSWER Choose value that allows for most choices for
neighbors, fail-last, used for value selection
Conflict between MRV and LCV - ANSWER Limit variable, allow for many values (so they
doesn't contradict)
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller KenAli. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $12.79. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
79079 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now