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

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

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

車(chē)輛導航

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

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

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

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

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

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

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

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

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

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

直觀(guān)推斷

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

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

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

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

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

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

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

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

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

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

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

規則1^規則4->目標為西南
規則1^規則5->目標為東北
規則1^規則6->目標為北
規則2^規則4->目標為西南
規則2^規則5->目標為東南
規則2^規則6->目標為南
規則3^規則4->目標為西
規則3^規則5->目標為東
規則3^規則6->目標為空

將基本準則和復雜準則結合起來(lái)就能得到成功的查詢(xún)方法。如果目標在當前節點(diǎn)的西北方向，那么向北方和東方移動(dòng)是合法的。這里我認為應該是：“如果目標在當前節點(diǎn)的東北方向，向北方和東方移動(dòng)是合法的”，而向南方和西方移動(dòng)則不合法。

當查詢(xún)到節點(diǎn)12，選擇的邏輯路徑則是從節點(diǎn)12至節點(diǎn)11并且權值為15的邊線(xiàn)。此時(shí)方向為北方，這看來(lái)是合法的，且邊線(xiàn)權值達到最小。其實(shí)這完全是錯誤的，因為查詢(xún)偏離了目標節點(diǎn)?，F在我們利用規則對查詢(xún)進(jìn)行限定，節點(diǎn)12與節點(diǎn)17平行，因此準則3成立。此時(shí)經(jīng)度減少，因此規則5成立。如果規則3和規則5都成立，那么目標是正東方。規則基礎很好地完成任務(wù)：避免了“盲目”查詢(xún)或對“盲目”查詢(xún)進(jìn)行導向。結果如圖5所示。


本文小結

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

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

1?？紤]將部分處理移交至功能更為強大的系統，也許嵌入式系統只需要解決部分需要快速解決的問(wèn)題。

2。避免遞歸，任何遞歸函數都應當用迭代函數進(jìn)行重寫(xiě)。

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

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

5。最重要的是，有效地綜合“盲目”算法、“貪婪”算法和智能查詢(xún)算法。當然，也沒(méi)有任何規定限制只能采用一種方法解決需要利用智能的問(wèn)題。