摘要：該遞歸公共表表達(dá)式在第一次執(zhí)行的時(shí)候根據(jù)部分生成了一行數(shù)據(jù)。執(zhí)行該查詢語句，你會(huì)看到最短路徑需要英里并且按順序經(jīng)過了下列城市得益于遞歸公共表表達(dá)式，我們成功地用解決了旅行銷售員問題

原文：Solving the Traveling Salesman Problem with Postgres Recursive CTEs

Many SQL implementations don"t have loops, making some kinds of analysis very difficult. Postgres, SQL Server, and several others have the next best thing — recursive CTEs!

許多 SQL 實(shí)現(xiàn)沒有將循環(huán)包括在內(nèi)，使進(jìn)行一些分析工作變得很困難。Postgres、SQL Server 以及一些其它的 SQL 實(shí)現(xiàn)則提供了下面將要提到的優(yōu)良特性：遞歸公共表表達(dá)式（recursive CTE）。

We"ll use them to solve the Traveling Salesman Problem and find the shortest round-trip route through several US cities.

我們將使用它們來解決旅行銷售員問題（Traveling Salesman Problem ）并且找出經(jīng)過若干美國城市的最短巡回路徑。

Normal CTEs are great at helping to organize large queries. They are a simple way to make temporary tables you can access later in your query.

一般的公共表表達(dá)式（CTE）主要用于幫助組織大型查詢語句。你可以簡便地創(chuàng)建臨時(shí)表，并在稍后的查詢語句中訪問它們。

Recursive CTEs are more powerful - they reference themselves and allow you to explore hierarchical data. While that may sound complicated, the underlying concept is very similar to a for loop in other programming languages.

遞歸公共表表達(dá)式（Recursive CTEs）的能力更強(qiáng)——它們通過自引用，使你能夠探索層次化的數(shù)據(jù)。雖然這聽起來很復(fù)雜，但其背后的概念和其它編程語言中的 for 循環(huán)十分相似。

These CTEs have two parts — an anchor member and a recursive member. The anchor member selects the starting rows for the recursive steps.

該公共表表達(dá)式（CTE）包含兩個(gè)部分——一個(gè) anchor 部分和一個(gè) recursive 部分。 anchor 部分提供了遞歸步驟的起始數(shù)據(jù)。

The recursive member generates more rows for the CTE by first joining against the anchor rows, and then joining against rows created in previous recursions. The recursive member comes after a union all in the CTE definition.

recursive 部分為此公共表表達(dá)式（CTE）生成更多的數(shù)據(jù)，方法是先連接（join） anchor 數(shù)據(jù)，然后連接（join）上次遞歸產(chǎn)生的數(shù)據(jù)。在公共表表達(dá)式（CTE）的定義語句中，recursive 部分接在 union all 關(guān)鍵字后面。

Here"s a simple recursive CTE that generates the numbers 1 to 10. The anchor member selects the value 1, and the recursive member adds to it up to the number 10:

這是一個(gè)能產(chǎn)生數(shù)字1到10的簡單的遞歸公共表表達(dá)式（CTE）。其中 anchor 部分提供了數(shù)據(jù)值1，然后 recursive 部分將其逐步累加至10。

with recursive incrementer(prev_val) as (
  select 1 -- anchor member
  union all
  select -- recursive member
    incrementer.prev_val + 1
  from incrementer
  where prev_val < 10 -- termination condition
)

select * from incrementer

The first time the recursive CTE runs it generates a single row 1 using the anchor member. In the second execution, the recursive member joins against the 1 and outputs a second row, 2. In the third execution the recursive step joins against both rows 1 and 2 and adds the rows 2 (a duplicate) and 3.

該遞歸公共表表達(dá)式（recursive CTE）在第一次執(zhí)行的時(shí)候根據(jù) anchor 部分生成了一行數(shù)據(jù)“1”。在第二次執(zhí)行中， recursive 部分連接到數(shù)據(jù)“1”并輸出了第二行“2”。在第三次執(zhí)行中，recursive 部分同時(shí)連接到了數(shù)據(jù)“1”和“2”并且添加了新數(shù)據(jù)“2”（重復(fù)）和“3”。

Recursive CTEs also only return distinct rows. Even though our CTE above creates many rows with the same value, only a distinct set of rows will be returned.

同時(shí)遞歸公共表表達(dá)式（recursive CTE）只返回互不相同的數(shù)據(jù)。雖然我們的公共表表達(dá)式（CTE）創(chuàng)建了許多相同的數(shù)據(jù)行，但返回的數(shù)據(jù)集只包含互不相同的數(shù)據(jù)。

Notice how the CTE specifies its output as the named value prev_val. This lets us refer to the output of the previous recursive step.

注意該公共表表達(dá)式（CTE）是如何將其輸出命名為 prev_val 的。這使得我們可以引用上一次遞歸的輸出結(jié)果。

And at the very end there is a termination condition to halt the recursion once the sum gets to 10. Without this condition, the CTE would enter an infinite loop!

并且在最后的最后有一個(gè)終止條件：一旦 sum 到達(dá)10就停止遞歸。如果沒有這個(gè)條件，該公共表表達(dá)式（CTE）將會(huì)進(jìn)入一個(gè)無限循環(huán)！

Under the hood, the database is building up a table named after this recursive CTE using unions:

這樣，數(shù)據(jù)庫以該遞歸公共表表達(dá)式（recursive CTE）為名字，基于并集建立了一個(gè)數(shù)據(jù)表：

Recursive CTEs can also have many parameters. Here"s one that takes the sum, double, and square of starting values of 1, 2 and 3:

遞歸公共表表達(dá)式（recursive CTE）還可以包含多個(gè)參數(shù)。下面的例子以1、2和3為初始值，分別計(jì)算了依次加1的和、倍增值和依次平方的值。

with recursive cruncher(inc, double, square) as (
  select 1, 2.0, 3.0 -- anchor member
  union all
  select -- recursive member
    cruncher.inc + 1,
    cruncher.double * 2,
    cruncher.square ^ 2
  from cruncher
  where inc < 10
)

select * from cruncher

With recursive CTEs we can solve the Traveling Salesman Problem.

通過使用遞歸公共表表達(dá)式（recursive CTE），我們能夠解決旅行銷售員問題。

There are many algorithms for finding the shortest round-trip path through several cities. We"ll use the simplest: brute force. Our recursive CTE will enumerate all possible routes and their total distances. We"ll then sort to find the shortest.

有許多算法可以用于找出經(jīng)過若干城市的最短巡回路徑。我們將使用最簡單的一種：暴力搜索。我們的遞歸公共表表達(dá)式（recursive CTE）將枚舉所有可能的路徑和它們的總距離，然后排序以找出最短的一條。

First, a list of cities with Periscope customers, along with their latitudes and longitudes:

首先是一個(gè)顧客所在城市的列表，包含它們的緯度和經(jīng)度。

create table places as (
  select
    "Seattle" as name, 47.6097 as lat, 122.3331 as lon
    union all select "San Francisco", 37.7833, 122.4167
    union all select "Austin", 30.2500, 97.7500
    union all select "New York", 40.7127, 74.0059
    union all select "Boston", 42.3601, 71.0589
    union all select "Chicago", 41.8369, 87.6847
    union all select "Los Angeles", 34.0500, 118.2500
    union all select "Denver", 39.7392, 104.9903
)

And we"ll need a distance function to compute how far two lat/lons are from each other (thanks to strkol on stackoverflow.com):

然后我們需要一個(gè)距離函數(shù)來計(jì)算兩個(gè)經(jīng)緯度之間的距離（感謝 strkol 在 stackoverflow.com 上的回答）：

create or replace function lat_lon_distance(
  lat1 float, lon1 float, lat2 float, lon2 float
) returns float as $$
declare
  x float = 69.1 * (lat2 - lat1);
  y float = 69.1 * (lon2 - lon1) * cos(lat1 / 57.3);
begin
  return sqrt(x * x + y * y);
end
$$ language plpgsql

Our CTE will use San Francisco as its anchor city, and then recurse from there to every other city:

我們的公共表表達(dá)式（CTE）將使用 San Francisco 作為出發(fā)城市，然后從那開始遞歸抵達(dá)其它城市。

with recursive travel(places_chain, last_lat, last_lon,
    total_distance, num_places) as (
  select -- anchor member
    name, lat, lon, 0::float, 1
    from places
    where name = "San Francisco"
  union all
  select -- recursive member
    -- add to the current places_chain
    travel.places_chain || " -> " || places.name,
    places.lat,
    places.lon,
    -- add to the current total_distance
    travel.total_distance + 
      lat_lon_distance(last_lat, last_lon, places.lat, places.lon),
    travel.num_places + 1
  from
    places, travel
  where
    position(places.name in travel.places_chain) = 0
)

The parameters in the CTE are:

places_chain: The list of places visited so far, which will be different for each instance of the recursion

last_lat and last_lon: The latitude and longitude of the last place in the places_chain

total_distance: The distance traveled going from one place to the next in the places_chain

num_places: The number of places in places_chain — we"ll use this to tell which routes are complete because they visited all cities

該公共表表達(dá)式（CTE）中的參數(shù)有：

places_chain：截至目前訪問過的位置的列表，在每條遞歸路徑中都是不同的

last_lat and last_lon：places_chain 中最后一個(gè)位置的緯度和經(jīng)度。

total_distance：places_chain 中相鄰位置的距離的總和

num_places：places_chain 中位置的數(shù)目——我們使用該參數(shù)來分辨哪條路徑已經(jīng)完成，由其訪問過了所有城市

In the recursive member, the where clause ensures that we never repeat a place. If we"ve already visited Denver, position(...) will return a number greater than 0, invalidating this instance of the recursion.

在 recursive 部分中，where 子句確保了我們不會(huì)重復(fù)訪問一個(gè)地方。（比如說）如果我們已經(jīng)訪問過 Denver，position(...) 將返回一個(gè)大于0的數(shù)字，使得該遞歸路徑無效化。

We can see all possible routes by selecting all 8-city chains:

通過列出所有包含了8個(gè)城市的城市鏈，我們可以看到所有可能的路徑：

select * from travel where num_places = 8

We need to add in the distance from the last city back to San Francisco to complete the round-trip. We could hard code San Francisco"s lat/lon, but a join is more elegant. Once that"s done we sort by distance and show the smallest:

我們需要加上從最后一個(gè)城市回到 San Francisco 的距離以完成回路。我們可以在代碼中顯式寫入 San Francisco 的經(jīng)緯度，但使用連接操作看起來更加優(yōu)雅。一完成這個(gè)我們就可以根據(jù)距離進(jìn)行排序并輸出最短路徑：

select
  travel.places_chain || " -> " || places.name,
  total_distance + lat_lon_distance(
      travel.last_lat, travel.last_lon,
      places.lat, places.lon) as final_dist
from travel, places
where
  travel.num_places = 8
  and places.name = "San Francisco"
order by 2 -- ascending!
limit 1

Even though this query is significantly more complicated than the incrementer query earlier, the database is doing the same things behind the scenes. The top branch is the creating the CTE"s rows, the bottom branch is the final join and sort:

雖然該查詢語句明顯復(fù)雜于之前的 incrementer 查詢，數(shù)據(jù)庫在幕后做的事情依然一樣。最頂上的分支是創(chuàng)建該公共表表達(dá)式（CTE）的數(shù)據(jù)，最底部的分支是最終的連接和排序。

Run this query and you"ll see the shortest route takes 6671 miles and visits the cities in this order:

執(zhí)行該查詢語句，你會(huì)看到最短路徑需要 6671 英里并且按順序經(jīng)過了下列城市：

San Francisco -> Seattle -> Denver ->
Chicago -> Boston -> New York -> Austin ->
Los Angeles -> San Francisco

Thanks to recursive CTEs, we can solve the Traveling Salesman Problem in SQL!

得益于遞歸公共表表達(dá)式（recursive CTE），我們成功地用 SQL 解決了旅行銷售員問題！