algorithm - 检查是否存在两个相等的集合

Question

我有一套 J客户和一套设施I .对于每个客户j有K_j<=|I|到设施的不同距离。让这些(排序的)距离为 D_j^1 < D_j^2 < ... < D_j^ {K_j} .对于每个距离，我们定义一组比(在软意义上)比D_j^k更近的设施。与客户 j 的距离单位。此集合由 V_j^k={ i\in I | d_{ij}<=D_j^k } 给出.我的问题是，有没有一种聪明的方法来检查是否存在 i,j,k,l这样 V_j^K=V_i^l ？可以假设 V_j^k 中的索引排序。我唯一的解决方案是类似

for(j in J) do
  for(k in {1,...,K[j]} ) do
    V=V[j][k];
      for(i in J\{j} )
        for(l in {1,...,K[i]} ) do
          compare(V,V[i][l])

比较函数只是比较两个集合中的条目。但这有一个非常高的运行时间。是否有一些出色的方法来执行此任务？

Answer 1

您有一个矩阵 (M)，其中一行对应一个客户。该矩阵的元素是设施集。 M_cf = 包含离客户 c 最近的设施 f 的集合。在此矩阵中，第一列的元素将是仅包含一个设施的集合，该设施始终是离客户最近的设施。在第二列中，每个集合都有 2 个设施，依此类推。现在我们将找到具有相同设施的集合。这些集合必须在同一列中，否则每个集合中的元素数量会不同，因此集合不可能相等。在列 f 中，您通常需要将所有集合与所有其他集合进行比较以找到相等的集合，这将导致 O(f^2) 时间复杂度。如果您改为使用适当的算法对该列中的集合进行排序，则可以将其减少到 O(f*log(f))。总时间复杂度将为 O(j*f*log(f))，这比当前的 O(j^2*f^2) 要好得多，假设 O(1) 比较。