C++ 马尔可夫链

C++ 中的马尔可夫链入门

马尔可夫链是数学系统，它们从一个状态过渡到状态空间中的另一个状态。它们是一种特殊的随机过程，其中下一个状态仅取决于当前状态，而与之前的一系列事件无关。这个属性被称为马尔可夫性质。

在 C++ 的上下文中，马尔可夫链可以用于建模各种现实场景，例如预测天气模式、金融市场和 Web 应用程序中的用户行为。了解如何在 C++ 中实现和使用马尔可夫链对于开发预测模型和模拟非常有益。

方法 1：基本方法

输出

 
Day 1: Sunny
Day 2: Cloudy
Day 3: Cloudy
Day 4: Cloudy
Day 5: Sunny
Day 6: Sunny
Day 7: Sunny
Day 8: Sunny
Day 9: Sunny
Day 10: Rainy   

说明

• 步骤 1：定义状态
  首先，您需要定义系统的可能状态。在此示例中，状态代表不同类型的天气：晴朗、下雨和多云。每个状态都被分配一个唯一的标识符，通常使用枚举类型 (enum) 以提高清晰度和易用性。
• 步骤 2：创建转移矩阵
  接下来，您创建一个转移矩阵。这个矩阵是一个表格，显示从一个状态过渡到另一个状态的概率。例如，如果您目前正经历晴朗的天气，该矩阵将显示明天保持晴朗、转为下雨或多云的可能性。此矩阵中的每一行代表当前状态，每一列代表潜在的下一个状态。
• 步骤 3：设置初始状态
  然后，您为系统选择一个初始状态。在此示例中，模拟从晴朗的天气开始。此初始状态作为模拟的起点。
• 步骤 4：模拟马尔可夫链
  要模拟马尔可夫链，请执行以下步骤：
  
  1. 循环遍历每一天：模拟将运行预定的天数。
  2. 打印当前状态：每天，都会显示当前的天气状况。
  3. 生成随机数：使用随机数生成器生成一个介于 0 和 1 之间的数字。此数字将有助于根据转移概率确定下一个状态。
  4. 确定下一个状态：将随机数与当前状态的累积转移概率进行比较。累积概率是通过对转移矩阵中的概率求和来计算的，直到随机数落在特定范围内，这表示下一个状态。
  5. 更新状态：确定下一个状态后，将当前状态更新为此新状态，然后继续进行模拟的下一天。

复杂度分析

时间复杂度

马尔可夫链模拟的时间复杂度主要取决于迭代次数以及每次迭代中执行的操作。

初始化

• 定义状态和创建转移矩阵的操作只执行一次，因此这些是 O(1) 操作。

模拟循环

• 循环运行 n 次迭代，其中 n 是时间步数（或天气示例中的天数）。
• 在每次迭代中，生成随机数和确定下一个状态涉及：
• 生成随机数：O(1)。
• 检查转移概率：如果存在 m 个状态，在最坏的情况下，您可能需要检查多达 m 个概率。这是 O(m)。
• 总的来说，每次迭代涉及 O(m) 个操作。
• 因此，总时间复杂度为 O(n⋅m)。

空间复杂度

空间复杂度涉及用于存储状态、转移矩阵和任何额外变量的内存。

状态

• 状态的数量为 m，这通常是一个较小的固定数字。因此，所需的空间为 O(m)。

转移矩阵

• 转移矩阵是一个 m x m 的矩阵，它需要与状态数量的平方成正比的空间。这是 O(m²)。

变量

• 额外变量包括当前状态、随机数和累积概率。这些需要恒定的空间，O(1)。
• 因此，总空间复杂度为：O(m2)。

方法 2：使用类和面向对象编程

将马尔可夫链逻辑封装在类中，以提高模块化和可重用性。这种方法使代码更清晰，更易于管理。

实施

输出

 
Day 1: State 0
Day 2: State 0
Day 3: State 0
Day 4: State 0
Day 5: State 2
Day 6: State 2
Day 7: State 0
Day 8: State 0
Day 9: State 0
Day 10: State 2   

说明

• 步骤 1：定义 State 类
  创建 State 类
  State 类代表马尔可夫链中的单个状态。
  每个状态都有一个标识符 (id) 和一组转移概率 (transitions)。
  转移概率存储在一个向量中，其中每个元素对应于从当前状态过渡到特定状态的概率。
• 步骤 2：定义 MarkovChain 类
  创建 MarkovChain 类
  MarkovChain 类管理状态及其之间的过渡。
  它包含一个 State 对象列表，并跟踪链的当前状态。
  初始化 MarkovChain 类
  MarkovChain 类的构造函数接受一个 State 对象向量和一个初始状态。
  这设置了马尔可夫链的初始配置。
• 步骤 3：模拟马尔可夫链
  模拟方法
  MarkovChain 类的模拟方法模拟指定的天数。
  它使用循环来迭代模拟的每一天。
  打印当前状态
  在每次迭代（每一天）中，都会打印系统的当前状态。
  生成随机数
  生成一个介于 0 和 1 之间的随机数，以根据转移概率确定下一个状态。
  确定下一个状态
  该方法迭代当前状态的转移概率列表。
  它累积这些概率，直到随机数落在特定范围内，这表示下一个状态。
  然后，当前状态将更新为下一个状态。

复杂度分析

时间复杂度

模拟的时间复杂度主要取决于状态的数量 (m) 和您模拟的迭代次数 (n)。

初始化

创建 State 对象和初始化 MarkovChain 对象涉及迭代状态和初始化数据结构。这通常是 O(m)，其中 m 是状态的数量。

模拟循环

模拟运行 n 次迭代，每次迭代代表一天或一个时间步。

在每次迭代中，更新当前状态涉及迭代当前状态的转移概率。在最坏的情况下，此操作是 O(m)，其中 m 是状态的数量。

因此，模拟 n 天的总体时间复杂度为：O(n⋅m)。

空间复杂度

空间复杂度涉及用于存储状态、转移概率和任何额外变量的内存。

状态

存储 m 个 State 对象所需的空间取决于每个状态的属性（例如，标识符、转移概率）。这是 O(m) 空间。

转移概率

每个 State 对象都包含一个指向其他状态的转移概率的向量或数组。如果状态空间密集（每个状态有很多转移），这可能会占用大量空间。

当前状态和变量

需要额外的空间用于诸如当前状态索引和模拟循环中使用的任何临时变量之类的变量。这通常是 O(1) 空间。

因此，总空间复杂度主要由状态对象及其转移数据决定，即：O(m)。

方法 3：使用动态状态空间和哈希映射

对于状态空间动态或非常大的应用程序，使用哈希映射可能更有效。

实施

输出

 
Day 1: Sunny
Day 2: Sunny
Day 3: Sunny
Day 4: Sunny
Day 5: Sunny
Day 6: Cloudy
Day 7: Cloudy
Day 8: Cloudy
Day 9: Cloudy
Day 10: Cloudy   

说明

• 步骤 1：动态定义状态
  使用哈希映射
  状态由字符串或其他标识符动态表示，而不是预定义的枚举或整数。
  每个状态都存储在哈希映射 (std::unordered_map) 中作为键，从而可以高效地查找和管理。
• 步骤 2：使用嵌套哈希映射创建转移矩阵
  转移矩阵
  使用嵌套的 std::unordered_map 来表示转移概率。
  外部哈希映射将每个状态（键）映射到一个内部哈希映射。
  内部哈希映射将每个可能的状态映射到其对应的转移概率。
• 步骤 3：模拟过程
  初始化状态和转移
  用状态及其相应的转移概率填充外部哈希映射。
  这可以随着状态和转移的定义或更新而动态完成。
  运行模拟
  遍历指定的天数或时间步。
  每次迭代
  打印或记录当前状态。
  使用随机数生成，根据存储在哈希映射中的转移概率来选择下一个状态。
  相应地更新当前状态。

复杂度分析

时间复杂度

模拟的时间复杂度主要取决于状态的数量 (m) 和模拟中的迭代次数 (n)。

初始化

添加状态和初始化转移概率涉及将元素插入哈希映射。此操作的平均时间复杂度通常为 O(1) 进行插入。

如果状态和转移在运行时动态初始化，则复杂度可能会根据插入操作而有所不同。

模拟循环

模拟运行 n 次迭代，每次迭代代表一个时间步（例如，天）。

在每次迭代中

从哈希映射中检索当前状态的平均时间复杂度为 O(1)。

生成随机数和确定下一个状态涉及迭代当前状态的转移概率。

根据所选的下一个状态更新当前状态也需要平均恒定的时间，O(1)。

因此，模拟 m 个状态的 n 天的总体时间复杂度为：O(n⋅(1+k))。

其中 k 是每个状态的平均转移次数。

空间复杂度

空间复杂度涉及用于存储状态、转移概率和任何额外变量的内存。

状态

每个状态都存储为外部哈希映射中的一个键，这需要与状态数量成正比的空间，O(m)。

转移概率

每个状态的转移概率存储在内部哈希映射中。

如果状态空间密集（每个状态有很多转移），则哈希映射使用的空间可能会显著增长。

在最坏的情况下，即每个状态都有到所有其他状态的转移，转移概率的空间复杂度可能接近 O(m²)。

附加变量

诸如当前状态索引和模拟循环中使用的临时变量之类的变量需要恒定的空间，O(1)。

因此，总空间复杂度主要由状态及其转移数据决定，即：O(m+m2)。