{ "@context": "https://schema.org", "@type": "Organization", "name": "Brainscape", "url": "https://www.brainscape.com/", "logo": "https://www.brainscape.com/pks/images/cms/public-views/shared/Brainscape-logo-c4e172b280b4616f7fda.svg", "sameAs": [ "https://www.facebook.com/Brainscape", "https://x.com/brainscape", "https://www.linkedin.com/company/brainscape", "https://www.instagram.com/brainscape/", "https://www.tiktok.com/@brainscapeu", "https://www.pinterest.com/brainscape/", "https://www.youtube.com/@BrainscapeNY" ], "contactPoint": { "@type": "ContactPoint", "telephone": "(929) 334-4005", "contactType": "customer service", "availableLanguage": ["English"] }, "founder": { "@type": "Person", "name": "Andrew Cohen" }, "description": "Brainscape’s spaced repetition system is proven to DOUBLE learning results! Find, make, and study flashcards online or in our mobile app. Serious learners only.", "address": { "@type": "PostalAddress", "streetAddress": "159 W 25th St, Ste 517", "addressLocality": "New York", "addressRegion": "NY", "postalCode": "10001", "addressCountry": "USA" } }

Solving Problems by Searching Flashcards

(12 cards)

1
Q

What is a problem-solving agent?

A

An agent that plans a sequence of actions to reach a goal state when the correct action isn’t immediately obvious.

Example: Finding a route from home to SDU (Slide 4).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What are the components of a search problem?

A
  1. Initial state
  2. Goal state
  3. Successor function
  4. Path cost
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What is the state space?

A

The set of all states reachable from the initial state via the successor function — often visualized as a graph

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is an optimal solution?

A

A sequence of actions that leads to the goal with the lowest total path cost

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What type of agent uses search?

A

A goal-based agent operating in an observable, deterministic, discrete, and known environment

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is the fringe in tree search?

A

The list of unexpanded nodes — the frontier of the search

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What’s the difference between a node and a state?

A

A state represents a configuration in the problem, while a node is a data structure in the search tree that contains the state, path, and cost

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What are the four evaluation metrics for search strategies?

A
  1. Completeness – Will it find a solution if one exists?
  2. Optimality – Will it find the best (least-cost) solution?
  3. Time complexity – How long does it take?
  4. Space complexity – How much memory does it use?
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

How does Breadth-First Search (BFS) work?

A

Expands the shallowest nodes first using a FIFO queue.
Properties: Complete, optimal if cost = 1, time/space = O(b^d)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

How does Uniform-Cost Search (UCS) work?

A

Expands the least-cost node first using a priority queue ordered by path cost.
Properties: Complete, optimal, time/space = O(b^(1 + C*/ε))

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

How does Depth-First Search (DFS) work?

A

Expands the deepest node first using a LIFO stack.
Properties: Not complete (in infinite trees), not optimal, space = O(bm)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What is Iterative Deepening Search (IDS)?

A

Combines DFS with increasing depth limits to maintain completeness and low memory use.
Properties: Complete, optimal if cost = 1, time = O(b^d), space = O(bd)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly