拓扑排序在顶尖风控团队的业务落地

2023-02-16 82

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 拓扑排序在顶尖风控团队的业务落地

一、引言

上一章我们讲解了关于图的搜索方法，主要是深度优先搜索和广度优先搜索，两种方法的搜索方式各有优点

不知道大家在日常工作中有没有碰到这种情况：

比如，我们只有完成工作一之后，才能去完成工作二、工作三，当工作二和工作三同时完成时，我们的工作四才开始开始

简单来说，当前工作必须依赖别的工作完成之后，才能实施工作，那么我们怎么判断哪一份工作需要提前完成呢？

这就是我们今天要讲的 拓扑排序

二、什么是拓扑排序

在图论中，拓扑排序（Topological Sorting）是一个有向无环图的所有顶点的线性序列。

且该序列必须满足下面两个条件：

每个顶点出现且只出现一次。
若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。

有向无环图才有拓扑排序，有环图没有拓扑排序一说

对于上图来说，拓扑排序可以帮我们做点什么呢？

分析每一个点的前后完成的位置
判断该图是否有环无环

三、拓扑排序的风控落地

在常见的风控公司，有这样一个功能：决策流

简单来说，用户通过配置规则、dubbo服务，做一个流式的计算，如图所示：

这是一个比较简单的决策流，它由三个策略集编排，并有起始和结束，是符合BPMN规范的

我们的决策流在执行时，通过拓扑排序去判断每一个策略集完成的前后顺序，进行决策的判断

而dubbo接口的作用，通过远程服务调用，获取我们需要的信息去进行决策的判断，最终获取一个分数

四、决策流的实现代码

组装成图的思路可见：给我5分钟，带你秒杀所有图算法之图的对象化描述

拓扑排序的思路：对于当前图中入度为0的点，即为当前可以执行操作的点

简单理解就是：当前的点，没有人指向他

对于上述思路，我们简单的遍历一遍所有点，可以得出第一次需要执行的点

当我们把第一个点给使用掉之后，我们需要将该点所连接的点的入度减一

我们直接看下代码：

  public static void getScore(DecisionFlowGraph graph, HashMap<String, String> map) {
        // 使用一个队列
        Queue<DecisionFlowPoint> queue = new LinkedList<>();
        // 遍历所有的点，找到入度为 0 的点
        for (DecisionFlowPoint point : graph.points.values()) {
            // 入度为0
            if (point.in == 0) {
                queue.add(point);
            }
        }
        // 当前的队列不为空
        while (!queue.isEmpty()) {
            // 弹出当前队列的头
            DecisionFlowPoint point = queue.poll();
            // 使用当前该点代表的策略集
            finalScore = finalScore + resolve(point, map);
            // 将该点所连接的点的入度减一
            for (DecisionFlowPoint next : point.points) {
                next.in--;
                if (next.in == 0) {
                    queue.add(next);
                }
            }
        }
    }