《趣学算法》学习打卡:Day1

《趣学算法》学习打卡:Day1

• 《趣学算法》学习打卡:Day1
  • 1、算法是什么？
  • 2、贪心算法：寻找最优解（最优解的近似解）
  • Day1总结：

1、算法是什么？

算法是程序的灵魂，研究算法就是研究程序运行时，所需要时间和空间，所以评判算法的好坏就是从：时间复杂度和空间复杂度；理所当然，时间复杂度和空间复杂度越低越好ya，越低说明算法的质量很高。研究算法的目的，就是为了提高程序代码的质量，使程序完成一个相同的功能时，所需要的时间和空间尽可能的小，到达最优！

2、贪心算法：寻找最优解（最优解的近似解）

这个最优指的是程序运算的结果，而不是时间空间的最优（当然在结果最优不变下，时间空间最优也是我们最求的目标）

贪心策略：局部最优——全局最优；子问题最优——问题最优

相关贪心算法的例子

• 冒泡排序

  每次选择未被选择的最大的数，然后把它放到数组最后面，就形成从小到大的排序。贪心：选择最大的，放在最后面，从局部最优到全局最优。

  ---

• 加勒比海盗船——最优装载问题

  有n件宝物，宝物的重量不一，船的载重有限，怎样在有限的载重下搭载最多的宝物（件数最多）；

  宝物打碎一文不值

  1. 把宝物按照重量从轻到重排好序
  2. 每次选择当前最轻的宝物装载，并把当前已经装载的宝物重量之和与限重比较，得出能否装载，能就把装载宝物件数加一，不能则程序结束。

  ---

• 阿里巴巴与四十大盗——背包问题（0-1背包问题）

  有n件宝物，宝物有自己的重量和价值，其中宝物的重量可以拆卸，其对应的价值和它的重量挂钩（即宝物不会存在因为分开，而价值发生变化），背包只能装载一定的重量。

  宝物打碎价值不变，取走的价值按比例来，如：1kg宝物10万元，但是我现在只能装0.5千克，所以我取走0.5千克，价值5万

  1. 把宝物的价值/重量得到单位重量下的价值，按照单位重量下的价值进行排序（从大到小）
  2. 装载，按照单位重量价值排序装载，当背包装满的时候，其背包里的价值，一定是最大价值！

  ---

  • 0-1背包问题

    背包限载重量，宝物有价值和重量两个属性，其中（0-1）就表示，宝物不可以拆卸，所以不仅要考虑装入的重量尽可能接近限载重量，还要考虑装入的价值是不是最大的

    0-1背包问题具有贪心选择性质，原问题的整体最优解无法通过一系列的局部最优的选择的得到，即选择装载重量时，不一定的到最优解，当选择价值时，也不一定得到最优解。

    ---

• 高级钟点秘书——会议安排

  会议具有起始时间和结束时间，一个会议的结束时间可以是一个会议的起始时间（安排合理），如何在一天内，安排尽可能多的会议？

  会议时间表：

  会议（i）	1	2	3	4	5	6	7	8	9	10
  开始时间（b）	8	9	10	11	13	14	15	17	18	16
  结束时间（e）	10	11	15	14	16	17	17	18	20	19

  gantt dateformat HH title 会议时间甘特图 会议1:08,10 会议2:09,11 会议3:10,15 会议4:11,14 会议5:13,16 会议6:14,17 会议7:15,17 会议8:17,18 会议9:18,20 会议10:16,19

  从甘特图我们可以直观的看到，有的会议时间是冲突的，所以想在一天内安排尽可能多的会议，就要考虑会议的开始时间和结束时间，以及会议时长。

  贪心策略：

  1. 每次从未安排的会议中选择具有最早开始时间且与已安排会议不冲突的会议安排，以增大时间资源的利用率。
  2. 每次从未安排会议中选择会议持续时间最短的且与已安排会议不冲突的会议，这样可以安排多一些会议。
  3. 每次从未安排的会议中选择具有最早结束时间且与已安排会议不冲突的会议，这样可以尽快安排下一个会议。

  最早开始时间+持续时间最短==最早结束时间所以采用第三种贪心策略

  ---

• 一场说走就走的旅行-——最短路径问题（涉及图）

  艾兹格 · W ·迪科斯彻（Edsger Wybe Dijkstra），荷兰人，计算机科学家，Dijkstra算法是解决单源最短路径问题的贪心算法

  1. 把所有的顶点分为两个集合，已选顶点（初始时为源点）集合S和未选顶点（结束时为空）V_S
  2. 用一个数组（list）记录从源点到顶点的距离
  3. 用一个数组（p）记录顶点的前驱（怎么有点像链表呀？借用作者书里的一句话：“不是六郎似荷花，而是荷花似六郎”）
  4. 用一个值u表示当前起点

  这个图还不会画（/狗头）

  S	V_S
  1	2，3，4，5

  图的邻接矩阵：map[][]

  ∞	2	5	∞	∞
  ∞	∞	2	6	∞
  ∞	∞	∞	7	1
  ∞	∞	2	∞	4
  ∞	∞	∞	∞	∞

  当前起点：u=1；

  根据map[1][]来初始化list[]

  注意list[]的更新是没换一次就更新一次；但是更新不代表一定有改变，即满足条件的时候就更新！

  list[i]	1	2	3	4	5
  	0	2	5	∞	∞

  p[i]	1	2	3	4	5
  	-1	1	1	-1	-1

  没有前驱的记为-1

  每次选择离当前起点（不一定是源点）最近的点

  根据V_S查找list中的最小值；顶点2的list最小=2；

  更新起点：u=2

  更新S，V_S;

  1，2	3，4，5
  S	V_S

  更新list:

  想了想，还是解释一下这句话：map[2[3]+list[2]=2+2=4

  map[2][3]+list[2]=2+2=4<5=list[3],所以顶点3的前驱和list值都要改变，list[3]=4;p[3]=2;

  map[2][4]+list[2]=2+6=8<∞=list[4];所以顶点4的前驱和list值都要改变,

  list[4]=8;p[4]=2

  list[i]	1	2	3	4	5
  	0	2	4	8	∞

  p[i]	1	2	3	4	5
  	-1	1	2	2	-1

  重复以上步骤直到V_S{}集合为空；就可以得到源起点到各个顶点的集合了，当源起点发生变化时，如u=2为源起点时，你会发现程序不会受到影响，它同样可以检索出，源起点（顶点2）到其他顶点的距离，因为我们把顶点分成了两个集合，我们是根据集合去检索的，与源起点是不是1没有关联。

  ---

• 神秘电报密码——哈夫曼编码

  day2

  ---

• 沟通无限校园网——最小生成树

  day3

  ---