1.9 Heuristics Flashcards
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.
Which scenario results in faster searches?
Back-to-back searches for the same key
This is because the key will be found at the front of the list after the first search.
In the first search for 81, how many list items are compared?
4 items
The items compared are 56, 11, 92, and 81 before finding the search key.
In the second search for 81, how many list items are compared?
1 item
Since 81 is now at the front of the list, it is found immediately.
Fill in the blank: A move-to-front heuristic is used on a list that starts as _______.
(56, 11, 92, 81, 68, 44)
This is an example list used to illustrate the heuristic’s effect.
