本文主要是介绍前向/后向算法维特比算法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
前向/后向算法:
#include <map>
#include <queue>
#include <string>
#include <math.h>
#include <vector>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
double dp[5][5];
double A[3][3]={0.5,0.2,0.3,0.3,0.5,0.2,0.2,0.3,0.5};
double B[3][2]={0.5,0.5,0.4,0.6,0.7,0.3};
double pi[3]={0.2,0.4,0.4};
int C[3]={0,1,0};
int main(){int i,j,k;double ans;memset(dp,0,sizeof(dp));dp[0][0]=pi[0]*B[0][C[0]];dp[0][1]=pi[1]*B[1][C[0]];dp[0][2]=pi[2]*B[2][C[0]];for(i=1;i<3;i++){for(j=0;j<3;j++){for(k=0;k<3;k++)dp[i][j]+=(dp[i-1][k]*A[k][j]*B[j][C[i]]);}}//
// for(i=0;i<2;i++){
// for(j=0;j<3;j++){
// for(k=0;k<3;k++){
// dp[i+1][j]+=(dp[i][k]*A[k][j]*B[j][C[i+1]]);
// }
// }
// }ans=dp[2][0]+dp[2][1]+dp[2][2];printf("%.6lf\n",ans);return 0;
}
维特比算法:
#include <map>
#include <queue>
#include <string>
#include <math.h>
#include <vector>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
double dp[5][5];
double A[3][3]={0.5,0.2,0.3,0.3,0.5,0.2,0.2,0.3,0.5};
double B[3][2]={0.5,0.5,0.4,0.6,0.7,0.3};
double pi[3]={0.2,0.4,0.4};
int C[3]={0,1,0};
int pre[5][5];
void dfs(int u,int v){if(u<0)return;dfs(u-1,pre[u][v]);printf("%d ",v);
}
int main(){ //就是概率dp求个max,然后记录一下前驱int i,j,k; //例子是<统计学习方法> p186 例10.3double ans,tmp;memset(dp,0,sizeof(dp));memset(pre,-1,sizeof(pre));dp[0][0]=pi[0]*B[0][C[0]];dp[0][1]=pi[1]*B[1][C[0]];dp[0][2]=pi[2]*B[2][C[0]];for(i=0;i<2;i++){for(j=0;j<3;j++){for(k=0;k<3;k++){tmp=dp[i][k]*A[k][j]*B[j][C[i+1]];if(tmp>dp[i+1][j]){dp[i+1][j]=tmp;pre[i+1][j]=k;}}}}ans=max(dp[2][0],max(dp[2][1],dp[2][2]));printf("%.6lf\n",ans);for(i=0;i<3;i++){if(dp[2][i]==ans){dfs(2,i);break;}}return 0;
}
这篇关于前向/后向算法维特比算法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!