Oracleの階層問い合わせ（7）
（複雑な枝切り）

2. 階層問い合わせで迷路問題を解く

　次は、経路探索での複雑な枝切りを扱います。テーブルのデータと出力結果は、下記となります。

matrix

ID	A	B	C	D	E	F	G	H	I	J
A	1	1	1	0	0	0	1	0	1	0
B	0	0	0	0	1	1	1	0	1	0
C	0	1	1	1	1	0	0	0	0	1
D	1	0	0	0	1	0	1	0	0	0
E	1	1	0	0	0	0	0	0	0	1
F	0	1	1	0	1	1	0	0	0	0
G	0	1	0	1	1	1	0	1	0	1
H	1	1	0	1	0	0	0	1	0	0
I	0	1	1	1	0	1	1	1	0	1
J	1	0	0	0	0	0	0	1	0	1
K	1	0	0	1	1	1	0	1	1	0
L	0	0	1	0	1	1	0	0	1	0
M	0	0	1	0	0	0	0	1	1	1
N	1	0	1	0	0	0	1	1	1	0
O	1	0	0	1	1	0	1	0	0	0

　ID='A'の行のE列からスタートして、上下左右のいずれかに移動しながら、0と1を交互に訪問しつつ、ID='O'の行に到着する経路を求めます。

出力結果

path
------------------------------------------------------------
[A,E];[B,E];[B,D];[C,D];[D,D];[D,E];[D,F];[D,G];[C,G];[B,G];
[B,H];[B,I];[B,J];[C,J];[D,J];[E,J];[F,J];[G,J];[G,I];[G,H];
[G,G];[G,F];[H,F];[I,F];[J,F];[K,F];[K,G];[K,H];[L,H];[L,I];
[L,J];[M,J];[N,J];[N,I];[O,I]

[A,E];[B,E];[B,D];[C,D];[D,D];[D,E];[D,F];[D,G];[C,G];[B,G];
[B,H];[B,I];[C,I];[C,J];[D,J];[E,J];[F,J];[G,J];[G,I];[G,H];
[G,G];[G,F];[H,F];[I,F];[J,F];[K,F];[K,G];[K,H];[L,H];[L,I];
[L,J];[M,J];[N,J];[N,I];[O,I]

　どうにかして、階層問い合わせで経路探索できる形に加工してから、階層問い合わせを行えばよいと考えて、下記が答えとなります。

答え

select substr(sys_connect_by_path('[' || ID || ',' || X || ']',';'),2) as path
  from matrix UnPivot(vals for X in(A,B,C,D,E,F,G,H,I,J))
 where connect_by_IsLeaf = 1
   and ID = 'O'
start with ID = 'A' and X='E'
connect by nocycle (prior ID,prior X) in((chr(ascii(ID)+1),X),
                                         (chr(ascii(ID)-1),X),
                                         (ID,chr(ascii(X)+1)),
                                         (ID,chr(ascii(X)-1)))
       and mod(Level+1,2) = Vals
       and prior ID != 'O'
order by path;

　SQLのイメージは下記となります。経路を黄緑線でイメージしてます。

SQLのイメージ

　解説すると、まず『Oracle 11g R1新機能のPivotとUnPivot』で紹介したUnPivotで列を行に変換してます。UnPivotした結果の150行のうち、最初の15行を見てみましょう。

UnPivotで列を行に変換

select *
  from matrix UnPivot(vals for X in(A,B,C,D,E,F,G,H,I,J))
 where RowNum <= 15;

出力結果（最初の15行のみ）

ID	X	vals
A	A	1
A	B	1
A	C	1
A	D	0
A	E	0
A	F	0
A	G	1
A	H	0
A	I	1
A	J	0
B	A	0
B	B	0
B	C	0
B	D	0
B	E	1

　UnPivotで列を行に変換するSQLのイメージは下記となります。行ごとに区切る赤線を引いて、列B,C,D,E,F,G,H,I,Jを、列Aの下に移動させる黄緑線を引いてます。

SQLのイメージ

　階層問い合わせでは、同じ行への再訪ができないのでUnPivotで列を行に分割し、階層問い合わせの準備ができましたので、start with句でID = 'A' and X='E'を満たす行を階層問い合わせの根としてます。なお、閉路（cycle）対策としてconnect by nocycleを指定してます。

　次に、上下左右のいずれかに移動できるという条件をconnect by句で下記のマルチカラムin述語で指定してます。この場合は、条件式をorでつなげるよりもマルチカラムin述語を使ったほうがシンプルなSQLとなります。chr関数とascii関数を指定してアルファベット順で次の文字や前の文字を求めてます。

connect by句でのマルチカラムin述語

(prior ID,prior X) in((chr(ascii(ID)+1),X),
                      (chr(ascii(ID)-1),X),
                      (ID,chr(ascii(X)+1)),
                      (ID,chr(ascii(X)-1)))

　そして、0と1を交互に訪問するのですから、connect by句でmod(Level+1,2) = Valsを指定してます。また、ID='O'の行に到着したら探索は終了ですので、connect by句でprior ID != 'O'を指定して枝切りを行ってます。

　探索が終了した際に、ID='O'の行に到着していなければならないので、where句でconnect_by_IsLeaf = 1 and ID = 'O'を指定してます。

　最後にselect句でsys_connect_by_path関数を使って、経路を出力させてます。