基于數(shù)據(jù)可視化處理的嵌入式智能查詢算法

數(shù)據(jù)在許多研究領(lǐng)域都可采用圖形來表示，圖形和圖形理論為人工智能決策提供了有效的可視化工具、體系化準則和相關(guān)技術(shù)。本文以交通線路自動調(diào)整系統(tǒng)為例，說明在嵌入式智能查詢算法中如何利用圖形對數(shù)據(jù)進行可視化處理的方法來避免“盲目”操作，從而提高算法的決策效率。

圖形由節(jié)點和邊線組成，節(jié)點通常畫作圓形，而邊線則是節(jié)點之間的連線。在軟件中，節(jié)點通常采用將邊線作為指針或數(shù)組下標(biāo)的數(shù)據(jù)結(jié)構(gòu)加以實現(xiàn)。對圖形進行遍歷查詢的算法有多種，常用的算法包括深度優(yōu)先查詢和寬度優(yōu)先查詢算法。深度優(yōu)先和寬度優(yōu)先都屬于“盲目”查詢算法，深度優(yōu)先算法沿著一組邊線從根節(jié)點一直查詢到最遠端的葉節(jié)點，再查詢下一個葉節(jié)點；寬度優(yōu)先算法則首先查詢一個邊線距離以內(nèi)的所有節(jié)點，再查詢兩個邊線距離以內(nèi)的節(jié)點，以此類推。

上述算法之所以具有盲目性，是因為算法在查詢適當(dāng)解決方案的過程中并未指示任何有效信息，而只是盲目地遵循遍歷算法，甚至有可能在找到解決方案之前需要遍歷每一個節(jié)點，因而效率比較低。本文介紹的基于數(shù)據(jù)可視化處理的嵌入式智能查詢算法以車輛行駛線路自動調(diào)整系統(tǒng)為例來說明解決上述問題的思路。

車輛導(dǎo)航

在設(shè)計一個遍歷整個公路段的網(wǎng)絡(luò)系統(tǒng)中，假定存在一個自動垃圾收集站系統(tǒng)、運動攝像機或自動交通線路調(diào)整系統(tǒng)。圖1顯示了舊金山的部分城市交通圖。首先，需要創(chuàng)建代表上述數(shù)據(jù)的網(wǎng)絡(luò)圖，以確定將哪些單元作為節(jié)點。如果其他標(biāo)志不甚明顯，那么道路交叉口就可選擇為節(jié)點。隨著這些節(jié)點的插入，就完成了網(wǎng)絡(luò)圖的一部分，不過目前得到的只是城市交通圖的無目標(biāo)靜態(tài)表示。

下一步是添加系統(tǒng)進行智能決策所需的額外信息。如果系統(tǒng)的目標(biāo)是幫助車輛選擇最佳的路徑而從一個交叉口駛向另一交叉口，很自然地就會想到為那些連接交叉口的公路段分配權(quán)值。在最簡單的情形中，所有的道路都不是單行道，并且具有相同的速度限制和車道數(shù)目。即便這些條件不能完全反映真實的道路狀況，一旦構(gòu)建好網(wǎng)絡(luò)圖和權(quán)值模型，就能很容易擴展到這些真實環(huán)境中去。

對交通圖中的邊線賦以權(quán)值有助于系統(tǒng)找到最佳的路徑。在某種程度上，這些權(quán)值可以任意分配，這里假定權(quán)值表征平均車流密度。基于特定時段或局域條件的動態(tài)權(quán)值也是可行的，并不影響以下分析。

圖1中，邊線的權(quán)值表示了每小時穿過道路的平均車流量，這些統(tǒng)計數(shù)據(jù)并不基于任何實際的數(shù)據(jù)，但在分析中相當(dāng)有效。如果車輛必須從Scott和Jackson交叉口(節(jié)點5)行駛到Fillmore和Vallejo交叉口(節(jié)點17)，采用最小車流量判據(jù)，得到的查詢算法應(yīng)能得到總權(quán)值最小的路徑。

我們很容易就能在網(wǎng)絡(luò)圖中畫出結(jié)果，但仍然希望能借助計算機解決問題。表征圖形的兩種最常用方法是鄰接矩陣(adjacencymatrix)和鄰接表(adjacency

list)。鄰接矩陣是靜態(tài)的多維陣列，矩陣中的元素表示一個節(jié)點到另一節(jié)點的權(quán)值。圖2顯示了示例網(wǎng)絡(luò)中包含節(jié)點1至節(jié)點6之間邊線權(quán)值的部分鄰接矩陣。節(jié)點1和節(jié)點6之間的邊線權(quán)值位于最右角(對應(yīng)點位于左下角)。圖2中36個節(jié)點的公路網(wǎng)絡(luò)的整個鄰接矩陣可包含36個元素。

鄰接表通常采用鏈表實現(xiàn)，圖3顯示了網(wǎng)絡(luò)中節(jié)點1至節(jié)點6的鄰接表。圖中并未標(biāo)出邊線權(quán)值，但可以很方便地存儲在數(shù)據(jù)結(jié)構(gòu)中。

對鄰接矩陣和鄰接表進行選擇時，可以考慮如下因素：

1。如果網(wǎng)絡(luò)圖密集或較小，則用鄰接矩陣表示。鄰接矩陣的優(yōu)勢在于可以直接取得權(quán)值，而無須進行指針管理和鏈表遍歷。

2。如果網(wǎng)絡(luò)圖稀疏或很大，那么鄰接表可以減少內(nèi)存浪費。

3。如果需要實時地添加和刪除節(jié)點或邊線，則采用鄰接表。當(dāng)然，這時也需要系統(tǒng)具有動態(tài)內(nèi)存管理能力。

直觀推斷

如果根據(jù)每個節(jié)點出口的最小權(quán)值進行“盲目”查詢，那么很有可能會走錯路，甚至永遠無法到達目的地。更為智能的查詢應(yīng)能根據(jù)直觀推斷進行構(gòu)建，并且直觀推斷應(yīng)能在大多數(shù)時間內(nèi)成為查詢的常規(guī)指南。我們通常將其稱為經(jīng)驗規(guī)則。生活中最簡單的經(jīng)驗是：“因為現(xiàn)在是4月且天空多云，所以需要帶上雨傘。”雖然4月份和天空多云并不意味著會下雨，但這樣的條件下下雨的可能性遠遠高于正常天氣。

直觀推斷也是實現(xiàn)高速有效查詢的一個重要策略。如果尚未打定主意，最初可以選定一個不怎么適當(dāng)、甚至大錯特錯的值。對于公路遍歷問題而言，一種可能的直觀推斷是：“當(dāng)一個節(jié)點存在兩個(或更多)等權(quán)值的邊線時，執(zhí)行寬度優(yōu)先查詢，然后繼續(xù)查詢總權(quán)值最小的路徑。”例如節(jié)點15就出現(xiàn)了這樣的情形，該節(jié)點的出口存在兩個權(quán)值為15的邊線。利用寬度優(yōu)先查詢，對下一節(jié)點及其出口邊線的權(quán)值進行檢測。下一級節(jié)點為14和20，這兩個節(jié)點出口邊線的權(quán)值分別為15和45。根據(jù)最小邊線判據(jù)，選擇節(jié)點14繼續(xù)查詢，這完全合乎情理；因此節(jié)點20將被拋棄。

某些直觀推斷看起來非常明顯，但即便是這些直觀推斷也有助于探尋待解決問題的實質(zhì)。對于公路遍歷問題，最基本的直觀推斷就是：“選擇具有最小邊線權(quán)值的路徑。”這簡單易行，但背離了查詢的基線準則。

遵循最小邊線權(quán)值的方法稱為“貪婪算法”(greedyalgorithm)，該算法以即刻滿意度為基礎(chǔ)。貪婪算法并不考慮以后的情況，而選擇當(dāng)前最為廉價的路徑進行查詢。這并不能保證得到有效的解決方案，甚至有時會得到不怎么優(yōu)化的路徑。當(dāng)詢及為何選擇最終被證明是錯誤的路徑時，貪婪算法或許會回答：“在當(dāng)時，這看起來是個不錯的選擇。”