Given a graph whose nodes have values attached to them, find the shortest path (edges have distances attached to them) through the graph which visits enough nodes so that the sum of the values of the visited nodes equals or exceeds a given target threshold. Nodes aren't counted multiple times even if they are visited multiple times. (Or, prohibit visiting a node multiple times.)
This is a generalization of the traveling salesman problem: for regular TSP, give each node a value of 1 and set the threshold to the total number of nodes. This generalization appears exponentially more difficult than TSP because there are an exponential number of subsets.
Inspired by Zelda BOTW: find a subset of shrines, and a route among them, that allows pulling the Master Sword as early as possible (for a speedrun, not exploiting the heart duplication glitch). Or, speedrun maximizing your inventory space (weapon stashes), which requires choosing and finding the shortest path among 441 of the 900 Korok puzzles. binomial(900, 441) ~= 10^269 and 441! ~= 10^976.
No comments :
Post a Comment