는 (PL/SQL 함수를 사용하지 않고, 명확하게 SQL에) SQL

Question

은 어떻게 (예를 들어)이 미로에서 가장 짧은 길을 찾을 수 있습니다, 미로에서 최단 경로 찾기 :

시작 지점 '의' 엔드 포인트 : 결과적으로 'E'

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

, 나는 SQL 코드의 준비 솔루션을 기다리지 않고있어이

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

같은 무언가가 있어야하지만 나는 그것이 얼마나 아무 생각이 없다 SQL로 해결되었습니다. 누구든지 알고리즘을 알고 있습니까? 대상 데이터베이스 Oracle.

Answer 1

은 재귀 서브 쿼리 인수를 사용하여 두 가지 방법

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

당신은 아이디어를 요구하고 있기 때문에 :

1. 도달 가능성 쿼리 (WITH 절)
2. 재귀 공통 테이블 식 ...하지 않는 한 SQL SELECT 할 수 있습니다, "일반"SQL SELECT 문에서 표현할 수없는 statement 튜링 완료.