Пример использования СТЕ для решения задачи Коммивояжера

Проблема состоит в том, чтобы проехать на машине от Парижа до Тулузы, используя сеть автострад.

Создадим таблицу и занесем данные:
CREATE TABLE TUR

TO_TOWN VARCHAR(32),

MILES INTEGER);

Возьмем в качестве начала рекурсии “Париж” и построим СТЕ

WITH

TUR_PARIS ([TO-TOWN])

AS

(SELECT DISTINCT FROM_TOWN

FROM TUR

WHER FROM_TOWN= 'PARIS'

UNION ALL

SELECT TO_TOWN

FROM TUR INNER JOIN TUR_PARIS

ON TUR_PARIS.[TO-TOWN] = TUR.FROM_TOWN

)

SELECT * FROM TUR_PARIS;

Как видно из результата запроса, существует три способа добраться до Тулузы. Отфильтруем пункт назначения.

WITH

TUR_PARIS ([TO-TOWN])

AS

(SELECT DISTINCT FROM_TOWN

FROM TUR

WHER FROM_TOWN= 'PARIS'

UNION ALL

SELECT TO_TOWN

FROM TUR INNER JOIN TUR_PARIS

ON TUR_PARIS.[TO-TOWN] = TUR.FROM_TOWN

)

SELECT * FROM TUR_PARIS

WHERE [TO-TOWN] = 'TOULOUSE';

Мы можем уточнить этот запрос, подсчитав число шагов по каждому направлению, расстояния по различным направлениям и выведя списки городов, которые можно посетить, двигаясь по этим направлениям:

WITH

TUR_PARIS([TO-TOWN], STEPS, DISTANSE, WAY)

AS

(SELECT DISTINCT FROM_TOWN, 0, 0

,cast('PARIS' as VarChar(MAX))

FROM TUR

WHERE FROM_TOWN= 'PARIS'

Date: 2015-09-18; view: 371; Нарушение авторских прав