Lecture 1-2

P19.Optimizing and heuristic algorithms

最优解（优化算法）和启发式的区别、原因

相关知识点

有关optimization的三个定义
- optimization problem: can be described as the problem of finding the best solution from the set of all feasible solutions in some real or imagined scenario.
- optimization model: can be described as a mathematical representation of optimization problem. It consists of parameters, decision variables, objective function and constraints.
- optimization method: is an algorithm that is applied in order to solve an optimation problem.

最优解和启发式的区别

Optimizing and heuristic alogirithms
- There are two categories of algorithms for sloving optimization problems
  - Optimizing: Guarantees to find the optimal solution
  - Heuristic: Does not guarantee to find the optimal solution, but usually generates a "good" solution within a reasonable amount of time.
- Typically, heuristics can be stated as rules of thumb(经验法则) and they are often designed for a specific problem.

P20.Why heuristics?

为什么要选择启发式

得到最优解要消耗大量计算资源
- An optimizing algorithm might consume too much resources.
输入可能不是很准确，而启发式算法有较强的鲁棒性，能够找到一个不错的解
- Input to algorithm might be inaccurate and a heuristically good solution might be good enough.
启发式算法更容易理解
- For a non-expert, it might be easier to uderstand a heuristic rather than an optimizing algorithm.

P22.Constructive heuristics(建设性启发式)

均匀分布，在某个范围内等概率生成某些数
步骤、过程，step0-2、了解一下流程图

定义

A constructive heuristic is a method that iteratively "builds up" a solution.（迭代地构建解决方案）

怎么构建

Assuming that a solution consists of solution components, it starts with nothing and adds one value of exactly one variable(恰好一个变量的值) in each iteration.
详细描述
Let $x = (x_1, x_2, x_n)$ denote a solution to our problem
- 对应上面的Assuming a solution consists of solution components
step0: Initialization: Begin with all free solution $x^{(0)} = (-, ..., -)$ and set solution index t = 0
- 对应上面的start with nothing
step1: Termination criteria: If t = n, then break with approximate optimum (近似最优) $x = x^{(t)}$
- 对应下方的终止条件
setp2: Choose a solution component $x_p$ and a value for $x_p$ that plausibly(似真的) leads to a good feasible solution at termination.
Set $x^{(t+1)}$ = $x^{t}$ but with fixed variable $x_p$
Set solution index t = t+1, and go to step1
- 选择一个解决方案组件xp，并为xp选择一个值，该值似乎可以在终止时提供一个良好的可行解决方案。
- 对应于上面的adds one value of exactly one variable in each iteration

结束条件

The algorithm ends when all variables have been assigned a value.

用途

... are used to generate a feasible starting solution which can be improved by other algorithm later on.

P24.Greedy algorithm

构造启发式的一种自然且常见的类型是贪婪算法

A natural, and common type of constructive heuristics is greedy algorithms.
- Each variable fixings(变量固定值) is choosen as the variable that locally improve the objective most.
- Of course, variable fixings are choosen without breaking feasibility.

P26-.Huffman’s algorithm

哈夫曼编码、文字压缩
Huffman's algorithm - A greedy, constructive, algorithm for text compression.
Huffman's algorithm is a greedy algorithm that identifies the optimal code for a particular character set and text to code.(只需记住它是一种贪婪算法)

P29.Graph

图的定义

A graph is a set of objects that are connected to each other through links.

P31.Binary tree

什么是树

两种定义方式
- A tree is an undirected graph where each pair of vertices is connected by exactly one path.
- A tree connected with n vertices and n-1 edges.

什么是二叉树

A binary tree is a rooted tree in which no node has more than two children.

P35.Tries(prefix trees)

什么是Tries

Character codes can be represented using a special type of tree.
In a tries, each node is associated with a string and each edge is labeled with a sequence of characters.
The root is an empty node.
The value of a node is concatenating the value of its parent with the character sequence on the edge connecting it with the parent.

P36.Definition - Prefix

什么是前缀、后缀

A prefix can be described as a starting of a word.

举例：zhuyun的前缀
zhuyun
zhuyu
zhuy
zhu
zh
z

什么是前缀码

No character code is a prefix of another character code. This type of encoding is called prefix code.

给出字符串、能够写出前缀后缀、注意不止一个、是有一系列的前缀(上方的举例中有)

P42-.Huffmans’s algorithm

给一个例子，然后画出过程，构建huffman🎄

P43~P50中有例子

P58.Neighborhood search

用来求解背包问题(18年新题目)、把背包问题描述成数学的形式、自己写一遍算法、写出计算步骤

定义邻居
- 如果是在一维坐标轴上的实数
  - $N ( \overline { x } ) = \left\{ x \in \mathbb { R } ^ { 1 } : | x - \overline { x } | \leq 1 \right\}$
- 如果是二维坐标
  - $N ( \overline { x } , \overline { y } ) = \left\{ ( x , y ) \in \mathbb { R } ^ { 2 } : \sqrt { ( x - \overline { x } ) ^ { 2 } + ( x - \overline { y } ) ^ { 2 } } \leq 1 \right\}$
背包问题
- Parameters:
  - n: The number of items
  - l: {1, ..., n} Index set over the n items
  - $p_i$ : The value of item i
  - $w_i$ : The weight of item i
  - W: The weight capacity of the knapsack
- Decision variables:
  - $x _ { i } \in \{ 0,1 \}$
  - $x_i = 1$ if the item is chosen
  - $x_i = 0$ if the item is not chosen
- Objective function:
  - Maximize $\sum _ { i \in 1 } p _ { i } x _ { i }$
- Constraints:
  - $\sum _ { i \in l } w _ { i } x _ { i } \leq W$
  - $x _ { i } \in \{ 0,1 \} \quad \forall i \in l$
Example:
- Maximize:
  - $\sum _ { i = 1 } ^ { 4 } 4 x _ { 1 } + 10 x _ { 2 } + 5 x _ { 3 } + 8 x _ { 4 }$
- Subject to:
  - $\sum _ { i = 1 } ^ { 4 } 3 x _ { 1 } + 9 x _ { 2 } + 4 x _ { 3 } + 6 x _ { 4 } \leq 12$
  - $x _ { i } \in \{ 0,1 \} \quad \forall i \in \{ 1,2,3,4 \}$

构建数学模型
- Parameters:
  - n: 4
  - l: {1, 2, 3, 4}
  - p: {4, 10, 5, 8}
  - w: {3, 9, 4, 6}
  - W: 12
- Decision variables:
  - $x _ { i } \in \{ 0,1 \}$
- Subjective function:
  - MAX $\sum _ { i = 1 } ^ { 4 } 4 x _ { 1 } + 10 x _ { 2 } + 5 x _ { 3 } + 8 x _ { 4 }$
- Constraints:
  - $\sum _ { i = 1 } ^ { 4 } 3 x _ { 1 } + 9 x _ { 2 } + 4 x _ { 3 } + 6 x _ { 4 } \leq 12$
求解

x(0) = [0 0 1 0]T      Z = 5

N(x(0))  [1 0 1 0]T      Z = 9

            [0 1 1 0]T      infeasible

            [0 0 0 0]T      Z = 0

            [0 0 1 1]T      Z = 13

x(1) = [0 0 1 1]T

N(x(1))  [1 0 1 1]T     infeasible

            [0 1 1 1]T      infeasible

            [0 0 0 1]T      Z = 8

            [0 0 1 0]T      Z = 5

break

x(1) is local optimal

P89.Tabu search （不确定会考）

哪些要、哪些不要

x(0) = [0 0 1 0]T      Z = 5               tabu:None

N(x(0))  [1 0 1 0]T      Z = 9

            [0 1 1 0]T      infeasible

            [0 0 0 0]T      Z = 0

            [0 0 1 1]T      Z = 13

x(1) = [0 0 1 1]T                             tabu: x(0)

N(x(1))  [1 0 1 1]T     infeasible

            [0 1 1 1]T      infeasible

            [0 0 0 1]T      Z = 8

            [0 0 1 0]T      Z = 5 (不选，this is tabu)



x(2) = [0 0 0 1]                                tabu:x(1)

N(x(2))  [1 0 0 1]   Z = 12

             [0 1 0 1]   infeasible

             [0 0 1 1]   tabu

             [0 0 0 0]    Z = 0

...

P108.Recursion

定义

A function that is defined in terms of itself is called recursive.
Recursive functions require at least one base case
- A base case is an input value for which the function can be calculated without recursion.
- Without a base case it is not possible to terminate the calculation of a recursion function.
- 什么是base case（考点）：base case是一个(输入)值，不需要递归就可以为其计算函数。

举例

Example: f(x) = 2f(x -1) , where f(0) = 0 (x >= 0), f(0)=0为base case

递归的基本规则

Fundamental rules of recursion:
- Base cases: There needs to be at least one base case, which can be solved whithout recursion.
- Progress: For the cases that are solved using recursion, recursive calls must progress towards a base case.

P119.Mergesort

先分解再合并排序的过程
写出每步步骤

分治divide-and- conquer

Divide-and-conquer is an algorithm design technique based on recursion.
分治是一种基于递归的算法设计技术。
Divide: Smaller problems are solved recursively
Conquer: The solutions to the original problem is found by combining the solutions to the (smaller) subproblems.
- 原问题的解是由(较小的)子问题的解的组合得到的。

P133.Dynamic Programming

动态规划找出最优解、相比贪心算法的优点

P138

不选、选、画出图、动态规划要掌握该图
背包问题的动态规划图

图一定要会画（必考）