SQL Server 递归查询.狼羊过河问题

Posted on Edited on In Views:
狼羊过河问题、SQL、递归查询

狼羊过河问题

问题描述

  • 一个人带着一只狼、一只羊、一棵白菜要过河，小船一次只能容下一个人和一样动植物
  • 人不在场的时候，狼要吃掉羊、羊要吃掉白菜
  • 问应当如何渡河？

SQL Server 求解

  • 安装之后命令行直接输入如下命令便可进入 SQL Server 命令行模式
1
sqlcmd
  • 新建数据库
1
create database River;
  • 使用数据库
1
use River;

状态表

  • 新建一个数据库表 STATE 用于存储可行的状态，state 表示当前河岸的状态
  • 使用一个 4 位的二级制数表示状态
  • 低 4 位分别表示人（3）、狼（2）、羊（1）、菜（0）
1
2
3
create table STATE (
    state tinyint
)
  • 使用循环把可行的状态插入表中
  • 可行的状态，满足以下一个条件即可
    • 人在
    • 人不在，但是不存在狼羊或羊菜同时存在的情况
  • 最大的状态为 0b1111 = 15
    • 判断人不在：state < 0b1000
      • 0b1000 = 8
    • 判断狼羊都在：state & 0b0110 == 0b0110
      • 0b0110 = 6
    • 判断羊菜都在：state & 0b0011 == 0b0011
      • 0b0011 = 3
  • 同时对岸也得满足这个条件
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
declare @i int
declare @j int

set @i=0
while @i<=15
begin
    set @j=15-@i
    /* 当前岸 */
    if ((@i >= 8) or not ((@i & 6 = 6) or (@i & 3 = 3)))
    and
    /* 对岸 */
    ((@j >= 8) or not ((@j & 6 = 6) or (@j & 3 = 3)))
    begin
        insert STATE values (@i)
    end
    set @i=@i+1
end
  • 通过如下指令，我们可以看到一共有 10 个状态
1
select count(*) from STATE

路径表

  • 新建一个表，用于表示相邻边
1
2
3
4
5
create table PATH(
    state_from  tinyint,
    state_to    tinyint,
    path        varchar(100)
)
  • 对 STATE 表做笛卡尔积，挑选出可行边，保存在 PATH 中，path 字段记录中间节点
  • 可行边，同时满足以下所有条件
    • 满足下列两个条件之一
      • state_from - state_to 中有人，且最多有一件物品，同时 state_to 中不能有 state_from 没有的东西
        • 人过河
      • state_to - state_from 中有人，且最多有一件物品，同时 state_from 中不能有 state_to 没有的东西
        • 人从对岸回来
    • state_from、state_to 都是合法的
      • 这个由 STATE 表保证了
  • 实际解决
    • state_from - state_to 中有人（最高位为 1）
      • 打表：1-0=1，1-1=0，0-1=0，0-0=0
        • state_from - state_to = state_from & ~state_to >= 0b1000 = 8
    • 最多只有一件物品
      • state_from - state_to 的低三位只有一位为 1，或者全为 0
    • state_to 中不能有 state_from 没有的东西
      • state_to & ~state_from == 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
insert PATH
select S1.state, S2.state, ""
from STATE S1, STATE S2
where (
    (S1.state & ~S2.state >= 8)
    and
    (S2.state & ~S1.state = 0)
    and (
        (S1.state & ~S2.state & 7 = 0)
        or (S1.state & ~S2.state & 7 = 1)
        or (S1.state & ~S2.state & 7 = 2)
        or (S1.state & ~S2.state & 7 = 4)
    )
) or (
    (S2.state & ~S1.state >= 8)
    and
    (S1.state & ~S2.state = 0)
    and (
        (S2.state & ~S1.state & 7 = 0)
        or (S2.state & ~S1.state & 7 = 1)
        or (S2.state & ~S1.state & 7 = 2)
        or (S2.state & ~S1.state & 7 = 4)
    )
)
  • 可以做一个简单的优化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
insert PATH
select S1.state, S2.state, ""
from STATE S1, STATE S2
where (
    (S2.state & ~S1.state = 0)
    and (
        (S1.state & ~S2.state = 8)
        or(S1.state & ~S2.state = 9)
        or (S1.state & ~S2.state = 10)
        or (S1.state & ~S2.state = 12)
    )
) or (
    (S1.state & ~S2.state = 0)
    and (
        (S2.state & ~S1.state = 8)
        or(S2.state & ~S1.state = 9)
        or (S2.state & ~S1.state = 10)
        or (S2.state & ~S1.state = 12)
    )
)

求解

  • 我们简单的用一个表 ANSWER 记录结果
1
2
3
create table ANSWER(
    path    varchar(100)
)
  • 找一条路径满足起始点为 0b1111=15，终点为 0b0000=0，输出这条路径
  • 我们需要进行一个环路检测，我们简单的使用一个变量记录路径，不允许路径上的点重复出现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
with MultiBouncePath(state_from, state_to, path) as (
    select state_from, state_to, cast(path as varchar)
    from PATH

    union all

    /* 注意顺序 M,P, 末尾增长边 */
    select M.state_from , P.state_to, cast(M.path + ',' + cast(M.state_to as varchar) as varchar)
    from MultiBouncePath M, PATH P
    /* M.path 中找不到子串 P.state_t 说明路径上没有这个点 */
    where M.state_to = P.state_from and CHARINDEX(cast(P.state_to as varchar) ,M.path) = 0
)

insert ANSWER
select (cast(state_from as varchar) + path + "," + cast(state_to as varchar))
from MultiBouncePath
where state_from = 15 and state_to = 0
  • 我们可以查看具体的路径
1
select * from ANSWER
  • 结果如下
    • 15,5,13,4,14,2,10,0
    • 15,5,13,1,11,2,10,0
  • 我们将其转化为我们能够直接读得懂的内容
  • 增加一个标识 ID
1
alter table ANSWER add ID int identity(1,1)
  • 辅助实现
1
2
update ANSWER
set path = path + ','
  • 定义一个从数字到状态的转换函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/* 架构名.函数名 */
create function dbo.to_zh(
@num1 int
)
returns varchar(100)
as
begin
    declare @ans1 varchar(100)
    declare @ans2 varchar(100)
    declare @disc varchar(10)
    declare @index varchar(10)
    set @disc = "人狼羊菜"
    set @index = "8421"
    set @ans1 = ""
    set @ans2 = ""
    declare @i int
    set @i = 1
    while(@i <= 4)
    begin
        if ((@num1 & (ASCII(SUBSTRING(@index, @i, 1)) - ASCII("0"))) > 0)
        begin
            set @ans1 = @ans1 + SUBSTRING(@disc, @i, 1)
        end
        else
        begin
            set @ans2 = @ans2 + SUBSTRING(@disc, @i, 1)
        end
        set @i = @i + 1
    end
    return @ans1 + "|" + @ans2
end
  • 取出一个结果进行输出
    • master..spt_values 是系统中一个表
1
2
3
4
5
6
7
8
9
10
select dbo.to_zh(M.item) from (
    select SUBSTRING(ans.path, number, CHARINDEX(',', ans.path + ',', number) - number) as item
    from ANSWER ans, master..spt_values
    /* 查第 1 条记录*/
    where ID = 1
    and number >= 1
    and number < len(ans.path)
    and type = 'p'
    and SUBSTRING(',' + ans.path, number, 1)=','
) M
  • 输出结果如下
  • 15,5,13,4,14,2,10,0
1
2
3
4
5
6
7
8
人狼羊菜|
狼菜|人羊
人狼菜|羊
狼|人羊菜
人狼羊|菜
羊|人狼菜
人羊|狼菜
|人狼羊菜
  • 15,5,13,1,11,2,10,0
1
2
3
4
5
6
7
8
人狼羊菜|
狼菜|人羊
人狼菜|羊
菜|人狼羊
人羊菜|狼
羊|人狼菜
人羊|狼菜
|人狼羊菜

其他 SQL Server 相关

  • 删除整个表中的条目
1
truncate table STATE
  • 删除函数
1
drop function dbo.to_zh