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

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

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

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

车辆导航

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

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

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

图1中，边线的权值表示了每小时穿过道路的平均车流量，这些统计数据并不基于任何实际的数据，但在分析中相当有效。如果车辆必须从Scott和Jackson交叉口(节点5)行驶到Fillmore和Vallejo交叉口(节点17)，采用最小车流量判据，得到的查询算法应能得到总权值最小的路径。

我们很容易就能在网络图中画出结果，但仍然希望能借助计算机解决问题。表征图形的两种最常用方法是邻接矩阵(adjacencymatrix)和邻接表(adjacency

list)。邻接矩阵是静态的多维阵列，矩阵中的元素表示一个节点到另一节点的权值。图2显示了示例网络中包含节点1至节点6之间边线权值的部分邻接矩阵。节点1和节点6之间的边线权值位于最右角(对应点位于左下角)。图2中36个节点的公路网络的整个邻接矩阵可包含36个元素。

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

对邻接矩阵和邻接表进行选择时，可以考虑如下因素：

1。如果网络图密集或较小，则用邻接矩阵表示。邻接矩阵的优势在于可以直接取得权值，而无须进行指针管理和链表遍历。

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

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

直观推断

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

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

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

遵循最小边线权值的方法称为“贪婪算法”(greedyalgorithm)，该算法以即刻满意度为基础。贪婪算法并不考虑以后的情况，而选择当前最为廉价的路径进行查询。这并不能保证得到有效的解决方案，甚至有时会得到不怎么优化的路径。当询及为何选择最终被证明是错误的路径时，贪婪算法或许会回答：“在当时，这看起来是个不错的选择。”