葉小艷 鄧可兒 鐘彬勝 梁梓瀅 卓圳豪 鐘華鈞

摘? 要： 針對大型商場傳統(tǒng)導(dǎo)航和搜索效率低的問題，設(shè)計了一種導(dǎo)購策略，采用改進后的A*算法實現(xiàn)最優(yōu)路徑的規(guī)劃，根據(jù)混合交叉推薦技術(shù)進行數(shù)據(jù)采集與數(shù)據(jù)推薦，加強算法對復(fù)雜室內(nèi)地圖環(huán)境的適應(yīng)性，提高推薦效率。構(gòu)建了基于微信小程序的大型商場智能導(dǎo)購系統(tǒng)進行驗證，在店鋪搜索和推薦邏輯模型下，搜索效率提升了近50%，并解決了室內(nèi)導(dǎo)航以及信息個性化推薦問題。

關(guān)鍵詞： A*算法; 導(dǎo)購策略; 導(dǎo)航; 推薦; 搜索

中圖分類號：TP309.7????????? 文獻標識碼：A? 文章編號：1006-8228（2021）08-17-04

Strategy of indoor navigation and shopping guide system for

shopping malls and its application

Ye Xiaoyan， Deng Ke'er， Zhong Binsheng， Liang Ziying， Zhuo Zhenhao， Zhong Huajun

（Department of network technology， Guangzhou Institute of software， Guangzhou， Guangdong 510990， China）

Abstract： In order to solve the low efficiency of traditional navigation and search in large shopping malls， a shopping guide strategy is designed， which uses improved A-Star algorithm to realize the optimal path planning， and according to the hybrid cross recommendation technology， carries out the data collection and data recommendation to strengthen the adaptability of the algorithm to the complex indoor map environment and improve the recommendation efficiency. An intelligent shopping guide system for large shopping malls based on WeChat mini program is built to make the verification. With the logic model of shop search and recommendation， the search efficiency has been improved by nearly 50%， and the problems of indoor navigation and personalized information recommendation are solved.

Key words： A-Star algorithm; shopping guide strategy; navigation; recommendation; search

0 引言

如今大型商場一般都會有商場智能導(dǎo)覽導(dǎo)購系統(tǒng)，用于線路指引、自助查詢、客戶數(shù)據(jù)分析，也作為廣告宣傳和品牌推介。商場智能導(dǎo)購須解決以下關(guān)鍵技術(shù)問題：室內(nèi)路徑規(guī)劃，室內(nèi)環(huán)境布局搜索，根據(jù)用戶喜好推薦商品，從而達到導(dǎo)購的目的。

關(guān)于室內(nèi)路徑規(guī)劃與搜索的研究，主要集中在基于外部物理硬件設(shè)施的支持，如Shivam Verma^[1]“基于智能手機的室內(nèi)導(dǎo)航系統(tǒng)”、ToshinoriKagawa^[2]“基于傳感器的超寬帶自主導(dǎo)航系統(tǒng)在商場的部署與實驗”、Hongwei Ding^[3]“基于AP加權(quán)多重匹配近鄰的室內(nèi)指紋定位方法”。利用現(xiàn)有軟硬件條件來優(yōu)化解決方案，以達到節(jié)約成本、提高效率目的。

路線規(guī)劃常見的算法是A*（A-Star）算法，通過比較當前路徑柵格的啟發(fā)式函數(shù)值來逐步確定下一個路徑柵，即從初始點經(jīng)由節(jié)點到目標點的估價函數(shù)。其優(yōu)點是能夠嚴格沿著最短路徑搜索，但搜索點少，范圍小;其缺點是當搜索點數(shù)多、搜索范圍大時，搜索效率低。當前大型電商平臺通過采集用戶數(shù)據(jù)，對用戶的購物的個性化偏好程度和購物行為等變量信息^[4]進行分析，挖掘用戶的消費能力，向其精準推薦商品。在路徑規(guī)劃上，一些軟件也會借助手機GPS、陀螺儀、WiFi等感知單元，實時獲取更為豐富的時間、空間和出行狀態(tài)信息來描繪用戶個體出行過程，返回更加客觀、精確的導(dǎo)航數(shù)據(jù)。本文正是結(jié)合以上兩點，采用改進后的A*算法，實現(xiàn)最優(yōu)路徑規(guī)劃，加強算法對復(fù)雜室內(nèi)地圖環(huán)境的適應(yīng)性，根據(jù)混合交叉推薦^[5]等技術(shù)方法，實現(xiàn)根據(jù)用戶喜好、有針對性地推薦商品。

1 智能導(dǎo)購策略算法設(shè)計

1.1 改進A*算法，實現(xiàn)最優(yōu)路徑規(guī)劃

針對現(xiàn)有A*算法在移動的目標節(jié)點判別和計算時，出現(xiàn)大量節(jié)點在搜索的過程中被刪除現(xiàn)象^[6]。在被刪的節(jié)點中，也可能包括了最優(yōu)路徑節(jié)點，令搜索過程陷入“死循環(huán)”，從而導(dǎo)致無法搜索到目標路徑。對商城導(dǎo)航中A*算法進行優(yōu)化。首先，對A*算法的地圖數(shù)據(jù)進行劃分，獲取有效的且可支持完成導(dǎo)航的地圖數(shù)據(jù)。傳統(tǒng)A*算法啟發(fā)函數(shù)通常只考慮距離啟發(fā)信息且均采用單次計算，其應(yīng)用主要為二維平面的尋路，改進后的A*算法采用分層計算的思想，實現(xiàn)了室內(nèi)三維空間跨樓層的最優(yōu)路徑尋路。在路線規(guī)劃方法函數(shù)中加入相關(guān)限制，有效保證了最優(yōu)路徑的唯一性，同時實現(xiàn)了復(fù)雜室內(nèi)地圖環(huán)境下用戶步行路線最短的個性化需求，進一步增強了算法對復(fù)雜室內(nèi)地圖環(huán)境的適應(yīng)性。綜合室內(nèi)復(fù)雜地圖環(huán)境下用戶對最短距離和直行路程的需求，在位置計算中，引入同時考慮方向和距離啟發(fā)信息的啟發(fā)函數(shù)，把POI點與尋路節(jié)點分開處理，以映射的方式建立聯(lián)系，有效避免了直接搜尋POI節(jié)點數(shù)據(jù)量大、速率低的問題。

1.2 混合交叉推薦算法

混合交叉推薦算法是關(guān)聯(lián)分析算法和協(xié)同過濾算法的結(jié)合和改進，繼承了協(xié)同過濾算法的優(yōu)點，避免冷啟動的問題，不僅具有協(xié)同過濾算法的實時性，還具備關(guān)聯(lián)規(guī)則算法的實用性?；旌贤扑]算法不需收集用戶的個人信息，這不僅避免過于依賴于用戶個人行為，也保證用戶的個人隱私的安全，符合用戶關(guān)注隱私的要求，還提高了推薦效率。

將每一個類別的集合使用一個鏈表存儲，并將所有類別的集合使用到一個鏈表存儲^[7]。其算法不僅比完全冷啟動的協(xié)同過濾算法在精確性上更有優(yōu)勢，還保持了商品類型的一致性。與許多單一推薦技術(shù)相比，可以發(fā)現(xiàn)內(nèi)部應(yīng)用商品之間的關(guān)聯(lián)，挖掘出跨電商商品之間的關(guān)系，給用戶定制出更符合自身需求的個性化推薦方案。

混合交叉推薦算法主要分為兩個部分，分別是數(shù)據(jù)采集與數(shù)據(jù)推薦。

⑴ 數(shù)據(jù)采集：采用用戶搜索軌跡記錄方式，用戶搜索過的詞條會記錄在本機中，當短時間內(nèi)，用戶搜索過的兩件物品（稱為A與B）會被認為它們之間是有關(guān)聯(lián)的，如果A或B是一個物品、店鋪等，將獲取它的分類名稱，然后將A與B的分類名上傳到數(shù)據(jù)模型中。如圖1所示，給定一個數(shù)據(jù)集有a、b、c、d四個對象。

圖1? 對象關(guān)系圖

在圖的術(shù)語中，帶權(quán)的為網(wǎng)，圖1即是網(wǎng)結(jié)構(gòu)。其鄰接矩陣為：

其中為對象a與對象b的權(quán)值（a，b），使得：

對于所有對象，則有以下算式：

當對象a和對象b被搜索或者使用時，則兩個對象的權(quán)值會發(fā)生變化，其中k為常數(shù)值：

如果無兩個節(jié)點的數(shù)據(jù)，則初始化該兩個節(jié)點。

⑵ 數(shù)據(jù)推薦：同樣采用該用戶搜索軌跡進行推薦，如該用戶搜索過A物品或者店鋪，系統(tǒng)將獲取到A的分類名稱，將其作為請求參數(shù)請求數(shù)據(jù)，系統(tǒng)將審核請求參數(shù)的正確性，如果正確，系統(tǒng)通過判定缺省值將噪聲數(shù)據(jù)清除，在接下來生成數(shù)據(jù)模型中篩選與A關(guān)聯(lián)性最高的三個類型，在獲取類型后，系統(tǒng)進一步篩選出這三個類型店鋪中綜合評分最好的十個店鋪推薦給用戶。如A點，在矩陣中則有：。

混合交叉推薦算法將根據(jù)對象獲取與該對象最高權(quán)值的對象。根據(jù)對象a將得到按順序排序的對象c、對象d、對象b，則。

通過c、d、b三個對象去獲取相匹配的各十個店鋪，系統(tǒng)將根據(jù)這三十個店鋪的綜合評分，篩選出綜合評分最高的十個店鋪推薦給用戶。

通過對用戶整體行為和物品關(guān)聯(lián)性的記錄，同時減少噪聲數(shù)據(jù)量大但獲取有價值數(shù)據(jù)少的低回報率的處理行為，進行高回報率的處理行為。

2 智能導(dǎo)購系統(tǒng)應(yīng)用

基于改進的A*算法和混合交叉推薦算法，設(shè)計了基于微信小程序的大型商場智能導(dǎo)購系統(tǒng)。該系統(tǒng)由兩個功能模塊組成：室內(nèi)導(dǎo)航服務(wù)和個性化商鋪推薦。在導(dǎo)航部分，提供2D/3D導(dǎo)圖展示、路線規(guī)劃的制定和查找、店鋪等位置查詢服務(wù)。在個性化搜索部分，根據(jù)用戶活動痕跡推薦可能喜歡商品或商鋪，同時內(nèi)嵌了合作商鋪的廣告和活動信息。

用戶進入商場，打開本應(yīng)用后可以看到該商場的3D布局地圖，能清晰找到自己的位置和每個商鋪的位置，輸入起點和終點進入導(dǎo)航后，會即時規(guī)劃出最適合的路線、計算出行走時間，為用戶“指路”，并有語音播報輔助。在個性化商鋪推薦方面，會根據(jù)用戶的搜索記錄、瀏覽記錄、光顧頻繁度等推薦可能喜歡的店鋪。

3 商場智能導(dǎo)購系統(tǒng)實現(xiàn)

3.1 Redis數(shù)據(jù)庫

考慮商城智能導(dǎo)購系統(tǒng)需要對用戶的行為進行收集，而用戶的搜索行為頻繁是不可避免的。如果在這一場景下，采用結(jié)構(gòu)化數(shù)據(jù)庫，將會非常影響系統(tǒng)的用戶體驗。參考了眾多的中間件的優(yōu)缺點，最終選擇了非結(jié)構(gòu)數(shù)據(jù)庫Redis作為數(shù)據(jù)存儲。一方面Redis是內(nèi)存數(shù)據(jù)庫，查詢和存儲速度快，適合頻繁的用戶行為場景;另一方面Redis存在多種數(shù)據(jù)結(jié)構(gòu)，如String、Set、Sort Set、Geo等，靈活的數(shù)據(jù)結(jié)構(gòu)可以方便地為系統(tǒng)提供數(shù)據(jù)存儲結(jié)構(gòu)。其中有序集合Sort Set可以根據(jù)權(quán)值自動進行高效排序，適合系統(tǒng)當前的場景。

3.2 店鋪推薦

店鋪推薦使用Redis的有序集合實現(xiàn)，有序集合的名稱即是主節(jié)點，有序集合的元素是其他節(jié)點，元素的分數(shù)即是與主節(jié)點的關(guān)聯(lián)性。

接著，考慮節(jié)點的存儲和連線問題，需要將參數(shù)進行分析、存儲與持久化。節(jié)點的連線和權(quán)值的增加實現(xiàn)如下：

創(chuàng)建一個鏈表，用于存儲所有的節(jié)點

for （int i=0; i<鏈表的長度; i++） {

a<-從鏈表中彈出頭元素

for（Object b：鏈表） {

relate（a，b）=relate（a，b）+1

relate（b，a）=relate（b，a）+1

}

將a存入到鏈尾表

}

最終是推薦。需要根據(jù)關(guān)鍵字返回對應(yīng)的高關(guān)聯(lián)性的類別，并且在多個種類集合中，混合輸出元素，例如存在n個集合中，則前n個元素應(yīng)該是n個集合中的第一個元素，第n+1元素應(yīng)該是第1個集合的第2個元素。店鋪推薦邏輯模型如圖2所示。

圖2? 店鋪推薦邏輯模型

3.3 店鋪搜索

由于一個小類別與大類別是n與n的關(guān)系，使用Redis的集合存儲時比較方便。根據(jù)用戶的輸入一個或多個關(guān)鍵字，搜索出高度符合的店鋪。店鋪搜索邏輯模型如圖3所示。

圖3? 店鋪搜索邏輯模型

去重和排序的算法如下：

創(chuàng)建一個HashMap，用于存儲元素

if（HashMap中不存在該元素） {

將該元素作為鍵，值設(shè)定為1

} else {

將該元素的值自增1

}

定義一個排序器，對HashMap根據(jù)值進行排序，規(guī)則為降序

返回記錄

3.4 實現(xiàn)效果

在實際應(yīng)用測試過程中，發(fā)現(xiàn)該導(dǎo)購系統(tǒng)能個性化推薦商品并實現(xiàn)商品所在位置的最優(yōu)化路線規(guī)劃，獲得快速導(dǎo)航的效果。如在太古匯商場，輸入“喬丹”，程序顯示“F2”（第2層），并準確標識具體位置。“個性化商鋪”或“商品推薦效果”也可以根據(jù)用戶搜索和訪問記錄自動生成，“kefto”（太古匯商場F1）、“薯皇”（太古匯商場F1）、“雙鹿”（太古匯商場F3）。根據(jù)用戶的輸入一個或多個關(guān)鍵字，搜索出高度符合的店鋪，如搜索“衣服”顯示“NIKE”（體育用品）、“TRIES”（體育用品）、“雅鹿”（服飾）、“阿迪多納”（體育用品）。

從搜索的效果看，模型與算法改進后，搜索效率如圖4所示，搜索的整體效率提升了近50%，實現(xiàn)了達到加速導(dǎo)航算法的目的。

圖4? 模型與算法改進前后搜索效率比較

4 結(jié)束語

本系統(tǒng)采用了Redis的有序集合，使用模擬連線和關(guān)聯(lián)算法、對象元素交叉存儲算法，實現(xiàn)了個性化店鋪推薦，有效地提高了個性化推薦的效率;使用去重和排序算法，實現(xiàn)了智能店鋪搜索，使系統(tǒng)能根據(jù)關(guān)鍵詞，搜索出高度符合的店鋪。在個性化推薦方面做到了信息的有效過濾，解決了冷啟動、數(shù)據(jù)稀疏性及精確性所帶來的推薦信息不準確或不精細的問題，從而使推薦內(nèi)容更貼合用戶實際，提高用戶們的體驗感。在室內(nèi)導(dǎo)航方面做到了在商場內(nèi)實現(xiàn)了最優(yōu)路線規(guī)劃和導(dǎo)航，解決了用戶在商場無法快速準確到達目的地的問題。縱觀互聯(lián)網(wǎng)時代發(fā)展的潮流，對于研究者而言，如何解決更深入的路線規(guī)劃算法問題，如何解決信息推薦的協(xié)同過濾算法問題，這需要后面進一步的探索與檢驗。

參考文獻（References）：

[1] Shivam Verma;Rohit Omanwar;V Sreejith;G S Meera. A

smartphone based indoor navigation system[C]//2016 28th International Conference on Microelectronics. Giza， USA： IEEE Press，2017：402-405

[2] Toshinori Kagawa;Huan-Bang Li;Ryu Miura. A UWB

navigation system aided by sensor-based autonomous algorithm-Deployment and experiment in shopping mall[C]//2014 International Symposium on Wireless Personal Multimedia Communications.Giza，USA： IEEE Press，2017：402-405

[3] Hongwei Ding;Zhengqi Zheng;Yu Zhang. AP weighted

multiple matching nearest neighbors approach for fingerprint-based indoor localization[C]//2016 Fourth International Conference on Ubiquitous Positioning，Indoor Navigation and Location Based Services.Giza， USA： IEEE Press，2017：402-405

[4] 王姝靜.電子商務(wù)平臺個性化推薦強化學習算法研究[J].中

外企業(yè)家，2020.9：92

[5] 王騰宇.大數(shù)據(jù)時代下電子商務(wù)個性化推薦系統(tǒng)的分析與

設(shè)計[J].智庫時代，2020.8：132-133

[6] 丁恒，黃全舟.基于屬性特征的個性化旅游推薦算法研究[J].

智能計算機與應(yīng)用，2020.10（1）：193-196

[7] 漆陽華，楊戰(zhàn)平，黃清華.A*的改進路徑規(guī)劃算法[J].太赫茲

科學與電子信息學報，2009.4.

收稿日期：2021-03-11

作者簡介：劉聰（1995-），女，陜西西安人，碩士研究生，主要研究方向：服務(wù)計算、服務(wù)組合。

通訊作者：楊懷洲（1970-），男，陜西西安人，博士，副教授，主要研究方向：物聯(lián)網(wǎng)、服務(wù)計算。