CS2004_Search_Concepts_Flashcards
(10 cards)
What is a search space?
A search space is the set of all possible solutions for a problem. Each point in the space represents a potential solution.
✅ Example: In TSP, the search space is all possible city visit orders (permutations).
What is a state in a search problem?
A state is a representation of a specific configuration or situation in the problem domain.
✅ Example: A partially filled Sudoku board is a state.
What is a solution representation?
It is the way in which a candidate solution is encoded for the algorithm to process.
✅ Example: A binary string in OneMax or a tour list in TSP.
What is a fitness function?
A fitness function evaluates how good a given solution is, typically returning a numerical score.
✅ Example: Total tour length in TSP or number of 1s in OneMax.
What is the role of a fitness function in heuristic search?
It guides the search by helping the algorithm compare and choose between solutions based on their fitness scores.
What is the difference between local and global optima?
A local optimum is better than its neighbours but not necessarily the best in the entire space. A global optimum is the absolute best solution.
What is a neighbourhood in local search?
A neighbourhood is the set of solutions that can be reached by applying a small change to the current solution.
✅ Example: Swapping two cities in a TSP tour.
What is an example of a fitness landscape?
A fitness landscape maps solution quality across the search space, showing peaks (optima) and valleys (poor solutions).
✅ Helps visualise where an algorithm might get stuck.
What does it mean for a solution to be invalid?
An invalid solution breaks one or more problem constraints.
✅ Example: A TSP tour that repeats a city or skips one.
Why is solution representation important?
It affects the efficiency and success of the search algorithm. A good representation makes the search easier and more effective.
