2
回答
业务需要实现一个最短路径算法,关于技术实现的学习,决策以及实现难点思路请教
利用AWS快速构建适用于生产的无服务器应用程序,免费试用12个月>>>   

背景介绍

业务模型:

传输段由两个网元组成,它可以继续拆分成若干个传输时隙,时隙本身有空闲、占用两种状态,以及一个叫速率的属性。通过传输段可以遍历下级时隙,然后进行汇总计算则可以获得此传输段的空闲速率容量。

需求:

任意选择两个网元,规定好目标速率,然后找出其中满足目标速率且跳数最少的传输段列表作为最短路径。

目前的解决办法

在算法上采用 Dijkstra 算法,根据使用场景做了个变种,可达路径的权值均设为1。

过程分为两个步骤,

  1. 按照算法检索出符合要求的网元序列:每次站在下一跳网元根据速率约束搜索符合要求的下一跳网元,并缓存已检索到的网元列表,直到找到终点网元,取最先找到终点网元的那条路径作为最短路径。
  2. 再根据遍历到的网元序列检索符合要求的传输段序列。

由于段空闲容量的获取需要动态的进行数据库查询,所以为了减小过程中的网络开销,第一版代码是由前人用存储过程写在数据库的执行的。这也导致了如下几个显著的缺点:

  • 维护成本高昂,这个算法的主体写了小1k行(其他支持性函数加起来另外有1k行),任何后来人对这个算法做任何改动,都得先花几天时间对存过逻辑进行梳理。(这点其实有更深层次的原因,相较java,存过更不容易拥有良好的封装,所以coder们稍不自觉,业务逻辑和算法主体也就紧紧的耦合在一起了)
  • 难以拓展,业务中与网元自动搜索相似的最短路径搜索需求其实挺多的,但是因为算法方案与业务逻辑耦合比较紧密,所以每类需求的实现都有不同程度的重复代码,当经历了不同人的几轮维护之后,到我手中每处重复的代码都总有微小的不同,重构难度较大。
  • 计算速度偏慢,客户反馈过多次,跳数较多的情况下查询偏慢。其实也好理解,遍历过程中总有些核心网元与多个网元有链接,只要查询过程多经过几个核心网元,计算量都是爆炸。

可能的改造思路

改造思路

宏观来说,将主体算法移植进代码层并考虑替换掉 Dijkstra 算法

细节来说,逻辑上采用模板方法模式对算法主体进行封装,暴露出遍历下一跳的以及可达判定方法作为钩子方法。以完成算法主体逻辑与业务细节的解耦合。

面临的问题:

算法不熟:因为我对图论相关算法并不熟悉(其实别的算法积累也比较薄弱),所以目前并不知道什么样的算法比较适合这个业务场景,不知道有没有过来人能给点建议?

网络开销:将算法主体移植到代码层,固然提升了功能的可维护性以及可拓展性,但是由于查找下一跳以及判断是否可达,都需要动态查询。在原有算法思路下,过程中必然伴随着大量 sql 读请求的出现,相较于之前放在存过中,网络开销的增加也不可忽视,所以我很懵逼,有什么办法可以优化掉这层网络开销吗?建表进行数据缓存是一种可行的思路吗?

由于个人学识所限,面临这样一个综合问题有些无处下手的感觉,如果社区大大们有什么好的处理思路,还望不吝赐教,拜谢了

(ps:也欢迎大家在问题下进行讨论,解决思路并不局限于算法的选择,表存储的优化,实现方式的决策等,我会对问题的解决进度进行及时的更新的。)

<无标签>
举报
Thehope
发帖于6个月前 2回/168阅

大学毕业的时候作死的做了一个关于人脉交友的题目。自己YY出一个业务场景。然后通过找人与人之间的最短路径。每个人之间权重不一样。然后用的就是Dijkstra 算法。但是那个时候的那个电脑已经坏了,源码也没上传托管中心。大概说说记忆中当时的做法吧。可能是你们业务场景太复杂。我当时也没用多少量的代码。

先介绍下我的业务场景吧。毕竟有时候从业务优化远比从代码优化好得多。我当时YY的场景是。人和人之间需要添加好友是需要购买达到的。然后就需要找一条购买路径。这条路径上的每个人都需要买通,这个时候就需要找到花钱最少的那条路径。

数据库设计大概是这样的

id  user_id    friends_id friends_price del_flag
1 1 2 2.00 0
... ... ... ... ..

 

 

 

专门拿一张表来存储构建Dijkstra算法所需要的结构。然后每次把所有的数据读出来初始化Dijkstra结构。算法只管寻找最短路径。不处理业务逻辑。把最短路径找到了之后,把最短路径返回给调用的业务逻辑,进行处理。由于我对算法方面也从来没有过研究。所以也只能从熟悉的Dijkstra算法给出优化建议。

tips1:算法只管寻找最短路径。不要处理业务逻辑。所有业务逻辑都可以放到找到最短路径后来进行处理。

tips2:由于算法的特殊性。算法主要耗时在db读操作和结构初始化上。所以要针对该算法进行优化的话。建议考虑减少DB读操作和结构初始化操作。可以考虑对DB读加缓存,或者采用常驻内存的方式保存算法结构。避免每次查找最短路径的时候都进行读数据初始化结构这个操作。

tips3: 这个算不上建议了。只是当时做的一个测试。当数据量达到10w还是100w的时候。内存可能不够用。当然搜索效率怎么样。就不请出来。没有实际做过测试。

我当时因为是毕设,而且很扯淡。所以就做得很简单。没有考虑过极端情况。所有人的可达性在我的系统里面要么是不可达。要么是最多经过六个人就能达到。所以在小规模的情况下。性能还是很好的。当然对于你们的情况就要根据实际业务来看了。

 

以上建议纯属一时兴起。如有不正之处,望指教。

--- 共有 7 条评论 ---
Thehope 回复 @weechang93 : 从业务角度分析+1,所以我现在考虑,能不能从更高的业务模型角度,将现有的点和线放入依据某种规则建立的某种集合概念中,通过更高级别的抽象,来减少点和线元素的计算量,或许能抽象出某种带权的点集和线集也说不定。到那个时候面对较少的点集和线集以及带权的边,或许才是迪算法的用武之地吧。唉,真实的业务头绪太纷繁复杂,很多答案都隐藏的很深。 6个月前 回复
weechang 回复 @Thehope : 这个问题的话。其实还是可以从业务上分析的。你们的节点是速率是服务端每次pull。还是节点定时push。如果是节点push的话。你就可以把节点数据初始化好。然后每隔一段时间进行内存中节点数据的更新。能放内存最好。不能的话放缓存也是个不错的选择。另外楼下说的A*也可以考虑下。 能说的就这么多了吧。毕竟经验有限。毕竟初级程序猿一枚。TT 6个月前 回复
Thehope 回复 @weechang93 : 不好意思,回复的有些晚了。用户在调用最短路径搜索的时候,会传进来一个目标速率值,实际从点遍历的可达线元素时,需要动态计算线元素的空闲速率(通过计算下级资源,然后汇总)(其实有点像容量,空闲容量足够才行),满足要求的线元素权重都是1。 6个月前 回复
weechang 回复 @Thehope : 可以说得具体点吗?关于速率约束这一部分。 6个月前 回复
Thehope另外:实际业务场景中的点元素大概在1万~10万左右,放在代码内存中有点担心内存爆炸。。。 6个月前 回复

建议,考虑下A*算法,另外,就是考虑下节点的数据存放在内存里面,可能有类似的数据库系统,10万个节点的数据似乎应该可以存下,最后,考虑下分布式的算法,把计算量分布到几个Akka/Actor上计算似乎是有可能的, 一直运行计算,结果附加到搜索库里面,附言,以上只是一点设想,实际因为没有做过,所以代码上帮不上什么忙。加油!

--- 共有 1 条评论 ---
Thehope谢谢你的建议,我找找公司内对分布式熟悉的人咨询下看看。因为自己并没有类似的经验,所以之前从实践角度上,优先从业务角度考虑了找最优解了。 6个月前 回复
顶部