我们可以通过在有向图$G=(V,E)$中使用动态规划的算法来实现语音识别功能。

对每条边$(u,v) in E$打上一个声音标签$sigma (u,v)$，该声音来自于有限声音集$sum$ 。图中从特定的顶点$v_0 in V$开始的每条路径都对应模型产生一个可能的声音序列。对于一条有向路径，我们定义标签为路径中边的标签的简单连结。

寻找特定的声音序列

对给定的带标签的图$G$，特定顶点$v_0$以及$sum$上的声音序列$sigma=<sigma _1,sigma _2,sigma_3, cdots, sigma_k>$

返回从$G$中从$V_0$开始的一条路径，$s$为该路径的标签（如果存在这样的路径）。否则，返回NO-SUCH-PATH

viterbi_graph.h

#include 
    
     #include 
     
      #include 
      
       #include "stdlib.h"#include 
       
        using namespace std;#define MAXVEX 100enum color{WHITE,GRAY,BLACK};enum which_edge{NONE,TREE,BACK,FORWARD,CROSS};typedef int status;typedef string VertexType;typedef int EdgeType;typedef struct EdgeNode{    int Edgestart;    int Edgeend;  //邻接点域，储存该顶点对应的下标    EdgeType weight;  //用于存储权值    int type;    struct EdgeNode *next;  //下一个邻接点}EdgeNode;typedef struct VertexNode  //顶点表结点{    VertexType data;  //顶点域，存储顶点信息    int color;    int touch,finish;   //访问开始时间和结束时间    EdgeNode* FirstEdge;  //边表头指针    int parent; //指向遍历的父结点}VertexNode,AdjList[MAXVEX];typedef struct{    AdjList adjList; //图的顶点表    int numNodes,numEdges;}GraphAdjList;void CreateALGraph(GraphAdjList *G){    EdgeNode *e;    cout<<"Input the number of vertexes and edges: "<
        
         >G->numNodes>>G->numEdges;    //输入顶点表的信息    for(int i=0;i
         
          numNodes;i++) { cout<<"Input the data (information) of vertexes "<
          
           <
           
            >G->adjList[i].data; G->adjList[i].FirstEdge=NULL; G->adjList[i].parent=-1; G->adjList[i].color=WHITE; G->adjList[i].touch=G->adjList[i].finish=-1; } int beg,end; for(int k=0;k
            
             numEdges;k++) { cout<<"Input the serial number of edges (Vi,Vj) "<
             
              >beg; cout<<"Input the vertex of endding: "; cin>>end; e=(EdgeNode *)malloc(sizeof(EdgeNode)); e->Edgeend=end; e->Edgestart=beg; e->weight=0; e->type=NONE; e->next=G->adjList[beg].FirstEdge; G->adjList[beg].FirstEdge=e; }}
             
            
           
          
         
        
       
      
     
    

graph_algorithm.h

#include "viterbi_graph.h"int path_time=0;int path_exist=0;int path_print_signal=0;void print_graph(GraphAdjList *G){    EdgeNode *cur_edge;    for(int i=0;i
    
     numNodes;i++)    {        cout<<"The start is "<
     
      adjList[i].data<
      
       adjList[i].data;        if(G->adjList[i].FirstEdge)            cout<<" adjust end is: ";        for(cur_edge=G->adjList[i].FirstEdge;cur_edge;cur_edge=cur_edge->next)        {            cout<
       
        Edgeend<<"  ";        }        cout<
        
         adjList[start].color=GRAY;    path_time++;    G->adjList[start].touch=path_time;    for(EdgeNode *cur_e=G->adjList[start].FirstEdge;cur_e;cur_e=cur_e->next)    {        if(cur_e->Edgeend==end)        {            path_exist=1;        }        if(path_exist==1)            return;        int cur_end=cur_e->Edgeend;        if(G->adjList[cur_end].color==WHITE)        {            G->adjList->parent=start;            DFS_visit(G,cur_end,end);            cur_e->type=TREE;        }        else if(G->adjList[cur_end].color==GRAY)        {            cur_e->type=BACK;        }        else if(G->adjList[cur_end].color==BLACK)        {            if(G->adjList[start].touch
         
          adjList[end].touch) cur_e->type=FORWARD; else cur_e->type=CROSS; } } //G->adjList[start] has finished G->adjList[start].color=BLACK; path_time++; G->adjList[start].finish=path_time;}void DFS(GraphAdjList *G,int start,int end){ for(int u=0;u
          
           numNodes;u++) { G->adjList[u].color=WHITE; G->adjList[u].parent=-1; } path_time=0; if(G->adjList[start].color==WHITE) DFS_visit(G,start,end);}void path_print(GraphAdjList *G,int start,int end){ if(path_exist==1) { cout<<" "<
           
            adjList[start].FirstEdge;e_ptr;e_ptr=e_ptr->next) { if(e_ptr->Edgeend==end) { cout<<" "<
            
             adjList[start].FirstEdge;e_ptr;e_ptr=e_ptr->next) { if(e_ptr->type==TREE) path_print(G,e_ptr->Edgeend,end); } } } else { cout<<"The path is not exist"<
            
           
          
         
        
       
      
     
    

viterbi_algorithm.cpp

#include "graph_algorithm.h"int main(){    GraphAdjList G;    CreateALGraph(&G);    print_graph(&G);    int start,end;    cout<<"Input the start of the edge : "<
    
     >start;    cout<<"Input the end of the edge : "<
     
      >end;    DFS(&G,start,end);    cout<
     
    

算法运行结果

随机游动

假定每条边$(u,v) /in E$都关联一个非负概率$p(u,v)$，它表示从顶点$u$开始，经过边$(u,v)$，产生对应的声音的概率。任何一个顶点射出的概率之和均为1。

一条路径上的概率定义为路径上所有边的概率之积。

状态转移函数

可以看出：从$v_1$到$v_4$，最大的概率值为$0.8 times 1=0.8$

动态规划能够实现的状态转移函数如下：

answer=e->probability*DFS_compute(G,e->e_end,end);//计算从G->adjlist[beg]出发的每一条边，找出最大值if(answer>G->adjlist[beg].res){    G->adjlist[beg].res=answer;    G->adjlist[beg].direction=e->e_end;}

probability_graph.h

#include 
    
     #include 
     
      #include "stdlib.h"using namespace std;#define MAXVEX 100typedef int status;typedef string VertexType;typedef double EdgeType;typedef struct Edge{    int e_start;    int e_end;  //邻接点域    EdgeType probability;  //用于存储权值，即边的概率    struct Edge *next;}Edge;typedef struct Vertex{    VertexType data;    Edge* head; //边表头指针    int direction;  //用于指明节点下一步该往哪里走    double res;  //用于储存最后的结果，初始化为-1    //direction和res要联动}Vertex,adjvertex[MAXVEX];typedef struct{    adjvertex adjlist; //图的顶点表    int numNodes,numEdges;}GraphAdj;void CreateGraph(GraphAdj *G){    Edge *e;    cout<<"Input the number of vertexes and edges: "<
      
       >G->numNodes>>G->numEdges;    //输入顶点表信息    for(int i=0;i
       
        numNodes;i++)    {        cout<<"Input the data (information) of vertexes "<
        
         <
         
          >G->adjlist[i].data; G->adjlist[i].head=NULL; G->adjlist[i].direction=-1; G->adjlist[i].res=-1; } int beg,end; double prob; for(int k=0;k
          
           numEdges;k++) { cout<<"Input the serial number of Edges (Vi,Vj) "<
           
            >beg; cout<<"Input the vertex of endding: "; cin>>end; cout<<"Input the probability of edge: "; cin>>prob; e=(Edge *)malloc(sizeof(Edge)); e->e_start=beg; e->e_end=end; e->probability=prob; e->next=G->adjlist[beg].head; G->adjlist[beg].head=e; }}
           
          
         
        
       
      
     
    

viterbi_probability.h

#include "probability_graph.h"double answer=1;double maxpath=0;int path_exist=0;int path_print_signal=0;int has_founded[MAXVEX];double DFS_compute(GraphAdj *G,int beg,int end);double max(double a,double b){    return a>b?a:b;}double DFSTraverse(GraphAdj *G,int beg,int end){    for(int i=0;i
    
     numNodes;i++)        has_founded[i]=0;    maxpath=DFS_compute(G,beg,end);    return maxpath;}double DFS_compute(GraphAdj *G,int beg,int end){    if(beg==end)    {        answer=1;        return 1;    }    for(Edge *e=G->adjlist[beg].head;e;e=e->next)    {        if(has_founded[beg]==1)        {            answer=G->adjlist[e->e_start].res;            return G->adjlist[e->e_start].res;        }        if(has_founded[beg]==0)        {            if(e->e_end==end)            {                path_exist=1;                answer=e->probability;                if(answer>G->adjlist[e->e_start].res)                {                    G->adjlist[e->e_start].res=answer;                    G->adjlist[e->e_start].direction=e->e_end;                }                return G->adjlist[e->e_start].res;            }            answer=e->probability*DFS_compute(G,e->e_end,end);            //计算从G->adjlist[beg]出发的每一条边，找出最大值            if(answer>G->adjlist[beg].res)            {                G->adjlist[beg].res=answer;                G->adjlist[beg].direction=e->e_end;            }        }            }    //beg开始的answer已经全部计算完了    has_founded[beg]=1;    return G->adjlist[beg].res;}void print_graph(GraphAdj *G){    Edge *cur_edge;    for(int i=0;i
     
      numNodes;i++)    {        cout<<"The start is "<
      
       adjlist[i].data<
       
        adjlist[i].data;        if(G->adjlist[i].head)            cout<<" adjust end is: ";        for(cur_edge=G->adjlist[i].head;cur_edge;cur_edge=cur_edge->next)        {            cout<
        
         e_end<<"  ";        }        cout<
        
       
      
     
    

viterbi_probability.cpp

#include "viterbi_probability.h"int main(){    GraphAdj G;    CreateGraph(&G);    print_graph(&G);    int start,end;    cout<<"Input the start of the edge : "<
    
     >start;    cout<<"Input the end of the edge : "<
     
      >end;    double result=DFSTraverse(&G,start,end);    cout<
     
    

算法运行结果