计算机原理基础

（1）分枝定界法：

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

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

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

代码示例

#!/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()

延伸考点

正态分布表达式

中心极限定理

后续处理

代码实现

# 归一化
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

延伸考点

高斯分布表达式

高斯分布性质

代码可视化（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()

结果示例图