走一棵樹向後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

回答

相關問題