A formal framework for evaluating heuristic programs |
| |
Authors: | Lenore Cowen Joan Feigenbaum Sampath Kannan |
| |
Affiliation: | (1) Department of Mathematical Sciences and Department of Computer Science, Johns Hopkins University, Baltimore, MD 21218, USA;(2) AT&T Labs – Research, 180 Park Avenue, Florham Park, NJ 07932, USA;(3) Department of Computer and Information Science, University of Pennsylvania, Philadelphia, PA 19104, USA |
| |
Abstract: | We address the question of how one evaluates the usefulness of a heuristic program on a particular input. If theoretical tools do not allow us to decide for every instance whether a particular heuristic is fast enough, might we at least write a simple, fast companion program that makes this decision on some inputs of interest? We call such a companion program a timer for the heuristic. Timers are related to program checkers, as defined by Blum (1993), in the following sense: Checkers are companion programs that check the correctness of the output produced by (unproven but bounded‐time) programs on particular instances; timers, on the other hand, are companion programs that attempt to bound the running time on particular instances of correct programs whose running times have not been fully analyzed. This paper provides a family of definitions that formalize the notion of a timer and some preliminary results that demonstrate the utility of these definitions. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|