Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Microsoft SQL Server Новый топик    Ответить
 не простая задачка по комбинированию  [new]
PG81
Member

Откуда: Тверь
Сообщений: 882
Всем привет. Чот долго думал, как-то красиво не получается, а не красиво не хочется, поэтом решил посоветоваться.
есть табличка Tab1, это путь по точкам ABCDE
idItm
1A
2B
2C
3D

вот там где ID = 2, значит на втором шаге можно выбрать либо точку B либо С.
1)необходимо составить запрос, чтобы получить табличку, значения Val известная величина подставляется из справочника
SrcTrgVal
AB10
AC12
BD15
CD8

2)выбрать наименьший по величине путь т.е. в данном случае получается AC-CD так сумма тут 20
а AB->BD сумма 25 не подходит.

Не знаю понятно объяснил, если что спрашивайте.
11 май 16, 17:08    [19159667]     Ответить | Цитировать Сообщить модератору
 Re: не простая задачка по комбинированию  [new]
Добрый Э - Эх
Guest
PG81,

причем тут комбинаторика, если задача на графы?

З.Ы.
Из всех графов на рекурсивном SQL работать более-менее внятно можно только с деревьями. а у тебя тут замкнутые графы с циклами
11 май 16, 17:51    [19159919]     Ответить | Цитировать Сообщить модератору
 Re: не простая задачка по комбинированию  [new]
PG81
Member

Откуда: Тверь
Сообщений: 882
Добрый Э - Эх,
не нужно думать про графы, они тут не причем, и где тут интересно замкнутость??
просто нужно первую запись соеденить со второй и третей
а вторую и третью с четвертой и выбрать что из них лучше по критерию, какие тут графы?

если написать задачку типа "в первом графе три вершины, а во втором 5, сколько всего вершин в обоих графах?" она тоже будет про графы?)))нет же
11 май 16, 18:03    [19160015]     Ответить | Цитировать Сообщить модератору
 Re: не простая задачка по комбинированию  [new]
Добрый Э - Эх
Guest
PG81,

классическая задача на графы и поиск пути в нем из одной вершины в другую. твоя таблица как раз и задает пути в графе. и тебе нужно решить оптимизационную задачу по выбору кратчайшего пути. то, что у тебя две точки могут быть связаны более чем одной дугой - есть цикл. ну, про замкнутость может и поспешил, но не видя всех данных трудно сказать с уверенностью, что её не будет.
11 май 16, 18:09    [19160047]     Ответить | Цитировать Сообщить модератору
 Re: не простая задачка по комбинированию  [new]
TaPaK
Member

Откуда: Kiev
Сообщений: 6801
PG81,

ну для первой можно

DECLARE @graph TABLE
(
	ID INT,
	Code VARCHAR(1) 
)
INSERT INTO @graph 
VALUES
(1,	'A'),
(2,	'B'),
(2,	'C'),
(3,	'D')


;WITH cc(id,[source],[target],[Val]) 
AS
(
	SELECT 
		id,
		Code,
		Code,
		0
	FROM @graph
	WHERE 
		Id = 1
	UNION ALL

	SELECT 
		b.Id,
		a.target,
		b.Code,
		0
	FROM 
		cc	a
	JOIN
		@graph	b
	ON
		b.Id = a.Id + 1
	
)

SELECT [Source],[Target],[Val] FROM cc

а вторая классический поиск наименьшего пути по весам рёбер... гуглите
11 май 16, 18:20    [19160117]     Ответить | Цитировать Сообщить модератору
 Re: не простая задачка по комбинированию  [new]
PG81
Member

Откуда: Тверь
Сообщений: 882
Дело в том, что это уже готовый кротчайший путь, вычисленный по алгоритму дейкстры из большого графа, но из-за специфики применения возникают неоднозначности, вариации как в данном примере встречаются редко, поэтому просто сделал, что выбирается кратчайший вариант.
Спасибо за ответы, чото сразу про рекурсию идея не пришла в голову.
Благодарю за ответы, помогло.
12 май 16, 09:24    [19161786]     Ответить | Цитировать Сообщить модератору
Все форумы / Microsoft SQL Server Ответить