程序员经验分享-hwhale

使用Python实现二分图的KM算法在出租车订单匹配上的应用

2023-05-16

在这里插入图片描述

1. 需求

想要使用Python实现一个出租车仿真环境，其中每个时间窗口内产生的request及其周围的taxi满足一个二分图的关系。原本计划request与taxi之间的匹配按照接客时间权值最小为目标进行匹配，但是后面实践的时候觉得存在一定问题：①单个目标的权值设置为订单出行距离/接客时间比仅用接客时间作为权值更好。②最小匹配+非完备匹配+存在不可连接点的约束使得出现很多bug，且没想到解决方案。于是后面觉得改用出行距离/接客时间作为权值实现二分图最优匹配。

2.KM算法

KM算法是解决带权值的二分匹配问题的经典算法。解决request和taxi的匹配问题首先需要先了解二分图以及二分图的最优匹配（KM算法）。

二分图的理解这里不做解释，仅提示区分好二分图的几个重要概念：

  • 完备匹配：X或Y中全部匹配完
  • 完美匹配：XY都匹配完
  • 最佳匹配：权值最大的完备匹配（不是绝对的权值最大，因为限定了完备）。但可以增加一些权值为0的边使其统一起来
  • 带权匹配：就是求出一个匹配集合，使得集合中边的权值之和最大或最小
  • 相等子图：选择‘边权=顶标和’的边组成
  • 匈牙利算法是利用了增广的性质，使整个图匹配数最大。KM算法利用匈牙利算法求完备匹配下的带权二分图最佳匹配的算法。

KM算法理解可参考：

KM算法入门
KM算法运用篇
KM算法详解

重要的操作和踩坑（提醒）：

  • 最小匹配的问题可以通过权值取反实现（当权值都为正数时）
  • KM算法必须存在一个完备匹配，如果求一个最大权匹配(不一定完备)，添加一些边权值为0的连接，实现最大权匹配。
  • KM算法求是边权值和最大，若需边权之积最大，对每条边权取自然对数，然后求最大和权匹配，求得的结果a再算出e^a可得最大积匹配。
  • 算法中每次是选择交错树中顶标和与边权差最小的边。（计算一个d=min{L(x) + L(y) - wight(x,y)}
  • 设计算法按照不同的需求可能多次出现使用一个很大的数，如①代表二分图不可连接两点之间权值、②初始化的最小已寻找到的最小连接inc，③用大数-原权值求最小匹配。 的过程中注意区分几个很大的数之间的大小关系

KM算法实现

可以直接调用的函数
# 求的是最小匹配，idexes 返回所得连线的列表（元祖）
m = Munkres()
indexes = m.compute(matrix)

使用方法：

"""
@author:HY
@time:2020/12/3:19:15
"""
# 两个可以单独使用的函数
def cost(graph):

    """
    计算成本函数（路径最小化）
    :return:
    """
    # graph = [[5, 9, 1],
    #           [10, 3, 2],
    #           [8, 7, 4]]
    m = Munkres()
    indexes = m.compute(graph)  # idexes 返回的是连线的列表（元祖）
    print(indexes)

    total = 0
    for row, column in indexes:
        value = graph[row][column]
        total += value
    print('最小成本%r:'%total)


def profit():
    """
    计算利润的函数（路径最大化）
    其实利用一个取相反数转化为成本的形式再计算的，得到对应的线最后再从原本的矩阵中取值。也可以使用大数-原权值的方法
    :return:
    """
    graph = [[5, 9, 1],
             [10, 3, 2],
             [8, 7, 4]]
    cost_graph = []
    for row in graph:
        cost_row = []
        for col in row:
            cost_row += [- col]  # 这里课改为 大数-col 的形式
        cost_graph += [cost_row]

    m = Munkres()
    indexes = m.compute(cost_graph)
 
    total = 0
    for row, column in indexes:
        value = graph[row][column]
        total += value
    print('最大利润%r:'%total)
内部逻辑完整实现

按照对算法的理解和部分资料的改编结合。按照左边的男生和右边的女生为二分图匹配案例设计，故代码中的left和boy是相等概念，right和girl是相等概念。

"""
@author:HY
@time:2020/12/3:19:15
"""
import numpy as np
from munkres import Munkres, print_matrix
import sys


class KM_Algorithm_1:
    """
    此类是一个对KM算法的成功实现。
    本需求中不可直接使用，因为订单与车辆之间可能不能匹配的边以及订单会匹配失败的可能性
    """

    def __init__(self, Bipartite_Graph):
        self.Bipartite_Graph = Bipartite_Graph


        # 左右结点数量记录  
        self.left = self.Bipartite_Graph.shape[0]  # 以左边为主
        self.right = self.Bipartite_Graph.shape[1]

        # 初始化顶标
        self.label_left = np.max(self.Bipartite_Graph, axis=1)  # 设置左边顶标为权重最大值（每行的最大值）
        self.label_right = np.zeros(self.right)  # 右边集合的顶标设置为0

        # 初始化辅助变量——是否已匹配
        self.visit_left = np.zeros(self.left, dtype=bool)
        self.visit_right = np.zeros(self.right, dtype=bool)

        # 初始化右边的匹配结果.如果已匹配就会对应匹配结果
        self.match_right = np.empty(self.left) * np.nan

        # 用inc记录需要减去的权值d，不断取最小值故初始化为较大值。
        self.inc = 9999

    def match(self, boy):
        boy = int(boy)
        # 记录下这个boy已经被寻找
        self.visit_left[boy] = True
        for girl in range(self.right):
            # 如果这个女生还没匹配
            if not self.visit_right[girl]:
                gap = self.label_left[boy] + self.label_right[girl] - self.Bipartite_Graph[boy][girl]
                if gap == 0:   # # 差值为0，是可行的替换。所以可以直接尝试替换。后面不行再说。这个列表是记录希望匹配的
                    self.visit_right[girl] = True

                    # 女生未被匹配，或虽然已被匹配，但是已匹配对象(男生)有其他可选备胎
                    if np.isnan(self.match_right[girl]) or self.match(self.match_right[girl]):
                        self.match_right[girl] = boy
                        # 递归匹配，匹配成功
                        return 1

                # 找到权值最小的差距
                elif self.inc > gap:
                    self.inc = gap
        return 0

    def Kuh_Munkras(self):

        self.match_right = np.empty(self.left) * np.nan

        # find the perfect match
        for man in range(self.left):
            while True:
                self.inc = 9999  # 初始化最小距离为一个很大的值
                self.reset()  # 每次寻找过的路径，所有要重置一下

                # 可找到可行匹配
                if self.match(man):
                    break

                # 不能找到可行匹配
                # (1)将所有在增广路中的boy方点的label全部减去最小常数
                # (2)将所有在增广路中的girl方点的label全部加上最小常数
                for k in range(self.left):
                    if self.visit_left[k]:
                        self.label_left[k] -= self.inc
                for n in range(self.right):
                    if self.visit_right[n]:
                        self.label_right[n] += self.inc

    def calculateSum(self):
        sum = 0
        for i in range(self.left):
            sum += self.Bipartite_Graph[int(self.match_right[i])][i]
        return sum

    def getResult(self):
        return self.match_right


    def reset(self):
        # variable for record path
        self.visit_left = np.zeros(self.left, dtype=bool)
        self.visit_right = np.zeros(self.right, dtype=bool)


def change_cost(matrix):
    """
    与上面的类搭配使用计算成本
    :param matrix:
    :return:
    """

    cost_matrix = []
    for row in matrix:
        cost_row = []
        for col in row:
            cost_row += [- col]
        cost_matrix += [cost_row]

    km = KM_Algorithm_1(Bipartite_Graph=np.array(cost_matrix))

    km.Kuh_Munkras()
    km.Bipartite_Graph = - km.Bipartite_Graph

    print('最小权值:')
    print(km.Bipartite_Graph)
    print(km.calculateSum())


def test1():
    """
    测试最大匹配
    :return:
    """
    n = input("输入行列数n:")  # 输入二维数组的行数和列数
    if n == '':
        print("使用默认矩阵启动")
        graph = [[5, 9, 1], [10, 3, 2], [8, 7, 4]]
        km = KM_Algorithm_1(Bipartite_Graph=np.array(graph))
    else:
        n = int(n)
        graph = [[0] * n] * n  # 初始化二维数组
        print("输入一个n*n的二维数组，同一行的数字使用空格分隔，不同行的数字用回车换行:")
        for i in range(n):
            graph[i] = input().split(" ")
            graph[i] = [int(j) for j in graph[i]]
        print(graph)  # 打印二维数组
        km = KM_Algorithm_1(Bipartite_Graph=np.array(graph))


    km.Kuh_Munkras()
    print('最大权值:')
    print(km.Bipartite_Graph)
    print(km.calculateSum())


def test2():
    """
    测试最小匹配
    :return:
    """
    graph = [[5, 9, 1], [10, 3, 2], [8, 7, 4]]
    # graph = [[1, 2, 1000000, 1000000, 1000000], 
    #          [1, 1, 1000000, 1000000, 1000000], 
    #          [3, 3, 1000000, 1000000, 1000000], 
    #          [5, 0, 1000000, 1000000, 1000000]]
    change_cost(graph)


if __name__ == '__main__':
    test1()

3.订单匹配与KM算法结合

不同点：

  1. 与KM算法不同，仿真系统选择权值最优的情况匹配，允许request接单失败，taxi也可以不接客，即不是完备匹配。
  2. 当在一个较大的空间范围内收集request的时候，收集到的对应的taxies很多，在他们形成的二分图中，每个订单只与某几辆车存在连接关系，而与大部分taxi不存在连接关系。
  3. 以下两个匹配目标存在冲突，需要清晰自己的目标：
    • 尽可能使更多request可以获得响应（类似最优匹配，但仅尽可能完备）
    • 尽可能使得权值最优（带权匹配）

我的实现：

"""
@author:HY
@time:2020/12/6:21:35
"""

import numpy as np

class KM_Algorithm_4:
    """
    这个版本是将权值变成订单除以时间，这样就是求最大匹配了，但需要注意的是，时间可能为0此时不能相除，需要另外处理
    """

    def __init__(self, Bipartite_Graph):

        self.Bipartite_Graph = Bipartite_Graph

        # 左右结点数量记录
        self.left = self.Bipartite_Graph.shape[0]  # 以左边为主
        # print(self.Bipartite_Graph)
        self.right_true = self.Bipartite_Graph.shape[1]
        self.right = self.Bipartite_Graph.shape[1] + self.left

        self.reshape_graph()

        # 初始化顶标
        self.label_left = np.max(self.Bipartite_Graph, axis=1)  # 设置左边顶标为权重最大值（每行的最大值）

        self.label_right = np.zeros(self.right)  # 右边集合的顶标设置为0

        # 初始化辅助变量——是否已匹配
        self.visit_left = np.zeros(self.left, dtype=bool)
        self.visit_right = np.zeros(self.right, dtype=bool)

        # 初始化右边的匹配结果.如果已匹配就会对应匹配结果
        self.match_right = np.empty(self.right) * np.nan

        # 用inc记录需要减去的权值d，不断取最小值故初始化为较大值。权值都为负数，应该不用很大也行
        self.inc = 1000*1000*1000

        self.fail_boy = list()  # 每次匹配重新创建一个二分图匹配对象，所以这个也不用手动重置了

    def reshape_graph(self):
        new = np.ones((self.left, self.left)) * 0
        self.Bipartite_Graph = np.column_stack((self.Bipartite_Graph, new))
        print(self.Bipartite_Graph)

    def match(self, boy):
        print("---------------我是boy%d----------------------" % boy)
        boy = int(boy)
        # 记录下这个boy已经被寻找
        self.visit_left[boy] = True
        for girl in range(self.right):
            # 如果这个女生还没访问过
            if not self.visit_right[girl] and self.Bipartite_Graph[boy][girl] >= 0:  # 女孩仍未匹配并且男女之间存在匹配的可能性(不可匹配的点设置为负数，取反后变正数,故正数不可取)
                gap = self.label_left[boy] + self.label_right[girl] - self.Bipartite_Graph[boy][girl]  # gap也不会取到不能匹配的那条边
                if gap == 0:   # 差值为0，是可行的替换。所以可以直接尝试替换。后面不行再去将这个一起减去gap。这个列表是记录希望匹配的
                    self.visit_right[girl] = True
                    # 女生未被匹配，或虽然已被匹配，但是已匹配对象(男生)有其他可选备胎。这里那些是否已访问的列表不需要重置，因为不改变前面的尝试匹配
                    if np.isnan(self.match_right[girl]) or self.match(self.match_right[girl]):
                        self.match_right[girl] = boy
                        # print(self.match_right)
                        # 递归匹配，匹配成功
                        return 1

                # 找到权值最小的差距
                elif self.inc > gap:
                    self.inc = gap  # 等于0的gap不会存在这，所以只要存在可能匹配的情况，gap就不会等于原来的inc

        return 0

    def Kuh_Munkras(self):

        self.match_right = np.empty(self.right) * np.nan
        # 寻找最优匹配
        for man in range(self.left):
            while True:
                self.inc = 1000*1000  # the minimum gap
                self.reset()  # 每次寻找过的路径，所有要重置一下

                # 可找到可行匹配
                if self.match(man):
                    break
                # 不能找到可行匹配
                # (1)将所有在增广路中的boy方点的label全部减去最小常数
                # (2)将所有在增广路中的girl方点的label全部加上最小常数
                for k in range(self.left):
                    if self.visit_left[k]:
                        self.label_left[k] -= self.inc
                for n in range(self.right):
                    if self.visit_right[n]:
                        self.label_right[n] += self.inc

        return self.fail_boy

    def calculateSum(self):
        sum = 0
        boys_girls = []
        self.fail_boy = [i for i in range(self.left)]
        for i in range(self.right_true):
            if not np.isnan(self.match_right[i]):
                sum += self.Bipartite_Graph[int(self.match_right[i])][i]
                boy_girl = (int(self.match_right[i]), i)
                boys_girls.append(boy_girl)
                self.fail_boy.remove(int(self.match_right[i]))
        print("最短路径：", sum)

        return boys_girls, self.fail_boy

    def getResult(self):
        return self.match_right

    def reset(self):
        self.visit_left = np.zeros(self.left, dtype=bool)
        self.visit_right = np.zeros(self.right, dtype=bool)


def test3():
    # graph = [[-1, 2],
    #          [-3, 2],
    #          [5, 5],
    #          [10, 0]]
    # graph = [[-10, 1], [0, 10], [5,15]]

    graph = [[-1, -1, -1, 9, -1],
            [4, -1, 4, -1, 4],
            [-1, -1, -1, 6, -1],
            [-1, -1, -1, 6, -1],
            [-1, 5, -1, -1, -1],
            [-1, -1, -1, 11, -1]]
    # graph = [[-1,-1,-1, 9.49, -1, 0,0, 0, 0, 0, 0, ],
    #          [ 4.50, -1, 4.72, -1, 4.70, 0,0, 0, 0, 0, 0, ],
    #          [-1,-1,-1, 6.66, -1, 0, 0, 0, 0, 0, 0,],
    #          [-1,-1,-1, 6.22, -1, 0,0, 0, 0, 0, 0, ],
    #          [-1, 5.99, -1,-1,-1, 0,0, 0, 0, 0, 0,],
    #          [-1,-1,-1,11.67, -1, 0,0, 0, 0, 0, 0,]]
    print(graph)
    km = KM_Algorithm_4(np.array(graph))

    km.Kuh_Munkras()  # 匹配
    # 4. 结果

    boys_girls, fail_boys = km.calculateSum()  # 匹配结果元组,以及失败的男孩们

    print("匹配男女列表", boys_girls)
    print("失败男孩列表", fail_boys)


if __name__ == '__main__':
    test3()

[未完全测试，存在bug]

[未完待续]

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

使用Python实现二分图的KM算法在出租车订单匹配上的应用 的相关文章

  • Python中的列表（清晰易懂）

    列表是用来存放数据的 Python中的列表关键字是list 我们来定义一个列表 lista 61 34 a 34 34 b 34 34 c 34 666 34 a 34 可以看到列表lista中 有字符型数据 34 a 34 34 b 34

  • VR技术类毕业论文文献有哪些？

    本文是为大家整理的VR技术主题相关的10篇毕业论文文献 xff0c 包括5篇期刊论文和5篇学位论文 xff0c 为VR技术选题相关人员撰写毕业论文提供参考 1 期刊论文 运动炫科技 智慧赢未来 VR技术在体育领域内的应用与展望 期刊 xff

  • Haar特征类有哪些最新发表的毕业论文呢？

    一 总体简介 Haar特征的相关文献在2006年到2020年内共计132篇 xff0c 主要集中在自动化技术 计算机技术 无线电电子学 电信技术 公路运输 等领域 xff0c 其中期刊论文100篇 会议论文4篇 专利文献28篇 xff1b

  • 查阅国外文献的网站有哪些？

    毕业季不知道小伙伴们有没有为了论文感到头秃 xff0c 参考文献在我们的论文中有着举足轻重的作用 xff0c 每年这个时候都有大批小伙伴为这个寻找参考文献发愁 有些专业的小伙伴由于专业的特殊性很多需要的文献还是外文文献 xff0c 对他们来

  • 使用Python和C++的写数据结构和算法

    使用Python和C 43 43 的写数据结构和算法 1 数据结构和算法简介2 数据结构2 1 堆栈2 2 队列2 3 散列表2 4 二叉树2 5 线性搜索2 6 二进制搜索2 7 递归2 8 递归二进制搜索2 9 QuickSort2 1

  • Hive与Hbase的区别与联系

    一 概念 1 xff0c Hive hive是基于Hadoop的一个数据仓库工具 xff0c 用来进行数据提取 转化 加载 xff0c 这是一种可以存储 查询和分析存储在Hadoop中的大规模数据的机制 hive数据仓库工具能将结构化的数据

  • ros 命名空间

    文章目录 全局命名空间相对名称私有名称节点命名空间 全局命名空间 rosout前面的反斜杠 表明该节点名称属于全局命名空间 之所以叫做全局名称因为它们在任何地方 xff08 包括代码 命令行工具 图形界面工具等的任何地方 xff09 都可以

  • DenseNet及torchvision中的实现

    ResNets Highway Networks Stochastic depth DenseNet他们的共同的特点是 They create short paths from early layers to later layers 他们

  • Xmanager5用Xstart连接CentOS7

    今天安装了Xmanager5 xff0c 原本已经有了Xshell5 xff0c 没有冲突 xff0c 测试Xftp Xshell使用上均无问题 到了Xstart却出错了 xff0c 客户端设置完后点击运行 xff0c 出现报错 查找了许多

  • CAN总线入门学习（一）

    今天带着大家学习 xff0c CAN总线 1 概要 本资料是面向 CAN 总线初学者的 CAN 入门 对 CAN 是什么 CAN 的特征 标准规格下的位置分布等 CAN 的概要及 CAN 的协议进行了说明 2 使用注意事项 本资料对博世 B

  • java调用接口

    long dateStr 61 System currentTimeMillis 1000 String url 61 34 34 创建参数 JSONObject jsonObject 61 new JSONObject jsonObjec

  • 英特尔NUC 11板载USB3.0座子接口定义

    规格书没有座子PIN定义 xff0c 于是我找技术支持提供了定义

  • 宝塔配置Workerman

    map span class token variable http upgrade span span class token variable connection upgrade span span class token punct

  • px4飞控和机载电脑通信：机载电脑接收飞控的自定义px4消息

    机载电脑接收飞控的自定义px4消息 mavros功能包能够实现px4飞控和机载电脑之间的实时通信 而对于大部分的消息通信mavros都已经有相应接口可以调用 xff0c 例如 xff1a 位置 期望位置 速度 四元素等消息都可以通过C 43

  • px4飞控和机载电脑通信：飞控接收机载电脑的自定义mavlink消息

    前面一篇讲了机载电脑怎么接受飞控的px4消息 这一篇讲解如何飞控怎么接收从机载电脑传过来的消息 分成两部分 机载电脑发送消息 飞控接收消息 pixhawk版本 pixhawk4 px4版本 1 11 2 ros版本 1 14 10 机载电脑

  • 多无人机通信-路由器实现

    多无人机通信 多无人机之间相互通信是实现编队飞行的基础 而想要实现通信就需要组建网络 在网络之间实现数据信息的互相传输 按结构分成两大类 中心节点网络和无中心节点网络 我们这里所用的路由器就是中心节点网络 所有的数据的传输都要经过中心节点

  • js做文件分片上传

    js做文件分片上传 分片上传视频 xff0c 图片 xff0c 音频 xff0c 转base64 64 Layout 61 null lt DOCTYPE html gt lt html gt lt head gt lt meta name

  • 锐捷交换机基本配置命令

    锐捷交换机基本配置命令 锐捷交换机 xff0c 忘记colsole口的en密码 xff0c 重启交换机 xff0c 立即按ctrl 43 c xff0c 进入bootloader 菜单 xff0c 再按ctrl 43 q xff0c 然后输

  • 驱动设计思想（机制、策略、分离、分层）

    1 机制和策略 1 机制就是提供什么功能 xff0c 策略就是怎么使用这些功能 在编写驱动时需要在编程时间和驱动的灵活性之间取一个可接受的折中 xff0c 驱动提供机制 xff0c 尽量不提供策略 xff0c 策略让上层应用去做 2 机制和

  • debian重启没办法进入图形界面

    在遇到重启有时候没办法进入图形界面的情况下 xff0c 你可以考虑是自己电脑或者服务器显卡的问题 xff0c 如果你进入了命令行的界面 xff0c 执行 etc init d kdm restart 可以重新启动图形界面的话那么就可以肯定时

随机推荐

热门标签