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?

为什么要选择启发式

1. 得到最优解要消耗大量计算资源
   • An optimizing algorithm might consume too much resources.
2. 输入可能不是很准确，而启发式算法有较强的鲁棒性，能够找到一个不错的解
   • Input to algorithm might be inaccurate and a heuristically good solution might be good enough.
3. 启发式算法更容易理解
   • 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 denote a solution to our problem

  • 对应上面的Assuming a solution consists of solution components

• step0: Initialization: Begin with all free solution and set solution index t = 0

  • 对应上面的start with nothing

• step1: Termination criteria: If t = n, then break with approximate optimum (近似最优)

  • 对应下方的终止条件

• setp2: Choose a solution component and a value for that plausibly(似真的) leads to a good feasible solution at termination.

• Set = but with fixed variable

• 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年新题目)、把背包问题描述成数学的形式、自己写一遍算法、写出计算步骤

• 定义邻居
  • 如果是在一维坐标轴上的实数
  • 如果是二维坐标
• 背包问题
  • Parameters:
    • n: The number of items
    • l: {1, ..., n} Index set over the n items
    • : The value of item i
    • : The weight of item i
    • W: The weight capacity of the knapsack
  • Decision variables:
    • if the item is chosen
    • if the item is not chosen
  • Objective function:
    • Maximize
  • Constraints:
• Example:

  • Maximize:

  • Subject to:

---

• 构建数学模型

  • Parameters:

    • n: 4
    • l: {1, 2, 3, 4}
    • p: {4, 10, 5, 8}
    • w: {3, 9, 4, 6}
    • W: 12

  • Decision variables:

  • Subjective function:

    • MAX

  • Constraints:

• 求解

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

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

• 图一定要会画（必考）