基于学习的图搜索问题算法

Feb, 2024

Learning-Based Algorithms for Graph Searching Problems

Adela Frances DePavia, Erasmo Tani, Ali Vakilian

TL;DR在这篇研究论文中，我们考虑了最近由 Banerjee 等人（2022）提出的预测图搜索问题。我们设计了一种算法来应对未知图上的搜索任务，并且在预测误差上提供了最优或接近最优的算法依赖关系的保证。此外，我们还提出了 Banerjee 等人（2022）算法在已知图上的性能边界，并为该情景建立了新的下界。

Abstract

We consider the problem of graph searching with prediction recently introduced by Banerjee et al. (2022). In this problem, an agent, starting at some vertex $r$ has to traverse a (potentially unknown) graph $G$ t

graph searching prediction unknown graphs formal guarantees performance bounds

发现论文，激发创造

在线图形探索方法的鲁棒化

利用机器学习预测作为辅助，通过引入预测算法结合最近邻算法，探索未知环境的学习增加变种基于线上图探索问题的研究，证明当预测精度高时算法显著优于其他线上算法，并在预测较差时保持良好保证，提供了与预测误差平稳退化的理论最坏情况下的绑定，并通过计算实验证实了结果，同时还扩展了该概念到鲁棒算法的一般框架，通过在给定算法与最近邻算法之间进行谨慎插值，证明了新的性能边界，既利用特定输入的良好性能，又确立了对任意输入的鲁棒性。

Dec, 2021

学习使用不确定拓扑地图进行规划

本文采用一种数据驱动的策略和基于图像的规划，应用于 3D 环境中的导航系统，通过机器学习方法实现了图像哈希表上的最短路径规划，比传统符号算法更优秀。

Jul, 2020

带预测的不确定性下的排序和超图定向

该论文研究了在不确定性条件下，利用学习增强算法处理排序和超图方向问题，并提出了针对准确和错误预测的性能保证算法，可以通过查询提高不确定性元素的精确度，从而最小化问题求解所需的查询数量。

May, 2023

图中的确定性和概率二分搜索

本文研究在带权无向图中的二分查找问题，并给出了一个在查询顶点时几乎达到信息熵下界的算法，同时也探讨了该问题在不同情况下的复杂性。

Mar, 2015

具有时序反馈图的对抗在线学习

基于分区策略，本研究提出了一种新的学习算法，用于预测与专家建议的问题并同时受限于反馈图结构，证明对于传递反馈图，该算法可以高效实现且达到最优遗憾界（与一个常数因子定量相近）的预测性能优化。