sql - 查询获取路径

Question

我有一个包含以下数据的表：

Source | Destination
-------------------
46      47
47      49
48      49
49      50

我想编写一个返回路径列表的 sql，即 For 46,50 作为输入查询应该返回 46,47,49,50 作为输出。

Answer 1

在 SQL Server 中，您可以使用递归公用表表达式 (CTE)，如下所示：

declare @table Table(child int, parent int)

insert into @table(child, parent)
Values  
    (46, 47),
    (47, 49),
    (48, 49),
    (49, 50)


declare @start int
set @start = 46
;

with t1(child, parent) as (
select child, parent from @table t2
where child = @start
union all
select t.child,t.parent
from @table as t
join t1 on t1.parent = t.child
)
select parent from t1
union
select child from @table
where child = @start 

以下是上述查询的结果：

(4 row(s) affected)
parent
-----------
46
47
49
50

(4 row(s) affected)

Answer 2

这是一个 WHILE 循环（伪/未测试）；您也可以尝试递归 CTE。

--INPUT VARS
@path_begin int
@path_end int

--FUNCTION OR PROC
DECLRE @source int
DECLRE @destination int
DECLRE @path varchar(max)
SET @path = 'No Path Exists'

SELECT @source = source FROM table WHERE source = @path_begin
SELECT @destination = destination FROM table WHERE destination = @path_end

IF @source is not null AND @destination is not null
BEGIN
   SET @path = @source
   WHILE @source < @destination
   BEGIN
      SELECT @source = min(source) FROM table WHERE source > @source AND @source < destination
      SET @path = @path + ',' + @source
   END
   SET @path = @source + ',' + @destination
END

RETURN @path

Answer 3

Derek Greer 上面关于使用公用表表达式的解决方案是不正确的，原因有几个。两个简单的是：

1. 它没有回答最初的问题，因为目标是提供起点和终点，但他的解决方案只有一个起点。
2. 如果样本表中的第二行 (47, 49) 被删除，它将消除从 47 到 50 的任何可能路径，并且应该返回一个空值。相反，提供的代码提供了错误的路径（46、47、48、49）

以下来自 tamago 的解决方案也不起作用。尝试一些简单的案例，包括您在问题中请求的 (46, 50) 示例，您会发现它不起作用。

答案是这是计算机科学中的一个经典问题，称为旅行商问题。您可以在 Wikipedia 上阅读更多相关信息，网址为http://en.wikipedia.org/wiki/Travelling_salesman_problem。

已经有许多关于这个主题的算法发表。最容易实现的方法是搜索所有可能的排列，但由于存在大量可能性，这只适用于小数据集。更高级的算法需要更长的时间来实现，但可以处理更大的数据集。

你也可以考虑寻找一个近似的解决方案。有一些近似算法可以处理更大的数据集，虽然它们会返回有效路径，但它们可能找不到最短路径。