买专利卖专利找龙图腾，真高效！ 查专利查商标用IPTOP,全免费！专利年费监控用IP管家,真方便！

龙图腾网恭喜大连理工大学申请的专利非对称问题拍卖算法的GPU实现方法获国家发明授权专利权，本发明授权专利权由国家知识产权局授予，授权公告号为：CN114996521B 。

龙图腾网通过国家知识产权局官网在2025-04-08发布的发明授权授权公告中获悉：该发明授权的专利申请号/专利号为：202210485454.7，技术领域涉及：G06F16/901；该发明授权非对称问题拍卖算法的GPU实现方法是由刘崇威;李豪杰;王智慧设计研发完成，并于2022-05-06向国家知识产权局提交的专利申请。

本非对称问题拍卖算法的GPU实现方法在说明书摘要公布了：本发明属于计算机技术领域，提供了一种非对称问题拍卖算法的GPU实现方法。拍卖算法是求解线性分配问题的经典算法，本发明提供一种非对称问题拍卖算法在GPU上的实现方法。本发明将拍卖算法分成两个步骤：竞价和分配。在竞价步骤中，使用GPU同时对不同行进行并行处理来求解每一行各自的最大值、第二大值、和最大值的索引；在分配步骤中，使用GPU同时对不同列进行并行处理来求解每一列各自的最大值和最大值的索引。本发明首先判断输入的成本矩阵是否需要转置，之后通过循环迭代竞价和分配步骤来实现GPU上的非对称问题拍卖算法。

本发明授权非对称问题拍卖算法的GPU实现方法在权利要求书中公布了：1.一种非对称问题拍卖算法的GPU实现方法，其特征在于，所述的方法包括步骤：1建立非对称问题拍卖算法的GPU实现方法；具体来讲，输入N×M的成本矩阵C1，如果N大于M，则对这个矩阵进行转置操作，此时将N与M的值互换，C1仍为N×M大小的矩阵，否则维持原状；初始化一个N+1×M的竞价矩阵B1；一个人物分配表person2item1，包含N个元素，每个元素均初始化为-1；一个物人分配表item2person1，包含M个元素，每个元素均初始化为-1；一个价格表prices1，包含M个元素，每个元素均初始化为0；然后做如下循环操作：竞价矩阵B1中所有元素均设为0；执行竞价步骤后，竞价矩阵B1得到更新；执行分配步骤后，person2item1、prices1和item2person1得到更新；在每次循环开始前判断person2item1中-1元素的个数，如果个数不为0则开始循环，否则结束循环；如果成本矩阵C1执行过转置操作，则最终结果为item2person1，否则为person2item1；2建立竞价步骤；输入一个N×M的成本矩阵C2，C2中所有元素均大于等于0；一个N+1×M的竞价矩阵B2，B2中所有元素均为0；一个人物分配表person2item2，包含N个元素，每个元素均为大于-2且小于M的整数；一个价格表prices2，包含M个元素，每个元素均不为负数；GPU并行地计算出成本矩阵C2中的person2item2中数值为-1的索引所表示的行的最大值x2、第二大值y2、以及最大值x2在成本矩阵C2中的索引[n2，m2]，n2为当前行索引，m2大于等于0且小于M；之后GPU并行地对B2进行如下更新：B2[n2][m2]＝x2–y2+1N；B2[N][m2]＝1；在计算某一行即行索引已知且为n2的M个元素中的x2，y2，[n2，m2]时，GPU首先生成一个M×3个元素的新数列t2并进行如下初始化：t2[i2×3]＝C2[n2][i2]–prices2[i2]；t2[i2×3+1]＝0；t2[i2×3+2]＝i2；其中，i2大于等于0且小于M；t2[i2×3]、t2[i2×3+1]和t2[i2×3+2]构成一组基本单位，基本单位的索引值为i2，三者分别表示单位内最大值、单位内第二大值、单位内最大值在成本矩阵C2中的列索引；初始化完成之后，计算小于M的2的幂中的最大值f2，对于索引值大于等于f2的单位，如果t2[i2×3]大于等于t2[i2–f2×3]，则依次计算：t2[i2–f2×3+1]＝t2[i2–f2×3]；t2[i2–f2×3]＝t2[i2×3]；t2[i2–f2×3+2]＝t2[i2×3+2]；否则计算：t2[i2–f2×3+1]＝t2[i2×3]；之后在数列t2前f2×3个元素的基础上进行规约操作，即令j2为f22，对于索引值小于j2的单位，如果t2[i2×3]小于等于t2[i2+j2×3]，则依次计算：t2[i2×3+1]＝maxt2[i2×3],t2[i2+j2×3+1]；t2[i2×3]＝t2[i2+j2×3]；t2[i2×3+2]＝t2[i2+j2×3+2]；否则当t2[i2×3+1]小于t2[i2+j2×3]时计算：t2[i2×3+1]＝t2[i2+j2×3]；之后令j2为j22继续执行上述操作直到j2为0为止，则t2[0],t2[1],t2[2]即为所求x2，y2，m2；3建立分配步骤；输入一个N+1×M的竞价矩阵B3，B3中所有元素均不为负数；一个人物分配表person2item3，包含N个元素，每个元素均为大于-2且小于M的整数；一个物人分配表item2person3，包含M个元素，每个元素均为大于-2且小于N的整数；一个价格表prices3，包含M个元素，每个元素均不为负数；GPU并行地计算出竞价矩阵B3中的最后一行中数值为1的列索引的最大值x3、以及最大值x3在竞价矩阵B3中的索引[n3，m3]，n3大于等于0且小于N，m3为当前列索引；之后GPU并行地对person2item3，prices3，和item2person3进行如下更新：person3＝item2person3[m3]；ifperson3＝0person2item3[person3]＝-1；prices3[m3]+＝x3；person2item3[n3]＝m3；item2person3[m3]＝n3；在计算某一列即列索引已知且为m3的前N个元素中的x3，[n3，m3]时，GPU首先生成一个N×2个元素的新数列t3并进行如下初始化：t3[i3×2]＝B3[i3][m3]；t3[i3×2+1]＝i3；其中，i3大于等于0且小于N；t3[i3×2]和t3[i3×2+1]构成一组基本单位，基本单位的索引值为i3，二者分别表示单位内最大值和单位内最大值在矩阵B3中的行索引；初始化完成之后，计算小于N的2的幂中的最大值f3，对于索引值大于等于f3的单位，如果t3[i3×2]大于t3[i3–f3×2]，则计算：t3[i3–f3×2]＝t3[i3×2]；t3[i3–f3×2+1]＝t3[i3×2+1]；之后在数列t3前f3×2个元素的基础上进行规约操作，即令j3为f32，对于索引值小于j3的单位，如果t3[i3×2]小于等于t3[i3+j3×2]，则计算：t3[i3×3]＝t3[i3+j3×3]；t3[i3×3+1]＝t3[i3+j3×3+1]；之后令j3为j32继续执行上述操作直到j3为0为止，则t3[0]和t3[1]即为所求x3和n3。

如需购买、转让、实施、许可或投资类似专利技术，可联系本专利的申请人或专利权人大连理工大学，其通讯地址为：116024 辽宁省大连市甘井子区凌工路2号；或者联系龙图腾网官方客服，联系龙图腾网可拨打电话0551-65771310或微信搜索“龙图腾网”。