最小化演算法
A. DFA確定化和最小化
從正規式開始
通過下面的對應法則將正規式轉換成NFA
例如：
運用子集法的3個概念：
(1 )狀態集的ε-閉包: 狀態集I中的任何狀態s經任意條ε弧而能到達的所有狀態的集合，定義為狀態集I的ε -閉包，表示為ε -closure()。
(2)狀態集的a弧轉換: 狀態集I中的任何狀態s經過一條a弧而能到達的所有狀態的集合，定義為狀態集1的a弧轉換，表示為move(l,a)。
(3)狀態集的a弧轉換的閉包a: lg= ε-closure(move(l,a))
上面的正規式轉換成NFA：
先從初態0開始求：
【因為每個狀態通過一條ε弧到達自己本身，所以求得ε的閉包包含自己】
（1）求0的ε的閉包：經過任意條ε所能到達的狀態，集合為{0,1,3,4,5,6,7,9}
（2）求0的a弧轉換：1經過a弧到達2，4經過a弧到達4，其餘沒有鄭凱經過一條a弧到達某個狀態，所以集合為{2,4}
（3）求a弧轉換的閉包：{2,4}分別經過任意條ε所能到達的狀態，集合為{2,4,6,7,9}
（4）求0的b弧轉換：5經過b到5，7經過b到8，，其餘沒有經過一條b弧到達某個狀態，所以集合為{5,8}
（5）求b弧轉換的閉包：{5,8}分別經過任意條ε所能到達的狀態，集合為{5,6,7,8,9}
0的ε-閉包：{0,1,3,4,5,6,7,9}
0的a弧轉換：{2,4}
0的a弧轉換的ε-閉包：{2,4,6,7,9}
0的b弧轉換：{5,8}
0的b弧轉換的ε-閉包：{5,6,7,8,9}
現在列一個表格：
（1）表格的列數為輸入字元的個數+1，此題為a，b兩個輸入字元，所以為3列。
（2）第一列第一行填寫初態的ε-閉包（此題0的ε-閉包），第二列第一行填寫初態的a弧轉換的ε-閉包（此題0的a弧轉換的ε-閉包），第三列第一行填寫初態的b弧轉換的ε-閉包（此題0的b弧轉換的ε-閉包）......以此類推。
（3）第一列的第二行以下填入上一行第二列以後的沒有出現過的狀態集。（此題第一行第二列第三列都沒有出現在第一列中，將他們填入第一列）
下圖為填好的表：
【新的終態的判斷方法就是包含原來終態的集合就為終態，例如此題原來終態為9，所以包含9的集合就為終態，[雙圈代表終態]；
新的初態就是包含原來初態的集合就為初態，例如此題原來初態為0，所以包含0的集合就為初態】
為表裡的狀態集重新標上號：
先了解幾個概念：
1.多於狀態：對於一個狀態Si，若從開始狀態出發，不可能到達改狀態Si，則Si為多餘（無用）狀態。
2.死狀態：對於一個狀態Si，對於任意輸入符號a，若轉到它本身後，不可能從它到達終止狀態，則稱Si為死狀態。
都稱為無關狀態
3.等價辯肢狀態：若Si為自動機的一個狀態，我們把從Si出發能導出的所有符號串的集合記為L（Si）。
設有兩攜叢世個狀態Si和Sj，若有L（Si）=L（Sj），則稱Si和Sj是等價狀態。
4.可區別狀態：自動機中兩個狀態Si和Sj，如果它們不等價，則稱它們可區別。
5.兩個狀態(Si和Sj)等價的判斷條件:
（1）狀態Si和Sj必須同時為終止狀態或同時為非終止狀態。即終止狀態和非終止狀態是可區別的。
（2）狀態Si和Sj對於任意輸入符a∈Σ，必須轉到等價的狀態里，否則Si和Sj是可區別的。
DFA的化簡演算法：對於DFA M=(S,Σ,f,S0,Z)
(1)首先將DFA的狀態集進行初始化，分成Π=(Z,S-Z);
(2) 用下面的過程對Π構造新的劃分Π new
for (Π中每個組G) do //每個組都是一個狀態集
begin
把G劃分成小組，G中的任意兩個狀態Si和Sj在同一組中，當且僅當對於Σ中任意輸入符號a ，Si和Sj的a轉換是到同一組中，move(Si,a) ∈Gi ，move(Sj,a) ∈Gi。這樣，只要Si和Sj的a轉換是到不同的組中，則說明Si和Sj是可區別的，可進行劃分。在Π new中用剛完成的對G的劃分代替原來的G。
end ; Π := Π new；
(3)重復執行(2)，直到Π中每個狀態集不能再劃分(Π new= Π)為止;
(4)合並等價狀態 ,在每個G中，取任意狀態作為代表，刪去其它狀態;
(5)刪去無關狀態，從其它狀態到無關狀態的轉換都成為無定義。
舉例：
之前上面這個圖畫錯了,現在圖已經修改過了,謝謝提醒 :-D
B. < DFA M狀態最少化的程序實現>編譯課程設計啊！！！還要求MFC的界面！！！ 求大神啊！搞定給財富值~
DFA狀態數的最小化
package chapter3;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
/**
* 演算法 3.39 最小化一個DFA的狀態數
* @author Administrator
*
*/
publicclass Arithmetic_3_39
{
/**
* 輸入一個DFA D
* @param d DFA狀態轉換表
* @param S 狀態集合
* @param E 輸入字元表
* @param s 開始狀態
* @param F 接受狀態集
* @return 一個DFA D', 它和D接受相同的語言, 且輸入狀態數最少
*/
publicint[][] convert(int[][] d, Set<Integer> S, char[] E, int s, Set<Integer> F)
{
// 首先用接受狀態組和非接受狀態組劃分 PI
Set<Set<Integer>> PI = new HashSet<Set<Integer>>();
// 計算 S - F
S.removeAll(F);
PI.add(F);
PI.add(S);
// 最初, 令PInew = PI
Set<Set<Integer>> PInew = new HashSet<Set<Integer>>();
// TODO 解決淺復制帶來的問題
PInew.addAll(PI);
while (true)
{
// 對PI中的每個組G
for (Iterator<Set<Integer>> it = PI.iterator(); it.hasNext(); )
{
List<Object> groupList = new ArrayList<Object>();
Set<Integer> G = it.next();
// 使用字元表測試G的元素
// 對於字元表的每個輸入a
for (int i = 0; i < E.length; i++)
{
Map<Integer, Set<Integer>> groupMap = new HashMap<Integer, Set<Integer>>();
char a = E[i];
for (Iterator<Integer> sIt = G.iterator(); sIt.hasNext(); )
{
int stat = sIt.next();
// 從狀態S出發 沿著a能夠到達的狀態
int tar = d[stat][a];
// 獲取目標狀態在PI中的位置
int idx = getElelementIdx(PI, tar);
Set<Integer> group = groupMap.get(idx);
if (group == null)
{
group = new HashSet<Integer>();
groupMap.put(idx, group);
}
group.add(stat);
}
groupList.add(groupMap);
}
// 在PInew中將G替換為對G進行分組得到的那些小組
PInew.remove(G);
PInew.addAll(setListPoly(groupList));
}
// 判斷2個集合組是否相等
if (!isTwoSetGrpEqual(PI, PInew))
{
PI.clear();
PI.addAll(PInew);
} else
{
break;
}
}
// TODO 步驟4
for (Iterator<Set<Integer>> it = PI.iterator(); it.hasNext(); )
{
Set<Integer> set = it.next();
// 令S1是PI組中某個G的代表
for (Iterator<Integer> sIt = set.iterator(); sIt.hasNext(); )
{
int s1 = sIt.next();
while (sIt.hasNext())
{
// 用S1替換SWP
int swp = sIt.next();
for (int i = 0; i < d.length; i++)
{
for (int j = 0; j < d[i].length; j++)
{
if (d[i][j] == swp)
{
d[i][j] = s1;
}
}
}
// 刪除SWP的轉換函數
d[swp] = newint[]{};
}
}
}
return d;
}
/**
* 獲取某個元素在集合組中的索引
* @param set
* @param element
* @return
*/
privateint getElelementIdx(Set<Set<Integer>> set, int element)
{
int idx = 0;
for (Iterator<Set<Integer>> it = set.iterator(); it.hasNext(); )
{
Set<Integer> g = it.next();
if (g.contains(element))
{
// TODO 檢查HASHCODE 是否代表了集合的位置
return idx;
}
idx++;
}
return -1;
}
// 計算集合組聚合的結果
@SuppressWarnings("unchecked")
private Set<Set<Integer>> setListPoly(List<Object> oriSetList)
{
Set<Set<Integer>> result = new HashSet<Set<Integer>>();
if (oriSetList.size() > 0)
{
// 讀取第一個集合組
Map<Integer, Set<Integer>> groupMap = (Map<Integer, Set<Integer>>)oriSetList.get(0);
for (Iterator<Integer> it = groupMap.keySet().iterator(); it.hasNext(); )
{
result.add(groupMap.get(it.next()));
}
for (int i = 1; i < oriSetList.size(); i++)
{
// 獲取中間集合
Map<Integer, Set<Integer>> midMap = (Map<Integer, Set<Integer>>)oriSetList.get(i);
List<Set<Integer>> midSetList = new ArrayList<Set<Integer>>();
for (Iterator<Integer> it = midMap.keySet().iterator(); it.hasNext(); )
{
midSetList.add(midMap.get(it.next()));
}
// 開始計算
// 運算結果
List<Set<Integer>> calcResult = new ArrayList<Set<Integer>>();
for (Iterator<Set<Integer>> it = result.iterator(); it.hasNext(); )
{
Set<Integer> srcSet = it.next();
for (int k = 0; k < midSetList.size(); k++)
{
// 計算2個集合的交集
Set<Integer> mixed = getSetMixed(srcSet, midSetList.get(k));
// 如果結果不為空
if (!mixed.isEmpty())
{
// 保存運算結果
calcResult.add(mixed);
}
}
}
// 將計算結果替換result
result.clear();
result.addAll(calcResult);
}
}
return result;
}
// 計算二個集合的交集
private Set<Integer> getSetMixed(Set<Integer> set1, Set<Integer> set2)
{
Set<Integer> mixed = new HashSet<Integer>();
for (Iterator<Integer> it = set1.iterator(); it.hasNext(); )
{
int emu = it.next();
if (set2.contains(emu))
{
mixed.add(emu);
}
}
return mixed;
}
/**
* 判斷2個集合組是否相等
* @param setGrp1
* @param setGrp2
* @return
*/
privateboolean isTwoSetGrpEqual(Set<Set<Integer>> setGrp1, Set<Set<Integer>> setGrp2)
{
boolean same = false;
int matchCounts = 0;
if (setGrp1.size() == setGrp2.size())
{
for (Iterator<Set<Integer>> it = setGrp1.iterator(); it.hasNext(); )
{
Set<Integer> set1 = it.next();
for (Iterator<Set<Integer>> it2 = setGrp2.iterator(); it2.hasNext(); )
{
Set<Integer> set2 = it2.next();
if (set2.equals(set1))
{
matchCounts++;
}
}
}
if (matchCounts == setGrp1.size())
{
same = true;
}
}
return same;
}
}
// 測試:
package test;
import java.util.HashSet;
import java.util.Set;
import chapter3.Arithmetic_3_39;
publicclass TestCase
{
publicstaticvoid main(String[] args)
{
new TestCase().test_339();
}
publicvoid test_339()
{
// DFA的轉換表
int[][] d = {{}, {2, 3}, {2, 4}, {2, 3}, {2, 5}, {2, 3}};
// 輸入狀態集合
Set<Integer> S = new HashSet<Integer>();
S.add(1);
S.add(2);
S.add(3);
S.add(4);
S.add(5);
// 輸入字元
char[] E = {0, 1};
int s = 1;
Set<Integer> F = new HashSet<Integer>();
F.add(5);
Arithmetic_3_39 a339 = new Arithmetic_3_39();
a339.convert(d, S, E, s, F);
}
}
對於一個NFA，當把它確定化之後，得到的DFA所具有的狀態數可能並不是最小的。其原因之一，就在於上面所給出的確定化演算法沒有考慮到DFA中具有某種「同一性」的一些狀態可加以合並的問題。所謂一個DFA M狀態數的最小化，是指構造一個等價的DFA M′，而後者有最小的狀態數。為了說明狀態數最小化演算法的思想，我們先引入可區分狀態的概念。設M=(K,Σ,f,S0,Z)為一DFA，並設s和t是M的兩個不同狀態，我們說狀態s,t為某一輸入串w所區分，是指從s,t中之一出發，當掃視完w之後到達M的終態，但從其中的另一個狀態出發，當掃視完同一個w後而進入非終態。如果兩個狀態s和t不可區分 (即對任何輸入串w，當且僅當f(s,w)∈Z,f(t,w)∈Z)，則稱s和t等價。顯然，在一個DFA中，就識別符號串的作用而言，相互等價的狀態處於同等的地位，故可設法將它們合並，以減少DFA的狀態個數。下面給出一個將DFA M狀態數最小化的演算法。此演算法的基本思想，就是將M的狀態集K逐步進行劃分，以期最後按上述狀態的等價關系將K分裂為r個 (r≤|K|)互不相交的子集，使得屬於同一子集中的任何兩個狀態都是等價的，而屬於不同子集的任意兩個狀態都是可區分的。此演算法的執行步驟如下：(1) 首先，將M的狀態集K按終態與非終態劃分為兩個子集Z及K-Z，以構成初始分劃，記為π={Z,K-Z}。(2) 設當前的分劃π中已含有m個子集，即π={I1, I2, …, Im}其中，屬於不同子集的狀態是可區分的，而屬於同一子集中的諸狀態則是待區分的。即需對每一子集Ii={Si1,Si2,…,Sin}中各狀態Sir (Sir∈K,1≤r≤n)進行考察，看是否還能對它們再進行區分。例如，Sip和Siq是Ii中的兩個狀態，若有某個a∈Σ，使f(Sip,a)=Sju及f(Siq,a)=Skv，而狀態Sju及Skv分別屬於π中兩個不同的子集Ij和Ik，故Sju與Skv為某一w所區分，從而Sip和Siq必為w所區分，故應將子集Ii進一步細分，使Sip和Siq分別屬於Ii的不同的子集。也就是說，對於每一子集Ii及每一a∈Σ，我們需考察Iai=f(Ii,a)=∪n[]r=1f(Sir,a)若Iai中的狀態分別落於π中的p個不同的子集，則將Ii分為p個更小的狀態子集I(1)i,I(2)i,…，I(p)i，使得對於每一個I(j)i,f(I(j)i,a)中的全部狀態都落於π的同一子集之中。注意，若對某狀態Sir,f(Sir,a)無意義，則Sir與任何Sit(f(Sit,a)有定義)都是可區分的。這樣，每細分一次，就得一個新的分劃πnew，且分劃中的子集數也由原來的m個變為m+p-1個。(3) 若πnew≠π，則將πnew作為π再重復第2步中的過程，如此等等，直到最後得到一個分劃π，使πnew=π，即π中的各個子集不能再細分為止。(4) 對於所得的最後分劃π，我們從它的每一子集Ij={Sj1,Sj2,…,Sjr}中任選一個狀態，如Sj1，作為Ij中所含各狀態的代表，這些所選出的狀態便組成了M′的狀態集K′。而且，若Ij中含有M的初態，則Sj1為M′的初態；若Ij中含有M的終態，則Sj1為M′的一個終態。此外，為構成DFA M′，還應將各子集中落選的狀態從原DFA M中刪去，並將原來進入這些狀態的所有矢線都改為進入它們的代表狀態。例36設已給DFAM=({S0,S1,…,S4}, {a,b},f,S0,{S4})相應的狀態轉換圖和狀態轉移矩陣如圖314(a)及(b)所示。現用上述演算法將M最小化。(1) 初始分劃由兩個子集組成，即π:{S0,S1,S2,S3}, {S4}(2) 為得到下一分劃，考察子集{S0,S1,S2,S3}。為敘述方便起見，下面我們用記號{}a表示：當M分別處於該子集各狀態之下，對輸入符號a轉移到的下一狀態所組成的集合。因為{S0,S1,S2,S3}a={S1}{S0,S1,S2,S3}但{S0,S1,S2}b={S2,S3}{S3}b={S4}即{S0,S1,S2,S3}b不包含在π的同一子集之中，故應將{S0,S1,S2,S3}分為兩個子集{S0,S1,S2}及{S3}，於是便得到下一分劃πnew:{S0,S1,S2}, {S3}, {S4}又因πnew≠π，現以πnew作為π，即π:{S0,S1,S2}, {S3}, {S4}再考慮{S0,S1,S2}，因為{S0,S1,S2}a={S1}{S0,S1,S2}而{S0,S2}b={S2}{S1}b={S3}故應將{S0,S1,S2}再分為{S0,S2}及{S1}，從而又得到πnew:{S0,S2}, {S1}, {S3}, {S4}由於此時仍有πnew≠π，故再以πnew作為π，即π:{S0,S2}, {S1}, {S3}, {S4}現考察{S0,S2}，由於{S0,S2}a={S1}而{S0,S2}b={S2}{S0,S2}即{S0,S2}a與{S0,S2}b已分別包含在π的同一子集{S1}及{S0,S2}之中，故子集{S0,S2}已不能再分裂。此時πnew=π，子集分裂的過程宣告結束。(3) 現選擇狀態S0作為{S0,S2}的代表，將狀態S2從狀態轉換圖中刪去，並將原來引向S2的矢線都引至S0，這樣，我們就得到了化簡後的DFA M′，如圖315(a)及(b)所示。最後，再考察圖314(a)及圖315(b)所示的FA。容易看出，它們所接受的語言均是以abb為後綴的任意a,b符號串所組成的集合，也就說，這兩個FA是相互等價的。實際上，我們還可以進一步證明如下的定理。定理32對於有同一接受集的FA，與之等價且具有最小狀態數的DFA在同構意義下 (即不顧狀態的命名)是惟一的。
C. 約束能量最小化演算法
6.2.2.1 約束能量最小化演算法思想
約束能量最小化（Constrained Energy Minimization，CEM）演算法是在參考光譜已知、背景光譜未知的條件下對小目標進行探測和提取的演算法（耿修瑞，2005）。演算法根據目標光譜，放大特定方向信號，衰減其他背景信號，從而實現目標提取。其具體思想如下：
記S＝｛r1，r2，…，rN｝為所有高光譜數據像元矢量集合，其中ri＝（ri1，ri2，…，riL）T為任意像元光譜矢量，i＝1，2，…，N，N為像元數目，L為影像波段總數。假設d＝（d1，d2，…，dL）T為已知目標像元光譜矢量，CEM就是要設計這樣一種線性濾波器w＝（w1，w2，…，wL）T，使之滿足：
高光譜遙感影像信息提取技術
當輸入像元光譜矢量ri時，經過濾波器，其輸出yi為
高光譜遙感影像信息提取技術
所有像元光譜輸入濾波器後，平均輸出能量為
高光譜遙感影像信息提取技術
式中： 是影像數據集S的自相關矩陣。
濾波器w的設計就是求式（6.11）在約束條件式（6.9）下的最小值問題，即：
高光譜遙感影像信息提取技術
6.2.2.2 約束能量最小化運算元的求解
主要是採用拉格朗日乘數法對該約束條件最小值問題進行CEM運算元的求解，求解步驟如下：
1）構造拉格朗日函數：F（w）＝wTRw＋λ（dTw－1），λ是拉格朗日構造參數；
2）求偏導：##F（w）/##w＝Rw＋RTw＋λd＝2Rw＋λd；
3）令偏導等於0，得：w＝－1/（λR－1d）；
4）將w代入式（6.9），得：λ＝－2/（dTR－1d）；
5）將λ代入步驟3），得運算元為：w*＝R－1d/（dTR－1d）。
因此，將w*作用於S，得到設計的濾波器為
高光譜遙感影像信息提取技術
D. 新版ms的discover模塊中non-bond在哪
Discover模塊(1)原子立場的分配：在使用 Discover 模塊建立基於力場的計算中，涉及幾個步驟。主要有：選 擇力場、指定原子類型、計算或指定電荷、選擇 non-bond cutoffs。 在這些步驟中，指定原子類型和計算電荷一般是自動執行的。然而，在某些 情形下需要手動指定原子類型。 原子定型使用預定義的規則對結構中的每個原子 指定原子類型。在為特定的系統確定能量和力時， 定型原子使工作者能使用正確的力場參數。通常，原子定型由 Discover 使用定型引擎的基本規則來自動執行，所以不需要手動原子定型。然而，在特殊情形下，人們不得不手動定型原子，以確保它們被正確地設置。調出選擇原子窗口; 選擇原子窗口; 計算並顯示原子類型；編輯集合；設定新集合；給原子添加立場。點擊 Edit→Atom Selection；彈出對話 框，從右邊的的元素周期表中選擇 元素(例如Fe)，再點 Select，此時所建 晶胞中所有 Fe 原子都將被選中，原子被紅色線圈住即表示原子被選中。再編輯 集合，點擊 Edit→Edit Sets，彈出對話框，點擊New，給原子集合設定一個名字，這里設置為Fe，則3D視圖中會顯示「Fe」字樣。再分配力場：在工具欄上點擊discover按鈕，從下拉列表中選擇set up，顯示discover set up對話框，選擇Typing選項卡，在 Forcefield types 里選擇相應原子力場，再點 Assign(分配)按鈕進行原子 力 場 分 配 。 注 意 原 子 力 場 中 的 價 態 要 與 Properties Project 里 的 原 子 價 態(Formal charge）一致。(2)體系立場的選擇點擊 Energy 選項卡， 力場下拉菜單，進行力場選擇爛漏。力場的選擇： 力場是經典模擬計算的核心， 因為它代表著結構中每種類型的原子與圍盯山繞著它的原子是如何相互作用的。對系統中的每個原子，力場類型都被指定了，它描述了原子的局部環境。力場包括描述屬性的不同的信息， 如平衡鍵長度和力場類 型對之間的電子相互作用。常見力場有 COMPASS、CVFF 和 PCFF。 Select 下拉菜單中有三個選項： ①COMPASS 力場：COMPASS 力場是第一個把以往分別處理的有機分子體系的力場與無機分子體系的力場統一的分子力場。 COMPASS 力場能夠模擬小分子與高分子，一些金屬離子、金屬氧化物與金屬。在處理有機與無機體系時，採用分類別處理的方式，不同的體系採用不同的模型，即使對於兩類體系的混合，仍然能夠採用合理的模型描述。一般採用此力場。 ②CVFF 力場： CVFF 力場全名為一致性價力場(consistent valence force field), 最初以生化分子為主，適應於計算氨基酸、水及含各種官能團的分子體系。其後，經過不斷的強化CVFF 力場可適用於計算多肽、蛋白質與大量的有機分子。此 力場以計算系統的結構與結合能最為准確，亦可提供合理的構型能與振動頻率。 ③PCFF 力場：PCFF 為一致性力場，增加一些金屬元素的力參數，可以模擬含有相應原子的分子體系， 其參數的確定除大量的實驗數據外，還需要大量的 量子力學計算結果。
(3)非鍵的設置打開 Non-bond 選項卡，非鍵選項卡。非鍵作用力包括范德華力和庫倫力。這里將兩者都選上，為的是後期做 minimize 優化原子位置時精確度更高，因為考慮的作用力因素多，即兩者都考慮了。Summation method(模擬方法) ： ①Atom Based：atom based 基於原子的總量，包括一個原子的截斷距離，一 個原子的緩沖寬度距離； 為直接計演算法， 即直接計算原子對之間的非鍵相互作用，當原子對超出一定距離（截斷半徑 cutoff distance）時，即認為原子對之間相互 作用為零（註：cutoff distance 指范德華作用力和庫侖力的范圍，比如：凱歷中設 定截斷半徑為 5，則表示已分子或原子中心為圓心，以 5 為半徑作圓，半徑以外 的作用力都不考慮）。此方法計算量較小，但是可能導致能量和其導數的不連續性。當原子對間距離在 Cutoff 半徑附近變化時， 由於前一步考慮了原子對之間的相互作用， 而後一步不考慮， 由此會導致能量發生跳躍。 當然，對於較小的體系， 則可以設置足夠大的 Cutoff 半徑來保證所有的相互作用都被考慮進來。②Group Based：group based 基於電子群的，總量中包括一個原子的截斷距離，一個原子的緩沖寬度距離；大多數的分子力場都包括了每個原子之間點電荷 的庫侖相互作用。甚至在電中性的物種中也存在點電荷，例如水分子。點電荷實 際上反映了分子中不同原子的電負性。在模擬中，點電荷一般是通過電荷平衡法 (charge equilibrium)評價或者力場定義的電荷來分配的。當評價點電荷時，一 定要小心不要在使用 Cutoff 技術時引入錯誤的單極項。 要了解到這一點，可以參 看如下事實：兩個單極，當只有 1e.u.電荷時，在 10A 的位置上其相互作用大約 為 33Kcal；而對於由單位單極分離 1A 所形成的兩個偶極，相同距離其相互作用 能不超過 0.3Kcal/mol。很明顯，忽略單極-單極相互作用會導致錯誤的結果，而忽略偶極-偶極相互 作用則是適度的近似。然而，如果單極相互作用處理不清的話，仍然會出問題。 當 non-bond Cutoff 使用基於原子-原子基組時，就可能發生，會有人為將偶極劈裂 為兩個「假」的單極(當一個偶極原子在 Cutoff 內，另一個在其外)。這就不是忽 略了相對較小的偶極-偶極相互作用，而是人為引入了作用較大的單極-單極相互 作用。為了避免這種人為現象，Materials Studio 引入了在 Charge Groups 之上的 Cutoff。 一個「Charge Group」是一個小的原子基團，其原子彼此接近，凈電荷為 0 或 者接近於 0。 在實際應用中， Charge Group 一般是常見的化學官能團，例如羰基、甲基或者羧酸基團的凈電荷接近於中性 Charge Group。Charge Group 之間的距離 為一個官能團中心到另一個官能團中心的距離 R，Cutoff 設置與 Atom Based 相 類似。③Ewald Summation：Ewald 是在周期性系統內計算 Non-bond 的一種技術。Ewald 是計算長程靜電相互作用能的一種演算法。Ewald 加和方法比較合適於結晶固體。原因在於無限的晶格內，Cutoff 方法會產生較大的誤差。然而，此方法放也可以用於無定形固體和溶液體系。Ewald 計算量較大，體系較大時，會佔用較多的內存並花費較長的時間。 ④cell multiple cell based：只能用於基於指定數量層。 一般情況下，基於 Atom 適合於孤立體系，對於周期性體系計算量較小，但 是准確性較差；基於 Group 適合於周期性和非周期性體系，計算的准確性好一些，計算量最小；Ewald 適合於周期性能體系，計算最為准確，但計算量最大。
(4)結構優化在工具欄上點擊 Discover 按鈕，然後選擇 Minimizer。或者從菜單欄選擇 Moles | Discover | Minimizer。顯示 Discover Minimizer 對話框，可以進行幾何結構優化計算。優化前(Minimizer) ，先查看所有原子是否都已分配力場，如果沒有，可以手動添加，在 Properties Explorer 中雙擊 Forcefield type，然後修改力場類型即可。其次在Minimizer 之前，需要把晶體結構所有原子重新固定。 Minimizer 只是對結構進行優化，以達到能量最小化。在作動力學(dynamics )之前最好執行 minimizer， 因為如果不執行 minimizer， 則計算收斂時間會比較長，能量波動會比較大，而且計算有可能出錯。優化方法 Method：最陡下降法（Steepest Descent） 、共軛梯度法（Conjugate Gradient） 、牛頓方法（Newton）和綜合法(Smart Minimizer) 。 Convergence level：收斂精度水平。 Maximum iteration：最大迭代數。 Optimize cell 選中的話表示優化晶胞參數和原子位置。MS Discover 結構優化原理分子的勢能一般為鍵合（鍵長、鍵角、二面角、扭轉角等）和非鍵合相互作 用(靜電作用、 范德華作用等) 能量項的加和，總勢能是各類勢能之和， 如下式： 總勢能 = 范德華非鍵結勢能 + 鍵伸縮勢能 + 鍵角彎曲勢能 + 雙面角扭 曲勢能 + 離平面振動勢能 + 庫倫靜電勢能 + ... 除了一些簡單的分子以外， 大多數的勢能是分子中一些復雜形勢的勢能的組合。勢能為分子中原子坐標的函數，由原子不同的坐標所得到的勢能構成勢能面 (Potential Energy Surface，PES)。勢能越低，構象越穩定，在系統中出現的機 率越大；反之，勢能越高，構象越不穩定，在系統中出現的機率越小。通常勢能面可得到許多極小值的位置，其中對應於最低能量的點稱為全局最小值（Global Energy Minimum），相當於分子最穩定的構象。由勢能面求最低極小值的過程 稱為能量最小化（Energy Minimum），其所對應的結構為最優化結構（Optimized Structure），能量最小化過程，亦是結構優化的過程。 通過最小化演算法進行結構優化時，應避免陷入局部最小值 (local minimum) ，也就是避免僅得到某一構象附近的相對穩定的構象，而力求得到全局最小值，即實現全局優化。分子力學的最小化演算法能較快進行能量優化，但它的局限性在於易陷入局部勢阱，求得的往往是局部最小值，而要尋求全局最小值只能採用系統搜尋法或分子動力學法。在 Materials Studio 的 Discover 模塊中，能量最小化算 法有以下四種： ①最陡下降法（Steepest Descent），為一經典的方法，通過迭代求導，對多 變數的非線性目標函數極小化， 按能量梯度相反的方向對坐標添加位移， 即能量 函數的負梯度方向是目標函數最陡下降的方向，所以稱為最陡下降法。此法計算 簡單，速度快，但在極小值附近收斂性不夠好，造成移動方向正交。最陡下降法 適用於優化的最初階段。②共軛梯度法（Conjugate Gradient），在求導時，目標函數下降方向不是僅 選取最陡下降法所採用的能量函數的負梯度方向，而是選取兩個共軛梯度方向， 即前次迭代時的能量函數負梯度方向與當前迭代時的能量函數負梯度方向的線 性組合。此法收斂性較好，但對分子起始結構要求較高，因此常與最陡下降法聯 合使用，先用最陡下降法優化，再用共軛梯度法優化至收斂。 ③牛頓方法（Newton），以二階導數方法求得極小值。此法的收斂很迅速， 也常與最陡下降法聯合使用。 ④綜合法（Smart Minimizer），該方法可以混合最陡下降法，共軛梯度法和 牛頓法進行結構優化，在 MS 中是可選擇的。Smart Minimizer 中，牛頓法可以設 定最大的原子數， 如果體系的原子數大於所設定的值， 則計算是會自動地轉為前 面設定的收斂法（共軛梯度法或最陡下降法），收斂精度會改為共軛梯度法的默 認收斂精度值。 點開各種方法後面的 More，可設定收斂精度(Convergence)，演算法(Algorithm)和一維搜索(Line search，指每一次迭代中的精度)等。
當 Job 結束後，結果被返回到 Disco Min 目錄，最小化的結構被命名為 3D Atomistic.xsd，並被保存在 「3D Atomistic Disco Min」目錄。 還生成一個名為 「3D Atomistic.out」的文本文檔，它包含了有關計算的所有能量信息。同時還生成 「Simulation Energies.xcd」 它顯示了能量隨迭代次數的變化情況，由於優化是使結構更加穩定，所以能量也隨之降低，最終趨於某一值。結構優化後，原子會有所重排，使結構更加穩定。(5)高溫弛豫打開 discover 下的 Dynamics，Ensemble（系綜） NVE、NVT、NPT、NPH。 ： Temperature：目標溫度。 Pressure：給系統所施加的壓力。 Number of steps：整個動力學所運行的總步數。 Time step：每一動力學步驟所花費的時間（單步長時間） 。 Dynamics time：Number of steps ×Time step（總模擬時間） 。 Trajectory Save：Coordinates 表示保存坐標；Final Structure表示只保存最終結構；Full 表示保存所有。 Frame output every： 若輸入 5000， 則表示每 5000 步輸出一幀(即晶體結構) 。運行結束後，可以通過調用 Animation 觀看三維動畫。動畫工具條可以控制三維窗口中動畫文件的顯示，它包含以下命令： Play Backwards：倒映動畫文件。 Step Backwards：每次向後放一幀。 Stop：停止放映。 Step Forwards：每次一幀加速放映。 Play：放映動畫。 Pause：暫停放映，再按一次後繼續放映。 Animation Mode：顯示動畫模式下拉菜單。系綜簡介系綜(ensemble)是指具有相同條件系統(system)的集合。平衡態的分子動力學模擬，總是在一定的系綜下進行。系綜是統計力學中非常重要的概念，系統的一切統計特性基本都是以系綜為起點推導得到的。實際應用時，要注意選擇適當的系綜，如（N，T，P） 常用於研究材質的相變化等。①NVE(微正則系綜)在微正則系綜（micrononical ensemble）中，模型體系的粒子數 N、體積 V 及內能（熱力學能）E（在熱力學通常用 U 表示內能）保持不變,是一個孤立、保守的系統。值得注意的是：體系總能量，即勢能和動能的總和，是保持守恆的，常被用來判斷積分的精度固定不變。它對應於絕熱過程，即體系與環境沒有熱交換，不存在溫度 T 和壓力 p 的控制因素。由於體系的能量 E 是守恆的，體系的 動能和勢能之間互轉化。一般說，給定能量的精確初始條件是無法得到的。能量的調整通過對速度的標度進行，這種標度可能使系統失去平衡， 迭代弛豫達到平衡。②NVT 系綜(正則系綜) 正則系綜(canonical ensemble)中，體系的粒子數 N、體積 V 及溫度 T 保 持不變，且總動量保持不變。因此正則系綜動力學有時也被稱為恆溫動力學。為了控制體系的溫度，就需要設置一個「虛擬」的熱浴環境,與體系進行能量交換。常用的熱浴 (bath) 包括： Nose-Hoover， Berendsen， Andersen 以及 「velocity scaling （速度標定） 」方法等。
系綜控溫機制。系綜的控溫：溫度調控機制可以使系統的溫度維持在給定值，也可以根據外界環境的溫度使系統溫度發生漲落。 一個合理的溫控機制能夠產生正確的統計系 綜，即調溫後各粒子位形發生的概率可以滿足統計力學法則。系綜控溫機制主要有：Velocity Scale、Nose、Berendsen。Thermostat 下拉菜單有四個： ①Velocity Scale（直接速度標定法）：系統溫度和粒子的速度直接相關，可以通過調整粒子的速度使系統溫度維持在目標值。 實際分子動力學模擬中，並不需要對每一步的速度都進行標定，而是每隔一定的積分步，對速度進行周期性的標定，從而使系統溫度在目標值附近小幅波動。 直接速度標定法的優點是原理簡 單，易於程序編制。缺點是模擬系統無法和任何一個統計力學的系綜對應起來； 突然的速度標定引起體系能量的突然改變，致使模擬系統和真實結構的平衡態相 差較遠。 ②Nose：該方法可以把任何數量的原子與一個熱浴耦合起來，可以消除局域 的相關運動，而且可以模擬宏觀系統的溫度漲落現象。 ③Andersen：體系與一強加了指定溫度的熱浴相耦合。 ④Berendsen 控溫機制: 又稱 Berendsen 外部熱浴法。 其基本思想是假設系統 和一個恆溫的外部熱浴耦合在一起， 通過熱浴吸收和釋放能量來調節系統的溫度， 使之與恆溫熱浴保持一致。對速度每一步進行標定，以保持溫度的變化率與熱 浴和系統的溫差(Tbath-T(t))成比例。當系綜選定 NPT 時，控溫機制應用 Nose。 系綜控壓機制。幾種控壓機制 ，下拉菜單有 3 項： ①Andersen：假定系統與外界「活塞」耦合，當外部壓強不能補償系統內部 壓強時，「活塞」運動引起系統均勻地膨脹或收縮，最終使得系統壓強等於外部壓強。Andersen 方法具有重要的意義，後來的各種壓力控制方法基本都是基於 Andersen 思想發展起來的。②Berendsen：這種方法是假想把系統與一「壓浴」相耦合。 ③Parrinello：這種方法允許原胞的形狀與體積同時發生變化，以達到與外壓 平衡。這種方法是對 Anderson 調壓方法的一種擴展，可以實現對原胞施加拉伸 剪切以及混合載入情況的模擬，因此在對材料的力學性質的分子動力學模擬中，得到了廣泛地應用。由於本文採用 NPT 系綜，壓力一定，所以將會看到控壓機制不可選。 Dynamics 運行結束後，可以得到結構圖。
由於高溫(2000K)弛豫，高於熔化溫度，所以此時體系處於液態狀態，因此原 子處於遠程無序狀態。Project Explorer 中還生成了其他一些文件，如能量-模擬時間曲線圖，溫度-模擬時間曲線圖，以及一些輸入輸出文件。高溫弛豫中原子通過遷移、運動或者擴散，逐步降低原來的高內能態，向穩定的低內能態轉變。因此能量隨時間的推移將降低並趨於某一值，而溫度逐漸穩定在設定的 2000K 上下做微小變動。
￥
5.9
網路文庫VIP限時優惠現在開通,立享6億+VIP內容
立即獲取
MS中discovery模塊
Discover模塊
(1)原子立場的分配：
在使用 Discover 模塊建立基於力場的計算中，涉及幾個步驟。主要有：選 擇力場、指定原子類型、計算或指定電荷、選擇 non-bond cutoffs。 在這些步驟中，指定原子類型和計算電荷一般是自動執行的。然而，在某些 情形下需要手動指定原子類型。 原子定型使用預定義的規則對結構中的每個原子 指定原子類型。在為特定的系統確定能量和力時， 定型原子使工作者能使用正確的力場參數。通常，原子定型由 Discover 使用定型引擎的基本規則來自動執行，所以不需要手動原子定型。然而，在特殊情形下，人們不得不手動定型原子，以確保它們被正確地設置
E. 高數極大值和極小值的演算法
Minimax演算法 又名極小化極大演算法，是一種找出失敗的最大可能性中的最小值的演算法（即最小化對手的最大得益）。通常以遞歸形式來實現。
Minimax演算法常用於棋類等由兩方較量的游戲和程序。該演算法是一個零總和演算法，即一方要在可選的選項中選擇將其優勢最大化的選擇，另一方則選擇令對手優勢最小化的一個，其輸贏的總和為0（有點像能量守恆，就像本身兩個玩家都有1點，最後輸家要將他的1點給贏家，但整體上還是總共有2點）。很多棋類游戲可以採取此演算法，例如tic-tac-toe。
F. 雙剪叉結構如何降到最低
雙剪叉結構如何降到最低可通過優化化學鍵的長度和角度、合理選擇取代基的位置和類型、使用各種最小化演算法降到最低。
1、優化化學鍵的長度和角度：在雙剪叉結構棗臘中，化學鍵的長度和角度會影響其能量。通過使用合適的計算方法，優化參數，從而降清棗低結構的能量。
2、合理選擇取代基的位置和類型：在雙剪凳正滑叉結構中，取代基的位置和類型也對其能量有很大的影響。通過合理選擇取代基的位置和類型，使雙剪叉結構的能量降低。
3、使用各種最小化演算法：最小化演算法是一種可以優化分子構型的方法，包括梯度下降、共軛梯度、牛頓法、擬牛頓法等。通過使用這些演算法，可快速地找到雙剪叉結構的最低能量構型。
G. dfa的最小化如何化簡的步驟
下面具體介紹DFA的化簡演算法：
（1） 首先將DFA M的狀態劃分出終止狀態集K1和非終止狀態集K2。
K＝K1∪K2
由上述定義知，K1和K2是不等價的。
（2） 對各狀態集每次按下面的方法進一步劃分，直到不再產生新的劃分。
設第i次劃分已將狀態集劃分為k組，即：
K＝K1(i)∪K2(i)∪…∪Kk(i)
對於狀態集Kj(i)（j=1,2,…,k）中的各個狀態逐個檢查，設有兩個狀態Kj』、 Kj』』∈Kj(i)，且對於輸入符號a，有：
F（Kj'，a）＝Km
F（Kj''，a）＝Kn
如果Km和Kn屬於同一個狀態集合，則將Kj』和Kj』』放到同一集合中，否則將Kj』和Kj』』分為兩個集合。
（3） 重復第（2）步，直到每一個集合不能再劃分為止，此時每個狀態集合中的狀態均是等價的。
（4） 合並等價狀態，即在等價狀態集中取任意一個狀態作為代表，刪去其他一切等價狀態。
（5） 若有無關狀態，則將其刪去。
根據以上方法就將確定有限自動機進行了簡化，而且簡化後的自動機是原自動機的狀態最少的自動機。
H. DFA的最小化演算法
首先劃分終態集和慎盯帆非終態集，之後不斷進行劃分，直到不再發生變化。
每輪劃分對所有子集進行。對一個子集的劃分中，若每個輸入符號都能把狀態轉換到等價的狀態，則兩個狀態等價。
劃分完成後，從每個子集選出一個代表，若DFA中存在兩個子集內狀態之間的轉換，則MFA中兩個子集的代表之間也存在對應的轉換。簡便方法：對每個子集刪則早去除代表以外的狀態，並把指向它們的箭弧改為指向寬雹代表。
MFA的初態是含有DFA初態的子集的代表。MFA的終態集是DFA終態集劃分出來子集的代表。
最後，從MFA中刪除從初態無法到達的狀態和死狀態（只有入射弧或指向自身的出射弧的非終止狀態）。
去除不可達狀態。建表，行列為不同狀態，未標記的格子行列狀態等價。首先標記行列一個非終止狀態一個終止狀態的格子。對未標記的格子(q,q')，若存在一個輸入符號a，使q經a到達狀態和q'經a到達狀態不等價，則標記(q,q')。重復直到表格不再變化。
對於所有未標記的(q,q')，把與q'有關的轉換都改到q上，刪除q'。
I. 分類演算法 - SVM演算法
SVM的全稱是Support Vector Machine，即支持向量機，主要用於解決模式識別領域中的數據分類問題，屬於有監督學習演算法的一種。SVM要解決的問題可以用一個經典的二分類問題加以描述。如圖1所示，紅色和藍色的二維數據點顯然是可以被一條直線分開的，在模式識別領域稱為線性可分問題。然而將兩類數據點分開的直線顯然不止一條。圖2和3分別給出了A、B兩種不同的分類方案，其中黑色實線為分界線，術語稱為「決策面」。每個決策面對應了一個線性分類器。雖然在目前的數據上看，這兩個分類器的分類結果是一樣的，但如果考慮潛在的其他數據，則兩者的分類性能是有差別的。
之前在b站看到一個非常好的介紹！！十分推薦， 這是傳送門
按照我自己的理解，以二維數據為例，我們喂給模型已經分類好的數據，那麼假設有一線條可以將此部分數據正確劃分為2大部分，這樣可以形成2個等式，即橫線兩邊的數值歸類為1或者-1，一般情況下可以求出最大間隔即無數個解，因此需要一個限定條件求出最優的那條線條。限定方式為：無數個解形成一個解的范圍，距離邊緣相等的那條線條即是最優解。
有時候本來數據的確是可分的，也就是說可以用線性分類SVM的學習方法來求解，但是卻因為混入了異常點，導致不能線性可分，比如下圖，本來數據是可以按下面的實線來做超平面分離的，可以由於一個橙色和一個藍色的異常點導致我們沒法按照線性分類支持向量機方法來分類。
以上討論的都是在線性可分情況進行討論的，但是實際問題中給出的數據並不是都是線性可分的，比如有些數據可能是曲線的。
那麼這種非線性可分的數據是否就不能用SVM演算法來求解呢？答案是否定的。事實上，對於低維平面內不可分的數據，放在一個高維空間中去就有可能變得可分。以二維平面的數據為例，我們可以通過找到一個映射將二維平面的點放到三維平面之中。理論上任意的數據樣本都能夠找到一個合適的映射使得這些在低維空間不能劃分的樣本到高維空間中之後能夠線性可分。
當特徵變數非常多的時候，在高維空間中計算內積的運算量是非常龐大的。考慮到我們的目的並不是為找到這樣一個映射而是為了計算其在高維空間的內積，因此如果我們能夠找到計算高維空間下內積的公式，那麼就能夠避免這樣龐大的計算量，我們的問題也就解決了。實際上這就是我們要找的 核函數 ，即兩個向量在隱式映射後的空間中的內積。
（1）對於邊界清晰的分類問題效果好；
（2）對高維分類問題效果好；
（3）當維度高於樣本數的時候，SVM 較為有效；
（4）因為最終只使用訓練集中的支持向量，所以節約內存
（1）當數據量較大時，訓練時間會較長；
（2）當數據集的噪音過多時，表現不好；
（3）SVM 不直接提供結果的概率估計，它在計算時直接使用 5 倍交叉驗證。
（1）LR 與 SVM 都是分類演算法；
（2）LR 與 SVM 都是監督學習演算法；
（3）LR 與 SVM 都是判別模型；
（4）關於判別模型與生成模型的詳細概念與理解，筆者會在下篇博文給出，這里不詳述。
（5）如果不考慮核函數，LR 與 SVM 都是線性分類演算法，也就是說他們的分類決策面都是線性的
這里需要說明的是，LR 也是可以用核函數的，因在 LR 演算法里，每個樣本點都必須參與決策面的計算過程，也就是說，如果在 LR 里也運用核函數的原理，那麼每個樣本點都必須參與核計算，這帶來的計算復雜度是相當高的。所以在具體應用時，LR 很少運用核函數機制。
（1）損失函數不同；
（2）SVM 只考慮支持向量，而 LR 考慮全局（即遠離的點對邊界線的確定也起作用）；
（3）在解決非線性問題時，SVM 採用核函數的機制，而 LR 通常不採用核函數的方法；
（4）SVM 的損失函數就自帶正則（損失函數中的12||w||2項），這就是為什麼 SVM 是結構風險最小化演算法的原因，而 LR 必須另外在損失函數上添加正則項；
（5）LR是參數模型，SVM是非參數模型，本質不同。
（6）在訓練集較小時，SVM 較適用，而 LR 需要較多的樣本。
（1）LR 與線性回歸都是廣義的線性回歸；
（2）線性回歸模型的優化目標函數是最小二乘，而 LR 則是似然函數；
（3）線性回歸在整個實數域范圍內進行預測，敏感度一致，而分類范圍，需要在[0,1]。邏輯回歸就是一種減小預測范圍，將預測值限定為[0,1]間的一種回歸模型，因而對於這類問題來說，邏輯回歸的魯棒性比線性回歸的要好。
（4）邏輯回歸的模型本質上是一個線性回歸模型，邏輯回歸都是以線性回歸為理論支持的。但線性回歸模型無法做到 sigmoid 的非線性形式，sigmoid 可以輕松處理 0/1 分類問題。
（5）線性回歸主要做預測，LR 主要做分類（如二分類）；
J. 什麼是極小化極大演算法
樓主算是問對人啦。我是做計算機博弈游戲開發的。
1、提出這個問題是為了解決象棋，五子棋這樣的二人全息零和博弈
二人：游戲是2個人玩的
全息：雙方的棋面信息都可以看到。（撲克牌就不同了）
零和：雙方的利益和是0.如果你勝利積1分。我就是輸-1分。相加就是0
2、極大極小的概念是相對的
我走棋，希望對我的利益幫助是最大的。對你的利益幫主是最小的
3、經典的例子很多。井字棋，五子棋，中國象棋，國際象棋等
象棋為例：
我和樓主對弈，某一步，我有N中走法，期中一種走法x後。我還要評估樓主針對我的X走法的所有應付策略。如果對2個人的局面做一個評判。我肯定希望選擇者N種走法中，即時你應對了，對我利益也是最大的那種走法。
4、這個概念我就貼個地址吧。後面的負極大極小演算法，alphabeta剪枝演算法都很經典的
希望你早日寫一個屬於你自己的極大較小值演算法的游戲
http://www.xqbase.com/computer.htm【一定要通讀10遍以上】
好運！