[技术资料 嵌入式系统] 基于数据可视化处理的嵌入式智能查询算法

来源：互联网   发布日期：2011-09-07 14:24:35   浏览：5463次  

   当前位置： IC37首页 > 技术资料 > 嵌入式系统 > 基于数据可视化处理的嵌入式智能查询算法

基于数据可视化处理的嵌入式智能查询算法

类别：嵌入式系统  

　　据在许多研究领域都可采用图形来表示，图形和图形理论为人工智能决策提供了有效的可视化工具、体系化准则和相关技术。本文以交通线路自动调整系统为例，说明在嵌入式智能查询算法中如何利用图形对数据进行可视化处理的方法来避免“盲目”操作，从而提高算法的决策效率。

　　图形由节点和边线组成，节点通常画作圆形，而边线则是节点之间的连线。在软件中，节点通常采用将边线作为指针或数组下标的数据结构加以实现。对图形进行遍历查询的算法有多种，常用的算法包括深度优先查询和宽度优先查询算法。深度优先和宽度优先都属于“盲目”查询算法，深度优先算法沿着一组边线从根节点一直查询到最远端的叶节点，再查询下一个叶节点；宽度优先算法则首先查询一个边线距离以内的所有节点，再查询两个边线距离以内的节点，以此类推。

　　上述算法之所以具有盲目性，是因为算法在查询适当解决方案的过程中并未指示任何有效信息，而只是盲目地遵循遍历算法，甚至有可能在找到解决方案之前需要遍历每一个节点，因而效率比较低。本文介绍的基于数据可视化处理的嵌入式智能查询算法以车辆行驶线路自动调整系统为例来说明解决上述问题的思路。

　　车辆导航 　　在设计一个遍历整个公路段的网络系统中，假定存在一个自动垃圾收集站系统、运动摄像机或自动交通线路调整系统。图１显示了旧金山的部分城市交通图。　首先，需要创建代表上述数据的网络图，以确定将哪些单元作为节点。如果其他标志不甚明显，那么道路交叉口就可选择为节点。随着这些节点的插入，就完成了网络图的一部分，不过目前得到的只是城市交通图的无目标静态表示。

　　下一步是添加系统进行智能决策所需的额外信息。如果系统的目标是帮助车辆选择最佳的路径而从一个交叉口驶向另一交叉口，很自然地就会想到为那些连接交叉口的公路段分配权值。在最简单的情形中，所有的道路都不是单行道，并且具有相同的速度限制和车道数目。即便这些条件不能完全反映真实的道路状况，一旦构建好网络图和权值模型，就能很容易扩展到这些真实环境中去。

　　对交通图中的边线赋以权值有助于系统找到最佳的路径。在某种程度上，这些权值可以任意分配，这里假定权值表征平均车流密度。基于特定时段或局域条件的动态权值也是可行的，并不影响以下分析。

　　图１中，边线的权值表示了每小时穿过道路的平均车流量，这些统计数据并不基于任何实际的数据，但在分析中相当有效。如果车辆必须从Ｓｃｏｔｔ和Ｊａｃｋｓｏｎ　交叉口（节点　５）行驶到Ｆｉｌｌｍｏｒｅ和Ｖａｌｌｅｊｏ　交叉口（节点１７），采用最小车流量判据，得到的查询算法应能得到总权值最小的路径。

　　我们很容易就能在网络图中画出结果，但仍然希望能借助计算机解决问题。表征图形的两种最常用方法是邻接矩阵（ａｄｊａｃｅｎｃｙ　ｍａｔｒｉｘ）和邻接表（ａｄｊａｃｅｎｃｙ　ｌｉｓｔ）。邻接矩阵是静态的多维阵列，矩阵中的元素表示一个节点到另一节点的权值。图２显示了示例网络中包含节点１至节点６之间边线权值的部分邻接矩阵。节点１和节点６之间的边线权值位于最右角（对应点位于左下角）。图２中３６个节点的公路网络的整个邻接矩阵可包含３６个元素。

　　邻接表通常采用链表实现，图３显示了网络中节点１至节点６的邻接表。图中并未标出边线权值，但可以很方便地存储在数据结构中。

　　对邻接矩阵和邻接表进行选择时，可以考虑如下因素： 　　１．　如果网络图密集或较小，则用邻接矩阵表示。邻接矩阵的优势在于可以直接取得权值，而无须进行指针管理和链表遍历。

　　２．　如果网络图稀疏或很大，那么邻接表可以减少内存浪费。

　　３．　如果需要实时地添加和删除节点或边线，则采用邻接表。当然，这时也需要系统具有动态内存管理能力。

　　直观推断 　　如果根据每个节点出口的最小权值进行“盲目”查询，那么很有可能会走错路，甚至永远无法到达目的地。更为智能的查询应能根据直观推断进行构建，并且直观推断应能在大多数时间内成为查询的常规指南。我们通常将其称为经验规则。生活中最简单的经验是：“因为现在是４月且天空多云，所以需要带上雨伞。”虽然４月份和天空多云并不意味着会下雨，但这样的条件下下雨的可能性远远高于正常天气。

　　直观推断也是实现高速有效查询的一个重要策略。如果尚未打定主意，最初可以选定一个不怎么适当、甚至大错特错的值。对于公路遍历问题而言，一种可能的直观推断是：“当一个节点存在两个（或更多）等权值的边线时，执行宽度优先查询，然后继续查询总权值最小的路径。”例如节点１５就出现了这样的情形，该节点的出口存在两个权值为１５的边线。利用宽度优先查询，对下一节点及其出口边线的权值进行检测。下一级节点为１４和２０，这两个节点出口边线的权值分别为１５和４５。根据最小边线判据，选择节点１４继续查询，这完全合乎情理；因此节点２０将被抛弃。

　　某些直观推断看起来非常明显，但即便是这些直观推断也有助于探寻待解决问题的实质。对于公路遍历问题，最基本的直观推断就是：“选择具有最小边线权值的路径。”这简单易行，但背离了查询的基线准则。

　　遵循最小边线权值的方法称为“贪婪算法”（ｇｒｅｅｄｙ　ａｌｇｏｒｉｔｈｍ），该算法以即刻满意度为基础。贪婪算法并不考虑以后的情况，而选择当前最为廉价的路径进行查询。这并不能保证得到有效的解决方案，甚至有时会得到不怎么优化的路径。当询及为何选择最终被证明是错误的路径时，贪婪算法或许会回答：“在当时，这看起来是个不错的选择。” 　　一些对人类而言相当明显的直观推断对于机器则并非如此。例如直观推断“当节点存在两个（或更多）等权值边线时，将执行宽度优先查询，然后继续查询总权值最小的路径”，这本身并没有问题，但还是存在一个问题。如果最小成本的路径偏离了目标节点怎么办？这样选择得到的或许是一条更为昂贵的路径。由此可见，还必须了解从当前节点至目标节点的方向。以这种形式开发直观推断是展现待解决问题所需核心知识的良好途径。

　　解决公路网络导向问题的一个有效途径是动态计算当前节点和目标节点之间的距离和方位。这要求得到每个节点的经纬度数据，并对前进中的每一个节点进行浮点操作，因而极有可能是最不优化的解决方案。更好的策略是根据经纬度对之间的差异得到一套准则，这有助于提取最少准则所需的信息。

　　第一步必须明确方向和经纬度之间的关系，图４显示了根据经纬度差异得到的方向。

　　当向北方移动时，纬度将增加；向西方移动时，经度增加；以此类推。从这些简单的关系中可以看出，每个节点上完全可以去除许多不必要的操作。将以上知识与交通图相结合，可以得到Ｓｃｏｔｔ和Ｊａｃｋｓｏｎ交叉口的起始纬度和经度分别为Ｎ３７　４７．５１４和Ｗ１２２　２６．３５６，而目标Ｆｉｌｌｍｏｒｅ和Ｖａｌｌｅｊｏ交叉口则分别为纬度Ｎ３７　４７．７２５和经度Ｗ１２２　２６．００２。根据图４中的罗盘仪准则，现在目标交叉口位于起始交叉口的东北方向。

　　根据以上方向关系，可以得到如下六条准则： 　　准则１：如果纬度（目标）　＞　纬度（现在状态），那么目标为北方； 　　准则２：如果纬度（目标）　＜　纬度（现在状态），那么目标为南方； 　　准则３：如果纬度（目标）　＝　纬度（现在状态），那么目标为空； 　　准则４：如果经度（目标）　＞　经度（现在状态），那么目标为西方； 　　准则５：如果经度（目标）　＜　经度（现在状态），那么目标为东方； 　　准则６：如果经度（目标）　＝　经度（现在状态），那么目标为空； 　　可以将上述基本准则相结合以得到更为复杂的方向，如东北和西南。这只需要将基本准则通过＂与＂操作结合起来，这样有效的组合如下： 　　规则　１　＾　规则　４　－＞　目标为西南 　　规则　１　＾　规则　５　－＞　目标为东北 　　规则　１　＾　规则　６　－＞　目标为北 　　规则　２　＾　规则　４　－＞　目标为西南 　　规则　２　＾　规则　５　－＞　目标为东南 　　规则　２　＾　规则　６　－＞　目标为南 　　规则　３　＾　规则　４　－＞　目标为西 　　规则　３　＾　规则　５　－＞　目标为东 　　规则　３　＾　规则　６　－＞　目标为空 　　将基本准则和复杂准则结合起来就能得到成功的查询方法。如果目标在当前节点的西北方向，那么向北方和东方移动是合法的。这里我认为应该是：“如果目标在当前节点的东北方向，向北方和东方移动是合法的”，而向南方和西方移动则不合法。

　　当查询到节点１２，选择的逻辑路径则是从节点１２至节点１１并且权值为１５的边线。此时方向为北方，这看来是合法的，且边线权值达到最小。其实这完全是错误的，因为查询偏离了目标节点。现在我们利用规则对查询进行限定，节点１２与节点１７平行，因此准则３成立。此时经度减少，因此规则５成立。如果规则３和规则５都成立，那么目标是正东方。规则基础很好地完成任务：避免了“盲目”查询或对“盲目”查询进行导向。结果如图５所示。

　　本文小结 　　如上所述，图形表示法和盲目查询算法本身并不足以解决大多数问题。但将这些技术同直观推断以及特定问题的规则集相结合，就像上面所做的那样，就能得到有效的人工智能。类似的技术可应用于诸多应用领域。尽管本文的示例集中于静态数据，但当边线及边线权值改变并且不能对规则进行硬编码时，这里给出的技术仍然有效。

　　显然，嵌入式系统通常受制于某些特殊限制。嵌入式编程中一般不允许递归算法，尽管这是图形查询算法中的一种常用技术。关键应用中的嵌入式系统也不支持动态内存分配，但如果没有动态内存分配的话，将很难在链表数据表示法中添加和删除节点。出于以上考虑，可以得到如下嵌入式智能的应用技巧： 　　１．　考虑将部分处理移交至功能更为强大的系统，也许嵌入式系统只需要解决部分需要快速解决的问题。

　　２．　避免递归，任何递归函数都应当用迭代函数进行重写。

　　３．　尽可能减小动态内存分配。如果链表的长度相对保持恒定，就可用数组进行代替，使数组的大小等于链表的最大长度，一旦超过该最大长度就返回操作失败。

　　４．　将智能视为低能动物而非超级计算机，即将其想像为处理意外情况或干扰的低等动物形式。

　　５．　最重要的是，有效地综合“盲目”算法、“贪婪”算法和智能查询算法。当然，也没有任何规定限制只能采用一种方法解决需要利用智能的问题。

　　请登陆: ic37网（www.ic37.com） 浏览更多信息

赞助本站