围剿周克华—基于贪心策略广度优先搜捕算法

《围剿周克华—基于贪心策略广度优先搜捕算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、剿周克华_基于贪心策略广度优先搜捕算法摘要：悍匪周克华在重庆被捕，其过程可谓惊心动魄。而我们知道，重庆市是国内首个启用交巡警平台的直辖市。在围捕过程中，这些交巡警平台究竟发挥了怎样的作用，在面对类似问题时，交警部门又该采取何种抓捕策略？本文试图就交巡警围捕嫌犯策略进行探究，最后给出了基于贪心策略的围捕算法，希望能给未来的智能交警网做一点基础性的工作。关键字：floydDijkstra广度优先算法贪心搜索算法围捕策略k模型建立为了进一步探讨，首先要对问题建立模型。这里假设已知某市的交通图，包括该市所有道路，路口，路口间距离及交巡警平台的位置。并假设罪犯逃逸速度与警察围捕速度相同，

2、v警二v匪=60km/h,罪犯在P路口作案，案发3分钟后接到报警并开始实施抓捕。作为决策者应该知道警车从某平台到任一路口的最短时间以及罪犯从案发地到某一路口的最短时间。假设某平台到A路口的最短时间为Timin，罪犯到达A路口的最短时间为T2min,当且仅当T1+3

3、：当接到重大刑事案件报案后，第一时间封锁所有进出本市的交通要道，这样就形成了以市为单位的包围圈。这样做的好处是可以保证歹徒无法流窜到外市，但显然这个包围圈太大了，为以后的搜捕工作带来了不便。运用一定策略，我们完全可以将包围圈缩小到以案发地为中心的某个区域内。假设共封锁k个路口形成包围圈，各路口封锁所需时间分别为T1T2...TK3、基本广度优先算法与分析采用路口分级法将路口分级，从而将路口分布拓扑图化为树状图。某路口的子节点定义为该路口直接相连的路口，事发路口为根节点，与其直接相连的7、31、33号路口定义为第一级节点，这三个路口的直接相连的路口为第二级节点,以此类推。为了使包

4、围圈严密(即使罪犯无法逃脱)，可以自上而下逐层进行封锁决策，采用广度优先的遍历方式，枚举岀每层封锁哪些路口，这些路口又由哪些平台封锁，若某路口没有被封锁，则在下一层中加入其子节点，这样，当遍历到某一层使得该层路口全部被封锁时，包围圈就形成了。因为从根节点出发的每一条树枝都被封死，即罪犯所有可能的路线都被封堵住了，所以这个包围圈是严密的。这样，我们完全可以用遍历搜索的方法枚举出所有的包围圈，选出时间最少，范围最小的那个。但是，由于一个市区的路口数以百计，每个交巡警平台所能管辖的路口也很多，导致广度优先搜索的时间复杂度过大,超出了一般计算的运算能力。于是，本文提出了基于贪心策略的搜

5、索算法。4、加入贪心的搜索算法—般来说，最佳围堵方案需满足3个标准：（1）包围圈足够严密以确保将嫌犯围堵在包围圈内（2）形成包围圈的时间尽量少（3）包围圈尽量小。第一个标准基本广度搜索算法已经可以保证，为了让包围圈尽可能的小，我们采取优先封锁高级路口的贪心策略。即在遍历与案发路口直接相连的第一级路口7、31,33时，封锁所有能够被封锁的路口如7、31,对于33号路口，没有任意平台能够将其封锁，此时再将其子节点加入下一层路口集，对下一层路口采取相同策略。这样做的合理性在于当高级路口被封住时，其所有子路口都不用再封锁，显然，按此贪心策略可使最终得到的包围圈最小。不仅如此，这样做还剪

6、掉了大量的树枝，大大缩减了搜索量，广度优先搜索算法也因此可行。最后在搜索出的所有可行解中找出形成时间最短的包围圈作为最终围捕方案实施。5、算法流程具体算法流程如下：Stepl:遍历当前层的下一层（从案发路口开始），对该层路口进行封锁。Step2:对该层某一路口，搜索能将其封锁的所有平台记为此路口的决策集，若决策集中某一平台既没有被其它平台使用也没有在搜索算法回溯到当前层之前被该平台使用过，则用其封锁该路口，同时将此平台标记为已用并从此路口的决策层中删除，将该路口标记为已封所,转step4oStep3:若搜索完该路口所有临近平台也没有满足条件的，则在下一层路口集中添加此路口的子节

7、点。Step4:该层遍历完成后，若该层所有节点均已被封锁，则转step5,否则转stepl.Step5:一次遍历完成，生成调度方案，并计算该方案的封锁时间和包围圈范围进行记录。Step6:将当前层所有路口所使用的平台恢复标记为未使用，将当前层所有路口恢复标记为未封锁，回溯到上一层的父节点，令封锁它的平台取其决策集中的下一个，转steplo当该父节点决策集中所有平台都已取遍时，对该层其他父节点进行相同操作。Step7;当回溯到根节点，即第0层时，说明已完成所有情况的求解，在生成的若干个调度方案