赵 冲,贺春林

(西华师范大学 计算机学院,四川 南充 637009)



权值优先搜索在儿童失踪追查中的应用研究

赵 冲,贺春林

(西华师范大学 计算机学院,四川 南充 637009)

为了实现儿童失踪快速追查，引入了“安珀警戒”系统并分析其在运行过程中存在的问题。对“安珀警戒”系统的运行成本过高的问题，针对城市交通密集路网建立无边界不定向的线性模型，借鉴图论遍历中的广度优先搜索算法的扩展思想，通过增加辅助队列改变算法的搜索次序，并根据实际为城市路网模型添加松弛因子，提出了适用于城市交通路网的权值优先算法。该算法能有效地在城市无边界路网中快速确定绑匪所行路线范围并随时间推移逐步扩展，在保证搜索结果无盲点的同时避免了系统运行初期的资源浪费。通过仿真实验证明，该算法能有效降低安珀警报短信发布成本39.7%以上。

安珀警戒；权值优先算法；儿童失踪；城市路网；线性模型；VISSIM仿真

据统计，全球每年约有120万儿童失踪，而最终寻回的只有0.1%[1]。如何寻回失踪儿童，建立完整有效的追查机制，是政府和社会亟需解决的问题。对于快速查找失踪儿童，我国目前的研究略显不足，美国的“安珀警戒”(AMBER Alert)为我们提供了可借鉴的经验。

安珀警戒系统使用美国紧急警报系统(EAS)，通过广播电台、卫星电台、电视台及有线电视向全国发布，同时利用电子邮件、交通信号标志牌、以及手机短信等方式将儿童失踪信息发送给广大民众[2]以协助警方进行侦破。安珀警戒系统受多种学科、多个机构的影响[3]，它并不是一个单独的个体。因此，在实行过程中也面临以下问题:(1)错误警报。据统计，2004年美国共发布233次安珀警戒，其中仅有70件是儿童被合法监护人以外的陌生人带走，误报率达到了70%[4]。错误的源线索(source cue)极大影响了信息的信用评级[5]，因此美国司法部发布了四条指引用于规范信息的真实性。(2)司法冲突。安珀警戒作为一种紧急性的侦查措施，在实施过程中会大量占用社会公共设施，如广播电台、电视媒体、手机通讯以及公共交通标志牌等。这无疑会对正常的社会秩序产生不利影响。(3)立案标准。2013年《公安机关查找疑似被侵害失踪人员信息工作规定(试行)》第二条规定：不满14周岁的未成年人失踪超过48小时予以立案。而调查研究发现，75%的儿童绑架案在案发后三个小时内人质即遇害，所以解救被绑架儿童就是在跟时间赛跑[6-7 ]。我国公安机关实行儿童失踪快速查找机制，要求县、市公安机关接到儿童失踪警情后，可以打破警种界限和常规做法，立即立案启动查找工作[8]。这一规定与安珀警戒的核心思想同出一辙，表明我国已具备实现安珀警戒系统的隐形条件。(4)成本控制。 安珀警戒的侦查实质是“眼睛越多越好”，但无论是使用社会公共设施、道路交通设施还是移动设备，其警报发布成本与搜索范围成正比。成本问题是制约安珀警戒发展的关键。

目前安珀警戒系统尚无明确的搜索范围规定。以美国加州为例，当警察机构确认绑架案发生时，在封锁车站、机场等交通枢纽的同时通过管辖区域内所有的信号基站向其控制范围内的移动终端发送安珀警戒信息，造成发布范围大、成本高、资源浪费严重。因而正确的搜索范围能极大降低警报发布的成本。

1 安珀警戒搜索范围

安珀警戒搜索范围的确定实质上是解决这样一个问题：从发生绑架到发布警戒信息这一段时间内，嫌犯能走多远。为嫌犯的逃窜路线划定一个区域作为安珀警戒的搜索范围，在保证没有盲区的情况下，尽可能缩小搜索区域，以降低信息发布成本。因为无法确定嫌犯的逃窜路线，因此需要将所有的可行的道路全部考虑进来进行分析。

设路网中有N条道路，道路的长度为l1,l2,…,ln，每条道路的通行速度为v1,v2,…,vn，每条道路通行时间为t1，t2，…,tn。则满足：

(1)

要计算嫌犯在一定时间内的活动范围，即要求:

t1+t2+…tn≤T。

(2)

由(1)代入(2)可得：

(3)

l1x1+l2x2+…+lnxn≤T。

(4)

由于嫌犯运行路线不确定，即要求将所有符合要求的路线全部包括在内，因此嫌犯活动的最大范围可表示为：

Maxz=c1x1+c2x2+…+cnxn，

s.t.l11x1+l12x2+…+l1nxn≤T，l21x1+l22x2+…+l2nxn≤T， ⋮

(5)

lm1x1+lm2x2+…+lmnxn≤T，
xi>0，i=1,2,…,n。

式中，m是迭代次数，n为路段标号。以起点为例，第一条路段的标号n为1，所有从起点出发的路段集合为{l11,l21，…，lm1}。搜索过程中，存在着多种路径选择，因此在计算其总耗费时间时，需要将所有可行的路段逐一计算。而在实际情况中，不可能恰好在规定时间内将每一条路段走完。因此在计算时引入一个松弛变量：xn+1，xn+2，…，xn+m，可将式(5)转化为：

Maxz=c1x1+c2x2+…+cnxn，

s.t.l11x1+l12x2+…+l1nxn+xn+1=T，l21x1+l22x2+…+l2nxn+xn+2=T， ⋮

(6)

lm1x1+lm2x2+…+lmnxn+xn+m=T，xi>0，i=1,2,…,n；xj≤0,j=n+1,n+2，…,n+m。

2 无边界路网权值优先搜索算法描述

城市路网中的搜索范围的确定，可视为基于图论的遍历问题。通常有两条遍历图的路径：深度优先搜索和广度优先搜索[9]。但由于范围的不确定性，无法提供图中的节点数及边界，因此传统的各种遍历算法均存在不同程度的缺陷。例如图1所示。

当使用深度优先搜索DFS时，算法的搜索顺序为：①→②→④→⑤→⑥→③；使用广度优先搜索BFS时，算法的搜索顺序为：①→②→③→④→⑤→⑥。假设限制时间T=10，通过穷举计算可知图1中T时间内可以达到的节点有①②③④⑤⑥；深度优先搜索在④节点时超出限制条件，最终搜索范围确定为①②③；广度优先搜索在第一次搜索到④节点后将其设定为已访问，导致③节点无邻接节点，最终搜索范围确定为①②③；这两种遍历方式均与实际情况不相符，原因在于没有考虑到路径的权值。因此提出一种基于广度优先搜索的权值优先搜索算法来解决其路径选择问题。该算法与传统算法的区别在于借助队列来确定搜索次序,同时已访问的节点并不标记，在访问重复节点时，如权值小于队列中已存在的节点权值，则更新权值；若大于等于队列中已存在的节点权值，则不处理。这种策略的优点在于不会在搜索过程中产生盲点。算法主要代码如下：

1.InitQueue(&Q);GreatList(C); //C表存放符合条件的节点，即搜索范围

2.WFS(G，u){ //u为图G的头节点

3.Visit(u);EnQueue(Q,u);EnList(C,u);

4.for(w=FirstAdjvex(G,u);w>=0;w=NextAdjvex(G,u,w)) //w为头节点的后继节点

5.{Visit(w);w.date=u.date+d(vu,vw); //更新权值

6.if w.date+P<=T EnList(C,w); else break; //判断是否满足条件

7. for (i=1;i<=Q.length;++i)

8. {EnQueue(w);SortQueue(Q); }

9. DeQueue(u);} } //更新队头元素

10.if (!QueueEmpty(Q)) WFS(G,w) //递归调用WFS

现基于权值优先搜索算法对图1中的节点进行访问，不考虑松弛变量P，算法运行过程中辅助队列Queue(Q)和结果列表List(C)中的元素变化如下表1所示。

表1 权值优先算法对图1简单路网的计算步骤表

表1中，每运行一步，都要执行删除队头元素，目的是更新队头元素。当运行至Step 7时，队列内元素为空，算法结束。此时的List(C)表中所存放的节点数，即满足权值w

通过对式(5)的描述可知，搜索范围即将所有符合条件的节点和路段全部计算在内。因此权值优先算法在计算时，首先将头节点即起点的所有后继节点加入队列，并通过迭代计算最终将所有符合条件的节点计算入表。计算时保证了搜索范围不存在盲点，证明了算法的有效性。

在城市路网中，除城市主路以外，另有大量密集且路段长度较短的支路。这些特点造成在以广度优先算法搜索时无法一层一层扩展，而在以深度优先算法搜索时会产生比较多的重复节点。因此按权值对支路节点排序时，可以保证支路节点优先扩展，以保证算法在节点密集的区域能有效进行。

3 实验分析

实验以四川省南充市的一段路网为例，运用的仿真工具为德国PTV公司开发的VISSIM[10-11]软件，版本号为6.00。实验环境为Windows 7 64位操作系统，AMD Athlon II x4 651 2.99GHz CPU，4.00GB内存。为计算方便，设定路段长度为实际长度(数据来源于百度地图)；不考虑特殊交通情况(如交通拥堵等)；不考虑交通信号灯等待时间，设定松弛变量P=0。

3.1 实验准备

简化后的交通网络是由路段和交叉路口组成的网络系统[12]。在实验准备阶段，需要对路网图范围内所有的路段：包括快速路、主干路、次干路和支路[13]及交叉路口(连接器)。在VISSIM中建立的路网模型如图2。

3.2 实验过程

以图2中A点即儿童绑架案件发生的地点为起点，假设疑犯使用的交通工具为小型汽车，且运行方向不确定。以下列仿真参数运行，仿真参数如表2。

表2 VISSIM仿真运行参数表

参数类型参数值期望速度40km/h期望减速度3.0m/s2信号灯停等时间0仿真时间120仿真秒仿真精度20时间步长/仿真秒随机种子42运行次数100随机种子增量1仿真运行速度10.0仿真秒/s中断时刻0仿真秒多核数量4Core

表2中期望速度是车辆在路段中行驶速度；期望减速度是指车辆在弯道或减速带的减速值；仿真时间与仿真运行速度决定仿真运行时间；仿真精度决定仿真结果的精确度；随机种子及随机种子增量决定仿真过程中各种随机事件，如车道的变化、左右弯道选择等，设定为默认值；多核数量与计算机CPU有关，影响仿真运行的结果。

3.3 实验结果

按表2的实验参数对图2中的路网模型运行仿真。结果如图3所示：A为起点，VISSIM软件的仿真结果是以.vlz文本格式保存，提取结果文本中的路段名称与距离值在地图图像中用黑色小点予以标示，每一个点即代表一次仿真运行结果。灰色区域为权值优先搜索算法确定的搜索范围。

由图3可知：灰色区域能完全覆盖黑点出现的范围,即算法所计算出的范围能包涵从A点出发的车辆所选择的所有路段，并且能保证无盲点。假设A点发生儿童绑架案件，并马上启动安珀警戒，警报发布部门根据权值优先搜索算法计算出疑犯运行范围并在该范围内发布搜索信息，可完全保证绑匪的行踪在市民的监测范围之内。

3.4 成本计算

安珀警戒系统的运行成本中，除了电视电台以及网络资源、公共交通资源外，最常用的手段是向民众发送手机短信，且其发送成本在总成本中占较大比重。要计算其短信发送成本，即要求计算出该范围内有多少人口，可表示为：

(7)

其中：C总是总发送成本，S1是权值优先算法确定的搜索范围，S总是该行政区域总面积，N总是该行政区域总人口数，C1是人均发送成本。以四川省南充市为例：已知S总为1.25×103km2，N总为7.5902×105人[14]，C1为0.033元[15]。(7)式中仅S1是未知数，求出权值优先算法的搜索范围即可计算出总发送成本。

由图3可知，权值优先算法所确定的搜索范围是不规则图形，常用的面积计算方法有坐标法、梯形法、支距法、simpson1/3法、simspon3/8法和1/6法[16]。但这些算法的计算方法较为复杂，对于精确度要求不高的计算中，可以采用像素法来进行面积的估算[17]。将权值优先算法计算出的范围在PhotoShop软件中勾选出来，并为其填充不同颜色，通过统计其像素数量结合地图比例尺进行计算。将计算出的面积代入(7)式可求得发送总成本，结果如图4所示。

由图4可知，权值优先算法确定的搜索范围在发布成本上呈现随时间递增的趋势。当案件发生10分钟时，权值优先搜索范围为264.50 km2，发送成本为0.53×103元。而按区域搜索范围固定为1.25×104km2，发送成本为2.502×104元。即此时案件侦破，则可降低短信发布成本97.9%；若案件在90分钟内侦破，则权值优先搜索范围为7.56×103km2，成本为1.511×104元，即降低短信发布成本39.7% 。而在案件发生90分钟以后，疑犯已经拥有至少一条路径逃离该行政区域，按区域搜索已经存在盲点，需申请周边区域联合侦查。当案件发生100分钟时，需将周边各市均计算在内，因此区域搜索面积为8.91×104km2，总人口为3.144×106人[18]，总成本为1.0375×105元。而权值优先搜索的范围为9.02×103km2，成本为1.807×104元，与按区域搜索相比成本降低了82.6%。实验证明权值优先搜索算法节省了大量的资源，对安珀警戒的发展与完善具有一定的实际意义。

4 结束语

安珀警戒系统能有效的保证被绑架儿童的快速追回。而我国目前对安珀警戒系统的引进和实现还处于试验阶段，但已经拥有运行安珀警戒系统的隐性条件。本文通过权值优先搜索算法在安珀警戒系统中的应用，能有效降低安珀系统的运行成本，有助于该系统在我国的引进和实施，为被绑架儿童快速找回保驾护航。

[1] 孔 明.我国每年约有20万儿童失踪 仅有0.1%能找回[EB/OL].(2013-06-02).[2015-05-05].HTTP://china.cnr.cn/yxw/201306/t20130602_512724290.shtml.

[2] 王晓楠.论“安珀警戒”对我国应对绑架儿童犯罪的启示[J].法制与社会，2013，(11)：290-292.

[3] MONICA K,TIMOTHY G,SAMANTHA S.The psychology of amber alert: unresolved issues and implications[J].The Social Science Journal,2008,46(1)：111-123.

[4] HARGROVE T.False alarms endangering future of amber alert system[N].Scripps Howard News Service,2014-07-26(11).

[5] GREER J,PAN P,FLORES D.Priming and source credibility effects on individual responses to AMBER and other mediated missing child alerts[J].The Social Science Journal,2012,49(3)：295-303.

[6] 安德鲁·卡，犯罪被害人学导论[M].李伟等，译.北京：北京大学出版社，2010：230.

[7] GRIFFIN T.An empirical examination of AMBER Alert ‘s uccesses’[J].Journal of Criminal Justice,2010,38(5)：1053-1062.

[8] 王文硕.全国公安机关实行儿童失踪快速查找机制[N].人民公安报，2011-06-02(001).

[9] 严蔚敏，吴伟民.数据结构(C语言版)[M].北京：清华大学出版社，1997:167-170.

[10] PTV.Planung transport verkehr AG[R].VISSIM Introduce.PTV Corporation,2005.

[11] PTV.VISSIM 6.00 User Manual[R].German:Planung Transport Verkehr AG,2013.

[12] 崔毓伟，袁鹏程，倪安宁，等.基于COPULA函数的交通网络形成时间可靠度计算方法[J].计算机应用研究，2014,31(5)：1385-1389.

[13] 中华人民共和国住房和城乡建设部.CJJ37-2012 城市道路工程设计规范[S].中华人民共和国行业标准.北京：中国建筑工业出版社，2012.

[14] 南充地方志办公室.南充年鉴(2013)[R].四川：电子科技大学出版社，2013.12:50-59.

[15] 邹明强.中国群发短信入刑第一案：垃圾短信背后的利益链[J].法制与经济(上旬刊)，2011(8)：24-25.

[16] 曹新华.不规则图形面积计算的新方法[J].武测科技，1993(3)：14-19.

[17] 泮章胜，叶连宝.浅谈利用PhotoShop精确计算图形面积[J].绿色科技，2012(8)：261-263.

[18] 四川省统计局.四川统计年鉴(2014)[R].北京：中国统计出版社，2014.12：10-11.

Application of Weight First Priority Search in the Search for the Missing of Children

ZHAO Chong,HE Chunlin

(College of Computer Science,China West Normal University,Nanchong Sichuan 637009,China)

In order to realize fast track of the missing children,the “Amber Alert” System is introduced and the problems existing in its operation process is analyzed.As the “Amber Alert” control system operation costs high,aiming at urban traffic dense road network,non-boundary directional linear model is established,and the applicable priority weights algorithm for urban traffic network is put forward,which consults the prior algorithm of graphic traversal breadth search in terms of the search order of increasing assisted queue algorithm,and according to the actual model of added relaxation factor in urban road network.The algorithm can effectively locate the area of the kidnappers in the city without boundary in the network and gradually extended with the passage of time,which ensures the search results without blind spots and avoids the waste of resources at the initial operation of the system.Through simulation experiments,this algorithm can effectively reduce the amber alert message issued more than 39.7% of the cost.

amber alert;weight priority algorithm;children missing;urban road network；linear model;VISSIM simulation

1673-5072(2016)04-0479-06

2016-06-21

四川省教育厅自然科学重点项目(15ZA0148)

赵 冲(1986—)，男，四川广元人，硕士研究生，主要从事计算机应用技术研究。

贺春林(1971—)，男，四川广安人，教授，主要从事计算机应用研究，E-mail:93401318@qq.com

TP399

A

10.16246/j.issn.1673-5072.2016.04.021