Posts

H1 H2 H3 H4 H5 H6 基本语法测试 字体 粗体测试 斜体测试 粗斜体测试 引用块 引用块测试 嵌套引用块测试 hello world list for test 有序列表 First item Second item Third item 有序列表嵌套代码块，缩进八个空格。 Open the file. Find the following code block on line 21: ...

Graphviz 是什么 Graphviz 是一个开源的、用文本描述来绘制关系图、网络图的工具包。不需要用鼠标拖拽画图，而是用简单的文本语言（主要是 DOT 语言）描述图中的点和线（节点和边），然后 Graphviz 自动计算布局并生成图片。 ...

先用几句话简单说明一下时间复杂度。**时间复杂度并不是表示一个程序解决问题需要花多少时间，而是当问题规模扩大后，程序运行需要的时间增长得有多快。**也就是说，对于高速处理数据的计算机来说，处理某一个特定数据的效率不能衡量一个程序的好坏，而应该看当这个数据的规模变大到数百倍后，程序运行时间是否还是一样，或者也跟着慢了数百倍，或者变慢了数万倍。不管数据有多大，程序处理花的时间始终是一样的，我们就说这个程序很好，具有 $O(1)$ 的时间复杂度，也称常数级复杂度；数据规模变得有多大，花的时间也跟着变得有多长，这个程序的时间复杂度就是 $O(n)$，比如找 $n$ 个数中的最大值；而像冒泡排序、插入排序等，数据扩大 $2$ 倍，时间变慢 $4$ 倍的，属于 $O(n^2)$ 的复杂度。还有一些穷举类的算法，所需时间长度成几何阶数上涨，这就是 $O(a^n)$ 的指数级复杂度，甚至 $O(n!)$ 的阶乘级复杂度。不会存在 $O(2n^2)$ 的复杂度，因为前面的那个 $2$ 是系数，根本不会影响到整个程序的时间增长。同样地，$O (n^3+n^2)$ 的复杂度也就是 $O(n^3)$ 的复杂度。因此，我们会说，一个 $O(0.01n^3)$ 的程序的效率比 $O(100n^2)$ 的效率低，尽管在 $n$ 很小的时候，前者优于后者，但后者运行所需的时间随数据规模增长得慢，最终 $O(n^3)$ 的复杂度将远远超过 $O(n^2)$。我们也说，$O(n^{100})$ 的复杂度小于 $O(1.01^n)$ 的复杂度。 ...

按照定义，方差的 estimator 应该是： $$ \begin{equation} S^2 = \frac{1}{n}\sum_{i = 1}^n\left(X_i - \overline{X}\right)^2 \label{eq:sample-variance} \end{equation} $$ 但是这个 estimator 有 bias，因为： $$ \begin{align*} E(S^2) &= \frac{1}{n}\sum_{i = 1}^nE\left[\left(X_i - \overline{X}\right)^2\right] \\ &= \frac{1}{n}E\left[\sum_{i = 1}^n\left(X_i - \mu + \mu - \overline{X}\right)^2\right]\\ &= \frac{1}{n}E\left[\sum_{i = 1}^n\left(X_i - \mu\right)^2 - n \left(\overline{X} - \mu \right)^2\right] \\ &= \frac{1}{n} \left[\sum_{i = 1}^nE\left(\left(X_i - \mu\right)^2\right) - nE\left(\left(\overline{X} - \mu\right)^2\right)\right] \\ &= \frac{1}{n}\left[n\operatorname{Var}(X) - n\operatorname{Var}(\overline{X})\right] \\ &= \operatorname{Var}(X) - \operatorname{Var}(\overline{X}) \\ &= \sigma^2 - \frac{\sigma^2}{n} = \frac{n - 1}{n}\sigma^2 \end{align*} $$ 关于 $\operatorname{Var}(\overline{X}) = \frac{\sigma^2}{n}$ 的证明参考： Prove that $E (\overline{X} - \mu)^2 = \frac{1}{n}\sigma^2$ ...

公约数和最大公约数 公约数 在这里，我们约定集合 $\mathbb{Z} = \{\dots, -2, -1, 0, 1, 2, \dots\}$ 表示所有的整数，集合 $\mathbb{N} = \{0, 1, 2, \dots\}$ 表示所有的自然数。 对于任意的实数 $x$，将小于等于 $x$ 的最大整数记作 $\lfloor x \rfloor$，读作 “the floor of $x$”。对于任意的整数 $a$ 和任意正整数 $n$，$a \operatorname{mod} n$ 表示 $a / n$ 的余数（remainder or residue），也就是说： ...

TSPDroneLIB by Bogyrbayeva et al. (2023) TSPDroneLIB 仓库包含了用于 TSP-D 和 FSTSP 的数据集和相关链接。该仓库提到了 Dataset - TSP-D Instances by Bouman et al. (2018) 的数据集，另外包括了 Bogyrbayeva 等（2023）使用的数据集。相关的算法可以在 TSPDrone.jl 仓库中找到。有关数据集的字段说明可以在 TSPDroneLIB/data/Bogyrbayeva/description.md 中找到。该数据集分类如下： ...

Traveling Salesman Problem with Drones (TSP-D) 是经典 TSP 的拓展，它在 TSP 的基础上增加了无人机。无人机可以和车辆一起工作，或者自主起飞服务。根据无人机单次起飞降落过程中服务的顾客点数量的不同可以将问题分为单次起飞服务单个顾客点的和单次起飞服务多个顾客点。同样对无人机和车辆的会合点也有限制，即无人机只能在顾客节点或者仓库节点会合，因此会产生无人机和车辆之间互相等待的时间。TSP-D-Instances 就是用于 TSP-D 的数据集之一。 ...

TSPLIB 是一个和 TSP 相关的数据集，包含了 Symmetric Traveling Salesman Problem (STSP)、Asymmetric Traveling Salesman Problem (ATSP)、Hamiltonian Cycle Problem (HCP)、Sequential Ordering Problem (SOP) 和 Capacitated Vehicle Routing Problem (CVRP) 的数据集，可以在 tsp95.pdf 中查看有关数据集的完整说明文档。除了 HCP 以外，其他的问题都是定义在完全图上，且所有的距离都是以整数表示的。每个文件都包括说明部分和数据部分，说明部分包含了有关文件的格式和内容的信息。 ...

数据集来源及介绍 Amazon Delivery Dataset 是一个 Amazon 公司最后一公里物流运营情况的数据集，包含了超过 43632 次配送的多城市数据，数据字段包括订单详情、配送人员、天气、交通情况、配送仓库和配送地点的经纬度等信息。要将数据集转换为可以用于 TSP-D 的数据集，需要将数据集中的经纬度转换为欧几里得距离，即两点之间的直线距离，当然在此之前需要对原始数据集进行一些数据的预处理工作。 ...

精确算法 Concorde 是一个求解TSP的精确算法，由 ANSI C 编写。在 Concorde Downloads 页面可以下载到最新版本的Concorde。下载后通过在命令行输入下面的命令进行解压，解压后会得到一个名为 concorde 的文件夹，编译的过程参考 Ubuntu（Linux）安装concorde过程或者参考 Installing Solvers · perrygeo/pytsp Wiki。 ...