本文系 KDD2019 論文的解讀：
Wang, Jingyuan, Ning Wu, Wayne Xin Zhao, Fanzhang Peng, and Xin Lin. "Empowering A* Search Algorithms with Neural Networks for Personalized Route Recommendation." InProceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 539-547. ACM, 2019.

作者：吳寧

研究動機

A* 算法因為它的高效和準確而被廣泛應用于路徑發現和圖遍歷等任務上。斯坦福的 Peter Hart, Nils Nilsson and Bertram Raphael（Nils Nilsson 老先生于 2019 年 4 月 23 日去世，哀悼）于 1968 年首次提出了 A* 算法。A* 算法在尋找最優路徑的過程中，使用 f(n) 來評價所有候選節點的得分，每次要擴展結點的時候都會選擇那個 f(n) 最小的節點:

g(n) 是從出發點到 n 節點的費用值，而 h(n) 是一個被估計的從 n 到終點的費用值。不同于Dijkstra算法，A* 算法需要多考慮一個啟發值 h(n)，通過啟發值的幫助，A* 算法可以大大減小搜索空間。

此圖引用于：https://www.redblobgames.com/pathfinding/a-star/introduction.html

上圖是三種搜索算法的對比，Dijkstra 算法只使用 g(n), 雖然可以找到最優路徑，但是搜索空間巨大。貪心的最佳優先（Greedy Best-First）算法只使用 h(n)，雖然減小了搜索空間，但是不能保證得到最優的結果。而 A* 算法可以保證得到最優路徑，并且大大減小了搜索空間。

傳統的 A* 算法使用一些比較簡單的指標作為 g(n) 和 h(n)，比如歐氏距離，用以解決最短路徑等比較簡單的問題，因此對于一些復雜的非線性問題的搜索求解并不適用。

在智能交通領域，一個非常典型的例子就是個性化的路徑推薦。傳統的 A* 算法對于“最短路徑”、“最快路徑”的搜索非常有效，但是對于“最喜歡的路徑”搜索就很難發揮作用。

因為用戶的偏好是一個非常復雜的非線性過程，無法用簡單的歐氏距離進行度量。面對這樣的問題，我們提出使用深度神經網絡來學習 A* 算法的 g(n) 和 h(n) 值，以此來幫助 A* 算法解決更為復雜的問題。

研究思路

我們以個性化出行路徑推薦為例子介紹神經網絡是怎樣與 A* 算法結合的。出行路徑推薦是一個和我們平時生活息息相關的問題，也一直是各大地圖應用的核心算法之一。一個好的路徑推薦算法，可以提升人們的出行體驗，為經濟社會的發展帶來價值。

出行路徑推薦受到了學術界和工業界的廣泛關注，最初的路徑規劃算法討論的是怎樣在路網上找到一條最短路徑。隨著時代的發展，基于歷史軌跡數據的個性化的路徑推薦任務也開始受到研究者們的關注。

過去的路徑推薦方案大多以 A* 搜索為框架不同的費用函數對應于不同的搜索任務，比如說以移動距離為費用，那么搜索的便是最短路徑，以用時為費用，那么搜索的便是最快路徑，以用戶的偏好為費用，那么便是個性化的路徑推薦。

在現有工作中，大家往往以簡單的統計或者淺層的模型來作為搜索的費用函數，但是用戶的喜好往往是難以被如此簡單地建模的，因此，我們提出用神經網絡來學習 A* 搜索算法中的費用函數，以此為基礎結合 A* 搜索算法來完成個性化的路徑推薦。本文 Empowering A ? Search Algorithms with Neural Networks for Personalized Route Recommendation 已經被 KDD 2019 收錄，可以通過https://arxiv.org/pdf/1907.08489.pdf 下載。

模型介紹

任務定義

路徑推薦任務中，我們的模型接受一個歷史軌跡數據集D，起點 ls，終點 ld，出發時間 b 和用戶 u 作為輸入，然后基于輸入推薦個性化的軌跡 。形式化地來講，我們需要找到一條條件概率最高的最優路徑：

基于A*算法的解決方案

首先我們討論傳統 A* 算法在路徑推薦上的應用。A* 算法是 Dijkstra 算法的擴展，在尋找最優路徑的過程中，它每次擴展一個結點 n，然后使用 f(n) 來評價這個節點的得分：

g(n) 是從出發點到 n 節點的費用值，而 h(n) 是一個被估計的從 n 到終點的費用值。我們算法的關鍵部分就是 h(n) 的設計，它會大大影響算法的效果和性能。

前面已經說過了，我們的任務目標是最大化 Pr(p|q,u,D)，它等同于最小化負對數 -logPr(p|q,u,D)。給出一條可能的路徑

，我們可以將路徑的概率分解為各個項之和。

因此，對于一條路徑

，我們可以計算已知費用 ：

為了方便計算條件轉移概率，在傳統 A* 算法費用函數的計算中，一階馬爾可夫假設經常被使用，因此我們有

。然而在個性化路徑推薦的任務中，這樣簡單的假設并不能很好地建模用戶對于每個位置的選擇，因此我們需要引入深度學習來建模用戶和位置之間的復雜依賴關系。

NASR模型結構

本文的網絡主要分為兩部分：g() 和 h()，分別對應于 A* 搜索算法中的兩個 Cost：g 和 h。g() 學習的是從起點到候選位置的費用，我們稱之為可觀測費用，而 h() 學習的是從候選位置到終點的費用，我們稱之為估計費用。在設計這兩個網絡的時候，需要滿足一些要求：

1. 如何衡量已知路徑的費用：怎樣捕獲用戶的個性化偏好，時空特征以及路網限制呢? 用戶的每一次的選擇都會帶來費用，這個費用跟用戶的歷史信息有關，跟時空信息也有關，并且還受到了路網鄰接關系的影響。

2. 如何去衡量未來的費用：給定候選位置和終點，如何衡量這兩個位置之間的費用呢? 類似于衡量路網上兩個點的距離，在考慮用戶偏好的前提下，怎樣建模路網上兩個位置之間潛在的費用是一個很重要的問題。

特征嵌入:

首先我們介紹多源輸入信息的嵌入。通過詞嵌入技術，我們將離散的用戶信息嵌入到一個低維向量中，用 Vu 來表示。對于每一個位置，我們也使用相似的方法將這個位置嵌入到一個低維向量中，用 Vl 來表示。另外，我們又引入了時間信息，用 Vdi(b) 來表示天的向量，Vhi(b) 來表示小時的向量。最后這四者會被拼接起來成為循環神經網絡的輸入:

g網絡的設計:

我們采用 GRU（門控循環單元）來建模軌跡:

是 GRU 在第i時刻的隱狀態，它包含了該用戶當前的移動狀態， 是第 i 時刻的上下文向量。在引入了 GRU 之后，我們進一步引入了內部注意力機制來改進建模效果：

在這里

是通過內部注意力機制改進了之后的狀態向量，att() 是注意力函數:

上式中

是需要學習的參數。在內部注意力機制的基礎上，我們又進一步提出了外部注意力機制，將用戶的歷史軌跡數據也考慮了進來:

上式中

是用戶 u 的歷史軌跡集合。在實現了兩個注意力機制之后，我們開始以下式計算可觀察的花費函數，在這個式子中，我們考慮了:

上式中

為 li-1 的鄰居集合，在上式的基礎上我們可以用負對數和來計算 g 函數。

最后我們采用交叉熵來進行優化：

h網絡的設計：

對于 h 函數，我們使用圖神經網絡來建模。

上式中

是一個矩陣，這個矩陣每一行都是一個節點的表示, z 是第 z 次迭代。接著，在圖神經網絡的基礎上，我們引入了圖注意力神經網絡，并在計算注意力機制的時候考慮了移動的狀態信息和位置之間的距離信息。

在這里

和 都是可學習的參數。既然我們融入了這么多信息，因此我們使用了多頭的注意力機制來穩定訓練過程。

我們將 A 個參數不同的注意力機制計算的結果拼接起來，

是不同的注意力機制的參數。最后，我們使用了一個多層感知機 MLP() 來融合所有信息。

是 GRU 輸出的狀態向量，是 li 的表示向量， 是 ld 的表示向量， 是 和 之間距離的表示向量。最后，為了對 h() 網絡進行訓練，我們采用了時間差分的方法。首先我們將用戶運動的過程定義為一個馬爾可夫決策過程，對于每一次位置的轉移，都會得到一個獎勵，我們將獎勵定義為如下形式。

因此，h() 函數可以被以下式子近似，這個式子代表了未來獎勵之和:

上式中，γ 是折扣因子，T 是到達終點時的時間步驟數，距離當前時間點越遠，那么這個獎勵就需要被打的折扣越多。進一步，通過時間差分法，我們可以將時間差分學習的標簽寫成如下形式。

預測誤差可以被寫成如下形式:

最終對于所有用戶，所有軌跡的損失函數可以被定義成如下形式:

實驗結果

表 2 是模型的性能，對比的都是經典或者最新的算法，可以看出本文的模型表現最佳。圖 2 展示了注意力機制，圖注意力神經網絡以及時序差分學習對于性能的幫助。

圖 3 展示了圖注意力機制的有效性，我們可視化了路網上每個節點與起點和終點的相似度之和，可以發現，通過圖注意力機制，我們的模型可以更多地關注那些可能經過的路網上的節點。而圖 4 則展示了我們 h 網絡的有效性，通過 h 網絡，算法的搜索空間被大大減小了，避免了很多無謂的搜索。

總結

作者提出使用神經網絡來學習 A* 搜索中的費用函數，并專門設計了兩個網絡。這兩個網絡建模了用戶的偏好并充分利用了路網的結構信息，取得了非常好的效果。

按照本文的思路，未來可以嘗試設計不同的神經網絡來適應不同的路徑規劃任務，從而滿足用戶不同的需求。更多關于大數據與城市計算的論文以及相關代碼數據請訪問：https://www.bigscity.com/。

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的为什么a*算法采用哈密尔顿距离作为启发函数比不在位数为启发函数的性能要好?_KDD2019: 使用神经网络为A*搜索算法赋能 --以个性化路径推荐为例...的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。