candidate的由来（什么是bug啊还有什么是beta）

本文目录

• 什么是bug啊还有什么是beta
• Introduction to linear optimization 阅读笔记（一）

什么是bug啊还有什么是beta

1 “BUG”的由来：
Bug一词的原意是“臭虫”或“虫子”。但是现在，在电脑系统或程序中，如果隐藏着的一些未被发现的缺陷或问题，人们也叫它“Bug”，这是怎么回事呢？
原来，第一代的计算机是由许多庞大且昂贵的真空管组成，并利用大量的电力来使真空管发光。可能正是由于计算机运行产生的光和热，引得一只小虫子�Bug　钻进了一支真空管内，导致整个计算机无法工作。研究人员费了半天时间，总算发现原因所在，把这只小虫子从真空管中取出后，计算机又恢复正常。后来，Bug这个名词就沿用下来，表示电脑系统或程序中隐藏的错误、缺陷或问题。
与Bug相对应，人们将发现Bug并加以纠正的过程叫做“Debug”，意即“捉虫子”或“杀虫子”。遗憾的是，在中文里面，至今仍没有与“Bug”准确对应的词汇，于是只能直接引用“Bug”一词。虽然也有人使用“臭虫”一词替代“Bug”，但容易产生歧义，所以推广不开。
所谓“（Bug）”，是指电脑系统的硬件、系统软件（如操作系统）或应用软件（如文字处理软件）出错。硬件的出错有两个原因，一是设计错误，一是硬件部件老化失效等。软件的错误全是厂家设计错误。那种说用户执行了非法操作的提示，是软件厂商不负责的胡说八道。用户可能会执行不正确的操作，比如本来是做加法但按了减法键。这样用户会得到一个不正确的结果，但不会引起bug发作。软件厂商在设计产品时的一个基本要求，就是不允许用户做非法的操作。只要允许用户做的，都是合法的。用户根本就没有办法知道厂家心里是怎么想的，哪些操作序列是非法的。
从电脑诞生之日起，就有了电脑BUG。第一个有记载的bug是美国海军的编程员，编译器的发明者格蕾斯·哈珀（GraceHopper）发现的。哈珀后来成了美国海军的一个将军，领导了著名计算机语言Cobol的开发。
1945年9月9日，下午三点。哈珀中尉正领着她的小组构造一个称为“马克二型”的计算机。这还不是一个完全的电子计算机，它使用了大量的继电器，一种电子机械装置。第二次世界大战还没有结束。哈珀的小组日以继夜地工作。机房是一间第一次世界大战时建造的老建筑。那是一个炎热的夏天，房间没有空调，所有窗户都敞开散热。
突然，马克二型死机了。技术人员试了很多办法，最后定位到第70号继电器出错。哈珀观察这个出错的继电器，发现一只飞蛾躺在中间，已经被继电器打死。她小心地用摄子将蛾子夹出来，用透明胶布帖到“事件记录本”中，并注明“第一个发现虫子的实例。”
从此以后，人们将计算机错误戏称为虫子（bug），而把找寻错误的工作称为（debug）。
2: Beta，这个希腊字母的英文写法，怎么会变成了“测试”的含义。据我所知的，广义上对测试有三个传统的称呼，alpha、beta、gamma，用来标识测试的阶段和范围。alpha 是指内测，即现在说的 CB，指开发团队内部测试的版本或者有限用户体验测试版本。beta 是指公测，即针对所有用户公开的测试版本。然后做过一些修改，成为正式发布的候选版本时（现在叫做 RC - Release Candidate），叫做 gamma。
可是，这个 beta，无论如何它是“测试”的定语，什么时候喧宾夺主变成了“测试”的中心词了？
在此我大胆臆测一下：
由于大部分人看到的版本已经是公众测试版本，所以通常都带有 beta 字样。某人不知其含义，于是误以为 beta 的就是测试的。凡是你要表示这是个测试版本，就要带上一个 beta。但是，实际情况，总有封测/内测和公测之分啊，好，那加个定语，于是有了 Closed Beta、Open Beta。

Introduction to linear optimization 阅读笔记（一）

首先从单纯形法开始说起。这本书前面的内容将放在后面说。

单纯形法是得名于拓扑概念单纯形，它是三角形和四面体概念的泛化，k 维单纯形指的是包含 k+1 个节点的多面体。单纯形法最早是有著名运筹科学家 Dantzig（知名运筹学专家、冯诺依曼奖获得者叶荫宇的老师）于 1947 年提出的，他随后在 1963 年在一个课题中将其正式简化成易于理解的文字。

单纯形法被用来解决线性规划问题，它大大缩小了搜索占用的内存空间和时间。下面我将逐步介绍这一方法的由来和原理。

一个经典的线性规划的标准形式是这样表述的：

                                                                    

那么我们要求这样一个线性规划的最优可行解实际上要保证两点，第一，这个解是满足限制条件的，也就是说它是可行的，第二，这个解释所有的可行解中最好的，也就是满足最优解。

规定 是该问题标准形式的基可行解， 为对应的基矩阵。

根据

我们可以反算出 ,其中 是 可行方向中对应基矩阵的部分。

下面文章中简单介绍了两种情况，也就是 x 是非退化和 x 是退化的情况，实际上，在fig1图中，就是是否 x 到达了边界，如果对于 ,说明解仍然可行，当 足够小的时候，也就是说 d 仍然是可行方向。如果 ,那么，在这种情况下,非负的限制就会被打破，就成为了非可行解。
由此我们可以得到一个 单纯形法的计算方法（simplex method）：

1、首先找到一组基础列 组成基底,以及对应基础可行解 x

2、然后计算 reduced cost， ，如果所有 reduced cost 均为非负，则解为最优解，否则，挑选出使reduced cost 为负的 j

3、计算 ,如果 u没有部分是正的，那么我们就有 ,最优成本函数是 ,算法停止。

4、如果 u 一部分是正的，令

5、找到满足条件的 ，将 替换为  ，如果 y 是新的基可行解，那么这个新的基础变量的值是

上面讨论的单纯形方法适用于非退化的基可行解，如果是退化的可行解，那么有两种情况。

第一种，目前的基可行解是退化的，而 ，在这种情况下，我们可以通过使这些等于 0 的 的对应向量 出基，从而使得定理 3.2成立。

第二种， ,多于一个原始基础变量成为 0，考虑到它们中只有一个出基，其他基变量仍然在0 位置，新的基可行解是退化的。
在 fig2 中，我们其实可以很明显看出， 是退化解，因为 是冗余的约束，因此此时的f,g 方向上的 ,但当我们将基底换为 ，就可以继续找到可行方向和最优解了。

那么问题来了，如何选择入基向量和出基向量？这样一个选择的规则，我们把它叫做 pivoting rule。下面有两种方法可以选择：

（1）选择一个 ,使其 reduced cost绝对值最大，然而，这样的方式并不能保证最快的移动，因为实际的 cost 需要考虑移动的距离。于是我们有了第二个方法。

（2）选择一个 ，使其对应的 最大，这项规则使得 reduced cost 在最短的周期下达到最优，但是这带来一个问题，那就是每次都需要计算出所有 对应的 ,根据经验，第二种方法相对于第一种并没有优势。

对于大型的计算问题，甚至第一种办法也不是很好，因为它需要计算出所有的 reduced cost。事实上，我们采取更简单的策略，那就是选择最小的 j 使得 ，这种方法被称为最小角标法，这种方法还能很有效的避免循环。还有一些方法被用来降低运行时间，比如说 Devex （Harris，1973）以及 steepest edge rule（Goldfarb and Reid,1977）最后，还有一些方法是基于候选表（candidate list），有许多不同的方法来维护候选表。

对于单纯形的实施，我们介绍三种方法，依次是原始方法（naive implementation），修正单纯形方法（revised simplex method）以及全列表方法（the full tableau implementation）。

原始法的做法很简单，就是先计算 ，然后从中选出入基向量和出基向量，然后计算 从而得到新的基可行解。

修正单纯形法相比于原始法保留了上一个基础矩阵的部分信息。

一个修正单纯形方法的循环包括以下步骤：

1、在一个经典的循环中，我们开始于一个基础列矩阵 以及相关的基础可行解 x和基础矩阵的逆

2、计算reduced cost ,如果它们全部是非负的，那么当前的基可行解就是最优解，算法停止，如果不是，选择使得 reduced cost 小于0 的 j 进入候选表

3、计算 。如果u 的部分没有正数，那么最优成本是 ，算法停止。

4、如果有一部分是正的，那么令

5、找到使上式成立的 ，用 代替 ，计算出新的基可行解。

6、形成 维矩阵 ,同时计算出新的基础矩阵

今天就先写到这里，未完待续……