Three algorithms for finding mines in a line
Authors
Abstract
We introduce three algorithms for the problem of finding mines in a line. In this problem we are given a line partitioned into small segments, the time takento either search in or travel through each segment, as well as a score value assigned to each segment. The goal is to choose the segments to visit such that the sum of the corresponding scores is maximized and the total travel and search time is minimized. The two algorithms are based on dynamic programming approaches for the multi-criteria knapsack problem. The third algorithm solves
a bi-criteria shortest path problem formulation.