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

3833020

楼上的写法适用于固定两人的情形；t1包含着一个笛卡尔积，回程是没有做优化的，把所有已过河的人都尝试一遍。每次递归都包含了来和回两个步骤，所以从NAK(对岸的人名单)中挑选最快的还不够，还得加上本次要过河的两人，再从中筛选出最快的。
-----------------------------------------------------------------------


对于每次最多过N人的情况的确比较复杂，没有考虑到。
newkid大师前面几页的总结还没仔细看，今天有空看看。

yushusong

不知道SQL怎么写，不过最短应该是17
AB  去   2
A    回   1
CD  去 10
B    回   2
AB  去   2

yushusong

将速度相近的、最慢的放在一起走，返回要用最快的

newkid

现在我试图论证138楼的算法：

假设桥的容量为n,即每次最多过n人。


1.先考虑回程的情况：返回的必定是已过河的人中最快的：这个很简单，因为这个人送了手电之后，最终还是要过河，所以要挑成本最低的。
  
2.现在考虑过河的情况: 把所有未过河的人按速度从快到慢编号，为了和上述的P区别，假设最快的人为R1, 最慢为Rm，所用时间分别为T1到Tm。
  2.1假如m<=n: 所有人全部过河，没什么好说的。
  2.2以下考虑m>n的情况, 又可分两种情形：
    2.2.1 本次要返回的人，是在这m人之外，即在已经过河的人之中：此时的最佳策略是挑选最慢的N人，即Rm-n+1到Rm，称为“慢组”。
          理由：既然回送的人不在这一批，那么本次过河的人不会影响本次返回的成本；至于未来返回的成本问题，留给未来过河的时候去考虑。
          本次过河只需考虑对全局利益最大化的一批人。Rm这个人无论什么时候过河，他的成本都是Tm, 所以我们这时候挑选最慢的N人，不会提高总体时间，而且顺带还解决了最可能影响总体速度的那N-1人。
    2.2.2 本次要返回的人，在此m人之中。那么由1的推论，我们应该选择R1作为本次返回的人。R1过河的时候，总人数k可以从2..n不等。最佳策略是挑选最快的k人。
          反证法：假设本次有若干“慢”人不在R1..Rn中，最慢的设为Ri, i>n, 则可以肯定这些人也不会是P1..Pn中的人。现在要证明这样做的结果不会比最佳策略更好。
          理由：
          A.这些“慢”人并不会减少往返次数（桥的容量n并未增加，最佳策略k覆盖了2..n的所有情形）;
          B.这些“慢”人使得本次过河的成本从Tk上升为Ti; 但这样的调整也有可能调低未来的过河成本，剩下的任务就是证明这种影响总体上没有好处。
            2.2.2.1 某“慢”人本该被“慢组”所覆盖：
                    2.2.2.1.1 他是“慢组”中的最慢：那么调整使得该组时间有所下降，但他却连累了快组从Tk上升为Ti，比较两种策略，所有这样的“慢”人所节省的时间之和不可能超过增加的幅度Ti-Tk, 因此这种调整不合算。
                    2.2.2.1.1 他不是“慢组”中的最慢：那么本次调整并没有影响慢组的时间，反而白白连累了快组, 因此这种调整不合算；
            2.2.2.2 此人本该被“快组”所覆盖：这样的调整只是对调了某些顺序，不会超出最佳策略所覆盖的范围。

newkid

yushusong 发表于 2012-4-11 17:29
将速度相近的、最慢的放在一起走，返回要用最快的

前面已经证明这种算法对1,98,99,100 无效了。

newkid

点评69楼guostong的答案, 希望作者修改：

column name format a10;
column name_BACK format a10;
column name_HIST format a20;

var num number;

------ num 为每次过河的人数限制
exec :num := 3;

with
t_accessory (totalsteps, cnt, md) as
(
    select ceil((count(1)-1)/(:num-1)) + ceil((count(1)-1)/(:num-1)) - 1 totalsteps ---- 这个totalsteps用来限制总步数，它的前提是每次过河都是尽可能更多的人，但这个前提是错的，有时候过河的人更少反而节省总体的时间, 例子见94楼。
          , count(1) cnt
          , mod(count(1)-1,2) md ------ 总人数是奇数还是偶数
     from bridge_crossing
),
t_positions (name, time, ps, od) as
(
   select name, time, power(2,row_number() over (order by name) -1) ps,  ---- 每个人编为二进制的一位。
     rank() over (order by time) od  --------- 按速度排序，用的是RANK()所以相同速度的人会有相同的序号, 可考虑改为ROW_NUMBER()
     from bridge_crossing
),
t_combinations ( name, ps, p_ps, time, step, od ) as ------- 用递归的方法生成 1~num人的所有组合，每种组合需要耗费的时间。
(
   select name, ps, ps, time, 1 step, od from t_positions
   union all
   select t.name||' ' || b.name, t.ps + b.ps, b.ps, greatest(t.time, b.time), step + 1, t.od
   from t_combinations t, t_positions b
   where b.ps > t.p_ps and t.step < :num
),
steps (name, ps, name_hist, name_back, ps_back, time, step) as
---- 用递归的方法模拟过河的每一步, name: 已过河的人名单 ps:已过河的人的二进制之和，name_hist: 过河名单历史
----- name_back: 返回的人名单历史    ps_back:最近一次返回的人的二进制编号 time:已用总时间  step: 用了几步
---- 因为用了BITAND操作，这几个列已经毫无意义：name, name_back, ps_back 可以考虑去掉。
(
    -- step 1
    select name,ps, name, '', 0, time, 1
     from t_combinations where step = :num  -------- 假设第一步总是过去最多的人, 这个也有问题
    union all
    select
       case when mod(s.step,2) = 1 then replace(s.name, c.name) --- s.step 为奇数，意味着返回，从河对岸的名单s.name去除返回人c.name, 此处前提是所有人名不出现互相包含的情况，比如有人叫A,另一人叫AA这样的。
            else s.name || c.name ---- 如果s.step 为偶数则意味着过去, 把名单并入到过河名单中
       end name,
       case when mod(s.step,2) = 1 then s.ps - c.ps --- 类似上面，用的是二进制的和来表示哪些人已过河。返回的扣减，过河的增加
            else s.ps + c.ps
       end ps,
       s.name_hist||','|| c.name, ----- 过河名单历史
       case when mod(s.step,2) = 1 then s.name_back || c.name ----- 如果是返回，则增加返回的人名单历史
            else s.name_back  ------ 如果是过河，则无须修改这个返回名单历史
       end name_back,
       case when mod(s.step,2) = 1 then c.ps ----- 最近一次返回的人的二进制编码
            else 0
       end ps_back,
       s.time + c.time, s.step + 1
     from steps s, t_combinations c, t_accessory a
     where s.step < a.totalsteps  -----限制总步数不能超过计算值，但有时候过河的人更少反而节省总体的时间, 例子见94楼。建议修改递归出口条件为 s.ps<>power(2, cnt) - 1
     -- back
     and (  ---------- 如果是返回，则总是单人(c.step = 1)并且是速度靠前的那些人(用c.od 判断)
           (mod(s.step,2) = 1 and bitand(s.ps, c.ps) > 0 and c.step = 1 and c.od <= :num)
     -- forward
           or
           (mod(s.step,2) = 0 and bitand(s.ps, c.ps) = 0
            and( ----- 如果不是最后一步，或者最后一步且总人数为偶数（这个没什么道理？），则过河人数总是选最多的num人。这个不一定成立，反例见94楼
                 (a.totalsteps > s.step + 1 or a.totalsteps = s.step + 1 and a.md = 0 ) and c.step = :num
                 or ----- 如果是最后一步，并且总人数为奇数（这个也没什么道理？）, 则剩下的人全部过河
                  a.totalsteps = s.step + 1 and a.md <> 0 and c.step < case when :num=2 then 3 else :num end
                 and s.ps + c.ps = power(2, cnt) - 1
                )
           )
         )
)
select * from
(
   select steps.*, row_number() over (order by steps.time) od from steps, t_accessory t
   where step = t.totalsteps order by time
) where od <= 10;

guostong

newkid 发表于 2012-4-12 15:03
点评69楼guostong的答案, 希望作者修改：

column name format a10;

谢谢点评，要消化一下。

guostong

根据newkid的点评，已更正：


column name_HIST format a20;

var num number;
------ num 为每次过河的人数限制
exec :num := 3;
with
t_accessory (total_ps, cnt, md) as
(
     select power(2, count(1)) - 1 as ps ---- 放弃total_steps， 改用power(2, count(1)) - 1
           , count(1) cnt
      from bridge_crossing  
),
t_positions (name, time, ps, od) as
(
    select name, time, power(2,row_number() over (order by name) -1) ps,  ---- 每个人编为二进制的一位。
      row_number() over (order by time, name) od  --------- 根据耗时排序
      from bridge_crossing
),
t_combinations ( name, ps, p_ps, time, step, od ) as ------- 用递归的方法生成 1~num人的所有组合，每种组合需要耗费的时间。
(
    select name, ps, ps, time, 1 step, od from t_positions
    union all
    select t.name||' ' || b.name, t.ps + b.ps, b.ps, greatest(t.time, b.time), step + 1, t.od
    from t_combinations t, t_positions b
    where b.ps > t.p_ps and t.step < :num
),
steps (ps, name_hist, time, step) as
---- 用递归的方法模拟过河的每一步, name: 已过河的人名单 ps:已过河的人的二进制之和，name_hist: 过河名单历史
-----time:已用总时间  step: 用了几步
(
     -- step 1
     select ps, name, time, 1
      from t_combinations where step > 1  -------- 假设第一步总是过去最多的人, 这个也有问题 (已更正，第一步过去至少2个人)
     union all
     select
        case when mod(s.step,2) = 1 then s.ps - c.ps --- 类似上面，用的是二进制的和来表示哪些人已过河。返回的扣减，过河的增加
             else s.ps + c.ps
        end ps,
        s.name_hist||','|| c.name, ----- 过河名单历史
        s.time + c.time, s.step + 1
      from steps s, t_combinations c, t_accessory a
      where s.ps <> a.total_ps  -----由s.step < a.totalsteps 改为 s.ps<>power(2, cnt) - 1
      -- back
      and (  ---------- 如果是返回，则总是单人(c.step = 1)并且是速度靠前的那些人(用c.od 判断)
            (mod(s.step,2) = 1 and bitand(s.ps, c.ps) > 0 and c.step = 1 and c.od <= :num)
      -- forward
            or
            (mod(s.step,2) = 0 and bitand(s.ps, c.ps) = 0
             and c.step > 1 -- 不一定过最多的人, 但至少2人
            )
          )
)
select * from
(
   select steps.name_hist, steps.time, row_number() over (order by steps.time) od
   from steps, t_accessory a
   where steps.ps = a.total_ps
) where od <= 10;

newkid

这里来个修改怎么样？只选已过河的最快的人返回，其他人就不用尝试了。
c.od <= :num
修改为 c.od = (SELECT MIN() .. WHERE BITAND()...) 类似我在137楼的修改。
如果你在t_positions中的ps是按速度排序的，则od就完全没有必要出现了，直接选最小的已过河的PS就是。

guostong

-- od 已经去掉了

column name_HIST format a20;

var num number;
------ num 为每次过河的人数限制
exec :num := 3;
with
t_accessory (total_ps, cnt) as
(
     select power(2, count(1)) - 1 as ps -- 放弃total_steps
           , count(1) cnt
      from bridge_crossing  
),
t_positions (name, time, ps) as
(
    select name, time, power(2,row_number() over (order by time) -1) ps  ---- 每个人编为二进制的一位。
      from bridge_crossing
),
t_combinations ( name, ps, p_ps, time, step ) as ------- 用递归的方法生成 1~num人的所有组合，每种组合需要耗费的时间。
(
    select name, ps, ps, time, 1 step from t_positions
    union all
    select t.name||' ' || b.name, t.ps + b.ps, b.ps, greatest(t.time, b.time), step + 1
    from t_combinations t, t_positions b
    where b.ps > t.p_ps and t.step < :num
),
steps (ps, name_hist, time, step) as
---- 用递归的方法模拟过河的每一步, name: 已过河的人名单 ps:已过河的人的二进制之和，name_hist: 过河名单历史
-----time:已用总时间  step: 用了几步
(
     -- step 1
     select ps, name, time, 1
      from t_combinations where step > 1  -------- 假设第一步总是过去最多的人, 这个也有问题 (已更正，第一步过去至少2个人)
     union all
     select
        case when mod(s.step,2) = 1 then s.ps - c.ps --- 类似上面，用的是二进制的和来表示哪些人已过河。返回的扣减，过河的增加
             else s.ps + c.ps
        end ps,
        s.name_hist||','|| c.name, ----- 过河名单历史
        s.time + c.time, s.step + 1
      from steps s, t_combinations c, t_accessory a
      where s.ps <> a.total_ps  -----由s.step < a.totalsteps 改为 s.ps<>power(2, cnt) - 1
      -- back
      and (  ---------- 如果是返回，则总是单人(c.step = 1)            
             (mod(s.step,2) = 1 and bitand(s.ps, c.ps) > 0 and c.step = 1
              -- 选已经过的人中最快的人返回
             and c.ps = (select min(ps) keep (DENSE_RANK FIRST ORDER BY time) from t_positions tt where bitand(tt.ps, s.ps) > 0 )
            )
      -- forward
            or
            (mod(s.step,2) = 0 and bitand(s.ps, c.ps) = 0
             and c.step > 1 -- 不一定过最多的人, 但至少2人
            )
          )
)
select * from
(
   select steps.name_hist, steps.time, row_number() over (order by steps.time) od
   from steps, t_accessory a
   where steps.ps = a.total_ps
) where od <= 10;