Solving the Target-Value Search Problem

Authors

  • Carlos Linares López Universidad Carlos III de Madrid
  • Roni Stern Ben Gurion University
  • Ariel Felner Ben Gurion University

Keywords:

Heuristic Search, Combinatorial Search, Target-Value Search

Abstract

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