满足图中的三倍

2020-02-23 algorithm graph tree language-agnostic

我正在解决一个问题,您在M天(2 <= M <= 10 ^ 9)中有N个事件(1 <= N <= 100000)。您正在尝试查找每个事件的最短发生时间。

对于每个事件,您都知道它不可能在Si日之前发生。您还具有由(a,b,x)描述的C三元组(1 <= C <= 10 ^ 5)。事件b必须在a之后至少x天发生。

例:

有4个事件,持续10天。事件1必须在第一天或之后发生。事件2必须在第二天或之后发生。事件3必须在第3天或之后发生。事件4必须在第4天或之后发生。

三元组是(1、2、5); (2,4,2); (3,4,4)。这意味着事件2必须在事件1之后至少5天发生;事件4必须在事件2之后至少2天发生;事件4必须在事件3之后至少4天发生。

解决方案是事件1在第1天发生。事件2在第6天发生;事件3在第3天发生;事件4是在第4天发生的。其背后的原因是事件2是在事件1之后至少五天发生的,因此不可能在事件1 + 5 = 6之前发生。事件4在事件2之后至少两天发生,因此它不可能在第6 + 2 = 8天之前发生。

我的解决方案:

我有使用三元组创建有向图的想法。因此,在上面的示例中,图形如下所示:

1 --5-> 2 --2-> 4

3 --4-> 4

基本上,您会创建一个从首先发生的事件到随后发生的事件的有向边。边缘权重就是它至少必须在之后发生的天数。

我以为我们可以先使用输入数据来创建图形。然后,您只需对第一个事件的所有可能开始日期进行二进制搜索(1到10 ^ 9,大约30)。在这种情况下,第一个事件是事件1。然后,您将遍历图表,查看是否可以开始此日期。如果您遇到过发生日期早于Si日期的事件,那么您将终止此搜索并继续二进制搜索。如果不是因为“事件b必须在a之后至少x天发生”,该解决方案将很容易工作。

有没有人有其他解决方案来解决这个问题,或者如何改变我的方法使其起作用?谢谢!如果您有任何疑问,请告诉我:))

Answers

可以将其映射到文献丰富的简单时态网络 ,例如:

  • Dechter, Rina, Itay Meiri, and Judea Pearl. "Temporal constraint networks." Artificial intelligence 49.1-3 (1991): 61-95.
  • Planken, Léon Robert. "Algorithms for simple temporal reasoning." (2013). 完整的论文

如评论中所示, 所有对的最短路径都可以计算最小网络 (它还会在所有这些事件之间生成新的弧/约束)。如果您的图是稀疏的 ,则Johnson的算法比Floyd-Warshall更好。

如果您不关心完整的最小网络,而仅关心事件的范围 ,则只对全对最短路径距离矩阵的第一列和第一行感兴趣。您可以通过应用Bellman-Ford * 2 * n *次来计算这些值。这些值是root -> ii -> root的距离,其中root是时间0

关于达明(Damien)指出的事情,仅作一些评论(从零开始,似乎令人印象深刻):

  • 我们在一般问题中使用负权重,使得纯Dijkstra不会做
  • 负循环的存在<->不可行/无解/不一致
  • 需要一些顶点,这是时间起源

编辑:上面有一些针对强推论 / 传播的目标,例如在其价值域方面给出严格的界限

如果您只对某个一致的解决方案感兴趣,那么将这些约束发布为线性程序并使用高度优化的实现之一来解决它可能是另一种想法(开源世界:CoinOR clp;也许是Google的阴谋)。基于单纯形的解决方案应该为您提供完整的解决方案(我认为问题完全单模的 )。基于内点的求解器应该更快,但是我不确定您的结果是否将是完整的,而无需额外的交叉 。 (添加一些像min(max(x))这样的虚拟目标可能是一个好主意(类似于makespan))

考虑您的DAG的拓扑类型

对于与图的拓扑排序相对应的列表L,您最后有叶子。 然后在一个顶点之前

L = [..., v, leaves]

您知道从v伸出的边只能到达之后的顶点(这里是leaves )。 这样,您可以通过应用Damien的最大值来计算与v相关的最小权重。

这样做直到L的头部。

拓扑排序为O(V + E)


这是一个带有更有趣图形的插图(从上至下阅读)

    5
   /  \
  4    7
       1 2
       0
       6

拓扑订购为( 4601275

因此,我们将按顺序4,6,0,1,2,7访问4,6,0,1,2,7然后5并且我们访问的任何顶点都已经计算了其所有依存关系。

假设每个顶点k2^k天后都有事件发生。之后的日期称为重量。

例如,顶点4的权重为2^4

假设每个边(i,j)的权重为5*i + j

  • 6加权2^6 = 64
  • 0被加权为max(2^0, 64 + (0*5+6)) = 70
  • 1取max(2^1, 70 + 5) = 75
  • 7需要max(2^7, 75 + 5*7+1, 2^2) = 2^7

需要重点指出的是(此处为7 ),由节点的依赖关系引起的最小日期可能发生在附加到该节点的日期之前。 (而且我们必须保留最大的)

function topologicalSort({ V, E }) {
  const visited = new Set ()
  const stack = []
  function dfs (v) {
    if (visited.has(v)) { return }
    E.has(v) && E.get(v).forEach(({ to, w }) => dfs(to))
    visited.add(v)
    stack.push(v)
  }
  // process nodes without incoming edges first
  const heads = new Set ([...V])
  for (const v of V) {
    const edges = E.get(v)
    edges && edges.forEach(({ to }) => heads.delete(to))
  }
  for (const v of heads) {
    dfs(v)
  }
  for (const v of V) {
    dfs(v)
  }
  return stack
}
class G {
  constructor () {
    this.V = new Set()
    this.E = new Map()
  }

  setEdges (from, tos) {
    this.V.add(from)
    tos.forEach(({ to, w }) => this.V.add(to))
    this.E.set(from, tos)
  }
}
function solve ({ g, vToWeight }) {
  const stack = topologicalSort(g)
  console.log('ordering', stack.join(''))
  stack.forEach(v => {
    const edges = g.E.get(v)
    if (!edges) { return }
    const newval = Math.max(
      vToWeight.get(v),
      ...edges.map(({ to, w }) => vToWeight.get(to) + w)
    )
    console.log('setting best for', v, edges.map(({ to, w }) =>  [vToWeight.get(to), w].join('+') ))
    vToWeight.set(v, newval)
  })
  return vToWeight
}
function demo () {
  const g = new G ()
  g.setEdges(2, [{ to: 1, w: 5 }])
  g.setEdges(4, [{ to: 2, w: 2 }, { to: 3, w: 4 }])
  const vToWeight = new Map ([
    [1, 1],
    [2, 6],
    [3, 3],
    [4, 4]
  ]) 
  return { g, vToWeight }
}
function demo2 () {
  const g = new G ()
  const addEdges = (i, ...tos) => {
    g.setEdges(i, tos.map(to => ({ to, w: 5 * i + to })))
  }
  addEdges(5,4,7)
  addEdges(7,1,2)
  addEdges(1,0)
  addEdges(0,6)
  const vToWeight = new Map ([...g.V].map(v => [v, 2**v])) 
  return { g, vToWeight }
}
function dump (map) {
  return [...map].map(([k, v])=> k+'->'+v)
}
console.log('----op\s sol----\n',dump(solve(demo())))
console.log('----that case---\n',dump(solve(demo2())))

距离矩阵(所有事件对之间=节点之间)可以通过迭代方式获得,类似于Floyd算法。基本上,迭代地:

T(x, y) = max (T(x,y), T(x, z) +T (z, y))

但是,正如OP在评论中提到的那样,Floyd算法为O(n ^ 3),对于n的值(最多10 ^ 5)而言,该值太大。

关键是不存在循环,因此应该存在更有效的算法。

grodzi在他们的建议中提出了一个不错的建议:使用拓扑形式的有向无环图(DAG)。

我根据这个想法用C ++实现了一个主要区别:

  • 我使用了一个简单的排序(来自C ++库)来构建拓扑排序。这样做很简单,并且复杂度为O(n logn)。 grodzi提出的专用方法可能更有效(似乎O(n))。但是,它非常容易实现,并且复杂度仍然很低。

经过拓扑排序后,我们知道给定事件仅取决于之前的事件。对于此部分,这确保了O(C)的复杂性,其中C是三元组的数量,即边的数量。

    #include    <iostream>
    #include    <vector>
    #include    <set>
    #include    <unordered_set> 
    #include    <algorithm>
    #include    <tuple>
    #include    <numeric>

    struct Triple {
        int event1;
        int event2;
        int days;
    };

    struct Pred {
        int pred;
        int days;
    };

    void print_result (const std::vector<int> &index, const std::vector<int> &times) {
        int n = times.size();
        for (int i = 0; i < n; i++) {
            std::cout << index[i]+1 << " " << times[index[i]] << "\n";
        }
    }

    std::tuple<std::vector<int>, std::vector<int>> ordering (int n, const std::vector<Triple> &triples) {
        std::vector<int> index(n);
        std::vector<int> times(n, 0);
        std::iota(index.begin(), index.end(), 0);

    //  Build predecessors matrix and sets
        std::vector<std::vector<Pred>> pred (n);
        std::vector<std::unordered_set<int>> set_pred (n);
        for (auto &triple: triples) {
                pred[triple.event2 - 1].emplace_back(Pred{triple.event1 - 1, triple.days});

                set_pred[triple.event2 - 1].insert(triple.event1 - 1);
        }

    //  Topological sort
        std::sort (index.begin(), index.end(), [&set_pred] (int &i, int &j) {return set_pred[j].find(i) != set_pred[j].end();});

    //  Iterative calculation of times of arrival
        for (int i = 1; i < n; ++i) {
            int ip = index[i];
            for (auto &p: pred[ip]) {
                    times[ip] = std::max(times[ip], times[p.pred] + p.days);
            }
        }

    //  Final sort, according to times of arrival
        std::sort (index.begin(), index.end(), [&times] (int &i, int &j) {return times[i] < times[j];});

        return {index, times};
    }

    int main() {
        int n_events = 4;
        std::vector<Triple> triples = {
            {1, 2, 5},
            {1, 3, 1},
            {3, 2, 6},
            {3, 4, 1}
        };

        std::vector<int> index(n_events);
        std::vector<int> times(n_events);
        std::tie (index, times) = ordering (n_events, triples);

        print_result (index, times);
    }

结果:

1 0
3 1
4 2
2 7

Related