A Generalization of the Shortest Path Problem to Graphs with Multiple Edge-Cost Estimates
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917592172593152 |
|---|---|
| author | Weiss, Eyal Felner, Ariel Kaminka, Gal A. |
| author_facet | Weiss, Eyal Felner, Ariel Kaminka, Gal A. |
| contents | The shortest path problem in graphs is a cornerstone of AI theory and applications. Existing algorithms generally ignore edge weight computation time. We present a generalized framework for weighted directed graphs, where edge weight can be computed (estimated) multiple times, at increasing accuracy and run-time expense. This raises several generalized variants of the shortest path problem. We introduce the problem of finding a path with the tightest lower-bound on the optimal cost. We then present two complete algorithms for the generalized problem, and empirically demonstrate their efficacy. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2208_11489 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | A Generalization of the Shortest Path Problem to Graphs with Multiple Edge-Cost Estimates Weiss, Eyal Felner, Ariel Kaminka, Gal A. Data Structures and Algorithms Artificial Intelligence Discrete Mathematics The shortest path problem in graphs is a cornerstone of AI theory and applications. Existing algorithms generally ignore edge weight computation time. We present a generalized framework for weighted directed graphs, where edge weight can be computed (estimated) multiple times, at increasing accuracy and run-time expense. This raises several generalized variants of the shortest path problem. We introduce the problem of finding a path with the tightest lower-bound on the optimal cost. We then present two complete algorithms for the generalized problem, and empirically demonstrate their efficacy. |
| title | A Generalization of the Shortest Path Problem to Graphs with Multiple Edge-Cost Estimates |
| topic | Data Structures and Algorithms Artificial Intelligence Discrete Mathematics |
| url | https://arxiv.org/abs/2208.11489 |