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

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

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

中圖分類號(hào)：TP309.7????????? 文獻(xiàn)標(biāo)識(shí)碼：A? 文章編號(hào)：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 引言

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

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

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

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

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

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

1.2 混合交叉推薦算法

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

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

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

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

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

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

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

對(duì)于所有對(duì)象，則有以下算式：

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

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

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

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

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

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

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

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

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

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

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

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

3.2 店鋪推薦

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

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

創(chuàng)建一個(gè)鏈表，用于存儲(chǔ)所有的節(jié)點(diǎn)

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)鍵字返回對(duì)應(yīng)的高關(guān)聯(lián)性的類別，并且在多個(gè)種類集合中，混合輸出元素，例如存在n個(gè)集合中，則前n個(gè)元素應(yīng)該是n個(gè)集合中的第一個(gè)元素，第n+1元素應(yīng)該是第1個(gè)集合的第2個(gè)元素。店鋪推薦邏輯模型如圖2所示。

圖2? 店鋪推薦邏輯模型

3.3 店鋪搜索

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

圖3? 店鋪搜索邏輯模型

去重和排序的算法如下：

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

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

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

} else {

將該元素的值自增1

}

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

返回記錄

3.4 實(shí)現(xiàn)效果

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

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

圖4? 模型與算法改進(jìn)前后搜索效率比較

4 結(jié)束語

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

參考文獻(xiàn)（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ù)平臺(tái)個(gè)性化推薦強(qiáng)化學(xué)習(xí)算法研究[J].中

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

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

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

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

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

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

科學(xué)與電子信息學(xué)報(bào)，2009.4.

收稿日期：2021-03-11

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

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