sql - Escenario de planificación a menor distancia

db2 traveling-salesman

Question

El otro día tuve un problema que fue bastante interesante. Se trata de programar una serie de "torneos". Las siguientes son las restricciones:

• Hay 7 equipos llamados A, B, ..., G
• Un torneo contiene 3 equipos, todos los equipos en un torneo juegan 1 juego contra los otros 2 equipos. Es decir, un torneo consta de 3 juegos
• Cada equipo alberga dos torneos
• Cada equipo viaja a cuatro torneos al lado de los torneos que organizan
• Cuando la serie termine, todos los equipos deberían haber jugado a los otros equipos dos veces

Cada viaje está asociado con una distancia. El objetivo es encontrar un horario tal que la diferencia entre el equipo que viaja más corto y el más largo sea mínima.

No es exactamente un problema de vendedor ambulante, sino más bien relacionado. Estaré encantado de eliminar esa etiqueta si hay fuertes opiniones en contra de ella.

Algunos datos de muestra:

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;

Comencé con la suposición de que sería más fácil elegir 4 viajes para cada equipo y filtrar desde allí. Vamos a llamar a esta relación team_travel. Al unir de forma cruzada el team_travels de A con el team_travel de B, obtenemos todas las combinaciones posibles de team_travels. Desde allí podemos excluir aquellos que no contengan exactamente 4 ''A'', 4 ''B'', etc. Al ordenar lo que queda con la diferencia de la mayor y la menor distancia de recorrido, podemos obtener el resultado.

Esto es feo y ciertamente puede mejorarse:

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

Tiene que haber algo más elegante que esto, ¿pensamientos?