在迷宫中寻找最短路径，SQL

Question

如何在这个迷宫中找到（例如）最短路线（显然 SQL，而不使用 PL/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

由于您是在征求意见：

可达性查询无法在 "plain" SQL SELECT 语句中表达，除非...
Recursive Common Table Expressions (WITH clause) can make a SQL SELECT statement Turing-complete.

Answer 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 无论如何都不是解决此特定任务的最佳方法。

在迷宫中寻找最短路径，SQL

Finding the shortest path in the maze, SQL

sql

oracle

maze