馬爾可夫算法

馬爾可夫算法是使用類似形式文法的規則在符號串上操作的字元串重寫系統。

基本介紹

• 中文名：馬爾可夫算法
• 語言：Refal 
• 操作：符號串上操作的字元串重寫系統
• 認定：圖靈完全

簡介

馬爾可夫算法是使用類似形式文法的規則在符號串上操作的字元串重寫系統。馬爾可夫算法被證明是圖靈完全的，這意味著它們適合作為一般的計算模型，並可以用它的簡單概念表示任何數學表達式。

Refal是基於馬爾可夫算法的程式語言。

算法

1. 自頂向下依次檢查規則，看是否能在符號串中找到任何在箭頭左邊的字元串。
   
2. 如果沒有找到，停止執行算法。
   
3. 如果找到一個或多個，把符號串中的最左匹配的文字替換為在第一個相應規則的箭頭右邊的字元串。
   
4. 返回步驟1並繼續。（如果套用的規則是終止規則，則停止執行算法。）
   

例子

下列例子展示了馬爾可夫算法的基本操作。

規則

1. "A" -> "apple"
   
2. "B" -> "bag"
   
3. "S" -> "shop"
   
4. "T" -> "the"
   
5. "the shop" -> "my brother"
   
6. "從不使用的" ->."終止規則"
   

符號串

"I bought a B of As from T S."

執行

如果算法套用於上述例子，符號串將被以如下方式變更。

1. "I bought a B of apples from T S."
   
2. "I bought a bag of apples from T S."
   
3. "I bought a bag of apples from T shop."
   
4. "I bought a bag of apples from the shop."
   
5. "I bought a bag of apples from my brother."
   

算法接著就終止了。

馬爾可夫鏈

馬爾可夫鏈（英語：Markov chain），又稱離散時間馬爾可夫鏈（discrete-time Markov chain，縮寫為DTMC），因俄國數學家安德烈·馬爾可夫（俄語：Андрей Андреевич Марков）得名，為狀態空間中經過從一個狀態到另一個狀態的轉換的隨機過程。該過程要求具備“無記憶”的性質：下一狀態的機率分布只能由當前狀態決定，在時間序列中它前面的事件均與之無關。這種特定類型的“無記憶性”稱作馬爾可夫性質。馬爾科夫鏈作為實際過程的統計模型具有許多套用。

在馬爾可夫鏈的每一步，系統根據機率分布，可以從一個狀態變到另一個狀態，也可以保持當前狀態。狀態的改變叫做轉移，與不同的狀態改變相關的機率叫做轉移機率。隨機漫步就是馬爾可夫鏈的例子。隨機漫步中每一步的狀態是在圖形中的點，每一步可以移動到任何一個相鄰的點，在這裡移動到每一個點的機率都是相同的（無論之前漫步路徑是如何的）。