趣味SQL：微软面试题：过河

newkid · 发表于 2012-4-15 04:38

多谢杨兄捧场！目前没有什么最佳答案，我们已经不满足于每次过两人的算法，而且还试图从全部尝试路径中找出一条捷径来，63,83,86,109,119楼是一些探讨，我在138楼提出一种设想，144楼则试图证明它（最后两个证明步骤有些勉强）。即时138楼算法成立也仍然是指数级的复杂度，希望有人能给出更好的。

guostong · 发表于 2012-4-16 22:31

老杨终于出手了。

newkid · 发表于 2012-4-17 00:01

这是我写的N人全组合的做法，和guostong的差不多，就是多了个预估时间的优化。后来猜想的算法以后再贴。

VAR N NUMBER;
EXEC :N:=2;

WITH b AS (
SELECT POWER(2,ROW_NUMBER() OVER (ORDER BY time)-1) bits_id ---- 速度从快到慢，每个人编为二进制的一位
      ,name
      ,time
      ,ROW_NUMBER() OVER (ORDER BY time) rn
      ,MIN(time) OVER() min_time -------- 最快的那个人过河一趟的时间
      ,COUNT(*) OVER() cnt ---- 总人数
   FROM bridge_crossing
)
,each_step(steps,direction,name,time,bits_id,bits) AS ( ---------- 递归求出所有1~N人组合
SELECT 1,1,CAST(name AS VARCHAR2(1000)),time,bits_id,bits_id FROM b  ---- 单人的是给回程用的，direction=1
UNION ALL
SELECT each_step.steps+1
      ,0    --- 两人以上的是过河的组合，direction=0
      ,each_step.name||' '||b.name
      ,b.time    ------- 取较大的时间
      ,b.bits_id
      ,each_step.bits+b.bits_id
   FROM each_step,b
   WHERE each_step.bits_id<b.bits_id
         AND each_step.steps<:N
)
,target AS (
SELECT SUM(CASE WHEN MOD(rn-1,:N-1)=0 THEN time + CASE WHEN cnt-rn+1<=:N THEN 0 ELSE min_time END
         END) AS estimated ---- 最快的那个人逐个陪伴其他:N-1人过河用的时间，作为参照时间。如果递归过程中发现时间已超过这个值则没必要继续
FROM b
)
,t(steps,names,bits,time) AS (
SELECT 0,CAST('' AS VARCHAR2(1000))
   ,POWER(2,(SELECT COUNT(*) FROM b))-1             ---------- 1未过河，0已过河
   ,0
  FROM DUAL
UNION ALL
SELECT t.steps+1,t.names||','||each_step.name
   ,DECODE(each_step.direction,1,t.bits+each_step.bits,t.bits-each_step.bits)
   ,t.time+each_step.time
  FROM t,each_step,target
WHERE MOD(t.steps,2)=each_step.direction
   AND (each_step.direction=0 ------ 往
         AND BITAND(t.bits,each_step.bits)=each_step.bits    ------ N人位置都为1, 都未过河
         OR each_step.direction=1 ------ 返
            AND each_step.bits=(SELECT MIN(b.bits_id) FROM b WHERE BITAND(t.bits,b.bits_id)=0)  --找出最快的人返回
         )
   AND t.time+each_step.time<=target.estimated
   AND t.bits<>0       ----------- 当t.bits=0则所有人已过河，为最终状态
)
SELECT names,time FROM (SELECT t.*,rank() OVER(ORDER BY time) rnk FROM t WHERE bits=0) WHERE rnk=1;

newkid · 发表于 2012-4-19 03:20

138楼算法的实现：欢迎提出反例或改进意见。

对递归WITH有兴趣的同学可以看看下面使用TABLE()函数的技巧。

WITH b AS (
SELECT POWER(2,ROW_NUMBER() OVER (ORDER BY time)-1) bits_id ---- 速度从快到慢，每个人编为二进制的一位
      ,name
      ,time
      ,ROW_NUMBER() OVER (ORDER BY time DESC) rn  ---- 速度从快到慢排序的序号, 用于下面计算参考时间
      ,COUNT(*) OVER() cnt
      ,MIN(time) OVER() min_time -------- 最快的那个人过河一趟的时间
   FROM bridge_crossing
)
,target AS (
---- 最快的那个人逐个陪伴其他:N-1人过河用的时间，作为参照时间。如果递归过程中发现时间已超过这个值则没必要继续
SELECT SUM(CASE WHEN MOD(rn-1,:N-1)=0 THEN time + CASE WHEN cnt-rn+1<=:N THEN 0 ELSE min_time END
         END) AS estimated
FROM b
)
,c AS (---- 构造出一个集合用于笛卡尔积
   SELECT 1 AS direction  ------ 方向：1过河, 0返回
         ,LEVEL num    ------ 过河人数; 从2~N逐一尝试
         ,1 AS sort_flag  ------ 排序标记，1表示从快到慢(取最快的2~N人过河)
         ,1 AS bits_flag  ------ 1表示未过河, 0表示已过河
      FROM DUAL
   WHERE LEVEL>1 CONNECT BY LEVEL<=:N
   UNION ALL SELECT 1,:N,-1,1 FROM DUAL ------ 选取最慢的N个人，这也是过河必须尝试的一种情况
   UNION ALL SELECT 0,1,1,-1 FROM DUAL  ------ 返回，永远是取最快的已过河的人
)
,t(step,names,bits,time,cnt) AS ( ---- 递归模拟过河的每一步骤。
---- step:第几步  names:往返人员名单  bits:未过河的人的二进制位之和  time:累计用时 cnt:未过河人数
SELECT 1,CAST('' AS VARCHAR2(1000))
   ,POWER(2,COUNT(*))-1             ---------- 1未过河，0已过河, 一开始把所有人的二进制位都置1
   ,0
   ,COUNT(*)
  FROM bridge_crossing
UNION ALL
---对COLUMN_VALUE的解释见下方。这个COLUMN_VALUE可以用标量子查询来取代，但是为了避免把一个复杂查询写很多遍，使用了TABLE()函数的技巧
---COLUMN_VALUE表示这个复杂计算的结果
---SUBSTR(COLUMN_VALUE,1,INSTR(COLUMN_VALUE,' ',1,num+1)) 取出前num个人的bits_id, 和集合b用instr条件连接，就知道哪些人在这前num个人中
SELECT t.step+1
   ,t.names||','||
            (SELECT LISTAGG(b.name,' ') WITHIN GROUP (ORDER BY bits_id) FROM b WHERE INSTR(SUBSTR(COLUMN_VALUE,1,INSTR(COLUMN_VALUE,' ',1,c.num+1)),' '||b.bits_id||' ')>0)  ---- 取出前num个人的姓名
   ---- 下面取出前num个人的二进制位bits_id并求和，这里也可以用 FROM DUAL CONNECT BY的办法对COLUMN_VALUE解析
   ,t.bits-c.bits_flag*(SELECT SUM(b.bits_id) FROM b WHERE INSTR(SUBSTR(COLUMN_VALUE,1,INSTR(COLUMN_VALUE,' ',1,c.num+1)),' '||b.bits_id||' ')>0)
   ---- 下面取出前num个人所用的时间并求出最大的，这是这一批人过河要用的时间
   ,t.time+(SELECT MAX(b.time) FROM b WHERE INSTR(SUBSTR(COLUMN_VALUE,1,INSTR(COLUMN_VALUE,' ',1,c.num+1)),' '||b.bits_id||' ')>0)  ---- 过去的num个人中时间取最大
   ,t.cnt-c.num*c.bits_flag ------- 计算人数的变化，过河为减少，返回为增加
  FROM t
   ,target
   ,c ---- 和前面生成的所有需要尝试的情况（集合c）做笛卡尔积
   ---下面的TABLE()函数返回一个集合，具有一个列COLUMN_VALUE, 相当于把t和c的连接结果的每一行做如下计算：
   ---把当前未过河的人(t.bits中二进制位为1的人)按照速度升序或降序排列，然后把这些人的bits_id用空格串成一个字符串
   ---如果为回程则是把当前已过河的人(t.bits中二进制位为0的人)按照速度排序，同样把bits_id串起来供后面使用
   ,TABLE(CAST(MULTISET(SELECT ' '||LISTAGG(b.bits_id,' ') WITHIN GROUP(ORDER BY c.sort_flag*b.time)||' '
                           FROM b
                        WHERE BITAND(t.bits,b.bits_id)=b.bits_id*c.direction ----
                        ) AS SYS.ODCIVARCHAR2LIST
               )
         ) ------- 这个COLUMN_VALUE
WHERE t.time<target.estimated  ---- 如果递归过程中发现时间已超过这个值则没必要继续
   AND t.bits<>0       ----------- 当t.bits=0则所有人已过河，为最终状态
   AND MOD(t.step,2)=c.direction
   AND (c.direction=1 AND (t.cnt<=:N AND c.sort_flag=1 AND c.num=t.cnt ---- 剩下不到N人了，则全部过河
                              OR t.cnt>:N AND (MOD(t.bits,POWER(2,:N))=0 ----- 最快的N人全部不在对岸，此时不能过最慢的N人
                                                   AND c.sort_flag=1 ----- sort_flag=1表示是2~N个最快的人
                                                OR MOD(t.bits,POWER(2,:N))>0  ----- 如果对岸有最快的N人之中的人，则快、慢组都应该尝试
                                                )
                              )    ---- c.direction=1: 过河
         OR c.direction=0 ---- 返回
         )
)
SELECT * FROM (
SELECT names,time
FROM t
WHERE t.bits=0
ORDER BY time
)
WHERE ROWNUM=1
;

newkid · 发表于 2012-4-19 03:29

本次活动告一段落，保持开放式结尾，欢迎大家随时补充答案或讨论。

guostong获得沙漏，以下人员各得彩蛋奖章一枚：
solomon_007,oversoul,changhe325,cwjl11,3833020,yangtingkun,lugionline, tree_new_bee, jixch, lastwinner

各种解答：
#69, #156作者guostong
#15作者solomon_007
#32作者oversoul
#33作者changhe325
#53作者cwjl11
#136作者3833020
#158作者yangtingkun
#163, #164作者newkid

算法探讨：
63,83,86,109,119,138,144楼