再帰with句08 最小全域木問題

SQLパズル

最小全域木を求める。

問題


答え

データ作成スクリプト

create table minTree(
ID     char(3),
nextID char(3),
cost   integer);

insert into minTree values
('A','B',5),
('A','C',2),
('B','C',4),
('B','D',2),
('C','D',3),
('C','E',2),
('D','E',6),
('D','F',6),
('E','F',4);

insert into minTree
select nextID,ID,cost from minTree;

SQL

with recursive W(Level,ID,nextID,cost,Path) as(
select 1,ID,nextID,cost,array[ID || nextID]
  from minTree
 where ID = 'A'
union all
select W.Level+1,b.ID,b.nextID,
case when b.ID || b.nextID = any(Path)
       or b.nextID || b.ID = any(Path)
     then W.cost else W.cost+b.cost end,
W.path || (b.ID || b.nextID)
  from W,minTree b
 where W.nextID = b.ID
   and W.cost < 5+2+4+2+3+2+6+6+4
   and W.Level <= 10)
select cost,path
from (select cost,path,rank() over(order by cost,Level) as rn
        from W
       where array_to_string(path,',') ~ '^(?=.*A)(?=.*B)(?=.*C)(?=.*D)(?=.*E)(?=.*F)') d
 where rn=1;

解説

正規表現は、strpos関数とandの組み合わせに書き換えるのもいいかもしれませんねぇ

Javaアルゴリズムパズル 3-10 最小全域木問題

---