人工智能与机器学习原理精解【14】

模拟退火优化算法

概述

模拟退火算法（Simulated Annealing, SA）是一种通用的概率优化算法，用于在给定的大搜索空间内寻找问题的近似全局最优解。该算法灵感来源于物理中固体物质的退火过程，即加热物体后再慢慢冷却，以达到最低能量状态的过程。在算法中，“温度”参数控制搜索过程的随机性，随着“温度”的逐渐降低，算法从广泛搜索逐渐转变为局部搜索，以期找到全局最优解。

模拟退火算法的基本步骤

1. 初始化：选择一个初始解$x_0$和一个足够高的初始温度$T_0$，以及温度下降的方式（如$T_{k+1}=\alpha T_k$，其中$0<\alpha <1$是冷却率）。设置终止温度$T_{\text{end}}$或迭代次数限制。

2. 当前解：将$x_0$设为当前解$x_{\text{current}}$，并计算其目标函数值$f(x_{\text{current}})$。

3. 扰动产生新解：对当前解$x_{\text{current}}$进行某种扰动（如随机改变其某些分量），产生新解$x_{\text{new}}$。

4. 接受准则：计算新解的目标函数值$f(x_{\text{new}})$。根据 Metropolis 准则决定是否接受新解作为当前解：

   • 如果$f(x_{\text{new}})<f(x_{\text{current}})$，则接受新解，即$x_{\text{current}}\leftarrow x_{\text{new}}$。
   • 如果$f(x_{\text{new}})\ge f(x_{\text{current}})$，则以概率$\exp \left(-\frac{f(x_{\text{new}})-f(x_{\text{current}})}{T_k}\right)$接受新解。这个概率随着温度的降低而减小，使得算法在温度较高时更容易接受较差的解，从而避免陷入局部最优。

5. 降温：根据预设的降温策略（如$T_{k+1}=\alpha T_k$）更新温度$T$。

6. 终止条件：检查是否满足终止条件（如温度低于$T_{\text{end}}$或达到预设的迭代次数）。如果满足，则算法结束，输出当前解作为近似最优解；否则，回到步骤
   3 继续执行。

优点与缺点

• 优点：

  • 通用性强，适用于求解各种优化问题。
  • 能在一定程度上避免陷入局部最优解。
  • 算法实现简单。

• 缺点：

  • 收敛速度较慢，特别是当问题规模较大时。
  • 初始温度、冷却率、终止温度等参数的选择对算法性能有较大影响，需要一定的经验或实验来确定。
  • 理论上不保证找到全局最优解，只能找到近似解。

模拟退火算法在组合优化、机器学习、信号处理等领域有广泛应用。

Metropolis准则

也称为Metropolis接受准则，是1953年由Metropolis等人提出的一种重要性采样方法，用于以概率接受新状态，而非完全确定的规则。这一准则在模拟退火算法（SA）等优化算法中扮演着关键角色，是算法收敛于全局最优解的重要机制。以下是Metropolis准则的详细解释：

一、基本概念

Metropolis准则定义了物体在某一温度T下从状态i转移到状态j的概率。在模拟退火算法中，这一准则用于判断在温度T下，系统是否应该接受一个新的状态j，即使这个新状态可能导致系统能量的增加。

二、具体规则

1. 能量比较：

   • 假设系统当前处于状态i，其能量为Ei。
   • 通过某种方式（如随机扰动）产生一个新状态j，其能量为Ej。

2. 接受准则：

   • 如果Ej < Ei（即新状态的能量低于当前状态），则无条件接受状态j为当前状态。
   • 如果Ej ≥ Ei（即新状态的能量不低于当前状态），则计算接受概率p：
     $$p=\exp \left(-\frac{Ej-Ei}{KT}\right)$$
     其中，K是玻尔兹曼常数，T是系统的温度。
   • 在[0,1)区间内生成一个随机数r。如果p > r，则接受状态j为当前状态；否则，保留状态i为当前状态。

三、特点与影响

1. 全局优化能力：Metropolis准则允许算法以一定概率接受恶化解（即能量增加的状态），这使得算法能够跳出局部最优解，具备全局优化的能力。
2. 温度的影响：
   • 在高温下，由于分母KT较大，接受概率p对能量差Ej - Ei的敏感度降低，因此可接受与当前状态能量差较大的新状态。
   • 在低温下，分母KT较小，接受概率p对能量差Ej - Ei的敏感度增加，因此只接受与当前状态能量差较小的新状态。
3. 收敛速度：通过调整温度T的大小和退火速度（即温度下降的速率），可以控制算法的收敛速度。温度下降过快可能导致算法过早陷入局部最优解，而温度下降过慢则会增加计算时间。

四、应用实例

Metropolis准则广泛应用于模拟退火算法中，用于解决各种优化问题，如旅行商问题（TSP）、调度问题、组合优化问题等。在这些问题中，Metropolis准则使得算法能够在搜索过程中保持多样性，避免陷入局部最优解，从而找到全局最优解或近似全局最优解。

综上所述，Metropolis准则是模拟退火算法等优化算法中的重要组成部分，它通过以一定概率接受恶化解的方式，使算法具备全局优化的能力。

模拟退火算法详解

是一种基于概率的通用优化算法，其思想来源于固体退火过程的物理现象。模拟退火算法通过模拟固体物质在加热后缓慢冷却的过程中粒子趋于有序、内能逐渐减小的过程，来解决组合优化问题。以下将详细介绍模拟退火算法的计算过程、例子和例题。

一、模拟退火算法的计算过程

模拟退火算法的基本步骤可以概括为：

1. 初始化：

   • 选择一个较高的初始温度$T_0$。
   • 在解空间中随机选择一个初始解$x_0$。
   • 设置每个温度下的迭代次数（即马尔可夫链的长度）$L$。
   • 设定降温函数（如$T_{k+1}=\alpha T_k$，其中$\alpha$为温度衰减率）。

2. 内循环（Metropolis过程）：

   • 在当前温度$T_k$下，进行$L$次迭代。
   • 每次迭代中，通过某种方式（如随机扰动）产生一个新解$x^{\prime }$。
   • 计算新解的目标函数值$f(x^{\prime })$与原解$x$的目标函数值$f(x)$的差$\Delta f=f(x^{\prime })-f(x)$。
   • 如果$\Delta f<0$，则接受新解$x^{\prime }$作为当前解。
   • 如果$\Delta f\ge 0$，则按概率$e^{-\Delta f/T_k}$接受新解$x^{\prime }$。

3. 外循环（退火过程）：

   • 按照降温函数逐步降低温度$T_k$。
   • 重复内循环过程，直到达到终止条件（如温度低于某一阈值或达到最大迭代次数）。

4. 输出最优解：

   • 算法结束时，当前解即为近似最优解。

二、模拟退火算法的例子

以旅行商问题（TSP）为例，模拟退火算法可以用于寻找访问一系列城市并返回出发点的最短路径。

• 初始化：随机生成一个初始路径，设置初始温度、降温函数、内循环和外循环的迭代次数等参数。
• 内循环：在当前温度下，通过交换两个城市的顺序来产生新路径，并计算新路径的总距离。根据Metropolis准则判断是否接受新路径。
• 外循环：逐步降低温度，并重复内循环过程，直到达到终止条件。
• 输出：算法结束时，输出最短路径及其总距离。

三、模拟退火算法的例题

假设有一个简单的优化问题，目标函数为$f(x)=x^2$，在区间$[-5,5]$内寻找最小值。

• 初始化：设置初始温度$T_0=100$，降温系数$\alpha =0.99$，终止温度$T_f=0.01$，内循环迭代次数$L=100$。随机选择一个初始解$x_0$。
• 内循环：在当前温度下，通过某种方式（如随机扰动）产生一个新解$x^{\prime }$，并计算目标函数值的差$\Delta f=f(x^{\prime })-f(x)$。根据Metropolis准则判断是否接受新解。
• 外循环：按照降温函数$T_{k+1}=\alpha T_k$逐步降低温度，并重复内循环过程，直到温度低于终止温度$T_f$。
• 输出：算法结束时，输出最小值及其对应的$x$值。

请注意，以上例题中的目标函数和约束条件较为简单，实际应用中模拟退火算法可以用于解决更复杂的优化问题。

线性规划对偶问题

对偶问题构造涉及到原问题的约束条件和目标函数的系数。

对于一个标准的线性规划问题：
$$\text{maximize }{c}^{T}x$$ $$\text{subject to }Ax\le b,x\ge 0$$

其对偶问题为： $$\text{minimize }{b}^{T}y$$ $$\text{subject to }{A}^{T}y\ge c,y\ge 0$$

具体见凸分析与凸优化精解【2】

julia实现

• 以直接计算其对偶问题为例
  $$\begin{gathered} min:35y_1+71y_2-16y_3 \\ subjectto: \\ 22y_1+7y_2+6y_3\ge 37, \\ 9y_1+11y_2+3y_3\ge 21, \\ 2y_1+7y_2+5y_3\ge 13 \\ {y}_1,y_2,y_3\ge 0 \end{gathered}$$
  $$\begin{gathered} b=[35,71,-16] \\ A=\left[\begin{array}{ccc}22& 7& 6\\ 9& 11& 3\\ 2& 7& 5\end{array}\right] \\ c=[37,21,13] \end{gathered}$$
• 代码

using Statistics
using Random 
#coding:https://blog.csdn.net/sakura_sea
function getObjectiveFun(y::Vector{Int64},b::Vector{Int64})
    return b'*y
end
function initParam()
    b=[35,71,-16]
    A=[[22 7 6];[9 11 3];[2 7 5]]
    c=[37,21,13]
    x_0=[rand(1:100),rand(1:100),rand(1:100)]
    T_0=10000000.0
    a=0.98
    step=2
    T_end=100
    return (b,c,A,x_0,T_0,a,step,T_end)
end
function getNextTemperature(T_k,a)
    return a*T_k
end
function gt_ab(a,b)
    return sum((a-b).>=0) ==length(a)
end
function simulatedAnnealing(x,b,step,T_k,T_end,c)
    x_current=x
    x_i=rand(1:length(x))
    j=0
    while true
        rng = MersenneTwister()
        x[x_i]+=rand(rng,-step:step)
        print(".")
        if x[x_i]>0 && gt_ab(A'*x,c)
            break
        end
        j+=1
        if j>200
            sleep(1)
            rng = MersenneTwister()
            j=0
        end
    end
    x_new=x
    f_new=getObjectiveFun(x_new,b)
    f_current=getObjectiveFun(x_current,b)
    if f_new>=f_current
        r=rand(1)[1]
        if ℯ^(-(f_new-f_current)/T_k)<=r
            x_new=x_current
        end     
    end
    T_k=getNextTemperature(T_k,a)
    if T_k<T_end 
        return x_new
    end
    println("try...",x_new)
    simulatedAnnealing(x_new,b,step,T_k,T_end,c)
end
best_result=100000000
b,c,A,x_0,T_0,a,step,T_end=initParam()
best_x=x_0
for i in 1:20
    global best_result,best_x
    b,c,A,x_0,T_0,a,step,T_end=initParam()
    x_result=simulatedAnnealing(x_0,b,step,T_0,T_end,c)
    println(A'*x_result)
    result=getObjectiveFun(x_result,b)
    if best_result > result
        best_result=result
        best_x=x_result
    end
    println(x_result,"==>",result)
end
println(best_x,A'*best_x,"==>",best_result)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

...
...
...
.try...[12, 65, 67]
.try...[12, 65, 68]
.try...[12, 65, 66]
.try...[13, 65, 66]
.try...[13, 65, 67]
.try...[13, 65, 65]
.[997, 1247, 588]
[13, 65, 63]==>4062
.try...[13, 10, 18]
.try...[13, 10, 18]
.try...[14, 10, 18]
.try...[16, 10, 18]
.try...[15, 10, 18]
.try...[15, 10, 18]
.try...[15, 10, 18]
.try...[13, 10, 18]
.try...[15, 10, 18]
.try...[15, 10, 17]
.try...[15, 12, 17]
.try...[15, 14, 17]
.try...[15, 16, 17]
.try...[14, 16, 17]
.try...[14, 16, 17]
.try...[14, 16, 19]
.try...[14, 17, 19]
.try...[14, 17, 19]
.try...[16, 17, 19]
.try...[16, 15, 19]
.try...[16, 15, 19]
.try...[16, 17, 19]
.try...[16, 17, 21]
.try...[17, 17, 21]
.try...[17, 16, 21]
.try...[17, 17, 21]
.try...[17, 18, 21]
.try...[17, 18, 22]
.try...[17, 16, 22]
.try...[17, 18, 22]
.try...[17, 16, 22]
.try...[17, 18, 22]
.try...[17, 17, 22]
.try...[17, 17, 24]
.try...[17, 17, 26]
.try...[18, 17, 26]
.try...[18, 17, 25]
.try...[18, 17, 25]
.try...[18, 17, 25]
.try...[18, 15, 25]
.try...[17, 15, 25]
.try...[17, 16, 25]
.try...[18, 16, 25]
.try...[18, 15, 25]
.try...[18, 15, 27]
.try...[18, 17, 27]
.try...[18, 17, 27]
.try...[17, 17, 27]
.try...[17, 18, 27]
.try...[19, 18, 27]
.try...[19, 18, 27]
.try...[19, 18, 29]
.try...[19, 18, 29]
.try...[19, 20, 29]
.try...[19, 20, 29]
.try...[19, 20, 27]
.try...[21, 20, 27]
.try...[21, 20, 27]
.try...[21, 18, 27]
.try...[19, 18, 27]
.try...[19, 18, 25]
.try...[17, 18, 25]
.try...[17, 18, 24]
.try...[16, 18, 24]
.try...[16, 18, 23]
.try...[14, 18, 23]
.try...[14, 18, 23]
.try...[14, 18, 23]
.try...[14, 18, 21]
.try...[12, 18, 21]
.try...[12, 18, 22]
.try...[14, 18, 22]
.try...[14, 18, 22]
.try...[12, 18, 22]
.try...[12, 18, 21]
.try...[11, 18, 21]
.try...[11, 18, 19]
.try...[13, 18, 19]
.try...[14, 18, 19]
.try...[12, 18, 19]
.try...[12, 18, 18]
.try...[12, 17, 18]
.try...[12, 17, 20]
.try...[12, 17, 19]
.try...[12, 18, 19]
.try...[12, 20, 19]
.try...[12, 20, 19]
.try...[12, 20, 17]
.try...[10, 20, 17]
.try...[10, 20, 17]
.try...[10, 20, 16]
.try...[10, 20, 16]
.try...[10, 20, 18]
.try...[10, 18, 18]
.try...[11, 18, 18]
.try...[11, 18, 18]
.try...[11, 18, 19]
.try...[12, 18, 19]
.try...[12, 18, 20]
.try...[12, 18, 20]
.try...[13, 18, 20]
.try...[13, 18, 18]
.try...[12, 18, 18]
.try...[12, 16, 18]
.try...[12, 16, 16]
.try...[10, 16, 16]
.try...[10, 16, 16]
.try...[8, 16, 16]
.try...[8, 16, 16]
.try...[8, 16, 15]
.try...[7, 16, 15]
.try...[7, 16, 16]
.try...[7, 16, 14]
.try...[8, 16, 14]
.try...[9, 16, 14]
.try...[9, 15, 14]
.try...[9, 16, 14]
.try...[9, 16, 16]
.try...[9, 16, 16]
.try...[9, 16, 15]
.try...[9, 16, 17]
.try...[9, 16, 18]
.try...[7, 16, 18]
.try...[7, 15, 18]
.try...[7, 15, 19]
.try...[7, 15, 21]
.try...[7, 14, 21]
.try...[7, 16, 21]
.try...[8, 16, 21]
.try...[8, 17, 21]
.try...[8, 17, 20]
.try...[8, 17, 22]
.try...[8, 15, 22]
.try...[8, 15, 22]
.try...[8, 15, 22]
.try...[8, 15, 22]
.try...[8, 15, 23]
.try...[8, 17, 23]
.try...[8, 17, 25]
.try...[6, 17, 25]
.try...[6, 17, 23]
.try...[6, 15, 23]
.try...[6, 13, 23]
.try...[6, 13, 23]
.try...[6, 13, 23]
.try...[6, 13, 24]
.try...[6, 13, 22]
.try...[6, 14, 22]
.try...[6, 14, 20]
.try...[6, 13, 20]
.try...[6, 15, 20]
.try...[8, 15, 20]
.try...[7, 15, 20]
.try...[9, 15, 20]
.try...[9, 17, 20]
.try...[8, 17, 20]
.try...[8, 18, 20]
.try...[8, 18, 18]
.try...[8, 18, 18]
.try...[7, 18, 18]
.try...[7, 18, 16]
.try...[8, 18, 16]
.try...[8, 18, 16]
.try...[8, 18, 16]
.try...[8, 17, 16]
.try...[8, 17, 14]
.try...[8, 15, 14]
.try...[10, 15, 14]
.try...[10, 15, 12]
.try...[8, 15, 12]
.try...[8, 13, 12]
.try...[7, 13, 12]
.try...[7, 12, 12]
.try...[7, 12, 13]
.try...[8, 12, 13]
.try...[8, 12, 13]
.try...[8, 12, 12]
.try...[7, 12, 12]
.try...[9, 12, 12]
.try...[10, 12, 12]
.try...[10, 12, 12]
.try...[10, 12, 12]
.try...[8, 12, 12]
.try...[7, 12, 12]
.try...[7, 12, 12]
.try...[7, 14, 12]
.try...[7, 13, 12]
.try...[7, 13, 13]
.try...[7, 15, 13]
.try...[7, 15, 13]
.try...[7, 15, 13]
.try...[6, 15, 13]
.try...[8, 15, 13]
.try...[8, 13, 13]
.try...[8, 13, 15]
.try...[8, 13, 13]
.try...[6, 13, 13]
.try...[5, 13, 13]
.try...[5, 13, 14]
.try...[5, 13, 13]
.try...[5, 12, 13]
.try...[4, 12, 13]
.try...[4, 12, 13]
.try...[4, 12, 13]
.try...[4, 11, 13]
.try...[4, 11, 11]
.try...[4, 10, 11]
.try...[4, 12, 11]
.try...[4, 12, 9]
.try...[4, 12, 9]
.try...[4, 12, 10]
.try...[4, 12, 11]
.try...[3, 12, 11]
.try...[3, 12, 10]
.try...[4, 12, 10]
.try...[6, 12, 10]
.try...[6, 12, 8]
.try...[6, 12, 8]
.try...[6, 12, 9]
.try...[8, 12, 9]
.try...[8, 12, 10]
.try...[8, 12, 12]
.try...[8, 13, 12]
.try...[8, 12, 12]
.try...[8, 12, 10]
.try...[8, 12, 9]
.try...[8, 14, 9]
.try...[8, 14, 7]
.try...[8, 14, 7]
.try...[8, 14, 6]
.try...[6, 14, 6]
.try...[6, 14, 6]
.try...[6, 16, 6]
.try...[6, 16, 4]
.try...[6, 16, 2]
.try...[6, 17, 2]
.try...[8, 17, 2]
.try...[9, 17, 2]
.try...[8, 17, 2]
.try...[8, 19, 2]
.try...[8, 20, 2]
.try...[8, 20, 3]
.try...[9, 20, 3]
.try...[8, 20, 3]
.try...[8, 21, 3]
.try...[9, 21, 3]
.try...[9, 21, 1]
.try...[9, 21, 1]
.try...[7, 21, 1]
.try...[7, 21, 2]
.try...[7, 21, 2]
.......try...[7, 21, 2]
.try...[8, 21, 2]
.try...[6, 21, 2]
.try...[4, 21, 2]
.try...[4, 23, 2]
.try...[4, 23, 2]
.try...[4, 22, 2]
.try...[4, 22, 4]
.try...[3, 22, 4]
.try...[3, 22, 4]
.try...[2, 22, 4]
.try...[2, 22, 5]
.try...[2, 21, 5]
.try...[4, 21, 5]
.try...[4, 19, 5]
.try...[2, 19, 5]
..............try...[1, 19, 5]
.try...[1, 19, 5]
.try...[1, 19, 7]
.try...[1, 19, 6]
.try...[1, 19, 5]
.try...[1, 21, 5]
.try...[1, 21, 5]
.try...[1, 22, 5]
.try...[1, 22, 6]
.try...[1, 22, 6]
.............try...[2, 22, 6]
.try...[2, 22, 4]
.try...[2, 22, 3]
.try...[2, 22, 4]
.try...[2, 22, 6]
.try...[2, 21, 6]
.try...[2, 21, 4]
.try...[2, 20, 4]
.try...[2, 20, 4]
.try...[2, 20, 4]
.try...[2, 20, 6]
.try...[2, 20, 6]
.try...[2, 20, 6]
.try...[2, 20, 8]
.try...[2, 20, 6]
.try...[2, 20, 8]
.try...[2, 20, 8]
.try...[2, 19, 8]
.try...[2, 19, 8]
.try...[2, 21, 8]
.try...[2, 23, 8]
.try...[2, 23, 8]
.try...[4, 23, 8]
.try...[6, 23, 8]
.try...[6, 23, 8]
.try...[4, 23, 8]
.try...[2, 23, 8]
.try...[2, 22, 8]
.try...[3, 22, 8]
.try...[4, 22, 8]
.try...[4, 22, 7]
.try...[4, 22, 6]
.try...[4, 22, 6]
.try...[4, 24, 6]
.try...[4, 24, 4]
.try...[3, 24, 4]
.try...[3, 24, 3]
.try...[3, 22, 3]
.try...[3, 22, 2]
.try...[4, 22, 2]
..............................................................................................................................................................................................................................................................................................................................................try...[4, 22, 2]
.try...[4, 22, 3]
.try...[4, 22, 2]
.try...[4, 21, 2]
.try...[4, 22, 2]
.try...[4, 22, 2]
.try...[5, 22, 2]
.try...[5, 22, 3]
.try...[5, 20, 3]
.try...[5, 20, 3]
.try...[5, 20, 5]
.try...[5, 21, 5]
.try...[5, 21, 5]
.try...[5, 22, 5]
.try...[5, 22, 5]
.try...[5, 24, 5]
.try...[5, 24, 5]
.try...[5, 22, 5]
.try...[5, 22, 5]
.try...[5, 22, 5]
.try...[5, 22, 5]
.try...[5, 20, 5]
.try...[5, 20, 4]
.try...[3, 20, 4]
.try...[3, 20, 5]
.try...[2, 20, 5]
.try...[2, 21, 5]
.try...[4, 21, 5]
.try...[4, 21, 5]
.try...[4, 22, 5]
.try...[6, 22, 5]
.try...[6, 22, 5]
.try...[6, 22, 5]
.try...[6, 22, 3]
.try...[6, 22, 5]
.try...[6, 22, 5]
.try...[6, 22, 6]
.try...[6, 22, 5]
.try...[6, 22, 7]
.try...[6, 22, 6]
.try...[6, 24, 6]
.try...[6, 24, 8]
.try...[4, 24, 8]
.try...[5, 24, 8]
.try...[5, 25, 8]
.try...[7, 25, 8]
.try...[7, 24, 8]
.try...[5, 24, 8]
.try...[5, 24, 7]
.try...[7, 24, 7]
.try...[7, 22, 7]
.try...[7, 22, 7]
.try...[7, 22, 8]
.try...[7, 20, 8]
.try...[7, 20, 8]
.try...[7, 20, 8]
.try...[7, 20, 7]
.try...[9, 20, 7]
.try...[9, 20, 9]
.try...[9, 22, 9]
.try...[9, 20, 9]
.try...[9, 18, 9]
.try...[9, 18, 10]
.try...[7, 18, 10]
.try...[7, 18, 11]
.try...[7, 18, 13]
.try...[7, 20, 13]
.try...[6, 20, 13]
.try...[8, 20, 13]
.try...[9, 20, 13]
.try...[9, 18, 13]
.try...[9, 18, 13]
.try...[9, 18, 13]
.try...[11, 18, 13]
.try...[11, 20, 13]
.try...[10, 20, 13]
.try...[9, 20, 13]
.try...[11, 20, 13]
.try...[11, 20, 12]
.try...[10, 20, 12]
.try...[10, 20, 11]
.try...[10, 20, 12]
.try...[10, 19, 12]
.try...[10, 17, 12]
.try...[10, 17, 13]
.try...[10, 17, 14]
.try...[10, 17, 14]
.try...[10, 15, 14]
.try...[10, 15, 12]
.try...[10, 15, 12]
.try...[10, 15, 10]
.try...[10, 15, 10]
.try...[10, 15, 10]
.try...[10, 16, 10]
.try...[10, 16, 12]
.try...[10, 16, 10]
.try...[10, 16, 10]
.try...[10, 16, 12]
.try...[10, 16, 11]
.try...[8, 16, 11]
.try...[8, 16, 10]
.try...[6, 16, 10]
.try...[5, 16, 10]
.try...[5, 15, 10]
.try...[5, 15, 10]
.try...[5, 15, 10]
.try...[5, 16, 10]
.try...[4, 16, 10]
.try...[4, 17, 10]
.try...[2, 17, 10]
.try...[2, 16, 10]
.try...[2, 16, 10]
.try...[2, 16, 8]
...try...[1, 16, 8]
.try...[1, 16, 8]
.try...[1, 16, 8]
.try...[1, 18, 8]
..try...[1, 18, 8]
.try...[1, 19, 8]
.try...[1, 18, 8]
.try...[1, 18, 8]
.try...[1, 19, 8]
.try...[1, 19, 8]
.try...[1, 19, 6]
.try...[1, 19, 7]
.try...[1, 19, 7]
.try...[1, 19, 5]
.try...[1, 21, 5]
.try...[1, 21, 5]
.try...[1, 20, 5]
.try...[2, 20, 5]
.try...[2, 19, 5]
.try...[2, 19, 5]
.try...[2, 17, 5]
..try...[1, 17, 5]
.try...[1, 17, 5]
.try...[3, 17, 5]
.try...[3, 17, 7]
.try...[3, 16, 7]
.try...[3, 16, 6]
.try...[3, 14, 6]
.try...[3, 14, 7]
.try...[3, 12, 7]
.try...[3, 13, 7]
.try...[3, 13, 7]
.try...[2, 13, 7]
.try...[2, 15, 7]
.try...[2, 15, 6]
.try...[2, 15, 7]
.try...[3, 15, 7]
.try...[3, 15, 9]
.try...[3, 15, 9]
.try...[3, 13, 9]
.try...[1, 13, 9]
.try...[2, 13, 9]
.try...[2, 13, 7]
.try...[2, 13, 7]
.try...[2, 11, 7]
.try...[2, 11, 8]
.try...[2, 11, 9]
.try...[2, 11, 9]
.try...[2, 9, 9]
.try...[2, 9, 10]
.try...[2, 9, 10]
.try...[2, 9, 9]
.try...[3, 9, 9]
.try...[2, 9, 9]
.try...[2, 8, 9]
.try...[2, 8, 11]
.try...[2, 8, 11]
.try...[1, 8, 11]
...try...[1, 8, 11]
.try...[1, 8, 11]
..try...[1, 8, 11]
.try...[1, 7, 11]
.try...[1, 5, 11]
..................try...[2, 5, 11]
.try...[2, 5, 9]
.try...[2, 5, 10]
.try...[2, 5, 12]
.try...[2, 5, 12]
.try...[2, 5, 12]
.try...[2, 3, 12]
.try...[2, 3, 12]
.try...[2, 2, 12]
.try...[2, 4, 12]
.try...[2, 4, 12]
.try...[2, 5, 12]
.try...[2, 5, 11]
.try...[2, 5, 10]
.try...[2, 5, 10]
.try...[2, 6, 10]
.try...[2, 5, 10]
.try...[2, 6, 10]
.try...[2, 6, 9]
.try...[2, 8, 9]
.try...[3, 8, 9]
.try...[3, 8, 9]
.try...[3, 8, 10]
.try...[3, 9, 10]
.try...[1, 9, 10]
.try...[1, 9, 9]
.try...[1, 9, 7]
.try...[1, 9, 7]
.try...[1, 7, 7]
.try...[1, 7, 7]
.try...[1, 5, 7]
.try...[1, 5, 7]
.try...[1, 5, 9]
.try...[1, 5, 11]
.try...[1, 5, 11]
.try...[1, 5, 11]
.try...[1, 5, 10]
.try...[1, 4, 10]
.try...[1, 4, 10]
.try...[1, 6, 10]
.try...[1, 6, 8]
.try...[1, 5, 8]
........................................try...[2, 5, 8]
.try...[2, 3, 8]
...try...[2, 3, 8]
.try...[2, 3, 8]
.try...[2, 3, 9]
.try...[4, 3, 9]
.try...[4, 3, 11]
.try...[6, 3, 11]
.try...[6, 3, 11]
.try...[6, 3, 11]
.try...[6, 3, 11]
.try...[6, 3, 10]
.try...[6, 2, 10]
.try...[6, 2, 8]
.try...[4, 2, 8]
.try...[3, 2, 8]
.try...[3, 2, 9]
.try...[3, 2, 9]
.try...[3, 1, 9]
.try...[1, 1, 9]
..try...[1, 2, 9]
.try...[1, 1, 9]
.try...[1, 3, 9]
.try...[1, 3, 9]
.try...[1, 1, 9]
..try...[2, 1, 9]
.try...[2, 2, 9]
.try...[2, 3, 9]
.try...[1, 3, 9]
.try...[1, 3, 9]
.try...[1, 3, 8]
.try...[1, 1, 8]
.............................try...[1, 2, 8]
.try...[1, 1, 8]
.[91, 88, 61]
[3, 1, 8]==>48
[3, 1, 8][91, 88, 61]==>48
 *  Terminal will be reused by tasks, press any key to close it. 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584

参考文献

1.文心一言
2.chatgpt