當(dāng)前位置:首頁 > 嵌入式 > 嵌入式硬件
[導(dǎo)讀]數(shù)據(jù)在許多研究領(lǐng)域都可采用圖形來表示,圖形和圖形理論為人工智能決策提供了有效的可視化工具、體系化準(zhǔn)則和相關(guān)技術(shù)。本文以交通線路自動(dòng)調(diào)整系統(tǒng)為例,說明在嵌入式智能查詢算法中如何利用圖形對(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)值。在最簡單的情形中,所有的道路都不是單行道,并且具有相同的速度限制和車道數(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ī)則。生活中最簡單的經(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)值的路徑。”這簡單易行,但背離了查詢的基線準(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)度增加;以此類推。從這些簡單的關(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)存分配。如果鏈表的長度相對(duì)保持恒定,就可用數(shù)組進(jìn)行代替,使數(shù)組的大小等于鏈表的最大長度,一旦超過該最大長度就返回操作失敗。

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

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

本站聲明: 本文章由作者或相關(guān)機(jī)構(gòu)授權(quán)發(fā)布,目的在于傳遞更多信息,并不代表本站贊同其觀點(diǎn),本站亦不保證或承諾內(nèi)容真實(shí)性等。需要轉(zhuǎn)載請(qǐng)聯(lián)系該專欄作者,如若文章內(nèi)容侵犯您的權(quán)益,請(qǐng)及時(shí)聯(lián)系本站刪除。
換一批
延伸閱讀

9月2日消息,不造車的華為或?qū)⒋呱龈蟮莫?dú)角獸公司,隨著阿維塔和賽力斯的入局,華為引望愈發(fā)顯得引人矚目。

關(guān)鍵字: 阿維塔 塞力斯 華為

倫敦2024年8月29日 /美通社/ -- 英國汽車技術(shù)公司SODA.Auto推出其旗艦產(chǎn)品SODA V,這是全球首款涵蓋汽車工程師從創(chuàng)意到認(rèn)證的所有需求的工具,可用于創(chuàng)建軟件定義汽車。 SODA V工具的開發(fā)耗時(shí)1.5...

關(guān)鍵字: 汽車 人工智能 智能驅(qū)動(dòng) BSP

北京2024年8月28日 /美通社/ -- 越來越多用戶希望企業(yè)業(yè)務(wù)能7×24不間斷運(yùn)行,同時(shí)企業(yè)卻面臨越來越多業(yè)務(wù)中斷的風(fēng)險(xiǎn),如企業(yè)系統(tǒng)復(fù)雜性的增加,頻繁的功能更新和發(fā)布等。如何確保業(yè)務(wù)連續(xù)性,提升韌性,成...

關(guān)鍵字: 亞馬遜 解密 控制平面 BSP

8月30日消息,據(jù)媒體報(bào)道,騰訊和網(wǎng)易近期正在縮減他們對(duì)日本游戲市場(chǎng)的投資。

關(guān)鍵字: 騰訊 編碼器 CPU

8月28日消息,今天上午,2024中國國際大數(shù)據(jù)產(chǎn)業(yè)博覽會(huì)開幕式在貴陽舉行,華為董事、質(zhì)量流程IT總裁陶景文發(fā)表了演講。

關(guān)鍵字: 華為 12nm EDA 半導(dǎo)體

8月28日消息,在2024中國國際大數(shù)據(jù)產(chǎn)業(yè)博覽會(huì)上,華為常務(wù)董事、華為云CEO張平安發(fā)表演講稱,數(shù)字世界的話語權(quán)最終是由生態(tài)的繁榮決定的。

關(guān)鍵字: 華為 12nm 手機(jī) 衛(wèi)星通信

要點(diǎn): 有效應(yīng)對(duì)環(huán)境變化,經(jīng)營業(yè)績穩(wěn)中有升 落實(shí)提質(zhì)增效舉措,毛利潤率延續(xù)升勢(shì) 戰(zhàn)略布局成效顯著,戰(zhàn)新業(yè)務(wù)引領(lǐng)增長 以科技創(chuàng)新為引領(lǐng),提升企業(yè)核心競(jìng)爭力 堅(jiān)持高質(zhì)量發(fā)展策略,塑強(qiáng)核心競(jìng)爭優(yōu)勢(shì)...

關(guān)鍵字: 通信 BSP 電信運(yùn)營商 數(shù)字經(jīng)濟(jì)

北京2024年8月27日 /美通社/ -- 8月21日,由中央廣播電視總臺(tái)與中國電影電視技術(shù)學(xué)會(huì)聯(lián)合牽頭組建的NVI技術(shù)創(chuàng)新聯(lián)盟在BIRTV2024超高清全產(chǎn)業(yè)鏈發(fā)展研討會(huì)上宣布正式成立。 活動(dòng)現(xiàn)場(chǎng) NVI技術(shù)創(chuàng)新聯(lián)...

關(guān)鍵字: VI 傳輸協(xié)議 音頻 BSP

北京2024年8月27日 /美通社/ -- 在8月23日舉辦的2024年長三角生態(tài)綠色一體化發(fā)展示范區(qū)聯(lián)合招商會(huì)上,軟通動(dòng)力信息技術(shù)(集團(tuán))股份有限公司(以下簡稱"軟通動(dòng)力")與長三角投資(上海)有限...

關(guān)鍵字: BSP 信息技術(shù)
關(guān)閉
關(guān)閉