自适应蒙特卡洛定位
蒙特·卡罗方法¶
蒙特·卡罗方法，也称统计模拟方法，是二十世纪四十年代中期由于科学技术的发展和电子计算机的发明，而被提出的 一种以概率统计理论为指导的一类非常重要的数值计算方法。是指使用随机数（或更常见的伪随机数）来解决很多 计算问题的方法。与它对应的是确定性算法。蒙特·卡罗方法在金融工程学，宏观经济学，计算物理学 （如粒子输运计算、量子热力学计算、空气动力学计算）等领域应用广泛。
蒙特卡罗方法是一种计算方法。原理是通过大量随机样本，去了解一个系统，进而得到所要计算的值。 它非常强大和灵活，又相当简单易懂，很容易实现。对于许多问题来说，它往往是最简单的计算方法，有时甚至是唯一可行的方法。
我们我们把随机算法分成两类 - 蒙特卡罗算法：采样越多，越近似最优解； - 拉斯维加斯算法：采样越多，越有机会找到最优解；
举个例子，假如筐里有100个苹果，让我挑出最大的。于是我随机拿1个，再随机拿1个跟它比，留下大的，再随机拿1个重复下去。 我每拿一次，留下的苹果都至少不比上次的小。拿的次数越多，挑出的苹果就越大，但我除非拿100次，否则无法肯定挑出了最大的。 这个挑苹果的算法，就属于蒙特卡罗算法——尽量找好的，但不保证是最好的。
而拉斯维加斯算法，则是另一种情况。假如有一把锁，给我100把钥匙，只有1把是对的。于是我每次随机拿1把钥匙去试，打不开就再换1把。 我试的次数越多，打开锁（找到最优解）的机会就越大，但在打开之前，那些错的钥匙都是没有用的。这个试钥匙的算法，就是拉斯维加斯算法——尽量找最好的，但不保证能找到。
马尔可夫聚类(MCL)¶
MCL是属于图聚类的一种，根据点之间的距离关系来将不同的点进行聚类
首先看下图
从图中，我们可以看到，位于同一簇的点，其内部的联系应当紧密，而和外部的联系则比较少。也就是说，如果你从一个点出发， 到达其中的一个邻近点，那么你在簇内的可能性远大于离开当前簇，到达新簇的可能性。这就是MCL的核心思想，如果在一张图上 进行多次的“Random Walks”，那么就有很大可能发现簇群，达到聚类的目的。而“Random Walks”的实现则是通过“Markov Chains”（马尔柯夫链）。
马尔科夫链¶
在此图中，我们可以分为两个子图：V(1,2,3,4)和V(5,6,7)，其中，V1是一簇，V2是另一簇。在同一簇群中，各点之间完全连接，在不同簇之间，仅有(2,5)一条边。 现在，我们从V1出发，假设每条边都一样，那么则一步之后我们有1/3的概率到达V2，1/3的概率到达V3，1/3的概率到达V4，同时，有0的概率到达V5,V6,V7。对于V2， 则有1/4的概率到达V1,V3,V4,V5，有0的概率到达V6,V7。通过计算每个点到达其余点的概率，我们可以得到如下的概率矩阵：
根据上述例子，我们已经接触到了马尔科夫链，那么现在就给其下一个定义：Markov Process——在给定当前知识或信息的情况下，过去（即历史状态）对于预测 将来（即未来状态）是无关的。 Markov Chain——如果有由随机变量X1,X2,X3⋯组成的数列。这些变量的范围，即他们所有可能取值的集合，被称为“状态空间”。 而Xn的值则是在时间n的状态，如果Xn+1对于过去状态的条件概率分布满足：P(Xn+1=x|X0,X1,X2,⋯,Xn)=P(Xn+1=x|Xn)，则我们称其是一条Markov Chain
有权图¶
之前的例子中，图的边是没有权值的，也就是所有的边都是一样的。现在，为每条边添加一个权重（可以理解为亲密程度），那么，就需要重新计算到达每个点的概率了。 假设有如下的图：
首先，我们要计算得到邻接矩阵，即：
通过邻接矩阵，我们就可以计算得到概率矩阵了，具体计算公式如下
最后的概率矩阵如下：
