swift - 如何优化这个在图中找到所有最大匹配的算法？

Question

在我的应用程序中，人们互相打分，满分 10 分。每天，算法都会为尽可能多的人计算匹配(不可能为所有人计算匹配)。它制作了一个图，其中顶点是用户，边是成绩

我将问题简化为如果 2 个人互相给对方打分，则他们之间的优势是各自平均成绩的权重。但是，如果 A 给 B 打了分，而 B 没有打分，那么他们之间就没有边了，他们永远无法匹配:这样，图就不再有方向了

我希望平均每个人都快乐，但与此同时，我希望尽可能少的人不匹配。

由于非常确定，我做了一个算法来找到图中的所有最大匹配。我这样做是因为我认为我可以分析所有这些最大匹配并应用一个看起来像这样的值函数:

V(Matching) = exp(|M| / max(|M|)) * sum(weight of all Edge in M)

也就是说，如果一个匹配的基数接近于最大匹配的基数，并且人与人之间的等级之和很高，那么这个匹配就是高值(value)的。我对比率 |M|/max|M| 设置了一个指数函数因为我认为如果 M 低于 0.8 是个大问题(所以当 |M|/max|M| 达到 0.8 时，exp 将被安排为大大降低 V)

我会选择 V(M) 最大的匹配。不过，最大的问题是我计算所有最大匹配的函数需要花费大量时间。只有 15 个顶点和 20 个边，它需要将近 10 分钟......这是算法(在 Swift 中):

import Foundation

struct Edge : CustomStringConvertible {
    var description: String {
        return "e(\(v1), \(v2))"
    }

    let v1:Int
    let v2:Int
    let w:Int?

    init(_ arrint:[Int])
    {
        v1 = arrint[0]
        v2 = arrint[1]
        w = nil
    }
    init(_ v1:Int, _ v2:Int)
    {
        self.v1 = v1
        self.v2 = v2
        w = nil
    }
    init(_ v1:Int, _ v2:Int, _ w:Int)
    {
        self.v1 = v1
        self.v2 = v2
        self.w  = w
    }
}


let mygraph:[Edge] =
[
    Edge([1, 2]),
    Edge([1, 5]),
    Edge([2, 5]),
    Edge([2, 3]),
    Edge([3, 4]),
    Edge([3, 6]),
    Edge([5, 6]),

    Edge([2,6]),
    Edge([4,1]),
    Edge([3,5]),
    Edge([4,2]),
    Edge([7,1]),
    Edge([7,2]),

    Edge([8,1]),
    Edge([9,8]),
    Edge([11,2]),
    Edge([11, 8]),
    Edge([12,13]),
    Edge([1,6]),
    Edge([4,7]),
    Edge([5,7]),
    Edge([3,5]),
    Edge([9,1]),
    Edge([10,11]),
    Edge([10,4]),
    Edge([10,2]),
    Edge([10,1]),
    Edge([10, 12]),


]

// remove all the edge and vertex "touching" the edges and vertex in "edgePath"
func reduce (graph:[Edge], edgePath:[Edge]) -> [Edge]
{

    var alreadyUsedV:[Int] = []

    for edge in edgePath
    {
        alreadyUsedV.append(edge.v1)
        alreadyUsedV.append(edge.v2)
    }


    return graph.filter({ edge in
        return alreadyUsedV.first(where:{ edge.v1 == $0 }) == nil && alreadyUsedV.first(where:{ edge.v2 == $0 }) == nil
    })

}


func findAllMaximalMatching(graph Gi:[Edge]) -> [[Edge]]
{

    var matchings:[[Edge]] = []

    var G = Gi // current graph (reduced at each depth)
    var M:[Edge] = [] // current matching being built
    var Cx:[Int] = [] // current path in the possibilities tree 
                      // eg : Cx[1] = 3 : for the depth 1, we are at the 3th edge 
    var d:Int = 0 // current depth

    var debug_it = 0


    while(true)
    {

        if(G.count == 0) // if there is no available edge in graph, it means we have a matching
        {
            if(M.count > 0) // security, if initial Graph is empty we cannot return an empty matching
            {
                matchings.append(M)
            }

            if(d == 0)
            {
                // depth = 0, we cannot decrement d, we have finished all the tree possibilities
                break
            }
            d = d - 1

            _ = M.popLast()
            G = reduce(graph: Gi, edgePath: M)

        }

        else
        {
            let indexForThisDepth = Cx.count > d ? Cx[d] + 1 : 0
            if(G.count < indexForThisDepth + 1)
            {
                // depth ended,

                _ = Cx.popLast()

                if( d == 0)
                {
                    break
                }

                d = d - 1
                _ = M.popLast()

                // reduce from initial graph to the decremented depth
                G = reduce(graph: Gi, edgePath: M)

            }
            else
            {
                // matching not finished to be built
                M.append( G[indexForThisDepth] )

                if(indexForThisDepth == 0)
                {
                    Cx.append(indexForThisDepth)
                }
                else
                {
                    Cx[d] = indexForThisDepth
                }

                d = d + 1
                G = reduce(graph: G, edgePath: M)
            }
        }

        debug_it += 1
    }


    print("matching counts : \(matchings.count)")
    print("iterations : \(debug_it)")

    return matchings

}


let m = findAllMaximalMatching(graph: mygraph)

// we have compute all the maximal matching, now we loop through all of them to find the one that has V(Mi) maximum
// ....

最后我的问题是:如何优化此算法以找到所有最大匹配并计算它们的值函数以在多项式时间内为我的应用找到最佳匹配？

Answer 1

我可能遗漏了一些东西，因为这个问题很复杂，但为什么不简单地使用 maximum flow problem ，每个顶点出现两次并且边缘权重是平均等级(如果存在)？如果配置正确并运行多项式时间，它将返回最大流量。