最小化算法
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遍以上】
好运！