Conjecture on limiting pheromone weights and geodesics
Conjecture on limiting pheromone weights and geodesics
Let be any finite graph with two distinct marked vertices and . For each edge , let be its pheromone weight after ants, and let a geodesic mean a shortest path from to in . The loop-erased and uniform-geodesic ant processes are the two return rules described in the model.
Limiting-weight conjecture. Almost surely, as , for every ,
where is a random vector satisfying: for the loop-erased ant process, almost surely if and only if belongs to at least one geodesic from to ; for the uniform-geodesic ant process, almost surely only if belongs to at least one geodesic from to . Consequently, if the geodesic is unique, then almost surely for every in both models.
This gives a precise formulation of geodesic selection through the limiting normalized pheromone weights. The source indicates proofs for particular graph classes, but does not state a resolution of the conjecture for arbitrary finite graphs.
Sources & referencesView supporting material
Primary source
Daniel Kious, Cécile Mailler and Bruno Schapira, “Finding geodesics on graphs using reinforcement learning”, arXiv:2010.04820 (2020).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.