Сценарий наименьшего расстояния
На днях у меня была проблема, которая была довольно интересной. Это касается планирования серии "турниров". Ниже приведены ограничения:
- Есть 7 команд с именами A, B, ..., G
- Турнир состоит из 3 команд, все команды в турнире играют 1 игру против двух других команд. Т.е. турнир состоит из 3 игр
- Каждая команда проводит два турнира
- Каждая команда отправляется на четыре турнира, кроме турниров, которые они проводят.
- Когда серия закончена, все команды должны были сыграть все остальные команды дважды
Каждое путешествие связано с расстоянием. Цель состоит в том, чтобы найти расписание так, чтобы разница между самой короткой и самой длинной командировочной командой была минимальной.
Не совсем проблема коммивояжера, но вроде как связанная. Я буду счастлив удалить этот тег, если есть сильные мнения против него.
Некоторые примеры данных:
create table d
( source varchar(20) not null
, destination varchar(20) not null
, distance int not null
, primary key (source, destination) );
insert into d (source, destination, distance)
select 'A', destination, distance
from (values ('B',204)
, ('C',31)
, ('D',185)
, ('E',213)
, ('F',142)
, ('G',165)
) T(destination, distance);
insert into d (source, destination, distance)
select 'B', destination, distance
from (values ('C',230)
, ('D',102)
, ('E',169)
, ('F',152)
, ('G',224)
) T(destination, distance);
insert into d (source, destination, distance)
select 'C', destination, distance
from (values ('D',200)
,('E',224)
,('F',157)
,('G',135)
) T(destination, distance);
insert into d (source, destination, distance)
select 'D', destination, distance
from (values ('E',68)
,('F',51)
,('G',123)
) T(destination, distance);
insert into d (source, destination, distance)
select 'E', destination, distance
from (values ('F',52)
, ('G',88)
) T(destination, distance);
insert into d (source, destination, distance)
select 'F', destination, distance
from (values ('G',80)
) T(destination, distance);
create view dv as
select source, destination, distance from d
union all
select destination, source, distance from d;
Я начал с предположения, что было бы проще выбрать 4 поездки для каждой команды и отфильтровать оттуда. Давайте назовем это отношение team_travel. Кросс-соединение команды team_travels с командой team_travel и т. Д. Мы получаем все возможные комбинации team_travels. Оттуда мы можем исключить те, которые не содержат ровно 4 'A', 4 'B' и т. Д. Упорядочив то, что остается с разницей наибольшего и наименьшего расстояния, мы можем получить результат.
Это неприятно и может быть улучшено:
create or replace function cnt_occ(s varchar(28), c varchar(1))
returns int
return values length(s) - length(replace(s,c,null));
with t(s,d,n) as (
select source, destination, distance
from dv
), team_travel(s, d1,d2,d3,d4,n1,n2,n3,n4) as (
select t1.s, t1.d, t2.d, t3.d, t4.d, t1.n,t2.n,t3.n,t4.n
from t as t1
join t as t2
on t2.d > t1.d
and t1.s = t2.s
join t as t3
on t3.d > t2.d
and t1.s = t3.s
join t as t4
on t4.d > t3.d
and t1.s = t4.s
where t1.s not in (t1.d,t2.d,t3.d,t4.d)
)
select
a1.s||'->'||a1.d1||a1.d2||a1.d3||a1.d4,a1.n1+a1.n2+a1.n3+a1.n4
, a2.s||'->'||a2.d1||a2.d2||a2.d3||a2.d4,a2.n1+a2.n2+a2.n3+a2.n4
, a3.s||'->'||a3.d1||a3.d2||a3.d3||a3.d4,a3.n1+a3.n2+a3.n3+a3.n4
, a4.s||'->'||a4.d1||a4.d2||a4.d3||a4.d4,a4.n1+a4.n2+a4.n3+a4.n4
, a5.s||'->'||a5.d1||a5.d2||a5.d3||a5.d4,a5.n1+a5.n2+a5.n3+a5.n4
, a6.s||'->'||a6.d1||a6.d2||a6.d3||a6.d4,a6.n1+a6.n2+a6.n3+a6.n4
, a7.s||'->'||a7.d1||a7.d2||a7.d3||a7.d4,a7.n1+a7.n2+a7.n3+a7.n4
, greatest(a1.n1+a1.n2+a1.n3+a1.n4
, a2.n1+a2.n2+a2.n3+a2.n4
, a3.n1+a3.n2+a3.n3+a3.n4
, a4.n1+a4.n2+a4.n3+a4.n4
, a5.n1+a5.n2+a5.n3+a5.n4
, a6.n1+a6.n2+a6.n3+a6.n4
, a7.n1+a7.n2+a7.n3+a7.n4)
- least(a1.n1+a1.n2+a1.n3+a1.n4
, a2.n1+a2.n2+a2.n3+a2.n4
, a3.n1+a3.n2+a3.n3+a3.n4
, a4.n1+a4.n2+a4.n3+a4.n4
, a5.n1+a5.n2+a5.n3+a5.n4
, a6.n1+a6.n2+a6.n3+a6.n4
, a7.n1+a7.n2+a7.n3+a7.n4) as min_diff
from ( select * from team_travel where s = 'A' ) as a1
cross join ( select * from team_travel where s = 'B' ) as a2
cross join ( select * from team_travel where s = 'C' ) as a3
cross join ( select * from team_travel where s = 'D' ) as a4
cross join ( select * from team_travel where s = 'E' ) as a5
cross join ( select * from team_travel where s = 'F' ) as a6
cross join ( select * from team_travel where s = 'G' ) as a7
where cnt_occ(a1.d1||a1.d2||a1.d3||a1.d4
||a2.d1||a2.d2||a2.d3||a2.d4
||a3.d1||a3.d2||a3.d3||a3.d4
||a4.d1||a4.d2||a4.d3||a4.d4
||a5.d1||a5.d2||a5.d3||a5.d4
||a6.d1||a6.d2||a6.d3||a6.d4
||a7.d1||a7.d2||a7.d3||a7.d4, 'A') = 4
and cnt_occ(a1.d1||a1.d2||a1.d3||a1.d4
||a2.d1||a2.d2||a2.d3||a2.d4
||a3.d1||a3.d2||a3.d3||a3.d4
||a4.d1||a4.d2||a4.d3||a4.d4
||a5.d1||a5.d2||a5.d3||a5.d4
||a6.d1||a6.d2||a6.d3||a6.d4
||a7.d1||a7.d2||a7.d3||a7.d4, 'B') = 4
and cnt_occ(a1.d1||a1.d2||a1.d3||a1.d4
||a2.d1||a2.d2||a2.d3||a2.d4
||a3.d1||a3.d2||a3.d3||a3.d4
||a4.d1||a4.d2||a4.d3||a4.d4
||a5.d1||a5.d2||a5.d3||a5.d4
||a6.d1||a6.d2||a6.d3||a6.d4
||a7.d1||a7.d2||a7.d3||a7.d4, 'C') = 4
and cnt_occ(a1.d1||a1.d2||a1.d3||a1.d4
||a2.d1||a2.d2||a2.d3||a2.d4
||a3.d1||a3.d2||a3.d3||a3.d4
||a4.d1||a4.d2||a4.d3||a4.d4
||a5.d1||a5.d2||a5.d3||a5.d4
||a6.d1||a6.d2||a6.d3||a6.d4
||a7.d1||a7.d2||a7.d3||a7.d4, 'D') = 4
and cnt_occ(a1.d1||a1.d2||a1.d3||a1.d4
||a2.d1||a2.d2||a2.d3||a2.d4
||a3.d1||a3.d2||a3.d3||a3.d4
||a4.d1||a4.d2||a4.d3||a4.d4
||a5.d1||a5.d2||a5.d3||a5.d4
||a6.d1||a6.d2||a6.d3||a6.d4
||a7.d1||a7.d2||a7.d3||a7.d4, 'E') = 4
and cnt_occ(a1.d1||a1.d2||a1.d3||a1.d4
||a2.d1||a2.d2||a2.d3||a2.d4
||a3.d1||a3.d2||a3.d3||a3.d4
||a4.d1||a4.d2||a4.d3||a4.d4
||a5.d1||a5.d2||a5.d3||a5.d4
||a6.d1||a6.d2||a6.d3||a6.d4
||a7.d1||a7.d2||a7.d3||a7.d4, 'F') = 4
and cnt_occ(a1.d1||a1.d2||a1.d3||a1.d4
||a2.d1||a2.d2||a2.d3||a2.d4
||a3.d1||a3.d2||a3.d3||a3.d4
||a4.d1||a4.d2||a4.d3||a4.d4
||a5.d1||a5.d2||a5.d3||a5.d4
||a6.d1||a6.d2||a6.d3||a6.d4
||a7.d1||a7.d2||a7.d3||a7.d4, 'G') = 4
order by min_diff
fetch first 100 rows only
Должно быть что-то более элегантное, чем это, мысли?