Skip to content

A map search tool, supports breadth first mode and depth first mode, and fork & join

License

Notifications You must be signed in to change notification settings

trytocatch/MapSearcher

Repository files navigation

通用图搜索工具

这是一个图搜索工具,支持广度优先和深度优先搜索策略,支持并行搜索,关心路径
权重不支持小数,如果有小数,请自行放大适当倍数来转换成整数
要求jdk1.8

编写背景:

为了解决一些图搜索问题,如:求两点最短距离及路线、求两点不重复(节点)的路线、求两点间不超过指定长度的所有路线等等

分析:

上述几个问题具有一定的共性,可以提取出通用需求,以达到复用的目的,用来解决这一类问题

通用需求提取:

实现图搜索,关心路径而不仅是路线条数或最短距离
为了应对不同场景,允许指定采用广度优先还是深度优先搜索策略
为了提升性能,利用多核资源,允许使用分治,并行搜索

约束:

为了简化问题,限定权重不能为小数,如果不满足,可以整体放大多少倍来适配

实现思路:

1、任务抽象

将具体任务抽象成一个Task类,其中有一个最关键的抽象方法check:

protected abstract ReturnState check(List<N> steps, int depth, int weight, R resultHolder, Boolean isRepeated);

工具在每一步搜索时都会调用此方法,它将传入当前路径、总权重、搜索深度等,在具体的任务中,可根据这些信息来完成具体的求解逻辑

通过返回不同的ReturnState,来指明是否结束当前路径的后续搜索,或者是结束整个任务,或者继续往下搜索,或者是指示将后续搜索转成一个并行任务

如果开启了并行搜索,则需要实现getForkResultHandler方法来定义一个ForkResultHandler,它指明了如何从当前结果收集器创建新的收集器(例如求最短路径的任务就需要用到当前结果,即已找到的最短路径),以及如何合并等

2、图数据整理(初始化)

在工具使用时,首先将图中的节点(比如节点为String类型,或是其它自定义对象)转换成索引,用索引值来表示图中的节点,以便于使用,提高效率对应于GraphSearcher类中的mapper、unmapper 然后将图中的路径、权重信息重新构建成一个二维数组data[][],data[m][n]表示从第m个节点到第n个节点的权重是多少,如果不可达,则用特定值标识,如-1

在搜索时,会遍历data[m]这个数组来寻找m节点可以到达哪些节点,为了提高 在m能到达的节点非常少的情况下 的遍历效率,构建的时候,例如data[m]为如下数组时 -1,-1,-1,-1,6,9,11,-1,-1,-1,4,8 会将data[m][0]修改为某个标记值,如-10004,用来表示下一个可到达的节点为data[m][4],同理,会将data[m][7]修改为-10010,修改后的数组为 -10004,-1,-1,-1,6,9,11,-10010,-1,-1,4,8 这样,便可以跳过中间连续的不可达节点,以达到快速遍历的目的

同时,为了节约内存,会尝试对data[m]进行前后截取,当data[m]的前后为连续的不可达节点,并超过一定长度时,会进行截取以减少内存占用,data[m]的最后一个元素一律用来记录头部截取了多少个元素,通过简单的加减运算,便可从截取后的数组中找到原来的第n个节点

3、搜索算法

a)深度优先

这个比较简单,使用递归就可以了,实现类GraphSearcher.DepthFirstSearcher<N>

b)宽度优先

算法比较复杂(实现类GraphSearcher.BreadthFirstSearcher<N>),因为要保留路径信息,仅仅将下一批可到达节点插到队列中的做法便不能达到此目的,于是我将路径信息也放入到队列中,但为减少内存占用,我采取了很多措施来优化。

例如:下面是队列中的两段数据 10003,2,3,1,4,5,3,1,10002,5,2,8,6,7 10003为控制信息,大于10000(代码中实际取的值为node个数+1),10003-10000得到的3表示,接下来的3个元素(2,3,1)表示,当前路径的最后3个节点切换成这3个节点,便可将当前路径切换到这段控制信息中记录的路径(因为在图搜索时,首先调整的是尾部的节点,所以这种记录方式是有效的),再接下来的4,5,3,1(直到遇到下一个控制元素为止)为这条路径接下需要搜索的节点。同理10002表明了接下来切换路径时,只需将当前路径中的最后两个节点切换成5和2,接下来的8,6,7为此路径的下一次搜索节点。

如果在搜索10003,2,3,1,4,5,3,1时,都被舍弃了,不需要进一步搜索时,此条控制信息便无意义了,此时,这条路径的控制部分(10003,2,3,1)会与后面的控制部分(10002,5,2)合并,变成10003,2,5,2。 上面说的是尾部合并,还有头部合并机制,队列最开始会插入一个周期标记,用来感知何时完成了一轮遍历,如果一个周期结束,路径的头部没发生过切换,那么没发生切换的这一段头部便可以移除掉,以此来节约空间,当搜索深度非常深且存活的路径只有尾部不一样时,便可省下大量控制元素。

为了减少内存占用,列队我没有使用自带的ArrayDeque,而是参照它自己实现了一个双向队列。

因为ArrayDeque内部使用的是一个对象数组,对象引用占用4个字节(64位可以指针压缩),而我往队列中插入的主要是节点的索引以及一些控制信息,都是非常小的整数,可能一个byte便够用了,这样便能成倍地减少内存占用,所以我编写了一个MagicArrayQueue,它有3种实现,区别在于内部使用的数组是byte[]、short[]还是int[],创建时参考传入的可能的最大元素值,来选择合适的实现,它们可以向上兼容,比如byte[]的实现,即ByteImpl也可以插入一个int,比如0x1FFFFFFF,此时便会使用4个byte来表示这个元素,第一个byte会包含一个控制信息,表明这个元素由4个byte构成。同时,还添加了针对这个搜索工具的修改方法,例如moveTail,在搜索时,可以在某个时候记录当前队列尾指针,接下来发现新插入的元素其实不需要,便不需要一个一个再移除元素,直接用moveTail来退回到原来位置即可,更高效。

4、其它

工具中还加入了节点重复检测,如果启用,则搜索出现重复节点时,结束该路径的后续搜索。

About

A map search tool, supports breadth first mode and depth first mode, and fork & join

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages