走一棵树向后SQL

我有一个非常简单的架构的表：走一棵树向后SQL

CREATE TABLE q(
orig INTEGER NOT NULL, 
dest INTEGER NOT NULL, 
cost FLOAT, 
PRIMARY KEY (orig, dest) 
);

我需要走该表向后成本最小化的方式。让我解释。

我需要参观15分，积分可以是orig或dest。我的算法是从最后dest回溯到初始orig。因此，这里是我怎么拼出来：

鉴于最终dest，发现这将链接orig以最小cost说dest。相应orig成为新dest;循环15次。

让我们假设我知道上次dest是数10。 SQL语句，让我找到了orig导致dest在cost-最小化的方法是：

SELECT orig FROM q WHERE cost = (SELECT MIN(cost) FROM q WHERE dest = 10);

现在我会用通过上述函数返回的orig找到先前的点（假设它回来了，说，点5）：

SELECT orig FROM q WHERE cost = (SELECT MIN(cost) FROM q WHERE dest = 5);

我可以继续下去，直到我有15分。

如何进行有效的查询在SQL做到这一点？我的桌子有五千万行。

来源

2010-10-07 Escualo

下面是假定你使用SQL Server 2005+的查询。它使用通用表格表达式（CTE）。此示例实际返回具有选定的orig和dest的所有具有累积成本的路径。它还显示路径中的点数。它可以改变返回最佳的选择（例如，最低的成本，最少的步骤等）

我不知道表现会怎样。但是，索引是有帮助的。

WITH Paths AS -- Get list of all paths 
    (SELECT ROW_NUMBER() OVER (ORDER BY orig) AS PathNumber, orig, 
     dest, cost, 1 AS points 
    FROM q 

    UNION ALL 

    SELECT Paths.PathNumber, Paths.orig, 
     q.dest, q.cost, paths.points + 1 AS points 
    FROM Paths 
    JOIN q ON Paths.dest = q.orig 
    WHERE Paths.points < 15 
    ) 
    , PathsRows AS -- Get total points in each path 
    (SELECT COUNT(*) OVER (PARTITION BY PathNumber) AS TotalPoints, PathNumber 
     , orig, dest, cost, points 
    FROM Paths 
    ) 
    , PathsSum AS -- summarize for each path 
    (SELECT PathNumber, 
     MIN(CASE WHEN points = TotalPoints THEN orig END) AS orig, 
     MAX(CASE WHEN points = TotalPoints THEN dest END) AS dest, 
     SUM(cost) AS cost, MAX(points) AS points 
    FROM PathsRows 
    GROUP BY PathNumber 
    ) 

SELECT PathNumber, orig, dest, cost, points 
FROM PathsSum 
WHERE dest = 4 
    and orig = 1 
ORDER BY PathNumber, points

来源

2010-10-08 00:23:21 bobs

从查看OP的问题标签，我怀疑MySQL是有问题的RDBMS--据我所知，MySQL不支持递归CTE。 – 2010-10-08 11:18:04

简答：你不能。

更长的回答：假设我已经正确地理解了你的问题，你可以编写一个尽可能高效的SQL语句，但它不太可能在合理的时间范围内返回结果 - 比如说宇宙的年龄至今。

假设你的5000万行表包括没有重复，从映射到所有其他位置的所有位置的直接路径，那么包含的位置的数目是约5000万的平方根 - 即有7070多个地点。

因此，可能采取的路径数量为7070 x 7069 x 7068 ... x 7056，或换句话说，比7000^15稍大（约4.75 x 10^57）。

最终，这是一个Travelling Salesman Problem的变体 - 基于SQL的蛮力方法不适合解决它，数据集很大。

来源

2010-10-08 11:38:04

是的，我同意你的回答。但是，请注意，我所做的是回溯，它没有列举组合 - 它仅仅是对路线的可行性研究（甚至不包括动态规划）。我最终选择了一种基于矩阵的方法，其中我试图解决的问题在大约10分钟内收敛。 – Escualo 2010-10-08 22:01:58

@Arrieta，你可以发布你的解决方案，作为一个单独的答案？我必须承认我无法想象它。 – 2010-10-09 09:46:47

走一棵树向后SQL

回答

相关问题