1.9 Heuristics Flashcards
(28 cards)
What is a heuristic?
A technique that willingly accepts a non-optimal or less accurate solution to improve execution speed.
Heuristics are often used in algorithms when optimal solutions require excessive computational resources.
What is the goal in the knapsack problem?
To put items in the knapsack such that the weight ≤ 30 pounds and the value is maximized.
Each item has a specific weight and value associated with it.
What is the maximum weight limit for the knapsack in the given example?
30 pounds.
What is an example of a combination of items that can fit in the knapsack worth $142?
One 20 pound item and one 8 pound item.
What combination of items provides the best value in the knapsack example?
5 6-pound items.
This combination is worth $151, which is greater than the other options.
True or False: The optimal solution for the knapsack problem can exceed the weight limit.
False.
What does the term ‘0-1 knapsack problem’ refer to?
A knapsack problem where at most 1 of each item can be taken.
What is the main characteristic of a heuristic algorithm?
It quickly determines a near-optimal or approximate solution.
What is the purpose of the Knapsack01 function?
To sort the item list by value and fill the knapsack with the most valuable items that fit within the weight limit.
What is the result of the Knapsack01 function in the given example?
$95.
What is a limitation of the heuristic algorithm demonstrated in the Knapsack01 function?
It sacrifices optimality for efficiency and simplicity.
Fill in the blank: A self-adjusting heuristic modifies a _______ based on its use.
data structure.
What happens when a frequently searched item is moved to the front of a list?
It lowers the total number of comparisons needed for future searches.
What does the move-to-front self-adjusting heuristic do?
Moves a list item to the front when that item is searched for.
True or False: A heuristic algorithm typically does not sacrifice accuracy.
False.
Which item combination is better than the result from Knapsack01, worth $102?
The 12-pound and 8-pound items together.
What is the sorting order for the item list in the Knapsack01 function?
Descending by value.
Under what condition will the Knapsack01 function not include the most valuable item?
If the weight of the most valuable item is greater than the knapsack’s limit.
What is the effect of frequent searches for already-searched-for keys?
Lowers the total number of comparisons
This is due to the move-to-front heuristic, which optimizes search efficiency by moving frequently accessed elements closer to the start of the list.
How many items does a linear search for 42 compare against when it is at the end of a list with 8 items?
8 items
A linear search checks each item sequentially until it finds the target.
What does the move-to-front heuristic do after a search for a key?
Moves the key to the front of the list
This technique reduces future search times for that key by placing it at the beginning.
After moving 42 to the front of the list, how many comparisons are needed for a subsequent search for 42?
1 comparison
This is the most efficient scenario for searching after the key has been moved to the front.
How many items does a search for 64 compare against when it is at the end of the list?
8 items
Similar to the search for 42, a linear search for 64 at the end of the list requires checking all items.
What happens to 64 after a search for it?
Moves to the front of the list
This adjustment follows the move-to-front heuristic principle.
