algorithm - 优化交易项目-最小成本最大流量

Question

有n项目， 。我有n项，但有些重复，有些缺失，我需要每项都只有一个。有一个交易表告诉您哪些元素可以与其他元素进行交易。例如:

<表类=“s-表”> <标题> 项目 项目 <正文> 1 2 2 5 4 3

交易表中有无限的贸易项目库存。但每笔交易，您需要支付 1 美元。

现在我们想知道要交易哪些元素，以便最终我们只拥有每个元素一次，并最大限度地减少所需的交易(成本)。如果不可能，那么我们应该检测到它是不可能的。

示例:

，我们有交易表为: 。 我们需要将 2x i1 交易到 i2，将 1x i2 交易到 i3。

使用最大流最小成本算法解决问题。我对时间复杂度并不是特别感兴趣。

如何构建图/流网络？

Answer 1

How do I construct the graph/flow network?

这样的网络需要资源。来源是重复的项目。每个源的输出容量等于备用数量 ( count - 1 )

网络需要接收器。缺少的元素是水槽。每个接收器的输入有一个容量如果 1

交易表提供了其余的链接，每个链接都有无限的容量。

所以，对于你的例子，

应用 Edmonds-Karp 算法来得到答案 https://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm请注意，只有一个源和一个接收器很方便，因此将公共(public)源连接到所有项目源，并将所有项目接收器连接到公共(public)接收器。

如果流入任何汇的计算流量为零，则该问题不可行

总成本是通过内部链接的总计算流量(所有未连接到源或接收器的图链接)

---

仅供引用，这里有一些 C++ 代码，使用上述算法和 PathFinder graph theory library 解决了这个问题。

构造示例:

void generate1()
{
    // initial holding of each item
    cHold::add("1", 3);
    cHold::add("2", 0);
    cHold::add("3", 0);
    cHold::add("4", 1);

    // possible trades
    cTrade::add("2", "1");
    cTrade::add("3", "2");
}

构建图/流网络

void cFlowGraph::make()
{
    // setup flow graph
    gd.g.clear();
    gd.g.directed();

    // setup link capacity storage
    int maxLinkCount = cItem::count() * cItem::count();
    const int infinite = 2e9;
    gd.edgeWeight.resize(maxLinkCount, infinite);

   
    for (cHold *hold : cHold::get())
    {
        if (hold->count() > 1)
        {
            // source
            // create links from holdings with spare items into trading graph
            std::string name = "source_" + hold->name();
            gd.g.add(
                "all_source",
                name);
            int ie = gd.g.add(
                name,
                hold->name());
            gd.edgeWeight[ie] = hold->count() - 1;
        }
        else if (!hold->count())
        {
            // sink
            // create links from trading graph to empty holdings
            int ie = gd.g.add(
                hold->name(),
                "sink_" + hold->name());
            gd.edgeWeight[ie] = 1;
            gd.g.add(
                "sink_" + hold->name(),
                "all_sink");
        }
    }

    // create the trading links
    for (cTrade *trade : cTrade::get())
    {
        gd.g.add(
            trade->giveName(),
            trade->getName());
    }
}

计算通过图表的流量

void cFlowGraph::calculate()
{
    vLinkFlow.clear();
    vLinkFlow.resize(gd.g.edgeCount(), 0);
    gd.startName = "all_source";
    gd.endName = "all_sink";

    //Apply Edmonds-Karp algorithm using Pathfinder method
    flows(
        gd,
        vLinkFlow);

    displayLinks();
}

检查可行性:

bool cFlowGraph::isFeasible()
{
    // check that every flow into an item sink is 1
    // meaning that the missing item was found
    for (auto &link : gd.g.edgeList())
    {
        if (gd.g.userName(link.second).find("sink_") == 0)
            if (flow( link ) != 1)
                return false;
    }
    return true;
}

显示所需交易

void cFlowGraph::displayTrades()
{
    std::cout << "\n";
    for (auto &link : gd.g.edgeList())
    {
        if (isTrade(link))
            std::cout << "trade " << gd.g.userName(link.first)
                      << " - > " << gd.g.userName(link.second)
                      << " times " << flow( link )
                      << "\n";
    }
}

把这些放在一起，输出是

 flow 2 in   all_source -> source_1
 flow 2 in     source_1 -> 1
 flow 2 in            1 -> 2
 flow 1 in            2 -> sink_2
 flow 1 in            2 -> 3
 flow 1 in       sink_2 -> all_sink
 flow 1 in            3 -> sink_3
 flow 1 in       sink_3 -> all_sink

trade 1 - > 2 times 2
trade 2 - > 3 times 1

完整的应用程序代码位于https://github.com/JamesBremner/trader