# 摘要
本文主要介绍了如何对卫星影像数据进行处理、构建huggingface diffuser格式的数据集并使用diffuser训练controlnet，从而实现使用全球语义图控制生成全球卫星图。



# 数据介绍
训练数据使用了MODIS数据集的xxxxx卫星图与xxxxx语义图。进行了一定的预处理后裁剪成512x512的小图，在SD1.5版本的controlnet上进行训练。(详细步骤还得等黄子扬同学回忆一下看看能不能加上来）

# 数据集的构建
从已经获取一系列source（控制图像）和target（目标图像）样本对开始记录。
需要的数据集结构如下：
```txt
dataset_name:
├─dataset_name.py
├─prompt.jsonl
├─source
│  ├─0_s.png
│  ├─1_s.png
│  ├─2_s.png
│  ├─3_s.png
│  └─...
└─target
   ├─0_t.png
   ├─1_t.png
   ├─2_t.png
   ├─3_t.png
   └─...
```

其中的prompt.jsonl的具体内容如下,每条记录对应一个样本对。

```
{"source": "数据集文件夹内的控制图像相对路径", "target": "数据集文件夹内的目标图像相对路径", "prompt": "{所需要生成的目标图像的描述提示}"}
{"source": "source/0_s.png", "target": "target/_t.png", "prompt": "a remote sensing image of earth. Containing Closed Shrublands,Open Shrublands,Savannas,Grasslands,Permanent Wetlands,Croplands,Urban and Built-up Lands,Barren,Water Bodies,"}
```

最后一个文件是和dataset文件夹同名的dataset_name.py,其主要作用是重写controlnet内的数据读取接口。

```python
--dataset_name.py:
import pandas as pd
import datasets
import os

_VERSION = datasets.Version("0.0.1")

_DESCRIPTION = "TODO"
_HOMEPAGE = "TODO"
_LICENSE = "TODO"
_CITATION = "TODO"

_FEATURES = datasets.Features(
    {
        "target": datasets.Image(),#!!首先需要改的是这三行，用来指定你的prompt中三个列分别对应的类型
        "source": datasets.Image(),#!!首先需要改的是这三行，用来指定你的prompt中三个列分别对应的类型
        "prompt": datasets.Value("string"),#!!首先需要改的是这三行，用来指定你的prompt中三个列分别对应的类型
    },
)

_DEFAULT_CONFIG = datasets.BuilderConfig(name="default", version=_VERSION)


class MyData(datasets.GeneratorBasedBuilder):
    BUILDER_CONFIGS = [_DEFAULT_CONFIG]
    DEFAULT_CONFIG_NAME = "default"

    def _info(self):
        return datasets.DatasetInfo(
            description=_DESCRIPTION,
            features=_FEATURES,
            supervised_keys=None,
            homepage=_HOMEPAGE,
            license=_LICENSE,
            citation=_CITATION,
        )

    def _split_generators(self, dl_manager):
        #！其次是下面三个路径，分别代表：
        # metadata_path -> prompt.jsonl的路径
        # images_dir -> target目标图像的路径，因为我们在prompt里已经记录了target/0.png， 所以这里只需要写上一级的dataset_name文件夹的路径
        # conditioning_images_dir -> source控制图像的路径，因为我们在prompt里已经记录了source/0.png， 所以这里只需要写上一级的dataset_name文件夹的路径
        metadata_path = "/home/disk/hzy/repos/diffusers/examples/controlnet/gpcvrs_small/small.jsonl"
        images_dir = "/home/disk/hzy/repos/diffusers/examples/controlnet/gpcvrs_small"
        conditioning_images_dir = "/home/disk/hzy/repos/diffusers/examples/controlnet/gpcvrs_small"
        dl_manager.download_and_extract
        return [
            datasets.SplitGenerator(
                name=datasets.Split.TRAIN,
                # These kwargs will be passed to _generate_examples
                gen_kwargs={
                    "metadata_path": metadata_path,
                    "images_dir": images_dir,
                    "conditioning_images_dir": conditioning_images_dir,
                },
            ),
        ]

    def _generate_examples(self, metadata_path, images_dir, conditioning_images_dir):
        metadata = pd.read_json(metadata_path, lines=True)

        for _, row in metadata.iterrows():
            text = row["prompt"]#！这里改为我们的提示词列名称，即"prompt"

            image_path = row["target"]#！这里改为我们的目标图像列名称，即"target"
            image_path = os.path.join(images_dir, image_path)
            image = open(image_path, "rb").read()

            conditioning_image_path = row["source"]#！这里改为我们的控制图像列名称，即"source"
            conditioning_image_path = os.path.join(
                conditioning_images_dir, row["source"]#！这里改为我们的控制图像列名称，即"source"
            )
            conditioning_image = open(conditioning_image_path, "rb").read()

            #最后迭代返回的是两个元素：
            # 1、该样本对目标文件路径（此处即为row["target"]）
            # 2、一个包含下列元素的字典，按照描述修改即可，返回的字典的键名对应开头（line45~47）指定的三个名字： 
            #       "prompt":prompt_str,
            #       "target":{
            #                "path": image_path,（目标图像路径）
            #                "bytes": image,（目标图像路径）
            #                 }
            #       "source":{
            #                "path": conditioning_image_path,（控制图像文件路径）
            #                "bytes": conditioning_image,（控制图像本身）
            #                 }
            yield row["target"], {
                "prompt": text,
                "target": {
                    "path": image_path,
                    "bytes": image,
                },
                "source": {
                    "path": conditioning_image_path,
                    "bytes": conditioning_image,
                },
            }
```

# 训练
在完成dataset_name.py的修改后，只需要修改huggingface 给出的controlnet的训练脚本即可：

```bash
#训练脚本train.sh修改示例：
export MODEL_DIR="runwayml/stable-diffusion-v1-5"
export OUTPUT_DIR="{输出的模型路径}"

accelerate launch --multi_gpu train_controlnet.py \
 --mixed_precision="fp16" \
 --pretrained_model_name_or_path=$MODEL_DIR \
 --output_dir=$OUTPUT_DIR \
 --train_data_dir="{你的dataset文件路径}" \
 --resolution=512 \
 --learning_rate=1e-5 \
 --train_batch_size=4 \
 --num_train_epochs=6 \
 --caption_column="prompt" \ #这里修改caption_column为提示词列名称prompt
 --image_column="target" \ #这里修改image_column为目标图像列名称target
 --conditioning_image_column="source" \ #这里修改conditioning_image_column为目标图像列名称source
```

在diffuser的example/controlnet目录下运行train.sh脚本可以直接开始训练。

ControlNet训练——使用语义图控制生成卫星图

# 摘要
本文简要介绍了如何使用`vue3`和`vue-cesium`实现三维地球表面贴图的可视化


# 背景
之前使用了`controlnet`完成了由语义图到卫星图的2d生成任务，并通过`tilediffusion`插件实现了无缝扩展生成全球的一整块卫星图瓦片。现在试图对这个卫星图进行3d的可视化。

# 创建vue项目
在vue.js中文官网https://cn.vuejs.org/ 上，目前的创建命令是
```bash
npm create vue@latest
```
输入项目名称后有一堆选项选，我只加了`ts`，其他的以后有需要再说。
# 安装vue-cesium组件库
`vue-cesium`是一个新兴的，将`cesium.js`包装成`Vue3`组件库的项目。官网为https://zouyaoji.top/vue-cesium/ 

安装命令目前为
```bash
npm install vue-cesium
```

# 创建SPA并导入vue-cesium相关组件，实现可视化
清理成最小运行单元后，`src`下创建一个`Global.vue`的`SPA`，内容如下：
```jsx
<script setup>
import { reactive } from 'vue'
import { VcConfigProvider, VcViewer, VcLayerImagery, VcImageryProviderSingletile } from 'vue-cesium'

const vcConfig = reactive({
    cesiumPath: 'https://unpkg.com/cesium@latest/Build/Cesium/Cesium.js'
})
const imagePath = './earth_generated_8ds_nearest_no_black.png'
</script>

<template>
    <vc-config-provider :cesium-path="vcConfig.cesiumPath">
        <vc-viewer>
            <vc-layer-imagery>
                <vc-imagery-provider-singletile :url=imagePath>

                </vc-imagery-provider-singletile>
            </vc-layer-imagery>
        </vc-viewer>
    </vc-config-provider>
</template>
```
注意这里的`imagePath`变量，为了访问方便，我把`earth_generated_8ds_nearest_no_black.png`这个卫星图放在了`public`文件夹下，由于打包后`public`文件夹下的内容会被直接放到根目录下，这样就可以使用`./`的相对路径访问，在开发环境与生产环境的`dist`下都可以访问成功。

如果图像放在了`src`下的目录，比如`assets`，实测这里用`@/assets/xxxxx`是不可行的，暂时不清楚是不是组件库的bug还是需要使用更复杂的方式导入图像。

然后修改一下`App.vue`下的内容。
```jsx
<script setup lang="ts">
import Global from './pages/Global.vue'
</script>

<template>
    <Global />
</template>

<style scoped></style>
```
为了打包后访问js文件路径不出错，还需要在`vite.config.ts`中加入
```ts
export default defineConfig({
    base: './',
})
```
# 效果

![CleanShot 2024-04-14 at 19.59.32.jpg](https://xuqi.space/static/img/afe680ad8c7bf4d23c62b0ff0db27161.CleanShot%202024-04-14%20at%2019.59.32.webp)

![CleanShot 2024-04-14 at 20.00.02.jpg](https://xuqi.space/static/img/8767ff30c2cf48231867da1dba5ee985.CleanShot%202024-04-14%20at%2020.00.02.webp)

使用vue+cesium实现三维地球可视化

# 2024华为软件精英挑战赛
首先祝贺蒟蒻小队"星月湖"（话说为啥ikaros每次起名字都是这种风格啊喂!!!），经过了3.7-3.22共计2 weeks 1 day的折磨，凭着亿点点运气获得武长赛区30名的成绩，进入复赛。🥹🎉🥳

下面将记录一下suki whu sakura同学（也就是insomnia本睡不醒啦~！），在这次比赛中遇到了什么奇奇怪怪又还算有意思的经历吧~（其实是不吐不快了，逃~



# 任务书
<iframe src="https://xuqi.space:7070/api/public/dl/B3-ZhIKp?inline=true" width="100%" height="1000px">
  <p>Your browser does not support iframes.</p>
</iframe>

# 对任务书的思考
看完任务书，我们主要思考的方向是
1. 机器人寻路算法
2. 机器人避障算法（为了让机器人之间互相不碰撞）
3. 机器人拾取货物的策略
4. 船选择泊位的策略
5. 船何时开船前往虚拟点的策略
6. 船在泊位之间轮转的策略
7. 针对特定地图优化的策略

# 关于跳帧、碰撞问题
题目中要求每帧必须在`15ms`内处理完成并发送`OK`，否则在没有收到`OK`前，判题器将不会继续输入场面帧信息，若处理超过了`15ms`，那么以判题器接受到`OK`的时刻为准，判题器输入的帧信息的序号就可能发生不连续的情况。

如果发生跳帧，那么就会丢失掉某一帧的场面信息，如果该帧恰好判题器向场地中随机添加了一些货物，那么这部分货物信息就被永远丢失掉了，这对分数影响是巨大的。我们应该**保证，即使在`15ms`内没能处理完所有机器人的计算操作（主要是寻路），也应该在帧耗时接近`15ms`的时候输出`OK`，并接受下一帧的场面信息**，让没能处理完的计算操作在**后台继续执行**，只需要**在使用时检查计算结果是否可用**就好了。

而对于碰撞，发生碰撞后会使得机器人进入长度为20帧的`RECOVERING`状态，这段时间内机器人无法响应任何操作，很显然发生碰撞也是纯亏的操作，所以我们应该**保证不会发生碰撞**。

# 关于寻路算法
寻路算法有单源最短路径和多源最短路径之分，我们一开始的思路就是单源最短路径中的`A*`算法，这个算法在最差情况下会退化到`dijkstra`算法，也就是最差时间复杂度为$O(n\log n)$，因为觉得多源最短路径是要$O(n^3)$时间复杂度，所以可能来不及在初始化的时候搞定，后面使用了泛洪算法求地图上的连通块与到某一点的距离，发现其实dfs遍历一整遍地图也耗时不大，初始化的5s其实大有可为（但截至目前也没有想到什么很好的办法）。

我们的`A*`算法的代码如下：

```cpp
// 启发式函数：曼哈顿距离
int PathFinder::HeuristicCostEstimate(int current_x, int current_y, int goal_x, int goal_y) {
    return abs(current_x - goal_x) + abs(current_y - goal_y);
}

// 判断移动是否合法
bool PathFinder::IsValidMove(int x, int y) { return world.originMap.isAccess(x, y); }

// A*搜索算法
Path PathFinder::FindPath(int sx, int sy, int ex, int ey) {
    //起止点相同，不进入寻路
    if(sx == ex && sy == ey){
        return {};
    }

    //不存在缓存地图，进入寻路
    std::priority_queue<Node, std::vector<Node>, std::greater<Node>> open_set;
    std::vector<std::vector<bool>> closed_set(utils::MAP_SIZE, std::vector<bool>(utils::MAP_SIZE, false));

    open_set.push(Node(sx, sy, 0, HeuristicCostEstimate(sx, sy, ex, ey), {}));

    while (!open_set.empty()) {
        Node current = open_set.top();
        open_set.pop();

        if (current.x == ex && current.y == ey) {
            return current.path;
        }

        if (closed_set[current.x][current.y]) {
            continue;
        }

        closed_set[current.x][current.y] = true;

        for (const auto &dir: directions) {
            int new_x = current.x + dir[0];
            int new_y = current.y + dir[1];

            if (IsValidMove(new_x, new_y)) {
                int new_cost = current.cost + 1;
                int heuristic = HeuristicCostEstimate(new_x, new_y, ex, ey);

                Path new_path = current.path;
                new_path.push_back((dir[0] == 0 && dir[1] == 1)    ? utils::Direction::RIGHT
                                   : (dir[0] == 0 && dir[1] == -1) ? utils::Direction::LEFT
                                   : (dir[0] == -1 && dir[1] == 0) ? utils::Direction::UP
                                                                   : utils::Direction::DOWN);

                open_set.push(Node(new_x, new_y, new_cost, heuristic, new_path));
            }
        }
    }

    return {}; // 未找到路径
}
```
可以看到，这里面还是存在着许多可以优化的地方的，比如`std::vector<bool>`的使用，熟悉`STL`的同学应该知道，`std::vector<bool>`其实并不是`bool`的`vector`，`STL`中对`std::vector<bool>`做了特化，对`bool`类型做了个proxy，使用了一个**代理类**，所以实际上凡是使用`std::vector<bool>`的地方，都应该想想是否可以使用`bool []`作为替代。

其次，这里面存在着大量的**拷贝**操作，每次操作`current.path`的时候，将会产生一次拷贝，而`path`是一个`vector<utils::Direction>`，所以将会产生不必要的性能消耗。事实上，可以记录一个每个节点的parents节点，这样可以通过**对终点的回溯**找到路径，解决发生大量拷贝的问题。

再次，这里对`Path`类型使用了`vector<utils::Direction>`的实现，这里让我们在后面的开发产生了产生了巨大的不便与潜在问题。后来想想，这里就应该使用`vector<Position>`的，每一个节点应该是一个包含`x、y`的位置，而后在输出的时候将两个位置的坐标做比对得到移动方向。如果在寻路的时候直接得到的就是一个`vector<utils::Direction>`的话，那么后续就永远丢**失掉了机器人的坐标位置**了，一旦发生跳帧、移动执行失败等错误，那么整个`Path`就不正确了，那就只能重新寻路了，这样会让整个程序显得不那么优雅。或许这就是“永远不要提早优化”的含义吧。

最后就是**可读性**问题，这次我们的coding习惯感觉还是存在很大的差异的，包括命名方式、对`git`的使用，对`.clangformat`的使用等等。考虑在之后写单独的文章介绍一些在ubuntu下的一些开发标准。

# 关于如何保证不发生碰撞——机器人避障算法
机器人避障是一个复杂的话题，不过总体来说，有两种思路，一种是考虑每个机器人在移动的时候进行试探观察，另一种是考虑对所有机器人的路径做整体调整规划。

## 碰撞的两种可能性

![CleanShot 2024-03-26 at 15.34.17.jpg](https://xuqi.space/static/img/69a1fb2404adf5a2e5036566b45bb478.CleanShot%202024-03-26%20at%2015.34.17.webp)

对于机器人来说，碰撞只会存在两种可能性，第一种是两个机器人在下一帧时将会**移动到同一个位置**，我们可以称为`collision`；第二种是两个机器人在下一帧将会**交换位置互相穿过**，我们称为`cross over`

而对于机器人`2`下一帧将会移动到机器人`3`这一帧的位置，机器人`3`下一帧将会移动到其他方向的位置，这种情况认为是**合法**的，因为实际在移动操作中是**不考虑输出指令的先后顺序**的，判题器会视为所有机器人同时移动。

## 通过试探观察进行避障

![CleanShot 2024-03-26 at 19.13.43.jpg](https://xuqi.space/static/img/c53d575c5858943fb237524f88654a49.CleanShot%202024-03-26%20at%2019.13.43.webp)

如果机器人`0`的路径列表是五个向右走的话（列表里存的节点实现到底是方向还是坐标这点并不要紧），那么在进行第一步行走的时候，`0`号机器人应该要查看右侧蓝色虚线标注的`0`号位置的上下右三个方向是否有机器人，如果有机器人的话，该机器人假设是`1`号机器人，如果正好也要移动到蓝色虚线标注的`0`号位置的话，那么就判断会发生`collision`。解决办法则是让`0`号机器人**呆在原地静止一帧**。


![CleanShot 2024-03-26 at 19.22.50.jpg](https://xuqi.space/static/img/6a4131548983b4acf740872e6ae899f1.CleanShot%202024-03-26%20at%2019.22.50.webp)

这里要思考的点是，**选择呆在原地静止一帧能不能解决问题**，与**选择呆在原地静止一帧会导致什么**。

`0`号机器人在原地静止一帧后，`1`号机器人就会占据蓝色虚线标注的`0`号位置，那么在下一帧，`1`号机器人如果向左走，则会触发`0`号机器人和`1`号机器人的`cross over`，如果往上或者往下走，那么`0`号机器人就可以正常移动了。


![CleanShot 2024-03-26 at 19.57.17.jpg](https://xuqi.space/static/img/53307afeee2f5773145bf2e0dfd3e3a0.CleanShot%202024-03-26%20at%2019.57.17.webp)

如果`0`号机器人要向右走，却发现右侧的位置已经有一个`1`号机器人了，那么如果`1`号机器人下一帧的移动方向是向左，就判断会发生`cross over`。解决办法则是让`0`号机器人**尝试向上、下、右侧避让，并在避让后插入一个相反的方向回到原来的位置**。

这里要注意的点是，**选择向哪个方向避让**与**为什么让`0`号机器人避让而不是`1`号机器人避让**

首先看向哪个方向避让的问题，我们可以进行如下思考：

1. 要选择可以走的方向避让，如果避让的那个方向是墙，则换一个方向
2. 如果`1`号机器人在下一帧要向下移动，那么`0`号机器人本帧就不要向下避让了，因为如果`0`号机器人本帧向下避让，那么在下一帧依然会发生`cross over`，但如果`0`号机器人不向下避让，则之后就不会再次发生`cross over`。总而言之，避让的方向选择不与被避让机器人下一步方向相同的。
3. 假如`0`号机器人排除掉了向下避让，还有向左向上两个方向进行选择，哪一个方向是更好的呢？我们发现`0`号机器人之后的路径中本就有一个向上的行走，如果我们**发现向上避让，并不插入相反的方向让机器人回到避让前的位置，而是接着向右走四步，每一步都可以执行并且也能到达终点的话，那么选择向上避让就会节省两帧的时间**。但如果不能满足这个条件的话，那么在当前已知信息下，向上避让与向左避让是同样优的。

再就是为什么让`0`号机器人避让而不是`1`号机器人避让的问题，这里涉及到了优先级的概念，暂时按下不表（这部分的设计insomnia并不是很清楚，等搞清楚了再补充）。

感谢评论区Zerol Acqua的补充
> 文章里提到的“碰撞的两种可能性”的逻辑，对于试探观察（实时）和整体调整（寻路时）的避障都是适用的。
> 
> 然而，还有一种在目前代码（实现不健全的前提下）会出现的情况
> 
> 一个机器人无法移动在发呆
> 由于寻路、取货、卸货时，机器人有一帧或者多帧无法移动
> 另一个机器人要往静止机器人所在的位置上移动
> 由于存在固定的优先级，优先级高的往优先级停的静止机器人上移动
> 寻路的结果，与避障的结果存到同一个路径队列 robotPaths[i] 中
> 这样就存在一个问题，静止的机器人如果要躲避来袭的高优先级机器人，势必要往自己的路径队列里加入避障移动（一般是一来一回的移动）。
> 假如这个静止的机器人正在寻路，此时发生避障行为就很麻烦，因为寻路随时会结束并往机器人路径里更新移动，
> 那么就可能出现加入的避障移动被寻路结束得到的路径覆盖的问题。
> 
> 同时，因为避障算法是在主线程 RobotWork() 中执行的，寻路则在分离的子线程中执行的。将两者的结果存在同一个路径队列中，会导致每次更新避障也要访问机器人的路径，那就必须扩大上锁的范围了
> 
> 因此，在试探观察避障的实现中，将避障的移动路径与寻路的移动路径分别存在两个队列中。这种分离方式，既能避免路径覆盖的问题，又有助于缩小锁的作用范围。


## 通过整体调整规划进行避障



![CleanShot 2024-03-27 at 17.22.05.jpg](https://xuqi.space/static/img/ea7ddead3abfe03ed6274d8f8e9b5c6c.CleanShot%202024-03-27%20at%2017.22.05.webp)

如图所示，`0`号机器人与`1`号机器人的路径列表中都存放着`xyt`结构，即在`t`帧时刻，机器人将要前往的`xy`位置。根据`xyt`我们可以发现，如果`0`号机器人与`1`号机器人的路径列表中存在`xyt`都相同的节点，则说明会发生`collision`

找到了发生`collision`的位置，就可以通过插入静止帧等办法解决`collision`。


![CleanShot 2024-03-27 at 17.32.35.jpg](https://xuqi.space/static/img/9f583133e0dda1bb809825ffa3c42a8b.CleanShot%202024-03-27%20at%2017.32.35.webp)

如图所示，根据`xyt`我们可以发现，如果`0`号机器人与`1`号机器人的路径列表中存在`t对齐而xy十字交叉相同`的节点，则说明会发生`cross over`

我们可以在机器人的路径列表发生增长的时候对所有机器人的整个路径列表进行检查，查看是否存在`collision`与`cross over`的情况，并尝试解决。

这里要思考一个问题，**尝试解决`cross over`与`collision`的过程中，我们是否会引入新的`cross over`或`collision`呢？**

我个人认为，通过递归结构可以解决该问题。即，一次只尝试解决当前场面中存在的碰撞情况，尝试解决之后，立刻再次检测是否存在碰撞情况，并再次尝试解决，直到不再存在碰撞为止。

那么，感性上这么做是可行的，如何证明不断递归尝试解决碰撞，一定可以停机呢？（也即在经过有限次该过程后，场面总能达到不存在碰撞的情况）

# 关于如何保证不跳帧——Timer与WaitGroup结构
我们希望程序处理每一帧的用时尽量不超过`15ms`，即使超过了`15ms`也不能影响下一帧的信息读入与处理。

在`go`语言中有所谓的`Timer`结构，专门用于处理这种需求。

```go
type Timer struct {
    C <-chan Time
    r runtimeTimer
}

func waitChannel(conn <-chan string) bool {
    timer := time.NewTimer(1 * time.Second) //设置超时时间 1s
    
    select {
    case <- conn:
        timer.stop() // 接收到数据后，要停止计时器
        return true
    case timer.C: //超时判断
        fmt.Println("WaitChannel timeout!")
        return false
    }
}
```
在这段代码中，`Timer`结构体是由一个`channel`与一个`rutimeTimer`构成的，`rutimeTimer`由`go运行时`接管，在到达指定的超时时间后向`C`这个`channel`中放入一个值。

在`waitChannel`函数中，`select`关键字会**阻塞**尝试从`conn`与`timer.C`中取出一个值，哪个`channel`中先有值，`select`就会执行对应的`case`代码，这样就保证了即使`conn`一秒后仍然没有值被放入，`select`也可以从`timer.C`中取出值，从而保证该函数的阻塞时长不会超过`1s`。

回到这次比赛的例子上，我们就是要在`c++`中实现类似的`Timer`结构的功能。

由于我们每个机器人都要开启一个单独的线程执行，所以一共会开很多个线程，这让人想到`go`中的`WaitGroup`结构。

```go
func main() {
    var waitGroup sync.WaitGroup

    start := time.Now()
    waitGroup.Add(5)
    for i := 0; i < 5; i++ {
        go func() {
            defer waitGroup.Done()
            time.Sleep(time.Second)
            fmt.Println("done")
        }()
    }

    waitGroup.Wait()
    fmt.Println(time.Now().Sub(start).Seconds())
}
```
输出为
```txt
done
done
done
done
done
1.000306089
```
在上面的代码中，`waitGroup.Add(5)`指定了要开启协程的数量，在协程内部，调用`waitGroup.Done()`将计数器减一，当`waitGroup`的计数器小于等于`0`时，解除`waitGroup.Wait()`的阻塞。

我们将`waitGroup`与`Timer`结构结合起来。也就是让解除`waitGroup.Wait()`阻塞的条件除了计数器小于等于`0`，还要加上超过了一段时间也解除阻塞。

用`C++`代码实现如下：

```cpp
class WaitGroup {
private:
    std::mutex mtx;
    std::condition_variable cv;
    int count;
    size_t waitUntilOnMs;

public:
    WaitGroup(int initialCount, size_t waitUntil) : count(initialCount), waitUntilOnMs(waitUntil) {
    }

    void Add(int delta) {
        std::thread([this] {
            std::this_thread::sleep_for(std::chrono::milliseconds(waitUntilOnMs));
            unique_lock lock(mtx);
            count = 0;
        }).detach();
        unique_lock lock(mtx);
        count += delta;
    }

    void Done() {
        unique_lock lock(mtx);
        count -= 1;
        if (count <= 0) {
            count = 0;
            cv.notify_all();
        }
    }

    void Wait() {
        unique_lock lock(mtx);
        cv.wait(lock, [this] { return count <= 0; });
    }
};
```
可以看到，在上面的程序中，`WaitGroup`类中有一个计数器与一个计时器，当调用`Add`函数时，会开启一个线程作为计时器，当到达指定的时间时，将计数器重置为`0`，此时视为等同于调用了`Done`函数至计数器归零。

# 事件循环

整理一下整个过程中按照时间顺序的时间循环

1. 世界初始化（读入地图与泊位初始信息）
2. 利用初始化时间对地图做预处理
3. 循环🔄
4. 读入帧信息
5. 根据帧信息更新场面数据
6. 调整机器人的路径（耗时操作）
7. 更新场面统计信息
8. 判断拾取命令
9. 判断卸货命令
10. 移动命令
11. 循环🔄

# 调整机器人路径算法
## 第一次取货
由于第一次取货是从机器人的初始位置出发，去寻找货物，再送到泊位，这部分的全局最优解应该满足，机器人到货物的距离+货物到最近泊位的距离最小（这里不考虑价值是因为第一次取货必定场上货物数量少于机器人数，所以不考虑价值），满足该条件则将机器人与该货物绑定，货物进入机器人的取货列表。
## 非第一次的取货
对于非第一次取货，总是从泊位出发，到距离目标货物最近的泊位结束，因此价值函数可以是
$$
    \forall(r,g)\quad\argmax_{(r,g)}\frac{g.value}{dist(r.xy, g.xy)+closest\_berth\_dist(g)}
$$
其中$r$为机器人，$g$为货物，$g.value$为货物$g$的价值，$dist(r.xy, g.xy)$为机器人$r$到货物$g$的路径长度，$closest\_berth\_dist(g)$为货物到距其最近的泊位的距离
## 对选择 货物-机器人对 这一过程的抽象
我们发现，总是要对所有的$(r,g)$进行遍历，对某一个价值函数进行计算，最后得到使得价值函数最大的$(r,g)$对，因此对该过程抽象为一个函数。

2024华为软件精英挑战赛-星月湖复盘

# 起因
马上就要放寒假了，组里的服务器都没有配公网ip的（我甚至怀疑没有配固定ip），为了能够回家后在家里也能连上组里服务器跑代码，因此需要做一个内网穿透，让服务器的ssh服务暴露在公网上。





# frp是什么
frp 是一个专注于内网穿透的高性能的反向代理应用，支持 TCP、UDP、HTTP、HTTPS 等多种协议，且支持 P2P 通信。**可以将内网服务以安全、便捷的方式通过具有公网 IP 节点的中转暴露到公网。**

github repo link：[https://github.com/fatedier/frp/](https://github.com/fatedier/frp/)

文档：[https://gofrp.org/zh-cn/docs/](https://gofrp.org/zh-cn/docs/)

# 安装frp
frp 主要由两个组件组成：客户端(frpc) 和 服务端(frps)。通常情况下，服务端部署在具有公网 IP 地址的机器上，而客户端部署在需要穿透的内网服务所在的机器上。

由于内网服务缺乏公网 IP 地址，因此无法直接被非局域网内的用户访问。用户通过访问服务端的 frps，frp 负责根据请求的端口或其他信息将请求路由到相应的内网机器，从而实现通信。
## 安装frps
在frp的中文文档中写到“frp 采用 `Go` 语言编写，支持跨平台，只需下载适用于您平台的二进制文件即可执行，无需额外依赖。”

但是，这里经过我自己的使用，我比较推荐使用github上的另一个叫做`frps-onekey`的repo提供的脚本
github repo link：[https://github.com/MvsCode/frps-onekey](https://github.com/MvsCode/frps-onekey)

这个脚本的使用方式如下：
```shell
# 从gitee下载
wget https://gitee.com/mvscode/frps-onekey/raw/master/install-frps.sh -O ./install-frps.sh
# 从github下载
wget https://raw.githubusercontent.com/mvscode/frps-onekey/master/install-frps.sh -O ./install-frps.sh

# 安装
chmod 700 ./install-frps.sh
./install-frps.sh install

# 卸载
./install-frps.sh uninstall

# 更新
./install-frps.sh update

# 使用
frps {start|stop|restart|status|config|version}
```

经过测试，该脚本可能在`Check updates for shell...`阶段卡住，解决办法是注释掉`shell_update`这个函数。

## frps配置文件
按照上述方式安装frps脚本后，配置文件的路径为`/usr/local/frps/frps.ini`，该配置文件参数如下：
```ini
# [common] is integral section
[common]
# A literal address or host name for IPv6 must be enclosed
# in square brackets, as in "[::1]:80", "[ipv6-host]:http" or "[ipv6-host%zone]:80"
bind_addr = 0.0.0.0
bind_port = 5443 # 这里填入frps监听的端口，frpc会向这个端口发送流量
# udp port used for kcp protocol, it can be same with 'bind_port'
# if not set, kcp is disabled in frps
kcp_bind_port = 5443 # 这里保持和bind_port一致
# if you want to configure or reload frps by dashboard, dashboard_port must be set
dashboard_port = 6443 # 这里填入dashboard的端口号，配置后可以通过访问该端口查看frp的连接情况
# dashboard assets directory(only for debug mode)
dashboard_user = xxxxxxxx # 访问dashboard所需的用户名（重要！）
dashboard_pwd = xxxxxxxx # 访问dashboard所需的密码（重要！）
# assets_dir = ./static
vhost_http_port = 8080 # 这里填入http服务的转发端口，frpc的内网http服务会被转发到这里
vhost_https_port = 4443 # 这里填入https服务的转发端口
# console or real logFile path like ./frps.log
log_file = ./frps.log
# debug, info, warn, error
log_level = info
log_max_days = 3
# auth token
token = xxxxxxxx # 校验密码（重要！），frpc需要在配置文件中填入一致的密码才会被frps接受
# It is convenient to use subdomain configure for http、https type when many people use one frps server together.
subdomain_host = 175.178.244.215
# only allow frpc to bind ports you list, if you set nothing, there won't be any limit
#allow_ports = 1-65535
# pool_count in each proxy will change to max_pool_count if they exceed the maximum value
max_pool_count = 50
# if tcp stream multiplexing is used, default is true
tcp_mux = true
```
更改好配置文件后，执行`frps restart`重新启动frps服务，执行`frps status`查看运行状况。
输出为`Frps (pid xxxx) is running...`则代表正常运行。

## 安装frpc
安装frpc则一般可以直接使用二进制包。从[https://github.com/fatedier/frp/releases](https://github.com/fatedier/frp/releases) 页面下载`.tar.gz`格式的压缩包后解压，其中有`frpc`、`frpc.toml`、`frps`、`frps.toml`四个文件，我们只需要其中`frpc`、`frpc.toml`两个。

## frpc配置文件
安装frpc时得到的`frpc`则为frpc的可执行二进制文件、`frpc.toml`则为其配置文件。

如果是要转发`ssh`服务的话，对应示例配置文件如下：
```toml
serverAddr = "x.x.x.x" # 你的公网服务器地址
serverPort = 5443 # frps的bind_port
auth.token = xxxx # frps的校验密码

[[proxies]]
name = "mygpuserver_ssh" # 该服务的名称
type = "tcp" # 转发类型，这里填入tcp
localIP = "127.0.0.1" # 本地ip，默认为127.0.0.1
localPort = 22 # ssh服务的端口号，默认为22
remotePort = 6000 # 访问公网服务器对应的端口
```

使用该配置的话，那么使用`ssh`连接内网服务器的命令为
```shell
ssh -P 6000 user@{serverAddr}
```


如果是要转发`http`服务的话，对应示例配置文件如下：
```toml
serverAddr = "x.x.x.x" # 你的公网服务器地址
serverPort = 5443 # frps的bind_port
auth.token = xxxx # frps的校验密码

[[proxies]]
name = "my_http_application1"
type = "http"
localPort = 80
customDomains = ["www.yourdomain.com"]

[[proxies]]
name = "my_http_application2"
type = "http"
localPort = 8080
customDomains = ["www.yourdomain2.com"]
```


修改完配置文件后，请别忘了给`frpc`添加可执行权限

`chmod a+x frpc`

## 使用systemd配置frpc服务
为了让`frpc`在后台运行，且可以开机自启，异常退出时自动恢复，我们有必要将`frpc`配置成`systemd`管理的服务。
```shell
# 创建frpc服务的配置文件
sudo vim /etc/systemd/system/frpc.service
```
写入内容为：
```
[Unit]
# 服务名称，可自定义
Description = frp server
After = network.target syslog.target
Wants = network.target

[Service]
Type = simple
# 配置异常退出重新启动
Restart=on-failure # 或者always
RestartSec=3
# 启动frpc的命令，需修改为您的frpc的安装路径
ExecStart = /path/to/frpc -c /path/to/frpc.toml

[Install]
WantedBy = multi-user.target
```
设置`frpc`开机自启动命令为
```shell
sudo systemctl enable frpc
```
使用`systemd`对`frpc`进行管理的命令为
```shell
# 启动frp
sudo systemctl start frps
# 停止frp
sudo systemctl stop frps
# 重启frp
sudo systemctl restart frps
# 查看frp状态
sudo systemctl status frps
```

从公网访问你的服务器/PC——frp内网穿透搭建

## 题目1
给定线性空间$\mathbb{R}^{3}$的两组基
$$
\varepsilon_{1}=(1,0,1)^{\top},\varepsilon_{2}=(2,1,0)^{\top},\varepsilon_{3}=(1,1,1)^{\top}
$$
$$
\eta_{1}=(1,2,-1)^{\top},\eta_{2}=(2,2,-1)^{\top},\eta_{3}=(2,-1,-1)^{\top}
$$
定义$\mathbb{R}^{3}$的线性变换$\mathscr{A}$为$\mathscr{A}(\varepsilon_i)=\eta_i(i=1,2,3)$ 试求：

(1)从基$\varepsilon_1,\varepsilon_2,\varepsilon_3$到基$\eta_1,\eta_2,\eta_3$的过渡矩阵； 

(2)$\mathscr{A}$在基$\varepsilon_1,\varepsilon_2,\varepsilon_3$下的矩阵；

(3)$\mathscr{A}$在基$\eta_1,\eta_2,\eta_3$下的矩阵


解：

(1)
从基$\varepsilon_1,\varepsilon_2,\varepsilon_3$到基$\eta_1,\eta_2,\eta_3$的过渡矩阵为
$$
P=(\varepsilon_1,\varepsilon_2,\varepsilon_3)^{-1}(\eta_1,\eta_2,\eta_3)=
\begin{pmatrix}
-2&1&1\\0&1&1\\1&0&1\end{pmatrix}^{-1}\begin{pmatrix}1&2&2\\2&2&-1\\-1&-1&-1\end{pmatrix}=\frac{1}{2}\begin{pmatrix}-4&-3&3\\2&3&3\\2&1&-5\end{pmatrix}
$$

(2)
$\mathscr{A}(\varepsilon_1,\varepsilon_2,\varepsilon_3)=(\eta_1,\eta_2,\eta_3)=(\varepsilon_1,\varepsilon_2,\varepsilon_3)P$，故$\mathscr{A}$在基$\varepsilon_1,\varepsilon_2,\varepsilon_3$下的矩阵为$P$

(3)
$\mathscr{A}(\eta_1,\eta_2,\eta_3)=\mathscr{A}((\varepsilon_1,\varepsilon_2,\varepsilon_3)P)=(\eta_1,\eta_2,\eta_3)P$，故$\mathscr{A}$在基$\eta_1,\eta_2,\eta_3$下的矩阵为$P$

## 题目2
设$\varepsilon_1,\varepsilon_2,\varepsilon_3,\varepsilon_4$是4维线性空间$V$的一组基，线性变换$\mathscr{A}$在这组基下的矩阵为
$$
\left(\begin{matrix}1&0&2&1\\-1&2&1&3\\1&2&5&5\\2&-2&1&-2\end{matrix}\right)
$$

(1)求$\mathscr{A}$在基$\eta_1=\varepsilon_1-2\varepsilon_2+\varepsilon_4,\eta_2=3\varepsilon_2-\varepsilon_3-\varepsilon_4,\eta_3=\varepsilon_3+\varepsilon_4,\eta_4=2\varepsilon_4$下的矩阵； 

(2)求$\mathscr{A}$的值域与核

解：

(1)
从$\varepsilon_1,\varepsilon_2,\varepsilon_3,\varepsilon_4$到$\eta_1,\eta_2,\eta_3,\eta_4$的过渡矩阵$P$为
$$
P=\begin{pmatrix}1&0&0&0\\-2&3&0&0\\0&-1&1&0\\1&-1&1&2\end{pmatrix}
$$
因此，$\mathscr{A}$在$\eta_1,\eta_2,\eta_3,\eta_4$的矩阵为
$$
A'=P^{-1}AP=\begin{pmatrix}1&0&0&0\\-2&3&0&0\\0&-1&1&0\\1&-1&1&2\end{pmatrix}^{-1}\begin{pmatrix}1&0&2&1\\-1&2&1&3\\1&2&5&5\\2&-2&1&-2\end{pmatrix}\begin{pmatrix}1&0&0&0\\-2&3&0&0\\0&-1&1&0\\1&-1&1&2\end{pmatrix}=\begin{pmatrix}2&-3&3&2\\\frac23&-\frac43&\frac{10}3&\frac{10}3\\\frac83&-\frac{16}3&\frac{40}3&\frac{40}3\\0&1&-7&-8\end{pmatrix}
$$

(2)
对$A$行化简得到
$$
A=\begin{pmatrix}1&0&2&1\\-1&2&1&3\\1&2&5&5\\2&-2&1&-2\end{pmatrix}\sim\begin{pmatrix}1&0&2&1\\0&2&3&4\\0&2&3&4\\0&-2&-3&-4\end{pmatrix}\sim\begin{pmatrix}1&0&2&1\\0&1&\frac{3}{2}&2\\0&0&0&0\\0&0&0&0\end{pmatrix}
$$
$A$的主元列为1、2列，因此，$R(\mathscr{A})=\operatorname{span}(\varepsilon_1,\varepsilon_2)$

任取$k_1\varepsilon_1+k_2\varepsilon_2+k_3\varepsilon_3+k_4\varepsilon_4\in\operatorname{Ker}(\mathscr{A})$

也即
$$
\begin{pmatrix}1&0&2&1\\0&1&\frac{3}{2}&2\\0&0&0&0\\0&0&0&0\end{pmatrix}\begin{pmatrix}k_1\\k_2\\k_3\\k_4\end{pmatrix}=0
$$
解得
$$
\begin{cases}
k_1 = -2k_3 -k_4\\
k_2 = -\frac{3}{2}k_3-2k_4\\
k_3 \text{是自由变量}\\
k_4 \text{是自由变量}\\
\end{cases}
$$
也即
$$
\operatorname{Ker}(\mathscr{A})=(-2k_3 -k_4)\varepsilon_1+(-\frac{3}{2}k_3-2k_4)\varepsilon_2+k_3\varepsilon_3+k_4\varepsilon_4=\operatorname{span}(-2\varepsilon_1-\frac{3}{2}\varepsilon_2+\varepsilon_3,-\varepsilon_1+2\varepsilon_2+\varepsilon_4)
$$

## 题目3
在$n$维线性空间$\mathbb{R}[x]_n$中，定义线性变换$\mathscr{D}(f(x))=f^{\prime}(x)$,其中$f(x)\in \mathbb{R}[x]_n$. 求$\mathscr{D}$的值域与核。

解：

任取
$f(x)=a_{0}+a_{1}x+a_{2}x^{2}+\cdots+a_{n-1}x^{n-1}\in \mathbb{R}[x]_n$, 则

$$
\mathscr{D}(f(x))=f^{\prime}(x)=a_{1}+2a_{2}x+\cdots+(n-1)a_{n-1}x^{n-2}
$$
 由$a_0,a_1,a_2,\cdots,a_{n-1}$的任意性，$R(\mathscr{D})=\mathbb{R}[x]_{n-1}$.
 
 $\mathscr{D}(f(x))=0$ 当且仅当$a_{1}=a_{2}=\cdots=a_{n-1}=0$,故$\operatorname{Ker}(\mathscr{D})=\mathbb{R}$。
 
 
 ## 题目4
设$A,B$是$n$阶矩阵，并且$AB=BA$。证明： 
 
(1)如果$A$有$n$个互异的特征值，则$B$相似于对角矩阵。
 
(2)如果$A$与$B$均为可对角化矩阵，则存在可逆矩阵$P$使得$P^{-1}AP$ 与$P^{-1}BP$同时为对角矩阵

证明：

(1)如果$A$有$n$个互异的特征值$\lambda_{1},\cdots,\lambda_{n}$，则存在可逆矩阵$P$使得
$$
A=P\left(\begin{matrix}\lambda_{1}&&\\&\ddots&\\&&\lambda_{n}\end{matrix}\right)P^{-1}
$$
也即
$$
AB=P\left(\begin{matrix}\lambda_{1}&&\\&\ddots&\\&&\lambda_{n}\end{matrix}\right)P^{-1}B=BA=BP\left(\begin{matrix}\lambda_{1}&&\\&\ddots&\\&&\lambda_{n}\end{matrix}\right)P^{-1}
$$
等式两边同时左乘$P^{-1}$右乘$P$，则
$$
\left(\begin{matrix}\lambda_{1}&&\\&\ddots&\\&&\lambda_{n}\end{matrix}\right)P^{-1}BP=P^{-1}BP\left(\begin{matrix}\lambda_{1}&&\\&\ddots&\\&&\lambda_{n}\end{matrix}\right)
$$
因为对角线元素互异的对角阵的可交换矩阵一定是对角阵，$P^{-1}BP$为对角阵，也即$B$相似于对角阵

(2)
该命题为高等代数中的“同时相似对角化问题”，
详见https://mp.weixin.qq.com/s?__biz=MzU4MTg0NjEzOQ%3D%3D&mid=2247492990&idx=2&sn=da46d2701c4c7d24c83d555a3648781d&chksm=fd43f06aca34797ccad03d57e091bf5f60b3a3997a356c85a7fd7bd091bb12c98232b202d664&scene=27
的例4

![CleanShot 2023-11-04 at 20.05.07@2x.png](https://xuqi.space/static/img/9c22bc8d82416450993e0a5848af6a34.CleanShot%202023-11-04%20at%2020.05.07@2x.webp)