嵌入式智能查詢算法中利用圖形對(duì)數(shù)據(jù)進(jìn)行可視化處理

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

圖形由節(jié)點(diǎn)和邊線組成，節(jié)點(diǎn)通常畫作圓形，而邊線則是節(jié)點(diǎn)之間的連線。在軟件中，節(jié)點(diǎn)通常采用將邊線作為指針或數(shù)組下標(biāo)的數(shù)據(jù)結(jié)構(gòu)加以實(shí)現(xiàn)。對(duì)圖形進(jìn)行遍歷查詢的算法有多種，常用的算法包括深度優(yōu)先查詢和寬度優(yōu)先查詢算法。深度優(yōu)先和寬度優(yōu)先都屬于“盲目”查詢算法，深度優(yōu)先算法沿著一組邊線從根節(jié)點(diǎn)一直查詢到最遠(yuǎn)端的葉節(jié)點(diǎn)，再查詢下一個(gè)葉節(jié)點(diǎn)；寬度優(yōu)先算法則首先查詢一個(gè)邊線距離以內(nèi)的所有節(jié)點(diǎn)，再查詢兩個(gè)邊線距離以內(nèi)的節(jié)點(diǎn)，以此類推。
上述算法之所以具有盲目性，是因?yàn)樗惴ㄔ诓樵冞m當(dāng)解決方案的過程中并未指示任何有效信息，而只是盲目地遵循遍歷算法，甚至有可能在找到解決方案之前需要遍歷每一個(gè)節(jié)點(diǎn)，因而效率比較低。本文介紹的基于數(shù)據(jù)可視化處理的嵌入式智能查詢算法以車輛行駛線路自動(dòng)調(diào)整系統(tǒng)為例來說明解決上述問題的思路。

車輛導(dǎo)航

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

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

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

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

我們很容易就能在網(wǎng)絡(luò)圖中畫出結(jié)果，但仍然希望能借助計(jì)算機(jī)解決問題。表征圖形的兩種最常用方法是鄰接矩陣(adjacencymatrix)和鄰接表(adjacencylist)。鄰接矩陣是靜態(tài)的多維陣列，矩陣中的元素表示一個(gè)節(jié)點(diǎn)到另一節(jié)點(diǎn)的權(quán)值。圖2顯示了示例網(wǎng)絡(luò)中包含節(jié)點(diǎn)1至節(jié)點(diǎn)6之間邊線權(quán)值的部分鄰接矩陣。節(jié)點(diǎn)1和節(jié)點(diǎn)6之間的邊線權(quán)值位于最右角(對(duì)應(yīng)點(diǎn)位于左下角)。圖2中36個(gè)節(jié)點(diǎn)的公路網(wǎng)絡(luò)的整個(gè)鄰接矩陣可包含36個(gè)元素。

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

對(duì)鄰接矩陣和鄰接表進(jìn)行選擇時(shí)，可以考慮如下因素：

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

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

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

直觀推斷

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

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

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

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

一些對(duì)人類而言相當(dāng)明顯的直觀推斷對(duì)于機(jī)器則并非如此。例如直觀推斷“當(dāng)節(jié)點(diǎn)存在兩個(gè)(或更多)等權(quán)值邊線時(shí)，將執(zhí)行寬度優(yōu)先查詢，然后繼續(xù)查詢總權(quán)值最小的路徑”，這本身并沒有問題，但還是存在一個(gè)問題。如果最小成本的路徑偏離了目標(biāo)節(jié)點(diǎn)怎么辦？這樣選擇得到的或許是一條更為昂貴的路徑。由此可見，還必須了解從當(dāng)前節(jié)點(diǎn)至目標(biāo)節(jié)點(diǎn)的方向。以這種形式開發(fā)直觀推斷是展現(xiàn)待解決問題所需核心知識(shí)的良好途徑。

解決公路網(wǎng)絡(luò)導(dǎo)向問題的一個(gè)有效途徑是動(dòng)態(tài)計(jì)算當(dāng)前節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)之間的距離和方位。這要求得到每個(gè)節(jié)點(diǎn)的經(jīng)緯度數(shù)據(jù)，并對(duì)前進(jìn)中的每一個(gè)節(jié)點(diǎn)進(jìn)行浮點(diǎn)操作，因而極有可能是最不優(yōu)化的解決方案。更好的策略是根據(jù)經(jīng)緯度對(duì)之間的差異得到一套準(zhǔn)則，這有助于提取最少準(zhǔn)則所需的信息。

第一步必須明確方向和經(jīng)緯度之間的關(guān)系，圖4顯示了根據(jù)經(jīng)緯度差異得到的方向。

當(dāng)向北方移動(dòng)時(shí)，緯度將增加；向西方移動(dòng)時(shí)，經(jīng)度增加；以此類推。從這些簡(jiǎn)單的關(guān)系中可以看出，每個(gè)節(jié)點(diǎn)上完全可以去除許多不必要的操作。將以上知識(shí)與交通圖相結(jié)合，可以得到Scott和Jackson交叉口的起始緯度和經(jīng)度分別為N3747。514和W12226。356，而目標(biāo)Fillmore和Vallejo交叉口則分別為緯度N3747。725和經(jīng)度W12226。002。根據(jù)圖4中的羅盤儀準(zhǔn)則，現(xiàn)在目標(biāo)交叉口位于起始交叉口的東北方向。

根據(jù)以上方向關(guān)系，可以得到如下六條準(zhǔn)則：

準(zhǔn)則1：如果緯度(目標(biāo))>緯度(現(xiàn)在狀態(tài))，那么目標(biāo)為北方；
準(zhǔn)則2：如果緯度(目標(biāo))緯度(現(xiàn)在狀態(tài))，那么目標(biāo)為南方；
準(zhǔn)則3：如果緯度(目標(biāo))=緯度(現(xiàn)在狀態(tài))，那么目標(biāo)為空；
準(zhǔn)則4：如果經(jīng)度(目標(biāo))>經(jīng)度(現(xiàn)在狀態(tài))，那么目標(biāo)為西方；
準(zhǔn)則5：如果經(jīng)度(目標(biāo))經(jīng)度(現(xiàn)在狀態(tài))，那么目標(biāo)為東方；
準(zhǔn)則6：如果經(jīng)度(目標(biāo))=經(jīng)度(現(xiàn)在狀態(tài))，那么目標(biāo)為空；

可以將上述基本準(zhǔn)則相結(jié)合以得到更為復(fù)雜的方向，如東北和西南。這只需要將基本準(zhǔn)則通過與操作結(jié)合起來，這樣有效的組合如下：

規(guī)則1^規(guī)則4->目標(biāo)為西南
規(guī)則1^規(guī)則5->目標(biāo)為東北
規(guī)則1^規(guī)則6->目標(biāo)為北
規(guī)則2^規(guī)則4->目標(biāo)為西南
規(guī)則2^規(guī)則5->目標(biāo)為東南
規(guī)則2^規(guī)則6->目標(biāo)為南
規(guī)則3^規(guī)則4->目標(biāo)為西
規(guī)則3^規(guī)則5->目標(biāo)為東
規(guī)則3^規(guī)則6->目標(biāo)為空

將基本準(zhǔn)則和復(fù)雜準(zhǔn)則結(jié)合起來就能得到成功的查詢方法。如果目標(biāo)在當(dāng)前節(jié)點(diǎn)的西北方向，那么向北方和東方移動(dòng)是合法的。這里我認(rèn)為應(yīng)該是：“如果目標(biāo)在當(dāng)前節(jié)點(diǎn)的東北方向，向北方和東方移動(dòng)是合法的”，而向南方和西方移動(dòng)則不合法。

當(dāng)查詢到節(jié)點(diǎn)12，選擇的邏輯路徑則是從節(jié)點(diǎn)12至節(jié)點(diǎn)11并且權(quán)值為15的邊線。此時(shí)方向?yàn)楸狈剑@看來是合法的，且邊線權(quán)值達(dá)到最小。其實(shí)這完全是錯(cuò)誤的，因?yàn)椴樵兤x了目標(biāo)節(jié)點(diǎn)?，F(xiàn)在我們利用規(guī)則對(duì)查詢進(jìn)行限定，節(jié)點(diǎn)12與節(jié)點(diǎn)17平行，因此準(zhǔn)則3成立。此時(shí)經(jīng)度減少，因此規(guī)則5成立。如果規(guī)則3和規(guī)則5都成立，那么目標(biāo)是正東方。規(guī)則基礎(chǔ)很好地完成任務(wù)：避免了“盲目”查詢或?qū)?ldquo;盲目”查詢進(jìn)行導(dǎo)向。結(jié)果如圖5所示。


本文小結(jié)

如上所述，圖形表示法和盲目查詢算法本身并不足以解決大多數(shù)問題。但將這些技術(shù)同直觀推斷以及特定問題的規(guī)則集相結(jié)合，就像上面所做的那樣，就能得到有效的人工智能。類似的技術(shù)可應(yīng)用于諸多應(yīng)用領(lǐng)域。盡管本文的示例集中于靜態(tài)數(shù)據(jù)，但當(dāng)邊線及邊線權(quán)值改變并且不能對(duì)規(guī)則進(jìn)行硬編碼時(shí)，這里給出的技術(shù)仍然有效。

顯然，嵌入式系統(tǒng)通常受制于某些特殊限制。嵌入式編程中一般不允許遞歸算法，盡管這是圖形查詢算法中的一種常用技術(shù)。關(guān)鍵應(yīng)用中的嵌入式系統(tǒng)也不支持動(dòng)態(tài)內(nèi)存分配，但如果沒有動(dòng)態(tài)內(nèi)存分配的話，將很難在鏈表數(shù)據(jù)表示法中添加和刪除節(jié)點(diǎn)。出于以上考慮，可以得到如下嵌入式智能的應(yīng)用技巧：

1。考慮將部分處理移交至功能更為強(qiáng)大的系統(tǒng)，也許嵌入式系統(tǒng)只需要解決部分需要快速解決的問題。

2。避免遞歸，任何遞歸函數(shù)都應(yīng)當(dāng)用迭代函數(shù)進(jìn)行重寫。

3。盡可能減小動(dòng)態(tài)內(nèi)存分配。如果鏈表的長(zhǎng)度相對(duì)保持恒定，就可用數(shù)組進(jìn)行代替，使數(shù)組的大小等于鏈表的最大長(zhǎng)度，一旦超過該最大長(zhǎng)度就返回操作失敗。

4。將智能視為低能動(dòng)物而非超級(jí)計(jì)算機(jī)，即將其想像為處理意外情況或干擾的低等動(dòng)物形式。

5。最重要的是，有效地綜合“盲目”算法、“貪婪”算法和智能查詢算法。當(dāng)然，也沒有任何規(guī)定限制只能采用一種方法解決需要利用智能的問題。