[發明專利]支持集束搜索的運算裝置和方法

有效

• 申請號: 201710279655.0
• 申請日: 2017-04-25
• 公開（公告）號: CN108733739B
• 公開（公告）日: 2021-09-07
• 發明（設計）人: 不公告發明人
• 申請（專利權）人: 上海寒武紀信息科技有限公司
• 主分類號: G06F8/30
• 分類號: G06F8/30;G06F16/903
• 代理公司: 中科專利商標代理有限責任公司 11021
• 代理人: 任巖

本公開涉及一種支持搜索的裝置和方法，其中裝置包括數據轉換模塊、數據運算模塊、整合結果模塊和控制器，其中數據轉換模塊，用于從裝置外獲取指令，以及獲取圖形結構中的部分節點并進行格式轉換；數據運算模塊，用于獲取尚未被運算的節點數據，整合結果模塊，獲得最優路徑存入存儲模塊；以及控制器，執行存儲模塊中的指令。

技術領域

本公開涉及計算機領域，進一步涉及一種人工智能領域。

背景技術

集束搜索是一種啟發式圖搜索算法，在圖的解空間比較大的情況下，集束搜索從源節點開始搜索，每次搜索圖中下一層的子節點時，只搜索較有希望構成最優路徑的節點，限制下一層搜索后保留的節點的數量不大于某個固定值K，從而減少搜索所占用的空間和時間開銷。

集束搜索多用在一些大型系統中，如機器翻譯系統，語音識別系統等。在這些應用中數據集較為龐大，而常用的裝置的內存有限，通過遍歷整個解空間進行求解時，內存難以滿足要求，同時運算量開銷很大。而對這些系統進行求解時，通常只需要得到一個近似最優解，集束搜索能有效減少存儲量，并且減少運算量，在較快的時間找到接近最優的解。

公開內容

有鑒于此，本公開的目的在于提供一種支持集束搜索的運算裝置和方法，以解決以上所述的至少一項技術問題。

根據本公開的一方面，提供一種支持集束搜索的裝置，包括數據轉換模塊、存儲模塊、數據運算模塊、整合結果模塊和控制器，其中

數據轉換模塊，用于從裝置外獲取指令，以及獲取圖形結構中的部分節點并進行格式轉換；

存儲模塊，用于從數據轉換模塊中獲取指令和格式轉換后的節點數據；

數據運算模塊，從存儲模塊獲取尚未被運算的節點數據，計算從源節點到對應節點路徑的總代價值，將總代價值最小的前k個節點選出作為候選節點，k為裝置允許的最大候選節點數，根據總代價值最小的節點判斷是否得到近似最優路徑，如果沒有，則繼續從存儲模塊獲取未被運算的節點數據進行計算和判斷，如果有，將總代價最小節點和其前驅節點寫入到整合結果模塊中；

整合結果模塊，根據從數據運算模塊得到的近似最優路徑的尾節點從存儲模塊中不斷尋找前驅節點，直至回溯至源節點，獲得最優路徑存入存儲模塊；

控制器，執行存儲模塊中的指令，分別對數據轉換模塊、存儲模塊、數據運算模塊和整合結果模塊進行控制。

根據本公開的另一方面，提供一種支持集束搜索的方法，包括步驟：

S1：從裝置外部獲取指令，經由一數據轉換模塊存儲到一存儲模塊中，再傳輸到一控制器；

S2：從裝置外部將原始圖中部分節點傳送到數據轉換模塊中，數據轉換模塊將傳入的節點進行格式轉換后，然后送至存儲模塊中；

S3：從存儲模塊獲取尚未被運算的節點數據，計算從源節點到對應節點路徑的總代價值，將總代價值最小的前k個節點選出作為候選節點，k為裝置允許的最大候選節點數，根據總代價值最小的節點判斷是否得到近似最優路徑，如果沒有，則繼續從存儲模塊獲取未被運算的節點數據進行計算和判斷，轉入步驟S2；如果有，將總代價最小節點和其前驅節點寫入到一整合結果模塊中；

S4：根據從數據運算模塊得到的近似最優路徑的尾節點從存儲模塊中不斷尋找前驅節點，直至回溯至源節點，獲得最優路徑存入存儲模塊；

S4：存儲模塊獲得最優路徑存入，并將其傳輸到裝置外部。

通過上述技術方案，可得知本公開的有益效果在于：

(1)通過對原始圖結構采用啟發式集束搜索算法(設定裝置允許的最大候選節點數)，找到一條能夠滿足條件的近似最優路徑，該裝置可以有效地減少空間消耗，并提高時間效率；