算法_回溯

发表于2024-11-25更新于2025-09-28阅读次数

内容

  1. 子集树
  2. 排列树

生成子集树

子集树可以用来解决从集合中挑选一些元素以达到一定条件的问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void func(int arr[], int length, int x[])
{
    if (i == length)
    {
        for (int j = 0; j < length; ++j)
        {
            if (x[j] == 1)
            {
                std::cout << arr[j] << " ";
            }
        }
        std::cout << std::endl;
    }
    else
    {
        x[i] = 1;
        func(arr, i + 1, length, x);
        x[i] = 0;
        func(arr, i + 1, length, x);
    }
}

另一种形式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void func(int arr[], int i, int length, int x[])
{
    if (i == length)
    {
        for (int j = 0; j < length; ++j)
        {
            if (x[j] == 1)
            {
                std::cout << arr[j] << " ";
            }
        }
        std::cout << std::endl;
    }
    else
    {
        // another form
        for (int k = 1; k >= 0; --k)
        {
            x[i] = k;
            func(arr, i + 1, length, x);
        }
    }
}

但是这一种形式不太利于直接添加剪支操作。

选数字，达到给定和

剪左支的条件：选择第i数时，当前累计和已经超过了given_sum，则没必要再往下进行。
剪右支的条件：选择第i数时，剩下的i + 1到n的累计和（即剩余未处理的数的和，注意，不是”未选择“，而是”未处理“，”处理“是层级别的概念，”选择“是左右子树概念）rest加上当前累计和不够given_sum，则没必要往下进行。

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
// 挑选数字：有一组整数，请挑选出一组数字，使它们的和等于指定的值
#include<iostream>
#include<vector>
int arr[] = { 4,8,12,16,7,9,3 };
int given_sum = 18;
int res = 0;
std::vector<int> aux;
bool func(int* arr, int i, int length)
{
    bool have = false;

    if (i == length)
    {
        if(res == given_sum)
        {
            for (int v : aux)
            {
                std::cout << v << " ";
            }
            std::cout << std::endl;
            have = true;
        }
    }
    else
    {
        if (res + arr[i] <= given_sum)
        {
            res += arr[i];
            aux.push_back(arr[i]);
            return func(arr, i + 1, length);

            res -= arr[i];
            aux.pop_back();
        }
        int rest = 0;
        for (int j = i + 1; j < length; ++j)
        {
            rest += arr[j];
        }
        if (res + rest >= given_sum)
        {
            return func(arr, i + 1, length);
        }
    }
    return have;
}
int main()
{
    bool have = func(arr, 0, sizeof(arr) / sizeof(arr[0]));
    if (!have)
    {
        std::cout << "have not resolution." << std::endl;
    }
}

更好的写法：在main函数中先给出rest的总值。在处理第i + 1层前，减去第i个数。处理完第i + 1层后，即开始回溯到i，则i层又活了，需要加回第i个数。
这样的写法，可以避免每次计算剪右支条件都要走一遍循环计算剩余数字（i + 1到n）的和，而替换成每次只需简单地减、加一个arr[i]。

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
// 挑选数字：有一组整数，请挑选出一组数字，使它们的和等于指定的值
#include<iostream>
#include<vector>
int arr[] = { 4,8,12,16,7,9,3 };
int given_sum = 18;
int res = 0;
int rest = 0;

std::vector<int> aux;
bool func(int* arr, int i, int length)
{
    bool have = false;

    if (i == length)
    {
        if(res == given_sum)
        {
            for (int v : aux)
            {
                std::cout << v << " ";
            }
            std::cout << std::endl;
            have = true;
        }
    }
    else
    {
        rest -= arr[i];
        if (res + arr[i] <= given_sum)
        {
            res += arr[i];
            aux.push_back(arr[i]);
            return func(arr, i + 1, length);

            res -= arr[i];
            aux.pop_back();
        }
        
        if (res + rest >= given_sum)
        {
            return func(arr, i + 1, length);
        }
        rest += arr[i];
    }
    return have;
}
int main()
{
    for (int v : arr)
    {
        rest += v;
    }


    bool have = func(arr, 0, sizeof(arr) / sizeof(arr[0]));
    if (!have)
    {
        std::cout << "have not resolution." << std::endl;
    }
}

同时还需要注意，未处理和未选择的概念不要混淆，我第一次写成了如下形式：这是错误的。

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
    // ...
    else
    {
        if (res + arr[i] <= given_sum)
        {
            res += arr[i];
            rest -= arr[i];   // 选择
            aux.push_back(arr[i]);
            return func(arr, i + 1, length);

            res -= arr[i];
            rest += arr[i];   // 未选择
            aux.pop_back();
        }
        
        if (res + rest >= given_sum)
        {
            return func(arr, i + 1, length);
        }
    }
    return have;
}
int main()
{
    for (int v : arr)
    {
        rest += v;
    }
    // ...
}

这与上面的含义完全不一样。我们要做的是”处理“、”未处理“时，rest变量的变化。而不是”选择“、”未选择“时，rest变量的变化。”处理“是层级别的概念，”选择“是左右子树概念。
即，不管选不选，走不走左右子树，rest都要在之前减去arr[i]；不管选不选，走不走左右子树，之后rest都要加上arr[i]。

多叉子集树-更高效

以下程序生成的是如下图的子集树：

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
#include<iostream>
#include<vector>
int arr[] = { 4,8,12,16,7,9,3 };
int given_sum = 18;
int res = 0;
int rest = 0;

std::vector<int> aux;
void func(int i, int length, int number)
{
    if (number == 0)
    {
        for (int v : aux)
        {
            std::cout << v << " ";
        }
        std::cout << std::endl;
    }
    else
    {
        // 以层的视角看，生成(k, k+1, ..., n)子树并遍历。
        for (int k = i; k < length; ++k)
        {
            if (number >= arr[k]) // 接下来的k元素不能大于number
            {
                aux.push_back(arr[k]);
                // 选择 k + 1，则向深度遍历，number条件改变
                func(k + 1, length, number - arr[k]);

                // 不选择 k + 1，则回溯到上一层，number条件不改变
                aux.pop_back();
            }
        }
    }
}
int main()
{
    func(0, 7, given_sum);
    return 0;
}

输出：8 7 3

变种：可以重复选择元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
    // ...
    else
    {
        // 以层的视角看，生成(k, k+1, ..., n)子树并遍历。
        for (int k = i; k < length; ++k)
        {
            if (number >= arr[k]) // 接下来的k元素不能大于number
            {
                aux.push_back(arr[k]);
                // 更改：
                // 选择 k，则向深度遍历，number条件改变
                func(k, length, number - arr[k]);

                // 不选择 k，则回溯到上一层，number条件不改变
                aux.pop_back();
            }
        }
    }
}
int main()
{
    func(0, 7, given_sum);
    return 0;
}

输出

1
2
3
4
5
6
7
8
9
4 4 4 3 3
4 4 7 3
4 8 3 3
4 7 7
8 7 3
12 3 3
9 9
9 3 3 3
3 3 3 3 3 3

排列树

序列有不同的排列方式，求解原始序列的某一种特定的排列方式以达到一定条件的问题。

排列问题可以表示为以下形式：
设R={r1,r2,r3,⋯ ,rn}R=\{ r_1, r_2, r_3, \cdots, r_n \}是要进行排列的nn个元素，Ri=R−{ri}R_i=R-\{r_i\}。
集合XX中元素的全排列记为perm(X)perm(X)。(ri)perm(X)(r_i)perm(X)表示在全排列perm(X)perm(X)的每一个排列前加上前缀rir_i得到的排列。
RR的全排列可归纳定义如下：

  • 当n=1n=1时，perm(R)=(r)perm(R)=(r)，其中rr是集合RR中唯一的元素
  • 当n>1n>1时，perm(R)perm(R)由(r1)perm(R1),(r2)perm(R2),⋯ ,(rn)perm(Rn)(r_1)perm(R_1),(r_2)perm(R_2),\cdots,(r_n)perm(R_n)构成。（Ri=R−{ri}R_i=R-\{r_i\}）

比如：R={1,2,3}R=\{1,2,3\}，则perm(R)perm(R)由(1)perm({2,3}),(2)perm({1,3}),(3)perm({1,2})(1)perm(\{2,3\}),(2)perm(\{1,3\}),(3)perm(\{1,2\})构成。

在第i层视角上，集合内每个元素都依次与第i个位置进行交换。如下图：元素1到了第1的位置，则出现：(1)R{2,3}，元素2到了第1的位置，则出现：(2)R{1,3}，元素3到了第1的位置，则出现：(3)R{1,2}。

于是，在代码中，我们可以写出for循环的条件：第i层时，（以下表述均对应实际元素数组的下标，例如：第0层，对应第1个元素的位置，下标为0），就要把从k（用k作为i的副本）到n-1的元素循环与第i个位置进行交换。

交换后再次进行perm计算，下一次的i更新为i+1。

从层次视角看，本层的perm调用结束后，不要忘记把状态回退，即第k个元素换回i位置。

当到达第n层，达到递归终止条件，这时arr数组中记录的各个元素的位置即为此时序列的某种全排列。直接全部输出即可。

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
#include<iostream>
void swap(int* arr, int i, int j)
{
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}
void func(int* arr, int i, int length)
{
    if (i == length)
    {
        for (int j = 0; j < length; ++j)
        {
            std::cout << arr[j] << " ";
        }
        std::cout << std::endl;
    }
    else
    {
        // 生成子树，遍历孩子节点
        for (int k = i; k < length; ++k)
        {
            // 从 i 到 n，每次arr数组元素的该位置 都与 k 位置交换一下
            swap(arr, i, k);
            // 注意此处很重要，不再是k + 1，而是i + 1。
            // 如果我们搞成了k + 1，则变成了上面的多叉子集树（选数字问题）。
            // 因为给出了i+1，for循环中k在变，i是不变的，所以每次都会是相同数个元素进行遍历。
            // 因此才能出现排列方式不同的全集（即全排列）。
            func(arr, i + 1, length);
            swap(arr, i, k);
        }
    }
}
int main()
{
    int arr[] = { 1, 2, 3, 4 };
    const int length = sizeof(arr) / sizeof(arr[0]);
    func(arr, 0, length);
}

输出

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
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 3 2
1 4 2 3
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 3 1
2 4 1 3
3 2 1 4
3 2 4 1
3 1 2 4
3 1 4 2
3 4 1 2
3 4 2 1
4 2 3 1
4 2 1 3
4 3 2 1
4 3 1 2
4 1 3 2
4 1 2 3

n皇后问题（n后、八皇后）

在n×nn\times n格的国际象棋棋盘上放置彼此不受攻击的nn个皇后。皇后可以攻击同一行、同一列或同一斜线上的棋子。

非递归

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
void NiceBackTrack()
{
    x[1] = 0;
    int k = 1;
    while (k >= 1)
    {
        x[k] += 1;
        while ((x[k]) <= n) && !Place(k))
        {
            x[k] += 1;
        }
        if (x[k] <= n)
        {
            if (k == n)
            {
                sum += 1;
                PrintQ();
            }
            else
            {
                k += 1;
                x[k] = 0;
            }
        }
        else
        {
            --k;
        }
    }
}

网络_自建远程桌面服务器

发表于2024-11-23更新于2025-09-28阅读次数

云服务器选购

阿里云2C2G3M（2 CPU、2G RAM、3M固定带宽（无限流量）），1年99元。选北京地区的，在国内延迟可能低一些。

软件选择

远程桌面软件选择RustDesk，开源的。
server端：
https://github.com/rustdesk/rustdesk-server/releases
client端：
https://github.com/rustdesk/rustdesk/releases

RustDesk下载

根据RustDesk官方文档。
服务端的文件有：两个可执行文件和一个文件夹。

  • hbbs - RustDesk ID/Rendezvous server
  • hbbr - RustDesk Relay server

一般，下载这个：
https://github.com/rustdesk/rustdesk-server/releases/download/1.1.12/rustdesk-server-linux-amd64.zip

使用wget + url命令即可下载。

代理

Linux服务器要下载好多开源项目或者国际软件。往往需要代理网络。

云服务器只有Linux命令行，因此需要下载mihomo项目（Clash Meta）来用命令行配置。
https://github.com/MetaCubeX/mihomo/releases
下载其中的：
https://github.com/MetaCubeX/mihomo/releases/download/v1.18.10/mihomo-linux-amd64-v1.18.10.deb
是deb格式的安装包。可以使用apt install + 文件名安装这种离线安装包。

安装后，可以通过find / -name mihomo来查找服务器上名字包含mihomo的文件在哪里。

1
2
3
4
/root/.config/mihomo
/etc/mihomo
/usr/share/licenses/mihomo
/usr/bin/mihomo

/root/.config/mihomo/是mihomo的配置文件目录。
有以下内容：
config.yaml geoip.metadb

/etc/mihomo/也是mihomo的一个配置文件目录，但是貌似优先用的是root的（即当前用户的配置优于etc目录下的全局配置）

守护进程

安装后，需要把mihomo作为一个守护进程跑在服务器上。
参考文档：
https://wiki.metacubex.one/en/startup/service/
如下创建系统配置文件 /etc/systemd/system/mihomo.service

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
[Unit]
Description=mihomo Daemon, Another Clash Kernel.
After=network.target NetworkManager.service systemd-networkd.service iwd.service

[Service]
Type=simple
LimitNPROC=500
LimitNOFILE=1000000
CapabilityBoundingSet=CAP_NET_ADMIN CAP_NET_RAW CAP_NET_BIND_SERVICE CAP_SYS_TIME CAP_SYS_PTRACE CAP_DAC_READ_SEARCH CAP_DAC_OVERRIDE
AmbientCapabilities=CAP_NET_ADMIN CAP_NET_RAW CAP_NET_BIND_SERVICE CAP_SYS_TIME CAP_SYS_PTRACE CAP_DAC_READ_SEARCH CAP_DAC_OVERRIDE
Restart=always
ExecStartPre=/usr/bin/sleep 1s
ExecStart=/usr/local/bin/mihomo -d /etc/mihomo
ExecReload=/bin/kill -HUP $MAINPID

[Install]
WantedBy=multi-user.target

使用以下命令重新加载 systemd：
systemctl daemon-reload
启用Mihomo服务：
systemctl enable mihomo
使用以下命令立即启动 Mihomo：
systemctl start mihomo
使用以下命令重新加载 Mihomo：
systemctl reload mihomo
使用以下命令检查 Mihomo 的状态：
systemctl status mihomo
使用以下命令查看Mihomo的运行日志：
journalctl -u mihomo -o cat -e或者journalctl -u mihomo -o cat -f

配置文件

wget + 代理服务商的clash订阅链接下载config.yaml到Linux服务器上。然后把config.yaml拷贝到mihomo配置目录下。
如果配置目录不对劲，可以通过mihomo -d [配置目录]指定、自定义。

终端自动代理

需要配置/etc/profile。
在内容中加入：

1
2
3
export http_proxy=127.0.0.1:7890
export https_proxy=127.0.0.1:7890
export all_proxy=127.0.0.1:7890

测试连通

curl www.google.com，如果输出了内容，则可以了。

UI控制

可以配置config.yaml中的：

1
2
3
4
5
6
7
external-controller: '0.0.0.0:9090'
# RESTful API 的口令
secret: 'YourPassword'

# 您可以将静态网页资源（如 clash-dashboard）放置在一个目录中，clash 将会服务于 `RESTful API/ui`
# 参数应填写配置目录的相对路径或绝对路径。
external-ui: ./public

如果要绑定到公网IP，需要把默认的127.0.0.1改为0.0.0.0。
如果对外网开放，强烈建议需要secret鉴权。
我们还需要提供一个UI的web目录。
以选用yacd为例。
https://github.com/haishanh/yacd/releases
下载yacd.tar.xz。解压操作略。
然后我们在配置目录下创建一个public，在public里创建yacd。把内容移动到yacd下面。
然后，就可以通过http://YourIP:9090/ui/yacd/?hostname=YourIP&port=9090&secret=YourSecret进入UI界面了。

Node.js安装

https://pm2.keymetrics.io/docs/usage/quick-start/

rustdesk官方建议我们使用pm2管理服务。

而pm2需要npm安装，即需要安装Node.js。
Node.js的安装又需要用到NVM。
根据：
https://nodejs.org/en/download/package-manager

1
2
3
4
5
6
7
8
# installs nvm (Node Version Manager)
curl -o- https://raw.githubusercontent.com/nvm-sh/nvm/v0.40.0/install.sh | bash
# download and install Node.js (you may need to restart the terminal)
nvm install 22
# verifies the right Node.js version is in the environment
node -v # should print `v22.11.0`
# verifies the right npm version is in the environment
npm -v # should print `10.9.0`

sudo npm install命令无效

但是我们之后发现pm2的安装需要sudo npm install权限。

但提示：sudo npm install command not found

根据
https://stackoverflow.com/a/73308302/16887299

1
2
sudo ln -s $(which npm) /usr/local/bin/npm
sudo ln -s $(which node) /usr/local/bin/node

即可解决。
主要原因是按照node.js官方的安装方法，他们给我们安到了：/root/.nvm/versions/node/v22.11.0/bin/node、/root/.nvm/versions/node/v22.11.0/bin/npm。
所以sudo命令不识别。

npm设置代理

同时发现需要给npm单独配置代理。终端的代理无效。
npm config set proxy http://127.0.0.1:7890
设置好后，可以通过npm config list查看proxy字段是否正确。

至此，就可以安装pm2了。

pm2安装

1
sudo npm install pm2@latest -g

安装完成后，则可以按照rustdesk文档中用pm2来启动服务。

1
2
pm2 start hbbs
pm2 start hbbr

可以通过pm2 list来查看当前pm2管理的服务。
如果想让hbbs / hbbr在重启后自动运行，最好再执行一下pm2 startup和pm2 save。（详细查阅pm2文档）

至此，rustdesk服务就运行在服务器上了。

rustdesk的key

服务一运行，会自动生成一对加密的私钥和公钥（分别位于运行目录下的id_ed25519和id_ed25519.pub文件中），其主要用途是通信加密。

这个id_ed25519.pub文件的内容需要填写到客户端的key中。

如果要更改密钥，请删除id_ed25519和id_ed25519.pub文件并重新启动hbbs / hbbr ， hbbs将生成新的密钥对。

云服务器防火墙配置

根据文档，默认情况下， hbbs监听 21114（TCP，用于 Web 控制台，仅在 Pro 版本中可用）、21115 (TCP)、21116 (TCP/UDP) 和 21118 (TCP)， hbbr监听 21117 (TCP) 和 21119 (TCP) 。请务必在防火墙中打开这些端口。请注意，应为 TCP 和 UDP 启用 21116。 21115用于NAT类型测试，21116/UDP用于ID注册和心跳服务，21116/TCP用于TCP打洞和连接服务，21117用于Relay服务，21118和21119用于支持网络客户端。如果不需要Web客户端（21118、21119）支持，可以禁用相应端口。

设置成如下的即可：

22是为了ssh协议（远程shell）。

坑：不要贸然开放所有端口

不要贸然开放所有端口，经过测试，服务器会莫名遭到DDoS攻击，导致CPU、带宽高占用，服务器连接数峰值达到10K，对于2C2G3M的服务器来说，肯定禁不住。导致ssh经常断联、无响应；远程桌面也很卡顿。
还好分析了一眼阿里云后台的监控数据，不然我以为是网络带宽太小的问题。其实就是端口全开放导致攻击漏洞太大的问题。（也算是亲自体验过DDoS攻击了，这才知道了防火墙的作用有多么重要，自此不再是累赘）

rustdesk客户端配置

设置-网络中。

ID服务器IP+21116端口，中继服务器IP+21117端口。

启动服务，若主页下面图标显示就绪，即可以使用。