Solving the Target-Value Search Problem
DOI:
https://doi.org/10.1609/socs.v5i1.18335Keywords:
Heuristic Search, Combinatorial Search, Target-Value SearchAbstract
This paper addresses the Target-Value Search (TVS) problem, which is the problem of finding a path between two nodes in a graph whose cost is as close as possible to a given target value, T. This problem has been previously addressed: first, for directed acyclic graphs; second, for general graphs under the assumption that nodes can be revisited given that the same edge can not be traversed twice. In this work we focus on a more restrictive variant of the same problem where nodes can not be revisited. We prove that this variant is NP-complete and discuss novel theoretical properties and provide empirical results to solve this problem optimally.
Downloads
Published
2021-09-01
Issue
Section
Research Abstracts