基于偏好的有向图路径搜索系统设计与实现

赵晓东+方欢+陈思宇

摘 要：利用Java对基于偏好的有向图路径搜索系统进行了分析和设计，用来解决以下实际问题：有向图中边的权值是一个区间[a，b]，其中a表示最小代价，b表示最大代价，根据个人偏好给出有向图中边的偏好因子和一个目标值F，找出从源点到汇点的所有路径中满足边的偏好权重值之和小于F的路径集合。提出的基于偏好的路径搜索可在相关优化算法中广泛应用。

关键词：偏好；权值区间；有向图；路径搜索；路径优化

DOIDOI：10.11907/rjdk.171321

中图分类号：TP319

文献标识码：A 文章编号文章编号：1672-7800（2017）008-0108-03

0 引言

路径搜索问题在很多领域都有其研究价值，很多问题最终都可转化为图的路径搜索问题。随着社会的发展，有向图最短路径搜索研究成果已经无法满足需求。为此，本文设计一套给定条件下基于偏好的有向图路径搜索系统。

实际生活中往往会遇到做一件事情的代价在一定范围内波动的问题，将这种问题转化为图的问题进行解决，引入权重区间来表示图中边的权取值范围。对于同一件事情有不同的解决方法，由于各种因素导致不同的方法有着不同的倾向，于是将问题转化为图的问题后引入偏好因子来衡量个人对边的倾向程度，表示对该边的倾向占整体的比例。实际问题中由于某些因素的限制，会使得问题处理具有一定的局限性。即便问题的处理有多样性也需要根据实际选择解决方法，将这种问题转化为图的问题引入偏好权重表示，根据代价的范围以及倾向程度决定带入计算的具体值。为了满足用户对图的边偏好以及图中边权重的波动需求，通过用户输入图的起点、终点、目标值、各边偏好因子和权重区间，在有向图环境下搜索出所有满足目标值条件的路径，很容易得到最短路径。

1 需求与功能分析

1.1 需求分析

随着计算机的普及，人们遇到问题时都希望通过计算机技术进行科学合理的解决。诸如房子装修问题，用户在一定预算下对不同的房间装修喜好要求不一，又如用户需要在一定时间内从地方A到地方B，由于路况等因素，对于不同路线的倾向程度不一样，考虑限速、堵车等因素，不同路段行驶时间预计在一定范围内，类似上述问题都可以转化为给定条件下基于偏好的有向图路径搜索。为了解决这类问题，设计开发了给定条件下基于偏好的有向图的路径搜索系统。偏好因子采用两种不同的表示方式，一种是用户只知道大致的偏好程度无法具体量化，另一种是根据各边的部分偏好占整体偏好的比例计算。用户通过输入图的顶点数、起始点、终点、目标值、图中各边的偏好因子、成本区间矩阵，经过后台算法计算，得到限制条件下满足个人偏好的所有路径[1]。

1.2 功能分析

图的路径搜索系统软件功能如下：①对满足目标值的所有路径进行显示；②对于图的每条路径的权重受用户偏好影响；③用户的偏好因子采用两种计算方式，由用户决定采用哪种；④界面简单易操作。

偏好的两种表示方式：

（1）用户只知道大致的偏好程度无法具体量化。采用A-F选项进行选择，A-F不同选项代表不同区间，然后从区间内产生一个随机数作为偏好因子[2]，选项代表的区间具体如下：

A选项对应区间为[-1.0，-0.6]，B选项对应区间为[-0.6，-0.3]，C选项对应区间为[-0.3，0]，D选项对应区间为[0，+0.3]，E选项对应区间为[+0.3，+0.6]，F选项对应区间为[+0.6，+1.0]。

该方式下偏好权重W为：

W=a+b2+b-a2×d（1）

其中，边的权重区间为[a，b]，边的偏好因子为d。

（2）根据部分偏好占整体偏好的比例，从起始点到终点的一条路径上各边的偏好因子之和为1，该方式下偏好权重W为：

W=a+b2+b-a2×（2×d-1）（2）

其中，边的权重区间为[a，b]，边的偏好因子为d。

这两种方式下，当偏好因子的取值范围为0～1时，偏好权重取值范围为a～b。

系统包括3大模块：①界面设计模块。该模块用以设计各种界面，用来输入图的顶点数、起始点、终点、目标值、图中各边的偏好因子、成本区间矩阵，完成各界面之间的数据交互以及最终限制条件下满足个人偏好的所有路径结果显示；②有向图路径搜索模块。根据界面模块提供的数据，基于深度优先算法进行路径搜索，得到想要的路径集合；③结果显示截获模块。利用Eclipse进行Java语言设计，把控制台结果截获以管道流的形式将输出结果在界面中的文本框中显示[3]。模块间的联系如图1所示。

2 系统设计

2.1 功能设计

为实现用户与系统的交互功能，考虑实际问题中用户的偏好问题，由用户输入转化后有向图顶点个数动态生成有向图，输入起始点、终点、目标值、各边偏好因子等数据完成路径搜索。由于有些用户的偏好程度无法量化，系统通过偏好程度选项自动生成衡量偏好程度的数值指标。系统界面输入相关数据和显示结果，算法用以求解路径集合[4]。系统执行流程如图2所示。

2.2 系统界面设计

（1）主界面设计。本界面用于输入顶点个数、开始顶点、结束顶点、目标值以及显示最终结果。单击输入成本邻接矩阵按钮跳转到成本邻接矩阵界面，单击输入偏好邻接矩阵（类型一）按钮跳转到偏好邻接矩阵（类型一）界面，单击输入偏好邻接矩阵（类型二）按钮跳转到偏好邻接矩阵（类型二）界面，单击显示满足条件的路径（类型一）按钮，显示由偏好邻接矩阵（类型一）界面数据得到的结果，单击显示满足条件的路径（类型二）按钮，显示由偏好邻接矩阵（类型二）界面数据得到的结果。主界面设计如图3所示。

（2）成本邻接矩阵界面设计。本界面根据主界面输入的顶点个数动态生成一个输入矩阵，用于输入有向图中各边权重，即两个相邻顶点之间需要的代价[5]。由于矩阵的每个元素是一个数值区间，为方便用户输入，将矩阵中的每个元素输入界面设计成图4樣式。对于矩阵对角线元素默认为[0，0]，顶点之间不连通的则不用输入。单击提交按钮进行提交且关闭界面。endprint

（3）偏好邻接矩阵（类型一）界面设计。本界面根据主界面输入的顶点个数动态生成一个输入矩阵，用于输入有向图中各边的偏好指标。考虑到有些用户对于偏好程度无法量化，系统通过偏好程度选项（A-F）自动生成衡量偏好程度的数值指标。

（4）偏好邻接矩阵（类型二）界面设计。本界面根据主界面输入的顶点个数动态生成一个输入矩阵，用于输入有向图中各边的偏好指标。根据部分偏好占整体偏好的比例进行填写，填写范围为0-1。

2.3 软件测试

进行功能测试，主要针对系统的输入、界面跳转、相关数据求解路径集合等进行测试，每种测试都包括正常和非正常两种情况。测试的相关数据如表1、表2、表3、表4所示。

根据上述数据运行结果如下：

当前的顶点个数：6

目標值：70

第V0个节点：V0-V0：0 V0-V1：1 V0-V2：1 V0-V3：0 V0-V4：0 V0-V5：0

第V1个节点：V1-V0：0 V1-V1：0 V1-V2：1 V1-V3：1 V1-V4：1 V1-V5：0

第V2个节点：V2-V0：0 V2-V1：0 V2-V2：0 V2-V3：0 V2-V4：1 V2-V5：0

第V3个节点：V3-V0：0 V3-V1：0 V3-V2：1 V3-V3：0 V3-V4：1 V3-V5：1

第V4个节点：V4-V0：0 V4-V1：0 V4-V2：0 V4-V3：0 V4-V4：0 V4-V5：1

第V5个节点：V5-V0：0 V5-V1：0 V5-V2：0 V5-V3：0 V5-V4：0 V5-V5：0 其中0表示两个相邻顶点之间不存在通路，1表示两个相邻顶点之间存在通路。

由偏好邻接矩阵（类型一）界面数据得到结果：

V0→V1→V3→V4→V5 总代价为：69.0

V0→V1→V3→V5 总代价为：61.0

V0→V1→V4→V5 总代价为：60.0

V0→V2→V4→V5 总代价为：64.5

由偏好邻接矩阵（类型二）界面数据得到结果：

V0→V1→V3→V4→V5 总代价为：62.0

V0→V1→V3→V5 总代价为：52.0

V0→V1→V4→V5 总代价为：55.0

V0→V2→V4→V5 总代价为：59.0

经检验，上述结果正确。

性能测试主要是进行响应时间测试，该测试通过不同数量的数据完成。

3 结语

采用Java语言设计并实现了给定条件下基于偏好的有向图路径搜索系统。应用本系统，用户基于偏好输入相关数据得到最终想要的路径集合，很容易得到最短路径。下一步将对系统进行优化，更多考虑人性化需求，美化系统操作界面，优化路径搜索算法，提高系统运行速度。

参考文献：

[1] 严蔚敏，吴伟民.数据结构[M].C语言版.北京：清华大学出版社，2006.

[2] 方贤文.Java语言程序设计[M].合肥：安徽科学技术出版社，2014.

[3] 李兴华.Java开发实战经典[M].北京：清华大学出版社，2009.

[4] 马可，艾伦，维斯.数据结构与算法分析：Java语言描述[M].第3版.北京：机械工业出版社，2016.

[5] 李刚.疯狂Java讲义[M].北京：电子工业出版社，2012.endprint