迷路での最短経路を見つける、SQL

Question

は、どのように私は（PL/SQL関数を使用せずにはっきりSQL上、）（例えば）この迷路での最短の道を見つけることができます。

スタート地点：「S」、エンドポイント：結果として「E」

'00 000 e000000' 
'   0  ' 
'0000 000 0 00000 ' 
' 0 0 0  ' 
's0 000 000 00000 ' 
' 0    ' 

、この

'00 000 e000000' 
'   0-  ' 
'0000 000 0-00000 ' 
'---0 0 -0  ' 
's0-000 000-00000 ' 
' 0---------  ' 

のようなものがあるはず私はSQLコードで準備ができて解決策を待っていないんだけど、私はそれがだか分かりませんSQLで解決されました。誰もがどのアルゴリズムを知っていますか？ターゲットデータベースOracle。

Answer 1

再帰サブクエリのファクタリングを使用して、2つのアプローチ

1. ブルートフォースがあります。
2. モデル節+反復を使用するLeeアルゴリズム。 https://en.wikipedia.org/wiki/Lee_algorithm

更新。最初のアプローチの簡単なデモンストレーション。

column str format a30 
with t(y, str) as 
(  select 1, '00 000 e000000' from dual 
union all select 2, '   0  ' from dual 
union all select 3, '0000 000 0 00000 ' from dual 
union all select 4, ' 0 0 0  ' from dual 
union all select 5, 's0 000 000 00000 ' from dual 
union all select 6, ' 0    ' from dual) 
, matrix as 
(select x, y, str, substr(str, x, 1) z, rownum id 
from t 
cross join (select rownum x from dual connect by level <= 17)) 
, rec(x,y,z,id_list) as 
(select x, y, z, cast(id as varchar2(4000)) from matrix where z = 's' 
union all 
select m.x, m.y, m.z, r.id_list || '|' || m.id 
from matrix m 
join rec r on (r.x + 1 = m.x and r.y = m.y 
      or r.x - 1 = m.x and r.y = m.y 
      or r.x = m.x and r.y + 1 = m.y 
      or r.x = m.x and r.y - 1 = m.y) 
      and instr('|' || r.id_list || '|', '|' || m.id || '|') = 0 
      and m.z != '0' 
      and r.z = any ('s', ' ') 
) 
, route as 
(select regexp_substr(x, '\d+', 1, rownum) mark 
from 
(select max(id_list) keep 
     (dense_rank first order by regexp_count(id_list,'|')) x 
from rec 
where z = 'e') 
connect by level <= regexp_count(x,'|')) 
select y, listagg(decode(z, ' ', nvl2(mark, '=', z), z)) 
      within group (order by x) str 
from matrix 
left join route on id = mark 
group by y 
order by y; 

     Y STR       
---------- ------------------------------ 
     1 00 000 e000000    
     2   0=     
     3 0000 000 0=00000    
     4 ===0 0 =0     
     5 s0=000 000=00000    
     6 0=========     

6 rows selected. 

モデルソリューションは、はるかに効率的であるが、SQLはとにかく、この特定のタスクを解決するための最良の方法ではありません。

Answer 2

あなたのアイデアを求めているので：SQL SELECTを行うことができます（WITH句）

再帰共通テーブル式...ない限り

1. 到達可能性クエリは、「プレーン」SQL SELECT文で表現可能ではありませんステートメントチューリング完了。