算法作业 _ 7_袁胜_2016M8009073008

Python

基本思路

通过题目中原图，构造如下字典用于记录待考察的相容线段集合：
Key: 序号
Value: 候选的相容线段集合列表。
构造完成后，选取其中最长的候选线段集合，即为所求的最大相容线段集合。

添加新候选列表的条件

• Dict 为空，即算法最开始的时候，新建一个 List，将第一条线段放入 List。
• 当前 Dict 中所有线段与新线段new皆相交，则新建一个 List，将新线段new放入。
• 当前 Dict 中所有 List 的末尾线段均与新线段new相交， 则寻找题目图中，位于new左侧，且距离new最近的不相交线段l；将当前 Dict 中所有 List 中，包含 l 的 List，取 list[0..l]；再将新线段接到末尾，新建 List 插入到 Dict 之中。即构建目前存在的所有 List[0..l,new]，依次插入到 Dict 中。

将新线段插入当前存在 List 末尾的条件

• 当前Dict 的 List 中，末尾线段与新线段 new 不相交的，全部插入。

因为题目中的相交条件是$i < j$且$\pi(i) > \pi(j)$，或者$i > j$且$\pi(i) < \pi(j)$，所以，如果在新线段new左侧找到一条相容线段l，则l 左侧所有与 l 相容的线段，皆与新线段 new 相容。即该子问题求解满足动态规划法需求中的无后效性。

这样经过[1..n]的1次循环考察，就构建了上图所示的 Dict，从中可以找出题目的最大相容线段集合。

伪码

Algorithm MaxNoCross(A[]):
  n <- Lenght(A);
  Dict <- 存储所有候选 List 的字典；
  for (i in 0..n-1):
    if Cross(All line in Dict, A[i]) || Dict.Empty():
      Dict.Add(new List(A[i]));
    else:
      Guard <- False; // 监视是否有直接可插入的 List
      foreach List in Dict:
        if !Cross(List末尾线段, A[i]):
          List.Append(A[i]);
          Guard <- True;
        end
      end
      if !Guard:
        l <- 位于A[i]左侧，且距离A[i]最近的不相交线段
        foreach List in Dict:
          if List.Contains(l):
            Dict.Add(List[0..l,A[i]]);
          end
        end
      end
    end
  end
  return LongestList(Dict);
end

时间复杂度分析

最坏情况，即每次考察新线段，当前 Dict 中所有线段与新线段皆相交。这样每次都要对比一遍目前已考察的所有线段。
令一次比较2线段是否相交的时间复杂度为 $O(1)$，则最坏情况下时间复杂度