软计算方法和算法分析 (100分)

随着实际应用需求的增长,传统的优化方法越来越不能适应
复杂性,非线性,不确定性 越来越多的实际问题的要求.
因此,人们在传统优化方法的基础之上提出了新的算法思想.
传统的方法分成两类:
1.穷尽法: 比如动态规划法,分枝定界法,整数规划法等.
只考虑到最优性,而忽略了搜寻的效率性.
2.构造算法: 比如 琼森法,贪婪法 等.
只考虑到搜索的速度,而忽略了优化质量.
因此,人们发展出了领域搜索法,演化算法和 以上算法的混合算法,
通称之为软计算方法.软计算方法是基于模糊推理和概率分析而发展起来
的新算法,可以大大改善NP问题和NPC问题的解质量,
从而为解决复杂系统的最优化问题提供了行之有效的方法.
实际中的事件往往是具备模糊和随机的特性的.
模糊性是指信息的意义,事件的本身有不确定的特性,比如:某个人是不是年轻的
这一事件就带有模糊性,到底到什么程度才算好?我们用一个模糊集合来代表它.
模糊集合一般用隶属函数来描述,比如年轻的隶属函数
/1 0<=age<24
Y=|
/1/( 1+ (x-24)/5 ) 24<=age
模糊集合也可以进行并,交,补 等运算.
模糊集合可以分解成若干或者无限的普通集合来表示,
这就表明,模糊性的成因乃是复杂性的结果,
无数的清晰事物叠加在一起,就形成总体模糊的事物,
根据需要,可以选择一定精度的普通集合来近似模糊集合,从而描述模糊事件.
随机性则是表示事物发生的不确定性即可能性,比如:明天下雨的可能是多大.
随机事件有连续型和离散型两种,分别有相应的描述函数.
连续型概率函数: P(x<α)=∫f(x) dx ;
f(x)是概率密度
离散型概率函数: P(x<=A)=∑p[x=xi] xi<=A
概率性和模糊性可以相互结合,比如模糊概率时间,
比如篮球比赛获得大胜的可能多大?
大胜是一个模糊概念,可能是一种概率.模糊推理理论和概率统计理论目前
都在快速的发展之中,并已经成为计算机算法的重要理论基础.
模糊推理经常用于解决建立数学模型的问题,而概率统计经常用于算法分析之中,
下面,我仅用一个对两种内排序方法的分析,来体验一下概率分析的作用.

unit MySortProc;
interface
//下面的条件编译指令 测试用时请保留否则请注释
{$DEFINE TEST_SORT}

type
TSortDatas=array of Integer;
{$IFDEF TEST_SORT}
TCarveStrategyProc=function(const Datas:TSortDatas;
Lo,Hi:Integer):Integer;

//快序排序法,实验用
procedure QuickSort(var Datas:TSortDatas;
Lo, Hi: Integer;
CarveStrategy:TCarveStrategyProc);
//对应于快速排序法的各种划分策略
function Strategy0(const Datas:TSortDatas;
Lo,Hi:Integer):Integer;
function Strategy1(const Datas:TSortDatas;
Lo,Hi:Integer):Integer;
function Strategy2(const Datas:TSortDatas;
Lo,Hi:Integer):Integer;
function Strategy3(const Datas:TSortDatas;
Lo,Hi:Integer):Integer;
{$else
}
//实际中常用的方法, 采用Strategy1或者Strategy2
procedure QuickSort(var Datas:TSortDatas;
Hi:Integer);
{$ENDIF}
//归并排序法
procedure MergeSort(Datas:TSortDatas;
Len:Integer);
implementation
{$IFDEF TEST_SORT}
//快序排序法,实验用
procedure QuickSort(var Datas:TSortDatas;
Lo, Hi: Integer;
CarveStrategy:TCarveStrategyProc);
procedure Sort(Lo, Hi: Integer);
var
L, H, Mid, Temp: Integer;
begin
L:=Lo;
H:=Hi;
Mid:=CarveStrategy(Datas,L,H);
//划分策略,关系到快速搜索的关键代码
repeat //寻找交换对象,每次需要搜索次数总计为H-L次
while Datas[L]<Middo
Inc(L);
while Datas[H]>Middo
Dec(H);
if L<=H then
begin
Temp:=Datas[L];
Datas[L]:=Datas[H];
Datas[H]:=Temp;
Inc(L);
Dec(H);
end;
until L>H;
if H>Lo then
Sort(Lo,H);
if L<Hi then
Sort(L,Hi);
//继续划分
end;
begin
Sort(Lo,Hi);
end;
////////////////////////
//策略1,和2是比较合适的
function Strategy0(const Datas:TSortDatas;
Lo,Hi:Integer):Integer;
begin
Result:=Datas[Lo];
//选取低点元素为划分基准
end;
function Strategy1(const Datas:TSortDatas;
Lo,Hi:Integer):Integer;
begin
Result:=Datas[(Lo+Hi) div 2];
//选取中间元素为划分基准
end;
function Strategy2(const Datas:TSortDatas;
Lo,Hi:Integer):Integer;
begin
Result:=(Datas[Lo]+Datas[Hi])div 2;
//选取最高和最低元素平均值为划分基准
end;
function Strategy3(const Datas:TSortDatas;
Lo,Hi:Integer):Integer;
var
i:Integer;
begin
Result:=0;
for i:=Lo to Hido
Result:=Result+Datas;
Result:=Result div (Hi-Lo+1);
//取所有元素平均值为划分基准
end;
///////////////////////
{$else
}
//实际中常用的方法, 采用Strategy1或者Strategy2
procedure QuickSort(var Datas:TSortDatas;
Hi:Integer);
procedure Sort(Lo, Hi: Integer);
var
L, H, Mid, Temp: Integer;
begin
L:=Lo;
H:=Hi;
Mid:=Datas[(H+L)div 2];
//或者} Mid:=(Datas[H]+Datas[L])div 2;
repeat
while Datas[L]<Middo
Inc(L);
while Datas[H]>Middo
Dec(H);
if L<=H then
begin
Temp:=Datas[L];
Datas[L]:=Datas[H];
Datas[H]:=Temp;
Inc(L);
Dec(H);
end;
until L>H;
if H>Lo then
Sort(Lo,H);
if L<Hi then
Sort(L,Hi);
end;
begin
Sort(0,Hi );
end;
{$ENDIF}

////////////////////////////////////////////////////////
//将0~N-1中的每2*Step个数据合并成有序数组
procedure Merge2N(Src,Dest:TSortDatas;
N,Step:Integer);
var
bs,es:Integer;
//将Src中的相邻两块数据合并到Dest中对应位置
procedure MergeTwo(BPos,MPos,EPos:Integer);
var
i,j,k:Integer;
begin
i:=BPos;
k:=BPos;
j:=MPos+1;
while (i<=MPos) and (j<=EPos)do
if Src<Src[j] //选取小值进行复制
then
begin
Dest[k]:=Src;
Inc(k);
Inc(i);
end
else
begin
Dest[k]:=Src[j];
Inc(k);
Inc(j);
end;
while i<=MPosdo
begin
Dest[k]:=Src;
Inc(k);
Inc(i);
end;
while j<=EPosdo
begin
Dest[k]:=Src[j];
Inc(k);
Inc(j);
end;
end;
begin
bs:=0;
while bs+Step<Ndo
begin
es:=bs+2*Step-1;
if es>=n then
es:=n-1;
MergeTwo(bs,bs+Step-1,es);
bs:=es+1;
end;
while bs<ndo
//剩余段直接复制
begin
Dest[bs]:=Src[bs];
Inc(bs);
end;
end;
//归并排序法
procedure MergeSort(Datas:TSortDatas;
Len:Integer);
var
Temp:TSortDatas;
Step,i:Integer;
begin
SetLength(Temp,Len);
Step:=1;
i:=Integer(True);
while Step<Lendo
begin
if Boolean(i)
then
Merge2N(Datas,Temp,Len,Step)
else
Merge2N(Temp,Datas,Len,Step);
Step:=Step*2;
//归并规模不断扩大,直到完全归并
i:=Integer(not Boolean(i));
end;
if not Boolean(i) then
//经过奇数趟归并后,复制回Datas内
for i:=0 to Len-1do
Datas:=Temp;
end;

end.

上面的代码演示了两种最快速的通用内排序法:
快速排序法和归并排序法.
两者的空间和时间复杂度都是O和O(n*LogN(2,n) )
快速排序法不是严格稳定的,而且是基于概率的划分方法,
虽然不能保证划分的绝对精确性,但是有极佳的简洁性和比较出色的划分,
它最糟糕的情况是对每次X个元素的划分都是1和X-1个,这就使时间复杂度
达到O(n^2),但这种概率是非常小的,仅 1/2^X 左右,而划分的数学期望为:
E(X/2)=X/4,所以效率为LogN(1.5,n)=LogN(2,n)*long(1.5,2)=1.7*LogN(2,n).
归并排序法是容易想到的并且有严格的稳定性,
划分质量极端出色,但是采用了繁杂的划分方法..
快速排序法只在需要交换时才进行交换,而归并法无论什么情况都需要进行
交换,所以单次效率 快速排序大约为归并排序的2*2=4倍,
综合考虑,快速排序法大约是归并排序法速度的4/1.7=2.35倍.
实验和算法分析都指出,基于概率划分的快速排序法实际上
在绝大多数情况下获得了更好的效果
---by DarwinZhang 2003.5.22

以上看法是我的浅薄之见，如有谬误，还请指教！

呵呵，不错.
写到笔记里去吧,也好加几颗星.

算法值得学习，收藏。

to LeeChange:
谢谢!我放在这里,主要考虑可能一些大富翁没有接触到上面的那些东西,
也许可以提供一点新思路.另外,我系统的了解和学习软计算方法不到半年时间,
用它做的东西也有很少,可能会有些见解不全的地方,希望能得到一些建议.
笔记上好象去的人不太多,就放在这里了.

http://www.delphibbs.com/delphibbs/dispq.asp?lid=1902189
围棋的问题，以后再说，一想到要回复帖子就得写很多很多，就头疼！
我现在变得十分懒惰。：（

谢谢你，小笨笨！
但是我不敢接受，因为分数太多了。[]
分数对我不为贵，可这却是这里的财富标志呢！
而假如我接受了的话，对我来讲是丢失了原则。
而对大富翁来说，也许是丢失了公平性。
再次感谢您！但我确实不能接受。

zg

哎,上面有一个非常明显的错误都没有人指出,看来没有多少人仔细看过[]
看来我的水平和表达能力还要提高--以后不发这样的东西了.[]

贴出来的东西不一定都是没错误的，即使是定律也有可能被更改，楼主就不必自责，大家就应当取精华就可以了

????55555我什么都看不到了。只能发言。55555
只好接受答案了。

不错，很有见解，还有别的算法的思想给我一份，谢谢！