1
$\begingroup$

I have a search problem that requires me to find a path from $v_s$ to $v_g$ in the graph $G = (V, E)$ where $v_s, v_g \in V$ are the start and goal vertices in a set of vertices and $E \subset V \times V$ is an undirected set of edges connecting vertices. Both $V$ and $E$ can be infinite. Each edge has an associated cost $c: E \rightarrow \mathbb{R}$ and the cost of a path (an ordered set of edges) between adjacent vertices that leads from the start to the goal is the sum of the cost of all of its edges. My goal is to find the path with minimal cost (assume it exists).

From my understanding, because this graph could possibly have an infinite branching factor, A* is not guaranteed to return a solution (or terminate). Are there any viable alternative algorithms that are designed for handling graphs with large or infinite state and action spaces? I'm not looking for guaranteed termination or optimality, just some names of algorithms that might be used in these sorts of problems as my search for "heuristic search infinite state space" doesn't turn much up.

$\endgroup$
2
  • 2
    $\begingroup$ Can the values really by arbitrary values in $\mathbb{R}$? Or did you mean $\mathbb{R^+}$? $\endgroup$
    – Jakube
    May 4, 2021 at 21:37
  • $\begingroup$ Technically they are positive but I'm trying a formulation where each edge has a cost (positive) and a resulting reward in the neighboring vertex (negative), so the sum of the cost and reward can be any real. $\endgroup$
    – sdasdadas
    May 5, 2021 at 19:28

1 Answer 1

1
$\begingroup$

I believe you can use any algorithm for heuristic search. On infinite graphs, no algorithm is guaranteed to terminate, so I don't see a clear basis to reject A* or other standard algorithms for heuristic search.

$\endgroup$
1
  • $\begingroup$ Thank you, that's sort of the response I expected from a brief search through literature but I appreciate the answer. $\endgroup$
    – sdasdadas
    May 5, 2021 at 19:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.