在强制唯一节点属性时寻路——我应该使用哪种算法

Question

更新时间:2011-12-28:这是一篇博客文章，对我试图解决的问题，我的工作和我目前的解决方案进行了更模糊的描述:观看每支MLB球队的比赛

---

我正在尝试解决一种奇怪的寻路挑战。我有一个无环方向图，每条边都有一个距离值。我想找到一条最短路径。简单,是吧?好吧，有几个原因我不能只用Dijkstra's或a *。

1. 我根本不关心路径的起始节点是什么，也不关心结束节点是什么。我只需要一个恰好包含10个节点的路径。但是:
2. 每个节点都有一个属性，假设它是颜色。每个节点有一个20不同的可能颜色。
3. 我试图找到的路径是最短路径正好是10节点，其中每个节点是不同的颜色。我不希望路径中的任何节点与其他节点具有相同的颜色。
4. 能够强制我的路径为其中一个属性具有一个值(例如，"至少有一个节点必须是蓝色的")是很好的，但这不是真正必要的。

这是一个简化的例子。我的完整数据集实际上有三个不同的属性，每个节点都必须是唯一的，我有2k多个节点，每个节点平均有35个向外的边。由于获得完美的"最短路径"可能需要指数级或阶乘时间，因此穷举搜索确实不是一种选择。我真正在寻找的是满足#3中标准的"好路径"的一些近似。

谁能给我指出一个算法，我可能能够使用(甚至修改)?

---

关于我的完整数据集的一些统计:

• 节点总数:2430
• 总边数:86524
• 没有传入边的节点:19
• 没有出边的节点:32
• 最外向边:42
• 每个节点的平均边数:35.6(每个方向)
• 根据数据的性质，我知道这个图是无环的
• 在完整的数据集中，我要寻找长度为15的路径，而不是10

Answer 1

问题实际上包含了大部分答案。

从所有根节点开始进行广度优先搜索。当并行搜索路径的数量超过某个限制时，删除最长的路径。可以对路径长度进行加权:最后一条边的权值为10，经过9跳的边的权值为1。此外，还可以为具有首选属性的所有路径或经过弱连接节点的路径分配较小的权重。存储哈希表路径的最后10个节点，以避免重复。把最后9条边长度的最小和和和最短路径放在某个地方。

Answer 2

如果可能值的数量很低，您可以使用Floyd算法进行轻微修改:对于每条路径，您存储一个表示已访问过的不同值的位图。(在你的例子中，每个路径的位图宽度为20位。

然后当你执行长度比较时，你也和你的位图来检查它是否是一个有效的路径，如果是，你把它们放在一起并存储为路径的新位图。

Answer 3

您是否尝试过直接的方法而失败了?从你对问题的描述来看，我看不出像深度优先搜索这样简单的贪婪算法可能很好:

• 选择一个开始节点
• 检查近邻，是否有可以附加到路径上的节点?使用其中之一展开路径，并对该节点重复此过程。
• 如果失败，则返回到上次成功的状态并尝试新的邻居。
• 如果没有邻居检查，该节点不能作为路径的起始节点。试试新的。
• 如果有10个节点，就完成了。

如果不知道属性是如何分布的，很难给出一个好的启发式方法来选择一个开始节点，但它可能对具有高优先度的节点有益。

Answer 4

看起来贪婪深度优先搜索将是你最好的选择。在属性值分布合理的情况下，我认为找到一个单一的有效序列需要E[O(1)]时间，即期望常数时间。我或许可以证明，但可能需要一些时间。这个证明将使用一个假设，即在每一步都有一个非零概率可以找到序列的下一个有效片段。

贪心搜索会在违反唯一属性值约束时回溯。当找到15段路径时，搜索停止。如果我们接受我的直觉，即每个序列都可以在E[O(1)]中找到，那么问题就在于确定要进行多少次并行搜索。

Answer 5

对于那些想要尝试的人，这里是一个(postgres) sql脚本来生成一些假数据。

SET search_path='tmp';
-- DROP TABLE nodes CASCADE;
CREATE TABLE nodes
    ( num INTEGER NOT NULL PRIMARY KEY
    , color INTEGER
    -- Redundant fields to flag {begin,end} of paths
    , is_root boolean DEFAULT false
    , is_terminal boolean DEFAULT false
    );
-- DROP TABLE edges CASCADE;
CREATE TABLE edges
    ( numfrom INTEGER NOT NULL REFERENCES nodes(num)
    , numto INTEGER NOT NULL REFERENCES nodes(num)
    , cost INTEGER NOT NULL DEFAULT 0
    );
-- Generate some nodes, set color randomly
INSERT INTO nodes (num)
SELECT n
FROM generate_series(1,2430) n
WHERE 1=1
    ;
UPDATE nodes SET COLOR= 1+TRUNC(20*random() );
-- (partial) cartesian product nodes*nodes. The ordering guarantees a DAG.
INSERT INTO edges(numfrom,numto,cost)
SELECT n1.num ,n2.num, 0
FROM nodes n1 ,nodes n2
WHERE n1.num < n2.num
AND random() < 0.029
    ;
UPDATE edges SET cost = 1+ 1000 * random();
ALTER TABLE edges
    ADD PRIMARY KEY (numfrom,numto)
    ;
ALTER TABLE edges
    ADD UNIQUE (numto,numfrom)
    ;
UPDATE nodes no SET is_root = true
WHERE NOT EXISTS (
    SELECT * FROM edges ed
    WHERE ed.numfrom = no.num
    );
UPDATE nodes no SET is_terminal = true
WHERE NOT EXISTS (
    SELECT * FROM edges ed
    WHERE ed.numto = no.num
    );
SELECT COUNT(*) AS nnode FROM nodes;
SELECT COUNT(*) AS nedge FROM edges;
SELECT color, COUNT(*) AS cnt FROM nodes GROUP BY color ORDER BY color;
SELECT COUNT(*) AS nterm FROM nodes no WHERE is_terminal = true;
SELECT COUNT(*) AS nroot FROM nodes no WHERE is_root = true;
WITH zzz AS    (
    SELECT numto, COUNT(*) AS fanin
    FROM edges
    GROUP BY numto
    )
SELECT zzz.fanin , COUNT(*) AS cnt
FROM zzz
GROUP BY zzz.fanin
ORDER BY zzz.fanin
    ;
WITH zzz AS    (
    SELECT numfrom, COUNT(*) AS fanout
    FROM edges
    GROUP BY numfrom
    )
SELECT zzz.fanout , COUNT(*) AS cnt
FROM zzz
GROUP BY zzz.fanout
ORDER BY zzz.fanout
    ;
COPY nodes(num,color,is_root,is_terminal)
TO '/tmp/nodes.dmp';
COPY edges(numfrom,numto, cost)
TO '/tmp/edges.dmp';

Answer 6

问题可以通过如下动态规划来解决。让我们从正式定义它的解开始。

给定一个DAG G = (V, E)，设C为迄今为止访问过的顶点的颜色集合，设w[i, j]和c[i]分别为与边(i, j)和顶点i相关联的权值(距离)。注意，如果边(i, j)不属于E，则w[i, j]为零。现在定义从顶点i到顶点j的距离d，考虑到C为

d[i, j, C] = w[i, j] if i is not equal to j and c[j] does not belong to C
           = 0 if i = j
           = infinite if i is not equal to j and c[j] belongs to C

我们现在准备定义子问题如下:

A[i, j, k, C] =从i到j的最短路径，该路径完全使用k的边并尊重C的颜色，因此路径中没有两个顶点使用相同的颜色(C中的一种颜色)

设m为路径中允许的最大边数，并假设顶点标记为1,2，…， n。设P[i,j,k]为j在满足从i到j约束的最短路径上的前导顶点。下面的算法解决了这个问题。

for k = 1 to m
  for i = 1 to n
    for j = 1 to n
      A[i,j,k,C] = min over x belonging to V {d[i,x,C] + A[x,j,k-1,C union c[x]]}
      P[i,j,k] = the vertex x that minimized A[i,j,k,C] in the previous statement

按如下方式设置初始条件:

A[i,j,k,C] = 0 for k = 0
A[i,j,k,C] = 0 if i is equal to j
A[i,j,k,C] = infinite in all of the other cases

算法的总体计算复杂度为O(m n^3);考虑到在您的特定情况下m = 14(因为您想要恰好15个节点)，它遵循m = O(1)，因此复杂性实际上是O(n^3)。为了表示集合C，使用哈希表，这样插入和成员测试平均需要O(1)。请注意，在算法中，操作C union C [x]实际上是一个插入操作，其中您将顶点x的颜色添加到C的哈希表中。然而，由于您只是插入一个元素，因此set union操作会导致完全相同的结果(如果颜色不在集合中，则添加;否则，它将被丢弃，集合不会改变)。最后，为了表示DAG，使用邻接矩阵。

算法完成后，要在所有可能的顶点i和j中找到最小的最短路径，只需在A[i,j,m,C]中找到最小值。请注意，如果该值为infinite，则不存在有效的最短路径。如果存在有效的最短路径，那么实际上可以通过使用P[i,j,k]值并通过前一个顶点向后跟踪来确定它。例如，从a = P[i,j,m]开始，最短路径上的最后一条边是(a,j)，前一条边是b = P[i,a,m-1]给出的，它是(b,a)，以此类推。