用C现em算法并回溯最优状态序列的代码

以下是一个简单的用C语言实现的Viterbi算法，并回溯最优状态序列的代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N 3   // 隐藏状态数
#define M 4   // 观测状态数
#define T 5   // 观测序列长度

double a[N][N] = {0.5, 0.2, 0.3, 0.3, 0.5, 0.2, 0.2, 0.3, 0.5};   // 状态转移矩阵
double b[N][M] = {0.5, 0.5, 0.0, 0.0, 0.0, 0.5, 0.5, 0.0, 0.0, 0.0, 0.0, 0.0, 0.3, 0.3, 0.2};   // 观测概率矩阵
double pi[N] = {0.4, 0.3, 0.3};   // 初始状态概率向量

int main() {
    int i, j, t;
    double alpha[N][T] = {0.0};   // 前向概率矩阵
    int path[N][T] = {0};   // 路径矩阵
    int q[T] = {0};   // 最优状态序列

    // 初始化前向概率矩阵和路径矩阵
    for (i = 0; i < N; i++) {
        alpha[i][0] = pi[i] * b[i][0];
        path[i][0] = i;
    }

    // 前向算法
    for (t = 1; t < T; t++) {
        for (j = 0; j < N; j++) {
            double max_alpha = 0.0;
            int max_index = 0;
            for (i = 0; i < N; i++) {
                double temp_alpha = alpha[i][t - 1] * a[i][j];
                if (temp_alpha > max_alpha) {
                    max_alpha = temp_alpha;
                    max_index = i;
                }
            }
            alpha[j][t] = max_alpha * b[j][t];
            memcpy(path[j], path[max_index], sizeof(int) * t);
            path[j][t] = j;
        }
    }

    // 回溯最优状态序列
    double max_prob = 0.0;
    for (i = 0; i < N; i++) {
        if (alpha[i][T - 1] > max_prob) {
            max_prob = alpha[i][T - 1];
            memcpy(q, path[i], sizeof(int) * T);
        }
    }

    // 输出结果
    printf("观测序列：");
    for (t = 0; t < T; t++) {
        printf("%d ", q[t] + 1);
    }
    printf("\n");
    printf("最大概率：%f\n", max_prob);

    return 0;
}

其中，a[N][N]表示状态转移矩阵，b[N][M]表示观测概率矩阵，pi[N]表示初始状态概率向量，alpha[N][T]表示前向概率矩阵，path[N][T]表示路径矩阵，q[T]表示最优状态序列。在程序中，我们先用前向算法计算出alpha[N][T]和path[N][T]，然后回溯最优状态序列q[T]。