2021-08-30 20:26 已编辑北京城市学院测试工程师

关注

计算机原理基础

1、求解整数规划有什么方法，都介绍一下

（1）分枝定界法：

对有约束条件的优化问题（其可行解为有限数）的所有可行解空间恰当地进行系统搜索，即为分枝定界的内容。通常把全部可行解空间反复地分割为越来越小的子集，称为分枝；并且对每个子集内的解集计算一个目标下界（对于最小值问题），称为定界。在每次分枝后，凡是界限超出已知可行解集目标值的那些子集不再进一步分枝，这样许多子集可以不予考虑，称为剪枝。

求解步骤：将要求解的整数规划问题称为问题A，将与它相应的线性规划问题称为问题B

用观察法找问题A的一个整数可行解，一般可取 $x_j=0, j=1, ..., n$ 求得其目标函数值，记为 $z_1$ ，以 $z_2$ 表示问题A的最优目标函数值；有 $z_1≤z_2≤z_3$ 进行迭代。( $z_3$ 为B有最优解的情况下，但不符合问题A的整数条件，记为的目标函数值)。

第一步：分枝，在B的最优解中任选一个不符合整数条件的变量 $x_j$ , 其值为 $b_j$ ，以 $[b_j]$ 为小于 $b_j$ 的最大整数，构造两个约束条件： $x_j ≤ [b_j]$ ，和 $x_j ≥ [b_j]+1$ 。

将这两个约束条件，分别加入问题B，求两个后继规划问题B1和B2。

定界，以每个后继问题为一分枝标明求解的结果，与其他问题的解的结果中，找出最优目标函数值最大者作为新的上界 $z_2$ ，从已符合整数条件的各分枝中，找出目标函数值为最大作为新的下界 $z_1$ ，若无可行解 $z_1=0$ 。

第二步：比较与剪枝，各分枝的最优目标函数中若有小于 $z_1$ 者，则剪掉，若大于，且不符合整数条件，则重复步骤一，一直到最后 $z_1=z_2$ 为止，得最优整数解

$x_j=2$ ，j=1,…,n

（2）过滤隐枚举法（求解0-1整数规划）

解0-1整数规划常规考虑穷举法，但是当变量个数较大，则复杂度决定了不能这么办。所以考虑只检查变量取值的组合的一部分，就能求到问题的最优解，即为隐枚举法。

例：

求解思路：

先试探求一个可行解，易得 $(x_1, x_2, x_3)=(1, 0, 0)$ 满足约束条件，且z=3。
因为是求极大值问题，故求最优解时，凡是目标值小于3的解不必再检验即可删除，于是增加约束条件即目标值下界。
由于对每个组合首先计算目标值以验证过滤条件，故应优先计算目标值z大的组合，这样可提前抬高过滤门槛，以减少计算量。

（3）割平面法（以依据Gomory的割平面法为例）

首先求解非整数约束的线性规划，再选择一个不是整数的基变量，定义新的约束，增加到原来的约束中，新的约束缩小了可行域，但是保留了原问题的全部整数可行解。

计算步骤：

1. 首先，求解原整数规划对应的线性规划 $minf(x)=c*x,s.t.\begin{Bmatrix}Ax≤b \\ x≥0 \end{Bmatrix}$

，设最优解为x*。

2. 如果最优解的分量均为整数，则x*为原整数规划的最优解，否则任选一个x*中不为整数的分量，设其对应的基变量为 $x_p$ ，定义包含这个基变量的切割约束方程 $x_p+\sum _jr_{ij}x_j=b_{con}$ 其中 $x_p$ 为非基变量。

3. 令 $\bar{r}_{ij}=r_{ij}-[r_{ij}] , \bar{b}_{con}=b_{con}-[b_{con}]$ ，其中[ ]为高斯函数符号，表示不大于某数的最大整数。将切割约束方程变换为 $\bar{r}_{ij}=r_{ij}-[r_{ij}] , \bar{b}_{con}=b_{con}-\left [ b_{con}\right ]$ ，由于

$0≤r_{ij}<1, 0≤b_{con’ }< 1$ ，所以有 $\bar{b}_{con}-\sum _j \bar{r}_{ij}x_j<1$ ，因为自变量为整数，则 $\bar{b}_{con}-\sum _j \bar{r}_{ij}x_j$ 也为整数，所以进一步有 $\bar{b}_{con}-\sum _j \bar{r}_{ij}x_j≤0$ 。

4. 将切割方程加入约束方程中，用对偶单纯形法求解线性规划

然后再转入步骤2进行求解，直到求出最优整数解停止迭代。

2、请你说说对于一些数据，如何判断其分布

画图，尤其是直方图，统计这些数据中各种样本出现的频次，可以很方便的看出来大致符合何种特征

代码示例

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Data    : 2021/8/15 3:27 下午
# @File    : 随机生成数据，可视化直方图.py
# @Software: PyCharm
import numpy as np
import matplotlib.pyplot as plt

def plot_hist():
    # 随机生成一批数据
    # 生成均匀分布的随机数
    data = np.random.normal(0, 1, 1000)
    # 1）创建画布
    plt.figure(figsize=(20, 10), dpi=100)
    # 2）绘制直方图
    plt.hist(data, 10)
    # 3）显示图像
    plt.show()


def main():
    plot_hist()


if __name__ == '__main__':
    main()

从上面的可视化结果中，可以很容易发现该数据符合正态分布。

延伸考点

有哪些常见的分布：

提示：正态分布、随机分布、0-1 分布、均匀分布、beta 分布等等（高数概率论基础）

3、请你说说为何实际生活中大部分数据服从正态分布或者拟正态分布；在知道数据的分布之后，如何进行后续处理。

正态分布表达式

$f(x)=\frac{1}{ \sqrt{2 \pi}} e^{-\frac{(-x)^{2}}{2}}$

若随机变量X服从一个数学期望为0、方差为1的正态分布，记为N(0，1)。

正态分布有极其广泛的实际背景，生产与科学实验中很多随机变量的概率分布都可以近似地用正态分布来描述。例如同一种生物体的身长、体重等指标；同一种种子的重量；测量同一物体的误差；弹着点沿某一方向的偏差；某个地区的年降水量；以及理想气体分子的速度分量，等等。

中心极限定理

中心极限定理的内容为：大量独立随机变量的和经过适当标准化之后趋近于正态分布，与这些变量原本的分布无关。比如，随机游走的总距离就趋近于正态分布。

该定理说明数据量足够大的情况下，基本都服从正态分布。

后续处理

去除离群点：对于明显偏离数据分布的特征可以提前滤除，避免影响结果
标准化：减均值，除以方差，使数据符合标准的正态分布
归一化：减去最小值，除以最大值和最小值的差，把数据压缩到 0-1 之间

代码实现

下面给出上述两种极其常用的归一化、标准化的示例代码

# 归一化
def normalization(data):
    _range = np.max(data) - np.min(data)
    return (data - np.min(data)) / _range
 
# 标准化 
def standardization(data):
    mu = np.mean(data, axis=0)
    sigma = np.std(data, axis=0)
    return (data - mu) / sigma

延伸考点

正态分布有哪些数学性质：

提示：正态分布进行适当的变换之后，仍是正态分布。

两个正态分布之积仍是正态分布
两个独立的服从正态分布的随机变量之和服从正态分布
对一个正态分布进行高斯卷积还是正态分布
正态分布经过傅立叶变换之后仍是正态分布

4、说说高斯分布是啥？

高斯分布表达式

$f(x)=\frac{1}{\sigma \sqrt{2 \pi}} e^{-\frac{(\mu-x)^{2}}{2 \sigma^{2}}}$

若随机变量X服从一个数学期望为μ、方差为σ^2的正态分布，记为N(μ，σ^2)。其概率密度函数为正态分布的期望值μ决定了其位置，其标准差σ决定了分布的幅度。

当μ = 0,σ = 1时的正态分布是标准正态分布。

正态分布的数学期望值或期望值 $\mu$ 等于位置参数，决定了分布的位置；其方差 $\sigma ^{2}$ 的开平方或标准差 $\sigma$ 等于尺度参数，决定了分布的幅度。

高斯分布性质

物理性质：

1. 中心极限定理：大量独立随机变量的和经过适当标准化之后趋近于正态分布，与这些变量原本的分布无关。

2. 给定均值方差，高斯分布最大化信息熵。即保留了最大的不确定性。

数学性质：

1. 封闭性，高斯分布用很多代数运算处理的结果还是高斯分布，这给公式推导带来极大方便。

2. 无限阶可导

3. 形式间接优美，由两个参数唯一确定

代码可视化（1D + 2D）

#!/usr/bin/env python
# -*- coding: utf-8 -*-
import matplotlib.pyplot as plt
import numpy as np
from mpl_toolkits.mplot3d import Axes3D

# 1D 高斯函数（手动实现）
def gaussian(mu, sigma, X):
    return np.exp(-(X - mu) * (X - mu) / (2 * sigma * sigma)) / (sigma * np.sqrt(2 * np.pi))

# 可视化 1D 高斯函数
def plot_1D_gaussian():
    # 单变量高斯分布
    mu = 1
    sigma = 0.2
    n_samples = 1000
    bins = 30
    Y_sampled = np.random.normal(mu, sigma, n_samples)
    x = np.linspace(0, 2)
    Y_truth = 50 * gaussian(mu, sigma, x)

    plt.figure(figsize=(8, 4))

    plt.subplot(1, 2, 1)
    plt.hist(Y_sampled, bins=bins, label='mu:{:0.2f}, sigma:{:0.2f}, bins:{:2d}'.format(mu, sigma, bins))
    plt.legend()
    plt.subplot(1, 2, 2)
    plt.plot(x, Y_truth, 'r', label='mu:{:0.2f}, sigma:{:0.2f}'.format(mu, sigma))
    plt.legend()
    plt.suptitle('Figure 1:Sampled and Ground Truth Distribution in 1D')


# 多维高斯函数
def multivariate_gaussian(mu, sigma, X):
    d = mu.shape[0]
    sigma_det = np.linalg.det(sigma)
    sigma_inv = np.linalg.inv(sigma)
    D = np.sqrt((2 * np.pi) ** d * sigma_det)
    # 本行代码为了实现：(x-mu)T.sigma-1.(x-mu)
    fac = np.einsum('...k,kl,...l->...', X - mu, sigma_inv, X - mu)
    return np.exp(-fac / 2) / D

# 可视化 2D 高斯函数
def plot_2D_gaussian():
    mu_v = np.array([0.5, -0.2])
    sigma_v = np.array([[2, 0.3], [0.3, 0.5]])
    bins = 30

    Y_sampled = np.random.multivariate_normal(mu_v, sigma_v, 10000)

    fig = plt.figure(figsize=(10, 5))
    ax = fig.add_subplot(121, projection='3d')
    z, x, y = np.histogram2d(Y_sampled[:, 0], Y_sampled[:, 1], bins=30, range=[[-6, 6], [-6, 6]])

    # 3D 可视化
    x_pos, y_pos = np.meshgrid(x[:-1] + 0.25, y[:-1] + 0.25, indexing="ij")
    x_pos = x_pos.ravel()
    y_pos = y_pos.ravel()
    z_pos = 0

    dx = dy = 0.5 * np.ones_like(z_pos)
    dz = z.ravel()
    ax.bar3d(x_pos, y_pos, z_pos, dx, dy, dz, zsort='average')

    x = y = np.linspace(-6, 6, 30, endpoint=False)
    X, Y = np.meshgrid(x, y)

    # 合并数据
    pos = np.empty(X.shape + (2,))
    pos[:, :, 0] = X
    pos[:, :, 1] = Y

    Z = multivariate_gaussian(mu_v, sigma_v, pos)

    ax1 = fig.add_subplot(122, projection='3d')
    ax1.plot_surface(X, Y, Z)

    plt.suptitle('Figure 2:Sampled and Ground Truth Distribution in 2D')
    plt.show()


def main():
    plot_1D_gaussian()
    plot_2D_gaussian()


if __name__ == '__main__':
    main()