Anzeige
Erschienen in:
2018 | OriginalPaper | Buchkapitel
On the Competitiveness of Memoryless Strategies for the k-Canadian Traveller Problem
verfasst von : Pierre Bergé, Julien Hemery, Arpad Rimmel, Joanna Tomasik
Erschienen in: Combinatorial Optimization and Applications
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
The k-Canadian Traveller Problem (\(k\)-CTP), proven PSPACE-complete by Papadimitriou and Yannakakis, is a generalization of the Shortest Path Problem which admits blocked edges. Its objective is to determine the strategy that makes the traveller traverse graph G between two given nodes s and t with the minimal distance, knowing that at most k edges are blocked. The traveller discovers that an edge is blocked when arriving at one of its endpoints.
We study the competitiveness of randomized memoryless strategies to solve the \(k\)-CTP. Memoryless strategies are attractive in practice as a decision made by the strategy for a traveller in node v of G does not depend on his anterior moves. We establish that the competitive ratio of any randomized memoryless strategy cannot be better than \(2k + O\left( 1\right) \). This means that randomized memoryless strategies are asymptotically as competitive as deterministic strategies which achieve a ratio \(2k+1\) at best.