如何优化图形的递归函数以进行清算和结算

Question

我必须在一个保险应用程序中创建一个模块，处理系统中注册的保险公司之间的结算和结算(我认为这是正确的金融术语)。实际上，系统必须将公司必须相互支付的所有金额配对，只有未配对的(剩余)金额通过银行支付。目前，该系统中约有30家公司。

我所做的关于清算和结算的所有阅读都将我引向了图形和图形理论(我很久以前在高中就学习过了)。对于包含4家公司的系统，图表将如下所示：

​

​

其中每个公司代表一个节点(N1 ...(N4:行情)，每个加权边代表一家公司必须向另一家支付的金额.在我的代码中，节点是int，代表公司的id。

到目前为止我所做的..。我创建了这个图(为了测试，我使用了随机生成器来表示数量)，并创建了一个递归函数来计算图中所有可能的循环。然后我做了另一个递归函数，它将所有非零循环从具有最大公共和的最长路径开始配对。就最终结果而言，该算法似乎是有效的，但对于大于7-8个节点的图，它需要太长时间才能完成。问题出在创建图中可能循环的递归函数中。下面是我的代码：

static void Main(string[] args)
{
    int nodes = 4;
    try
    {
        nodes = Convert.ToInt32(args[0]);
    }
    catch { }

    DateTime start = DateTime.Now;
    Graph g = new Graph(nodes);

    int step = 0;
    double CompensatedAmount = 0;
    double TotalCompensatedAmount = 0;

    DateTime endGeneration = DateTime.Now;
    Console.WriteLine("Graph generated in: " + (endGeneration - start).TotalSeconds + " seconds.");

    Compensare.RunCompensation(false, g, step, CompensatedAmount, TotalCompensatedAmount, out CompensatedAmount, out TotalCompensatedAmount);

    DateTime endCompensation = DateTime.Now;

    Console.WriteLine("Graph compensated in: " + (endCompensation - endGeneration).TotalSeconds + " seconds.");
}

..。和主类：

public static class Compensare
{
    public static void RunCompensation(bool exit, Graph g, int step, double prevCompensatedAmount, double prevTotalCompensatedAmount, out double CompensatedAmount, out double TotalCompensatedAmount)
    {
        step++;
        CompensatedAmount = prevCompensatedAmount;
        TotalCompensatedAmount = prevTotalCompensatedAmount;
        if (!exit)
        {
            List<Cycle> orderedList = g.Cycles.OrderByDescending(x => x.CycleCompensatedAmount).ToList();
            g.ListCycles(orderedList, "OrderedCycles" + step.ToString() + ".txt");
            using (Graph clona = g.Clone())
            {
                int maxCycleIndex = clona.GetMaxCycleByCompensatedAmount();
                double tmpCompensatedAmount = clona.Cycles[maxCycleIndex].CycleMin;
                exit = tmpCompensatedAmount <= 0 ? true : false;
                CompensatedAmount += tmpCompensatedAmount;
                TotalCompensatedAmount += (tmpCompensatedAmount * clona.Cycles[maxCycleIndex].EdgesCount);
                clona.CompensateCycle(maxCycleIndex);
                clona.UpdateCycles();
                Console.WriteLine(String.Format("{0} - edges: {4} - min: {3} - {1} - {2}\r\n", step, CompensatedAmount, TotalCompensatedAmount, tmpCompensatedAmount, clona.Cycles[maxCycleIndex].EdgesCount));
                RunCompensation(exit, clona, step, CompensatedAmount, TotalCompensatedAmount, out CompensatedAmount, out TotalCompensatedAmount);
            }
        }
    }
}

public class Edge
{
    public int Start { get; set; }
    public int End { get; set; }
    public double Weight { get; set; }
    public double InitialWeight {get;set;}

    public Edge() { }

    public Edge(int _start, int _end, double _weight)
    {
        this.Start = _start;
        this.End = _end;
        this.Weight = _weight;
        this.InitialWeight = _weight;
    }
}

public class Cycle
{
    public List<Edge> Edges = new List<Edge>();
    public double CycleWeight = 0;
    public double CycleMin = 0;
    public double CycleMax = 0;
    public double CycleAverage = 0;
    public double CycleCompensatedAmount = 0;
    public int EdgesCount = 0;

    public Cycle() { }

    public Cycle(List<Edge> _edges)
    {
        this.Edges = new List<Edge>(_edges);
        UpdateCycle();
    }

    public void UpdateCycle()
    {
        UpdateCycle(this);
    }

    public void UpdateCycle(Cycle c)
    {
        double sum = 0;
        double min = c.Edges[0].Weight;
        double max = c.Edges[0].Weight;
        for(int i=0;i<c.Edges.Count;i++)
        {
            sum += c.Edges[i].Weight;
            min = c.Edges[i].Weight < min ? c.Edges[i].Weight : min;
            max = c.Edges[i].Weight > max ? c.Edges[i].Weight : max;
        }
        c.EdgesCount = c.Edges.Count;
        c.CycleWeight = sum;
        c.CycleMin = min;
        c.CycleMax = max;
        c.CycleAverage = sum / c.EdgesCount;
        c.CycleCompensatedAmount = min * c.EdgesCount;
    }
}

public class Graph : IDisposable
{
    public List<int> Nodes = new List<int>();
    public List<Edge> Edges = new List<Edge>();
    public List<Cycle> Cycles = new List<Cycle>();
    public int NodesCount { get; set; }

    public Graph() { }

    public Graph(int _nodes)
    {
        this.NodesCount = _nodes;

        GenerateNodes();

        GenerateEdges();

        GenerateCycles();
    }

    private int FindNode(string _node)
    {
        for(int i = 0; i < this.Nodes.Count; i++)
        {
            if (this.Nodes[i].ToString() == _node)
                return i;
        }
        return 0;
    }

    private int FindEdge(string[] _edge)
    {
        for(int i = 0; i < this.Edges.Count; i++)
        {
            if (this.Edges[i].Start.ToString() == _edge[0] && this.Edges[i].End.ToString() == _edge[1] && Convert.ToDouble(this.Edges[i].Weight) == Convert.ToDouble(_edge[2]))
                return i;
        }
        return 0;
    }

    public Graph Clone()
    {
        Graph clona = new Graph();
        clona.Nodes = new List<int>(this.Nodes);
        clona.Edges = new List<Edge>(this.Edges);
        clona.Cycles = new List<Cycle>(this.Cycles);
        clona.NodesCount = this.NodesCount;
        return clona;
    }

    public void CompensateCycle(int cycleIndex)
    {
        for(int i = 0; i < this.Cycles[cycleIndex].Edges.Count; i++)
        {
            this.Cycles[cycleIndex].Edges[i].Weight -= this.Cycles[cycleIndex].CycleMin;
        }
    }

    public int GetMaxCycleByCompensatedAmount()
    {
        int toReturn = 0;
        for (int i = 0; i < this.Cycles.Count; i++)
        {
            if (this.Cycles[i].CycleCompensatedAmount > this.Cycles[toReturn].CycleCompensatedAmount)
            {
                toReturn = i;
            }
        }
        return toReturn;
    }

    public void GenerateNodes()
    {
        for (int i = 0; i < this.NodesCount; i++)
        {
            this.Nodes.Add(i + 1);
        }
    }

    public void GenerateEdges()
    {
        Random r = new Random();
        for(int i = 0; i < this.Nodes.Count; i++)
        {
            for(int j = 0; j < this.Nodes.Count; j++)
            {
                if(this.Nodes[i] != this.Nodes[j])
                {
                    int _weight = r.Next(0, 500);
                    Edge e = new Edge(this.Nodes[i], this.Nodes[j], _weight);
                    this.Edges.Add(e);
                }
            }
        }
    }

    public void GenerateCycles()
    {
        for(int i = 0; i < this.Edges.Count; i++)
        {
            FindCycles(new Cycle(new List<Edge>() { this.Edges[i] }));
        }
        this.UpdateCycles();
    }

    public void UpdateCycles()
    {
        for (int i = 0; i < this.Cycles.Count; i++)
        {
            this.Cycles[i].UpdateCycle();
        }
    }

    private void FindCycles(Cycle path)
    {
        List<Edge> nextPossibleEdges = GetNextEdges(path.Edges[path.Edges.Count - 1].End);
        for (int i = 0; i < nextPossibleEdges.Count; i++)
        {
            if (path.Edges.IndexOf(nextPossibleEdges[i]) < 0) // the edge shouldn't be already in the path
            {
                Cycle temporaryPath = new Cycle(path.Edges);
                temporaryPath.Edges.Add(nextPossibleEdges[i]);

                if (nextPossibleEdges[i].End == temporaryPath.Edges[0].Start) // end of path - valid cycle
                {
                    if (!CycleExists(temporaryPath))
                    {
                        this.Cycles.Add(temporaryPath);
                        break;
                    }
                }
                else
                {
                    FindCycles(temporaryPath);
                }
            }
        }
    }

    private bool CycleExists(Cycle cycle)
    {
        bool toReturn = false;
        if (this.Cycles.IndexOf(cycle) > -1) { toReturn = true; }
        else
        {
            for (int i = 0; i < this.Cycles.Count; i++)
            {
                if (this.Cycles[i].Edges.Count == cycle.Edges.Count && !CompareEdges(this.Cycles[i].Edges[0], cycle.Edges[0]))
                {
                    bool cycleExists = true;
                    for (int j = 0; j < cycle.Edges.Count; j++)
                    {
                        bool edgeExists = false; // if there is an edge not in the path, then the searched cycle is diferent from the current cycle and we can pas to the next iteration
                        for (int k = 0; k < this.Cycles[i].Edges.Count; k++)
                        {
                            if (CompareEdges(cycle.Edges[j], this.Cycles[i].Edges[k]))
                            {
                                edgeExists = true;
                                break;
                            }
                        }
                        if (!edgeExists)
                        {
                            cycleExists = false;
                            break;
                        }
                    }
                    if (cycleExists) // if we found an cycle with all edges equal to the searched cycle, then the cycle is not valid
                    {
                        toReturn = true;
                        break;
                    }
                }
            }
        }
        return toReturn;
    }

    private bool CompareEdges(Edge e1, Edge e2)
    {
        return (e1.Start == e2.Start && e1.End == e2.End && e1.Weight == e2.Weight);
    }

    private List<Edge> GetNextEdges(int endNode)
    {
        List<Edge> tmp = new List<Edge>();
        for(int i = 0; i < this.Edges.Count; i++)
        {
            if(endNode == this.Edges[i].Start)
            {
                tmp.Add(this.Edges[i]);
            }
        }
        return tmp;
    }

    #region IDisposable Support
    private bool disposedValue = false; // To detect redundant calls

    protected virtual void Dispose(bool disposing)
    {
        if (!disposedValue)
        {
            if (disposing)
            {
                // TODO: dispose managed state (managed objects).
                this.Nodes = null;
                this.Edges = null;
                this.Cycles = null;
                this.NodesCount = 0;
            }

            // TODO: free unmanaged resources (unmanaged objects) and override a finalizer below.
            // TODO: set large fields to null.

            disposedValue = true;
        }
    }

    // TODO: override a finalizer only if Dispose(bool disposing) above has code to free unmanaged resources.
    // ~Graph() {
    //   // Do not change this code. Put cleanup code in Dispose(bool disposing) above.
    //   Dispose(false);
    // }

    // This code added to correctly implement the disposable pattern.
    public void Dispose()
    {
        // Do not change this code. Put cleanup code in Dispose(bool disposing) above.
        Dispose(true);
        // TODO: uncomment the following line if the finalizer is overridden above.
        // GC.SuppressFinalize(this);
    }
    #endregion
}

我已经找到了几篇关于图的文章/答案，包括Java和C# (包括quickgraph)，但它们主要关注有向图(没有循环)。我也读过关于递归的尾部调用优化，但我不知道在我的例子中是否/如何实现。

我现在有很多关于这个主题的需要掌握的东西，但也许有人必须处理类似的事情，并且可以帮助我优化代码(正如我所说的，这似乎最终完成了工作)，或者让我转向另一个方向来重新思考整个过程。

Answer 1

所有的钱都是一样的，所以(使用你的例子) N1并不关心它是否从N2获得350，并向N2支付150，以此类推- N1只关心，它最终是145 down (如果我没有做错算术的话)。类似地，每个N只关心它的整体位置。因此，将每个节点的流入和流出相加，我们得到：

Company    Net position
N1         -145
N2         -65
N3         +195
N4         +15

因此，如果有人充当中央票据交换所--银行--只需安排N1和N2分别向票据交换所支付145和65英镑，并让N3和N4分别从票据交换所获得195和15英镑。大家都很开心。

当然，我可能遗漏了某些方面，在这种情况下，我相信有人会指出这一点……