Finding mines in a Line
Authors
Abstract
We discuss solution approaches for the following problem: Given a line partitioned into segments,each segment is assigned the time taken to either search in or travel through it, as well as a score
value representing the probability to find a mine there. The goal is to choose the segments to visit
such that the sum of the scores is maximized while the total time spent is minimized. We compare different dynamic programming approaches to determine the non-dominated set of the
problem that are based on the modeling of the problem as a knapsack as well as a shortest-path
problem.