Anzeige
Erschienen in:
2014 | OriginalPaper | Buchkapitel
Speeding Up k-Neighborhood Local Search in Limited Memory Influence Diagrams
verfasst von : Denis D. Mauá, Fabio G. Cozman
Erschienen in: Probabilistic Graphical Models
Verlag: Springer International Publishing
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
Limited memory influence diagrams are graph-based models that describe decision problems with limited information, as in the case of teams and agents with imperfect recall. Solving a (limited memory) influence diagram is an NP-hard problem, often approached through local search. In this paper we investigate algorithms for
k
-neighborhood local search. We show that finding a
k
-neighbor that improves on the current solution is W[1]-hard and hence unlikely to be polynomial-time tractable. We then develop fast schema to perform approximate
k
-local search; experiments show that our methods improve on current local search algorithms both with respect to time and to accuracy.