一. 算法设计模式

  • 枚举 或者说 暴力求解 （Brute force）
  • 分治法（Divide and conquer）
  • 贪婪算法（Greedy approach）
  • 动态规划（Dynamic programming）
  • 回溯法（Backtracking）
  • 分支定界法（Branch and bound）
  • 概率算法（Randomized algorithm）

二. 算法思维

1.什么是算法思维？

现实问题——》形式化描述——》设计算法——》方案实施——》现实问题

2.算法思维解决实际问题的步骤

  • Understand the problem（理解）
  • Formulate it（制定）
  • Design algorithm（设计）
  • Implment it（实现）
  • Run the code and solve the original problem（运行）

三.实例-交通信号设计

1.表示输入（冲突网络）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 *	String 表示通行方向 “AB”，“AC” ......
 *	LinkedList<String> 表示一个节点（通行方向）的所有邻接节点（即冲突的通行方向）
 *	HashMap<String,LinkedList<String>>表示通行冲突网络（每个节点及其对应的冲突通行方向链表）
 */
HashMap<String, LinkedList<String>> traffic_conflict = new HashMap<>();

traffic_conflict.put("AB", new LinkedList<String>(Arrays.asList("BC", "BD", "DA", "EA")));
traffic_conflict.put("AC", new LinkedList<String>(Arrays.asList("BD", "DA", "DB", "EA", "EB")));
traffic_conflict.put("AD", new LinkedList<String>(Arrays.asList("EA", "EB", "EC")));
traffic_conflict.put("BA", new LinkedList<String>());
traffic_conflict.put("BC", new LinkedList<String>(Arrays.asList("AB", "DB", "EB")));
traffic_conflict.put("BD", new LinkedList<String>(Arrays.asList("AB", "AC", "DA", "EB", "EC")));
traffic_conflict.put("DA", new LinkedList<String>(Arrays.asList("AB", "AC", "BD", "EB", "EC")));
traffic_conflict.put("DB", new LinkedList<String>(Arrays.asList("AC", "BC", "EC")));
traffic_conflict.put("DC", new LinkedList<String>());
traffic_conflict.put("EA", new LinkedList<String>(Arrays.asList("AB", "AC", "AD")));
traffic_conflict.put("EB", new LinkedList<String>(Arrays.asList("AC", "AD", "BC", "BD", "DA")));
traffic_conflict.put("EC", new LinkedList<String>(Arrays.asList("AD", "BD", "DA", "DB")));
traffic_conflict.put("ED", new LinkedList<String>());

2.表示输出 （通行方向分组）

1
2
3
4
5
6
7
8
9
10
11
/**
 *	LinkedList<LinkedList<String>>表示各个分组，每个分组为互不冲突的通行方向。
 */

//调用函数解决问题
LinkedList<LinkedList<String>> trafficGroups = TrafficPlanner.getTrafficGroups(traffic_conflict);

//打印数据
for (LinkedList<String> oneGroup : trafficGroups) {
		System.out.println(oneGroup.toString());
}

3.算法（从冲突网络到通行分组）

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
public class TrafficPlanner {
    public static LinkedList<LinkedList<String>> getTrafficGroups(HashMap<String, LinkedList<String>> traffic_conflict){
        //产生空白通行分组
        LinkedList<LinkedList<String>> groups = new LinkedList<>();

        //产生互不冲突且完全覆盖的通行分组
        LinkedList<String> roadSet = new LinkedList<>(traffic_conflict.keySet());
        while (roadSet.size() > 0){
            LinkedList<String> oneGroup = new LinkedList<>();
            String road = roadSet.get(0);
            oneGroup.add(road);
            roadSet.remove(road);

            Iterator<String> roadSetIterator = roadSet.iterator();
            while (roadSetIterator.hasNext()){
                String roadToAdd = roadSetIterator.next();

                if (checkNoConflict(roadToAdd, oneGroup, traffic_conflict)){
                    oneGroup.add(roadToAdd);

                    roadSetIterator.remove();
                }
            }
            groups.add(oneGroup);
        }

        //保证不冲突全覆盖后，将与每组不冲突的方向全部通行
        for (LinkedList<String> group : groups) {
            for (String road : traffic_conflict.keySet()) {
                if (checkNoConflict(road, group, traffic_conflict)){
                    group.add(road);
                }
            }
        }

        return groups;
    }

    /**
     * 判断新加的通行方向是否与本组已有方向冲突
     * @param roadToAdd
     * @param oneGroup
     * @param traffic_conflict
     * @return
     */
    private static boolean checkNoConflict(String roadToAdd, LinkedList<String> oneGroup, HashMap<String, LinkedList<String>> traffic_conflict){
        for (String road : oneGroup) {
            //是否和已存在的相冲突或者是否已存在
            if (traffic_conflict.get(road).contains(roadToAdd) || road.equals(roadToAdd)){
                return false;
            }
        }

        return true;
    }
}