神马文学网【精华】数据结构和算法版旧的精华贴 数据结构与算法 第二帖
来源：百度文库 编辑：神马文学网 时间：2024/04/18 21:00:15
{==========================================
最小生成树Prim 算法
基本思想：
T为最小生成树的边集；
U为一个顶点集
V为图的顶点集
图的顶点标号为1..n
procedure Prim;
begin
T:=Φ；
U:={1};
while U<>V do
begin
(u,v):= u∈U且v∈V-U的最小权边;
T:=T∪{(u,v)};
U:=U∪{v};
end;
end;
======================}
procedure Prim(var G:adj_matrix;size:integer);{G为图，size为图的节点数目;注意：假设输入的图是连通图}
var
lowcost:array [1..maxsize] of integer;
used:array [1..maxsize] of boolean;
closeset:array[1..maxsize] of integer;
i,j,k,min:integer;
begin
for i:=2 to size do {初始化，此时U只含有顶点1}
begin
lowcost[i]:= G[1,i];
closeset[i]:=1;
used[i]:=false;
end;
used[1]:=true;
for i:=2 to size do
begin
min:=maxint;
j:=i;
for k:=2 to size do {用选择法寻找顶点分别在V-U与U中权最小的边}
if (not used[k])and(lowcost[k]begin
min:=lowcost[k];
j:=k;
end;
writeln(fout,‘(‘,closeset[j],‘,‘,j,‘)‘); {输出找到的最小生成树的一条边，此处可根据情况修改}
used[j]:=true; {将j填加到U}
for k:=2 to size do {调整lowcost和closeset}
if (not used[k])and(G[j,k]begin
lowcost[k]:=G[j,k];
closeset[k]:=j;
end;
end;
end;
{==========================================
每对节点间最短路径
Flod-Warshall 算法
===========================================}
procedure Flod_Warshall(var G:adj_matrix;size:integer;var D,P:adj_matrix);
{D[i,j]表示从i到j的最短距离；P[i,j]表示从i到j的最短路径上j 的父节点}
var
i,j,k:integer;
begin
{初始化}
for i:=1 to size do {这里假设i,j不相邻时G[i,j]=∞。注意：为了防止溢出，无穷大不能取maxint，可以取maxint div 2}
for j:=1 to size do
begin
D[i,j]:=G[i,j];
P[i,j]:=i; {P[i,j]=0表示不存在从i到j的路径}
end;
for i:=1 to size do
begin
D[i,i]:=0;
P[i,i]:=0;
end;
for k:=1 to size do {进行size次迭代}
for i:=1 to size do
for j:=1 to size do
if (d[i,j]>d[i,k]+d[k,j]) then
begin
d[i,j]:=d[i,k]+d[k,j];
p[i,j]:=p[k,j];
end;
end;
{==========================================
求有向图的传递闭包
G[i,j]=1表示i,j相邻；G[i,j]=0表示i,j不相邻
===========================================}
procedure Transtive_Closure(var G:adj_matrix;size:integer;var T:TranstiveClosureType);
var
i,j,k:integer;
begin
for i:=1 to size do
for j:=1 to size do
if G[i,j]<>0 then //若i与j不相邻则G[i,j]=0，此处可根据情况修改
T[i,j]:=true;
for i:=1 to size do T[i,i]:=true;
for k:=1 to size do
for i:=1 to size do
for j:=1 to size do
T[i,j]:=T[i,j] or (T[i,k] and T[k,j]);
end;
{======================================================================
深度优先搜索，找出关于图的结构的信息
存储结构信息的变量说明如下：
/ =0 顶点i到顶点j无边
G-邻接矩阵表示的图，g[i,j]= -| >0 边(i,j)存在且允许访问
\ <0 边(i,j)存在但不允许访问
/ 0 顶点i到j没有边
| 1 (i,j)为树枝边
EdgeType - 边的类型，EdgeType[i,j]=| 2 (i,j)为反向边
| 3 (i,j)为正向边
\ 4 (i,j)为交叉边
d[u] - 第一次访问顶点u时给u盖上的时间戳
f[u] - 当访问完了以u为根的子树上的所有顶点后给u盖上的时间戳
/ 0 白色，未被访问过的节点标白色
c - 顶点颜色表 c[u] = | -1 灰色，已经被访问过一次的节点标灰色
\ 1 黑色，当该节点的所有后代都被访问过标黑色
p - 顶点的前驱表 p[u] - u在深度优先树中的父节点
b - 顶点的度数表 b[u] - 深度优先树中顶点u的度数
l - 顶点的low值表，
l[u]用来纪录顶点u或u的后代所能追溯到的最早（最先被访问）的祖先节点v的d[v]值
/ d[u] u首次被访问
l[u]= | min(l[u],d[v]) 访问反向边(u,v)时
\ min(l[u],l[s]) u的儿子s的关联边全部被访问时
边的分类方法：
1。树枝：
深度优先森林中的边。如果V是在访问边(u,v)时第一次被发现(此时v是白色的)，那么
(u,v)是一个树枝。在树枝边中，我们称u为v的父母，既作p[v]=u；
2。反向边：
在深度优先树种连接顶点u到他的祖先的那些非树枝边。环也被认为是反向边。显然，
如果第一次访问(u,v)时v为灰色，则(u,v)为反向边。在对图的深度优先搜索中没有发现
反向边，则该图没有回路。
3。正向边
深度优先树中连接顶点u到他的祖先的那些非树枝边。当第一次访问(u,v)时，v为黑色
且d[u]4。交叉边
其它类型的边。他们既可以连接一棵深度优先树中的两个顶点，只要一顶点不是另一
个顶点的祖先，也可以连接分属两棵深度有线数的顶点。当第一次访问(u,v)时，v为黑色
且d[u]>d[v]，则(u,v)为交叉边。
*深度优先搜索的复杂度为 θ(V+E)
*有向图或无向图G的深度优先森林中，节点v是节点u的后裔当且仅当 d[u]*找出有向图的强连通分支的算法：
S1. 调用DFS(G)以计算出每个节点u的完成时刻f[u];
S2. 计算出G的转置G‘，其中G‘是将G的每一条边反向后得到；
S3. 调用DFS(G‘)，但在DFS的主循环里按照f[u]递减的顺序考虑各节点；
S4. 输出S3中产生的深度优先森林中每棵树的节点，作为各自独立的强连通分支。
*根据f[v]从大到小对顶点排序，即得到有向图的拓扑排序；
*在对无向图G进行深度优先搜索时，G只有树枝和反向边两种边。
*若无向图的树枝边(u,v)满足l[v]>d[u]，即从v及其后代不存在一条连接u的祖先的反向边，
则(u,v)为桥；
* 无向图的节点v是割点当且仅当v具备以下条件成立：
若v是深度优先树的根(p[v]=0)，则v的子节点数目超过1；
若v不是深度优先树的根(p[v]>0)，则v存在一个子节点w,满足l[w]>=d[v]。
}
Top
ZhangYv（迎着朝阳,走向地狱）回复于 2003-11-16 20:08:17 得分 0
{==========================================
!!!!IMPORTANT
对于有向图，请把前面有!!!的行删去；
对于权可以为负的图，请修改前面有!!!的行。
============================================}
procedure DFS(var G:adj_matrix;size:integer);
const
white=0;
gray=-1;
black=1;
var
EdgeType:adj_matrix;
d,f,c,p,b,l:array[1..MaxSize] of integer;
u,time:integer;
procedure DFS_visit(u:integer);
var
v:integer;
begin
c[u]:=gray;
inc(time);
d[u]:=time;
l[u]:=time;
for v:=1 to size do
if G[u,v]>0 then {G[u,v]>0表示边(u,v)存在且未被访问，当边(u,v)不存在时G[u,v]=0}
case c[v] of
white: begin
{!!!} {G[u,v]:=-G[u,v]; {设置(u,v)暂时不可访问的标志，对于有向图，请把此行删去}
EdgeType[u,v]:=1; {(u,v)为树枝边}
inc(b[u]); {深度优先树中顶点u的度数加1}
p[v]:=u; {深度优先树中顶点v的父亲是u}
DFS_visit(v); {深度优先搜索顶点v}
if l[v]{!!!} {G[u,v]:=-G[u,v]; {恢复(u,v)可访问，对于有向图，请把此行删去}
end;
gray: begin
EdgeType[u,v]:=2; {(u,v)为反向边}
if d[v]end;
black: begin
if d[v]>d[u] then EdgeType[u,v]:=3 {(u,v)为正向边}
else EdgeType[u,v]:=4; {(u,v)为交叉边}
end;
end; {end of case}
c[u]:=black;
inc(time);
f[u]:=time;
end;
{===============================================
最大流算法
基于Ford-Fulkerson 算法的 Edmonds-Karp 实现
求出以s为源，以t为汇的最大网络流 时间复杂度为O(VE^2)
C为容量网络，如果(u,v)没有边，规定c[u,v]=0;
注意，Flow是一个已经求出的可行流，一般可以取Flow[i,j]=0;
================================================}
procedure Edmonds_Karp(var C:adj_matrix;size:integer;s,t:integer;var Flow:adj_matrix);
var
L:array [1..maxsize,1..2] of integer; {记录标号}
Q:array [1..maxsize] of integer; {队列}
u,v,head,tail:integer;
begin
repeat
fillchar(L,sizeof(L),0); {初始化，所有点标号为0}
L[s,1]:=0;
L[s,2]:=maxint;
head:=0;
tail:=1;
Q[tail]:=s; {s入队}
while (headbegin
inc(head);
u:=Q[head];
for v:=1 to size do
if (Flow[u,v]begin
inc(tail);
Q[tail]:=v;
L[v,2]:=min(C[u,v]-Flow[u,v],L[u,2]); {L[v,2]记录下从s到v的增广路径中最小的可改进流量}
L[v,1]:=u; {L[v,1]记录下从s到v的增广路径中v的前驱}
end;
end; {while}
if L[t,2]>0 then {如果汇点已标号}
begin
v:=t;
u:=L[v,1];
while v<>s do
begin
Flow[u,v]:=Flow[u,v]+L[t,2];
Flow[v,u]:=-Flow[u,v];
v:=u;
u:=L[v,1];
end; {while}
end; {then}
until L[t,2]=0; {直到汇点未标号}
end;
{=================================================
容量有上下界的最大流问题
B为容量下界矩阵；
C为容量上界矩阵；
如果存在可行流，返回值为真
===================================================}
function Max_Flow_With_Limt(var B,C:adj_matrix;size:integer;s,t:integer;var Flow:adj_matrix):boolean;
var
new_c:adj_matrix; {新的容量网络}
i,j:integer;
begin
fillchar(new_c,sizeof(new_c),0);
{构造一个新的容量网络new_c}
for i:=1 to size do {增加一个新汇点size+2}
for j:=1 to size do
new_c[i,size+2]:=new_c[i,size+2]+B[i,j];
for i:=1 to size do {增加一个新源点size+1}
for j:=1 to size do
new_c[size+1,i]:=new_c[size+1,i]+B[j,i];
for i:=1 to size do
for j:=1 to size do
new_c[i,j]:=C[i,j]-B[i,j];
new_c[s,t]:=maxint;
new_c[t,s]:=maxint;
{用Edmonds_Karp算法在新的容量网络中求最大流}
fillchar(flow,sizeof(flow),0);
Edmonds_Karp(new_c,size+2,size+1,size+2,flow);
{检验原容量限制网络是否有可行流}
for i:=1 to size do
if flow[size+1,i]begin
result:=false;
exit;
end;
result:=true;
{将新容量网络中求出的可行流化为原来的容量网络中的可行流}
flow[s,t]:=C[s,t];
flow[t,s]:=-flow[s,t];
for i:=1 to size do
for j:=1 to size do
if flow[i,j]>=0 then
begin
flow[i,j]:=flow[i,j]+B[i,j];
flow[j,i]:=-flow[i,j];
end;
{用Edmonds_Karp将求出的可行流进行放大}
Edmonds_Karp(c,size,s,t,flow);
end;
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
程序效率常用时间复杂度与空间复杂度衡量，现在我把一个递归程序用一个非递归算法实现了（非自己处理栈的那种方法），我想写一个报告说明其效率的提高，但不知道该有什么方法分析比较递归算法与实现相同功能的非递归程的效率才能让人信服。
我没有做软件项目的经验，不知是否有标准的做法?请高人不吝赐教。
分析一下你的非递归算法的复杂度，然后再分析一下递归算法的复杂度，比较一下不就知道了吗
递归算法用空间复杂度分析较合适，而改成的非递归算法用时间复杂度分析较合适。但这两种复杂度怎么放到一起比较呢？
对递归而言，时间主要花费在函数的调用上。其空间复杂度是很大的。非递归的算法的
效率一般比递归要高的多。而非递归算法又要去模似栈就必须要有一个循环。所以时间
复度杂度是比较大的。因此我同意楼上人的说法
递归算法用空间复杂度分析较合适，而改成的非递归算法用时间复杂度分析较合适。
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 这话说得没有道理
你已经说了你的非递归并非自己处理堆栈的方法，一般来说在这种情况下递推算法要比等价的递归算法效率高很多，比如计算斐波拉契数列，如果直接利用F(n+2) =F(n)+F(n+1)递归计算效率很低，但是改成一个循环（也就是递推）效率就高很多了。所以你应该首先分析你的时间复杂度。当然递推的空间效率一般也比递归高，所以你也可以同时推导一下它们的空间复杂度，作个比较。
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
证明题：
投100次硬币，出现的正反面排列组合情况为C(101,100)=C(101,1)=101.
然后得到推论，m个相同的球放进n个相同的盒子(可以一个盒子放多个)的排列组合为
C(m+n-1,m)。
最好不要用累加的方式推导，给出个简单的等价转换就可以得分。
公布答案，有m+n个盒子，有m+n-1个球排满前m+n-1个盒子，最右边的盒子为空现在我要你任意拿走n-1个球.然后有这样一个定义，从左至右，应该有n个空盒子。这n个空盒子分别代表一个分类，它前面的有球盒子的个数为这个分类的球的个数。则共有C(m+n-1,m)个分法Top
ZhangYv（迎着朝阳,走向地狱）回复于 2003-11-16 20:10:39 得分 0
猎人要带一条狼、一只羊和一棵大白菜过河。船太小，一次只能带一样。但猎人不在场的情况下，狼要吃羊，羊要吃白菜。请设计一个C++程序为猎人指出一个安全的渡河放案。
给你一个Pascal编的,自己改吧!
{*
Title : 主人和佣人过河问题
File : MasterAndServant.pas
Author : Arter
Date : 2001/08/04
*}
program MasterAndServant;
uses Dijkstra;
const
MaxNum = 300 ;
type
TStatus = Array [ 1..MaxNum ]
of Record
x : integer;
y : integer;
z : integer;
end ;
var
status : TStatus ;
procedure CreateDataFile;
var
i , j , count: integer ;
deltaX,deltaY :integer;
fin : Text ;
n , k : integer;
begin
write( ‘ 请输入商人数(n) 和 船上的最大装载量 (k) ‘);
readln( n , k );
for i := 1 to n+1 do
begin
status[ i ].x := n;
status[ i ].y := n+1-i;
status[ i ].z := 1;
status[ 3*n+i ].x := n;
status[ 3*n+i ].y := n+1-i;
status[ 3*n+i ].z := 0;
end;
status[ 3*n+1 ].x := 0;
status[ 3*n+1 ].y := 0;
status[ 3*n+1 ].z := 0;
for i := n+2 to 2*n do
begin
status[ i ].x := 2*n+1-i;
status[ i ].y := 2*n+1-i;
status[ i ].z := 1;
status[ 3*n+i ].x := 2*n+1-i;
status[ 3*n+i ].y := 2*n+1-i;
status[ 3*n+i ].z := 0;
end;
for i := 2*n+1 to 3*n do
begin
status[ i ].x := 0;
status[ i ].y := 3*n+1-i;
status[ i ].z := 1;
status[ 3*n+i ].x := 0;
status[ 3*n+i ].y := 3*n+1-i;
status[ 3*n+i ].z := 0;
end;
{write(‘Input created data file name ‘);
readln(inFileName);}
inFileName := ‘temp.dat‘;
assign(fin,inFileName );
rewrite(fin);
writeln( fin , 6*n ) ;
count := 0;
for i := 1 to 3*n do
for j := 3*n+1 to 6*n do
begin
deltaX := status[ i ].x - status[ j ].x ;
deltaY := status[ i ].y - status[ j ].y ;
if ( deltaX + deltaY > 0 )
and ( deltaX + deltaY <= k )
and ( (deltaX >= 0 )
and (deltaY >= 0 )
{ ( deltaX >= deltaY )
or ( deltaX = 0 )
or ( deltaY = 0 ) }
)
then begin
writeln(fin, i,‘ ‘ ,j , ‘ ‘ , 1);
end;
end;
close( fin );
end;
procedure ReadData;
var i , j :Integer ;
begin
{write(‘Input the input data file name: ‘);
readln(inFileName);}
assign(inFile,inFileName);
reset(inFile);
read(inFile,vectexNum);
if (vectexNum < 1) or (vectexNum > MaxVectexNum)
then
begin
writeln(‘The count of vectex is out of range!‘);
exit;
end
else
begin
for i := 1 to vectexNum do vectex[i] := i; { Init vectex[] }
for i := 1 to vectexNum do { Init edge[,] }
for j := 1 to vectexNum do
if i = j then edge[ vectex[i],vectex[j] ] := 0
else edge[ vectex[i],vectex[j] ] := MaxDistance;
repeat
read(inFile,i,j,edge[ vectex[i],vectex[j] ]);
edge[vectex[j],vectex[i]] :=
edge[ vectex[i],vectex[j]]; { No dection graph }
until ( eof(inFile));
close(inFile);
end ;
end ;
procedure PrintPath;
var
outFileName : String ;
outFile : Text ;
i : Integer ;
procedure PrintSinglePath( beginVertexPos : Integer ; endVertexPos : Integer );
begin
if preVectexPos[ endVertexPos ] = beginVertexPos
then
begin
write(outFile,‘[‘,status[beginVertexPos].x,‘,‘);
write(outFile,status[beginVertexPos].y,‘,‘);
write(outFile,status[beginVertexPos].z,‘]‘);
end
else
begin
PrintSinglePath( beginVertexPos , preVectexPos[ endVertexPos ] );
end;
write(outFile,‘-->‘);
write(outFile,‘[‘,status[endVertexPos].x,‘,‘);
write(outFile,status[endVertexPos].y,‘,‘);
write(outFile,status[endVertexPos].z,‘]‘);
end;
{PrintPath}
begin
write(‘ 请输入输出文件名：‘);
readln(outFileName);
assign(outFile,outFileName);
rewrite(outFile);
writeln(outFile,‘Shortest Path By DijkStra ‘);
{for i:= (vectexNum div 2) + 1 to vectexNum do }
for i:= (vectexNum div 2) + 1 to (vectexNum div 2) + 1 do
begin
write(outFile,‘d(‘,vectex[beginVectexPos]:2,‘,‘,vectex[i]:2,‘)=‘);
if dist[vectex[i]] < MaxDistance
then
begin
write(outFile,dist[vectex[i]]:7);
write(outFile,‘‘:2,‘ path: ‘);
PrintSinglePath(beginVectexPos , i);
writeln( outFile );
end
else
begin
write(outFile ,‘ +‘,Chr(236),‘‘:3);
writeln(outFile,‘‘:2,‘ No path ! ‘);
end ;
end;
close(outFile);
end;
begin
About;
CreateDataFile ;
ReadData ;
Dijk;
PrintPath ;
end.
Top
ZhangYv（迎着朝阳,走向地狱）回复于 2003-11-16 20:11:27 得分 0
(接上贴）
{*
Title : Dijksta for Master&Servent
File : Dijkstra.pas
Author : Arter
Date : 2001/08/04
*}
Unit Dijkstra;
{$X+,S-}
{$M 16384,16384,655360}
interface
const
MaxVectexNum = 150;
MaxDistance = 10000;
type
TRange = 1..MaxVectexNum ;
TVectexName = Integer ;
TWeight = Integer ;
TVectex = Array [TRange] of TVectexName ;
TEdge = Array [TRange,TRange] of TWeight;
TDistance = Array [TRange] of TWeight;
TSetOfVectex = Set of TRange;
var
vectex,preVectexPos : TVectex;
dist : TDistance;
edge : TEdge;
setOfVectex : TSetOfVectex;
beginVectexPos : Integer;
vectexNum : Integer;
minDist,distTemp: TWeight;
inFileName , outFileName : String ;
inFile , outFile : Text ;
procedure About;
procedure ReadData;
procedure PrintPath;
procedure Dijk;
implementation
procedure About;
begin
writeln;
writeln(‘{*****************************************}‘);
writeln(‘{* *}‘);
writeln(‘{* Master&Servent by Dijkstra *}‘);
writeln(‘{* Copyright(c) by Arter *}‘);
writeln(‘{* 2001/08/04 *}‘);
writeln(‘{* E-mail:javaart@263.net *}‘);
writeln(‘{* *}‘);
writeln(‘{*****************************************}‘);
end;
procedure ReadData;
var i , j :Integer ;
begin
write(‘Input the input data file name: ‘);
readln(inFileName);
assign(inFile,inFileName);
reset(inFile);
read(inFile,vectexNum);
if (vectexNum < 1) or (vectexNum > MaxVectexNum)
then
begin
writeln(‘The count of vectex is out of range!‘);
exit;
end
else
begin
for i := 1 to vectexNum do vectex[i] := i; { Init vectex[] }
for i := 1 to vectexNum do { Init edge[,] }
for j := 1 to vectexNum do
if i = j then edge[ vectex[i],vectex[j] ] := 0
else edge[ vectex[i],vectex[j] ] := MaxDistance;
repeat
read(inFile,i,j,edge[ vectex[i],vectex[j] ]);
edge[vectex[j],vectex[i]] :=
edge[ vectex[i],vectex[j]]; { No dection graph }
until ( eof(inFile));
close(inFile);
end ;
end ;
procedure PrintPath;
var
i : Integer ;
procedure PrintSinglePath( beginVertexPos : Integer ; endVertexPos : Integer );
begin
if preVectexPos[ endVertexPos ] = beginVertexPos
then
begin
write(outFile,beginVertexPos);
end
else
begin
PrintSinglePath( beginVertexPos , preVectexPos[ endVertexPos ] );
end;
write(outFile,‘-->‘);
write(outFile,endVertexPos);
end;
{PrintPath}
begin
write(‘Input the output data file name:‘);
readln(outFileName);
assign(outFile,outFileName);
rewrite(outFile);
writeln(outFile,‘Shortest Path By DijkStra ‘);
for i:= 1 to vectexNum do
begin
write(outFile,‘d(‘,vectex[beginVectexPos]:2,‘,‘,vectex[i]:2,‘)=‘);
if dist[vectex[i]] < MaxDistance
then
begin
write(outFile,dist[vectex[i]]:7);
write(outFile,‘‘:2,‘ path: ‘);
PrintSinglePath(beginVectexPos , i);
writeln( outFile );
end
else
begin
write(outFile ,‘ +‘,Chr(236),‘‘:3);
writeln(outFile,‘‘:2,‘ No path ! ‘);
end ;
end;
close(outFile);
end;
procedure Dijk;
var
i , j , nextI : Integer;
count : Integer ;
begin
{write(‘Input the begin vectex postion:‘);
readln(beginVectexPos);}
beginVectexPos := 1;
setOfVectex := [];
for i:=1 to vectexNum do
begin
setOfVectex := setOfVectex+[ vectex[i] ];
dist[vectex[i]] := edge[ vectex[i],vectex[beginVectexPos] ];
preVectexPos[i] := beginVectexPos;
end;
i := beginVectexPos;
count := 1;
setOfVectex:= setOfVectex-[ vectex[i] ];
repeat
minDist := MaxDistance;
for j := 1 to vectexNum do
begin
if vectex[j] in setOfVectex
then
begin
distTemp := dist[vectex[i]]+edge[vectex[i],vectex[j]];
if( (dist[vectex[j]] > distTemp ))
and ( edge[vectex[i],vectex[j]] < MaxDistance )
then
begin
dist[vectex[j]] := distTemp;
preVectexPos[j] := i;
end;
if (dist[vectex[j]]>0) and (dist[vectex[j]]begin
minDist := dist[vectex[j]];
nextI := j;
end;
end;
end;
if minDist<>MaxDistance then dist[vectex[nexti]] := minDist;
i := nextI;
inc( count );
setOfVectex := setOfVectex-[vectex[i]];
until ( count = vectexNum ) ;
end;
end.
Top
ZhangYv（迎着朝阳,走向地狱）回复于 2003-11-16 20:17:10 得分 0
两个自然数可以用一个自然数来表示，谁知道么？
书上说一对自然书a和b，可以用自然书((a+b)^2+3a+b)/2来表示，我试了试，好像是这样，可是怎么才能翻过来求出a和b呢？
即假如某人用这种办法把两个数变成一个数，我怎么通过这个书回到原来的两个数？
是这样的。若a=b，则变成一元二次方程很简单的就能解决（2a^2+2a-z=0,参数z即已知的那个数，下同）；否则：可以设a=(x+y)/2 b=(x-y)/2.(x,y是自然数,且x>y.即任何二个自然数均可表示二个自然数的这种形式，道理很明显吧。）。代入你的那个算式得：(x+1)^2=(2*z+1)-y
观察这个式子，可以做个循环：即对x from i(i是（2*z+1）的2次正根向下取整) to i-1 逐个验证。
令a+b=x1，3a+b=x2,联立得a=(x2-x1)/2,b=(3*x1-x2)/2,x1和x2要么都为奇数要么都为偶数，且x1抛砖引玉
(a+b)^2/2+(a-b)/2+(a+b)=n
x^2+y+2*x=2*n
(x+1)^2=2*n+1-y
此题不需要穷举，只需一些数学运算即可：
begin
令x=a+b，y=a-b，(x，y为整数)；
原式可化为：(x+1)^2=2*n+1-y，n为要转化的自然数；
令p=(2*n+1)开方向上取整；
if p^2-(2*n+1)<=p-1 then { x=p-1；y=(2*n+1)-p^2；}
else { x=p-2；y=(2*n+1)-(p-1)^2；}
a=(x+y)/2；b=(x-y)/2；
end；
提示：a，b为自然数则|a+b|>=|a-b|；
证明略。
---------------------------------------------------------------------------
请详细介绍贪心算法
贪心算法
1．概念
贪心算法是从问题的某一个初始解出发逐步逼近给定的目标，以
尽可能快地求得更好的解。当达到某算法中的某一步不能再继续
前进时，算法停止。这时就得到了问题的一个解，但不能保证求
得的最后解是最优的。在改进算法中，贪心算法演化为爬山法。
2．特点及使用范围
贪心算法的优点在于时间复杂度极底。贪心算法与其他最优化算
法的区别在于：它具有不可后撤性，可以有后效性，一般情况下
不满足最优化原理。贪心算法的特点就决定了它的适用范围，他
一般不适用于解决可行性问题，仅适用于较容易得到可行解的最
优性问题。这里较容易得到可行解的概念是：当前的策略选择後，
不会或极少使后面出现无解的情况。另外，对于近年来出现的交
互性题目，贪心算法是一个较好的选择。这是因为，在题目中，
一个策略的结果是随题目的进行而逐渐给出的，我们无法预先知
道所选策略的结果，这与贪心算法不考虑策略的结果和其具有后
效性的特点是不谋而合的。当然，贪心算法还可以为搜索算法提
供较优的初始界值。
-------------------------------------------------------------------
有一张M*N的矩形纸，要求裁出K[i]个A[i]*B[i]的小矩形，其中i = 1,2,...t， 问能否办到？是不是这样的题目呀？
这个题目似乎是个NP问题，可能根本没有多项式的解法。
m*n的棋盘的p*q矩形完全覆盖的充要条件
我先研究了大矩形可以被小矩形完全覆盖（不留空隙）的充要条件。先用数学语言定义几个概念：
m*n的棋盘是指由m行n列方格构成的棋盘。
所谓棋盘的覆盖，是指用若干个相同的图形去覆盖m*n的棋盘，覆盖棋盘的每个图形也由若干个方格组成，称之为覆盖形。在棋盘的覆盖中，约定任意两个覆盖形互不相重叠，且任意一个覆盖形的任何一个方格与棋盘的某个方格重合。
下面先研究简单的情况，当p=1,q=k的情况。
定理一：
m*n的棋盘存在1*k矩形的完全覆盖的充要条件是k|m或者k|n。 （其中a|b表示a整除b）
证：充分性显然。下面证明必要性。
假设m*n的棋盘存在1*k矩形的完全覆盖。在m*n棋盘的各个格中填数：第一列的格从上至下依次填1,2,..m，此外，对于其中的任何一行，所填的各数从左至右构成公差为1的等差数列。这样，每一个1*k矩形在棋盘的覆盖中所盖住的格所填的数字恰好构成模k的一个完系（如果一个整数集中的每一个数模k得到的集合是{0,1,...,(k-1)}，则称该集合为模k的完系）。因为m*n的棋盘存在1*k矩形的完全覆盖，所以m*n的棋盘中所填的数字中属于模k的不同剩余类的数的个数相等，也就是说，m*n的棋盘上所填的数字中，所有模k得到0的数字的个数=所有模k得到1的数字的个数=...=所有模k得到k-1的数字的个数。
设m=pk+s,n=qk+t，假设s*t<>0，则不妨设0+---------+------------+
| | |
| s*t | s*pk |
| | |
+---------+------------+
| |
| pk*n |
| |
+----------------------+
显然，pk*n的矩形和s*pk的矩形可被1*k矩形完全覆盖（由充分性知），所以这两个矩形中属于模k的不同剩余类中的数的个数相等，从而s*t的矩形中属于模k的不同剩余类中的数的个数也应该相等。考察s*t的矩形中所填的数字：
1 2 3 .... t-1 t
2 3 4 .... t t+1
............................
s-1 s s+1 .... s+t-3 s+t-2
s s+1 s+2 .... s+t-2 s+t-1
将上述的数表作如下改造：对于表中的每一个数a，如果a>k，则将a换作a-k，这并不改变该数模k的余，这样得到一个新的数表，记作A。考察数t与t+1在表A中出现的次数。观察上图可以注意到每一条从右上方到左下方的对角线上的数字都相同，我们从左到右给这些对角线标号。显然，在前t条对角线上不出现t+1。又s+t-1t+1)条对角线上也不出现t+1。所以t+1只出现在第t+1条对角线上，即t+1共出现了s-1次。注意到第t条对角线上的数都为t，所以t在表A中至少出现s次。于是t出现的次数多于t+1出现的次数。易知表A中模k余(t mod k)的数只有t，模k余((t+1) mod k)的数只有t+1，所以A中模k余(t mod k)的数的个数不等于模k余((t+1) mod k)的数，即原来的s*t矩形中属于模k的不同剩余类中的数的个数不相等，矛盾。
所以s*t<>0不成立，即s*t=0。必要性得证。
下面利用定理一将结论扩展到m*n的棋盘的p*q矩形完全覆盖。
定理二：m*n的棋盘的p*q矩形完全覆盖的充要条件是m,n满足下列条件之一：
(i) p|x且q|y
(ii)p|x,q|x且存在自然数a,b，使y=ap+bq
其中{x,y}={m,n}
证：充分性：
若条件(i)满足，不妨设x=m，y=n，令m=ps,n=qt,则m*n的棋盘可以划分为s*t个p*q矩形，结论成立；若条件(ii)满足，不妨设x=m,y=n，即p|m,q|m,且存在自然数a,b使得n=ap+bq。那么，将m*n的棋盘划分为两个棋盘：一个m*ap棋盘，一个m*bq棋盘，这两个棋盘均可以被p*q矩形完全覆盖，所以结论成立。
必要性：
设m*n的棋盘可被p*q矩形完全覆盖，从而m*n棋盘存在1*p矩形的完全覆盖，由定理一知p|m或p|n，同理q|m或q|n，这有以下两种情况：
(1)p,q可以分别整除m,n中的各一个，即有p|x,q|y且{x,y}={m,n}，则结论成立；
(2)p,q只能同时整除m,n中的同一个，不妨设p|m,q|m，且p\n,q\n(用符号a\b表示a不整除b)。考察至少盖住第一行中一个格的那些覆盖形，设其中以"p*q"方式覆盖的矩形有b块，以"q*p"方式覆盖的矩形有a块，再注意到第一行共有n个格，所以n=ap+bq，结论成立。
必要性得证。
根据上面定理很容易求出一个m*n的棋盘最多可被多少个p*q的矩形覆盖，
我以前写了个程序的，但是找不到了。目前只找到这么多东西了：（
拿到此问题的思路
此问题很复杂。设大矩形为m*n,小矩形为p*q，即使不考虑小矩形斜放的问题，如果m,n,p,q不是整数（或者不能化为整数），此问题还是没有好办法解决。此问题称为m*n棋盘的p*q骨牌饱和覆盖问题，用纯粹的数学方法解决很麻烦，而且对m,n,p,q都有一定的限制，完全无限制的情况还未求出解来。我现在正在努力求出其上下界，有了成果会贴出来的。
如果考虑用计算机来做，就只能采用搜索法。这里关键的难点在于如何在当前的状态下生成新的子状态。
下面的叙述中称m*n的大矩形为棋盘，p*q的小矩形为骨牌。规定骨牌不能旋转，只能横放或竖放。注意：这里用计算机搜索骨牌的覆盖，可以不必限制m,n,p,q都为整数。
定理一：
一定存在一种最优的布局，使得每一块骨牌至少有两条边与其他骨牌的边或者棋盘的边相邻。
证明：这时显然的，如果某种最优的布局中有一块骨牌至少有三条边与其他边有空隙，可以将该骨牌平移，使得该骨牌至少有两条边与其他骨牌的边或者棋盘的边相邻，这样还是得到一个最优覆盖方案。
定理二：
一定存在一种最优布局，使得棋盘的某个角的顶点被骨牌覆盖。
这也是显然的。
下面可以根据这两个定理设计一个生成新结点的方法。
1。首先检查棋盘是否可以被骨牌完全覆盖，检查方法我已经在上一张贴子中给出了。
2。初始状态棋盘为空；
3。取棋盘的左上角，放第一张骨牌，使骨牌的一个顶点与棋盘的角的顶点重和。第一张骨牌有横放和竖放两种情况，因此得到两个初始状态的子结点；
4。对于当前的状态，已经放置的骨牌的围成一个多边形（其中可能有空隙），该多边形的边和棋盘的边又将棋盘中的空地围成一个多边形，下面只要在这个多边形内部贴着边放置一个骨牌就可以了。
其实完全没必要考虑得那么复杂。
我去年作了一个排料方面的模块，也是要求在大的矩形板上裁减出足够多的小矩形板。我采用的是近似穷举的办法。速度很快，效果很好。作为商业软件已运行了一年多。
提醒各位一句：作软件最重要的是能实现功能，而不是沉迷于使用的多少技巧，多少高深的理论。
Top
ZhangYv（迎着朝阳,走向地狱）回复于 2003-11-16 20:19:34 得分 0
什么是优先队列？
怎么用“数组实现的二叉树”来实现优先队列？
希望得到具体回答
下面是数组实现的二叉堆，其中MAX_SIZE是数组的最大长度；ElementType是其中元素的类型；Priority(x: ElementType) 是一个函数，返回值是元素x的优先级，当然也可以用一个Priority数组来保存每个元素的优先级(在这个打字员问题中就应该用一个数组来保存每个元素的优先级，在这个问题中优先级就是从初始密码转换到该密码所需的操作的数目)。
type
PriorityQueue = record
contents: array [1..MAX_SIZE]of ElementType;
last : integer;
end;
{ 将一个优先队列变空 }
procedure MakeNull(var A: PriorityQueue);
begin
A.last := 0;
end;
{ 向优先队列A中插入一个元素x }
procedure Insert(x: ElementType; var A: PriorityQueue);
var
i: integer;
temp:ElementType;
begin
if A.last = MAX_SIZE then
Error(‘Priority Queue is full.‘)
else begin
A.last := A.last + 1;
A.contents[A.last] := x;
i := A.last;
while (i > 1) and ( Priority(A.contents[i]) < Priority(A.contents[i div 2]) do
begin
temp := A.contents[i];
A.contents[i] := A.contents[i div 2];
A.contents[i div 2] := temp;
i := i div 2;
end; { end of while }
end; { end of else }
end; { end of Insert }
{ 删除优先队列对头的那个优先级最小的元素，并将其值返回 }
function DeleteMin(var A: PriorityQueue): ElementType;
var
minimun : ElementType;
i : integer;
begin
if A.last = 0 then
Error(‘Priority Queue is empty. ‘)
else begin
minimun := A.contents[1];
A.contents[1] := A.contents[A.last];
A.last := A.last - 1;
i := 1;
while i < (A.last div 2) do
begin
if (Priority(A.contents[2*i]) < Priority(A.contents[2*i+1])) or (2*i = A.last)
then j := 2*i;
else j := 2*i + 1;
{ j节点是i节点具有较高优先级的儿子，当i节点只有一个儿子的时候，j节点是i节点的唯一儿子 }
if Priority(A.contents[i]) > Priority(A.contents[j]) then
begin
temp := A.contents[i];
A.contents[i] := A.contents[j];
A.contents[j] := temp;
i := j;
end
else begin { 不能再向下推了 }
DeleteMin := minimum;
exit;
end;
end; { end of while }
{ 这时已经到达叶结点 }
DeleteMin := minimum;
exit;
end; { end of else }
end; { end of DeleteMin }
优先队列插入和删除元素的复杂度都是O(lgn)，所以很快。
在计算机算法的书中，所有的log,lg只要没有说明，都是以2为底的；在数学书中lg是指以10为底的对数。每本算法书中的记号不同，有的喜欢用lg，有的喜欢用log，其实没有区别，都是以2为底的；另外，就算是以10为底的对数，和以2为底的对数没有渐进阶的差别，因为根据对数公式： log(a,b) = log(c,b) /log(c,a)， （这里log(a,b)是指以a为底的对数），所以无论以什么为底，只相差一个常数的倍数。
优先队列用C++描述如下
#define MAX_SIZE 100
typedef int ElementType; // 定义元素的类型，这里假设是int类型
struct PriorityQueue { // 定义优先队列
ElementType contents[MAX_SIZE];
int size;
};
int P[MAX_SIZE];
// 返回元素x的优先函数值，这个值越小说明优先级越高
int Priority(const ElementType& x)
{
return P[x]; // 实际应用中通常用数组P来存储每个元素的优先级，
// 但是实际上也可以用其他方法（比如通过公式）计算出优先级
}
// 将一个优先队列变空
void MakeNull(PriorityQueue& Q)
{
Q.size = 0;
}
// 向优先队列Q中插入一个元素x
void Insert(const ElementType& x, PriorityQueue& Q)
{
int i;
ElementType temp;
if (Q.size == MAX_SIZE) {
throw "Priority Queue is full.";
} else {
Q.contents[Q.size++] = x;
i = Q.size - 1; // 从最后一个元素开始
while( ( i > 0 ) && ( Priority( Q.contents[i] ) < Priority( Q.contents[(i-1)/2] ) ) )
{
temp = Q.contents[i];
Q.contents[i] = Q.contents[(i-1)/2];
Q.contents[(i-1)/2] = temp;
i = (i-1) / 2;
}
}
}
// 删除优先队列对头的那个优先函数值最小的元素，并将其值返回
ElementType DeleteMin(PriorityQueue& Q)
{
ElementType result;
int i, j;
if (Q.size == 0) {
throw "PriorityQueue& Q";
} else {
result = Q.contents[0];
Q.contents[0] = Q.contents[Q.size - 1];
Q.size--;
i = 0;
while (2*i + 1 < Q.size) {
// 节点i的左右儿子分别是2i+1和2i+2
if( (2*i+1 == Q.size-1) ||
( Priority(Q.contents[2*i+1]) < Priority(Q.contents[2*i+2]) ) )
{
j = 2*i + 1;
} else {
j = 2*i + 2;
}
// j节点是i节点具有较小优先函数值的儿子，当i节点只有一个儿子的时候，j节点是i节点的唯一儿子
if( Priority(Q.contents[i]) > Priority(Q.contents[j]) ) {
temp = Q.contents[i];
Q.contents[i] = Q.contents[j];
Q.contents[j] = temp;
i = j;
} else {
return result;
}
}
return result;
}
}
Top
ZhangYv（迎着朝阳,走向地狱）回复于 2003-11-16 20:30:52 得分 0
如何算不规则多边形的面积?
1.把（xi,yi)按逆时针排好。(i=1,2,3,....n, x(n+1)=x1);
2.计算它的有向面积:
(1)先看:(0,0),(xj,yj),(xk,yk)三点的面积S=
¦ 0 0 1 ¦
¦ xj yj 1 ¦*(1/2) =(xj*yk-yj*xk)/2
¦ xk yk 1 ¦
(2)多边形面积可以划分为三角形面积的和:
S[（0，0），（x1,y1),(x2,y2)]+S[（0，0），（x2,y2),(x3,y3)]+...
+ S[（0，0），（x(n-1),y(n-1),(xn,yn)]+S[（0，0），（xn,yn),(x1,y1)]
=((x1*y2-x2*y1)+(x2*y3-x3*y2)+...+(x(n-1)*yn-xn*y(n-1))+(xn*y1-x1*yn))/2
=(x1*(y2-yn)+x2*(y3-y1)+x3*(y4-y2)+...+x(n-1)*（yn-y(n-2))+xn*(y1-y(n-1)))/2
（或：(y1*(xn-x2)+y2*(x1-x3)+y3*(x2-x4)+...+y(n-1)*(x(n-2)-xn)+yn*(x(n-1)-
x1))/2 )
/******************************************** * *
* 计算多边形的面积 *
* *
* 要求按照逆时针方向输入多边形顶点 *
* 可以是凸多边形或凹多边形 *
* *
\********************************************/
float area_of_polygon(int vcount,float x[],float y[])
{
int i;
float s;
if (vcount<3) return 0;
s=y[0]*(x[vcount-1]-x[1]);
for (i=1;is+=y[i]*(x[(i-1)]-x[(i+1)%vcount]);
return s/2;
}
----------------------------------------------------------------------
Top
ZhangYv（迎着朝阳,走向地狱）回复于 2003-11-16 20:32:38 得分 0
===========================================================
问题：
在RPG游戏中精灵要从A走到B，其中有若干的障碍物，如何寻找最短路径？注意这里的地图是以像素为单位，而不是划分格子的（传统的日式RPG是划格子法，那要简单得多）
==============================================================
这个问题是计算几何学中的一个经典课题：算法的运动规划问题。
计算几何中的一些研究问题来源于机器人学领域，这些问题称为运动规划或者更准确地称为算法的运动规划。假设二维和三维空间中存在多个障碍物，这些障碍物呈多边形或者多面体。另外，一个可运动的物体从空间中的点s移动到另一点t，运动的物体碰到障碍物时必须绕过它。这里可以提出许多问题，例如，求从s至t的最短路径；运动物体的形状是点、一条线段、一个凸多边形、一个圆或者任意多边形，求从s至t的路径等等。物体在运动过程中，要避免与所有障碍物的碰撞，也就是说，物体边缘上的任一点a与障碍物的一个内点重合时，就发生碰撞；点a沿障碍物边界的滑动是允许的。没有碰撞的路径称为自由路径。这个课题主要讨论以下三类问题:
(l)判定问题:运动物体(即机器人)R能够从s移动到t吗？即从s至t是否存在一条自由路径。
(2)构造路径:寻找机器人R从s移动到t的一条自由路径。
(3)最短路径:寻找机器人R从s移动到t的一条最短自由路径。
另外，当R具有不同几何外形时，可以再次提出上述三个问题。问题(1)比问题(2)容易(可以举出例子来说明这一点)，而问题(2)又比问题(3)简单。问题(3)中“最短”的含义，一般是指自由路径长度最短。但进一步研究发现“最短”与R的外形也存在一定关系，如果R是一个圆，那么“最短”的含义是清楚的；而R是一条可以旋转的线段时，理解“最短”的含义就不那么简单了，这时先给出几个不同的定义，在此定义下求最短路径。
根据你的问题的实际情况，下面仅讨论平面中最短路径问题的几种情况：
1。机器人是一个点；
2。机器人是一个圆盘；
3。机器人是一个多凸边形；
其他的情况（机器人是线、任意多边形，杆状、机器人臂，etc）都比较复杂，好在上面的三种情况对于一般的平面RPG游戏已经足够了。
下面的讨论中假设障碍物是多个离散的多边形，而且多边形顶点总数为n，给定起点s和终点t，s和t不在任一障碍物多边形内部（如果起点终点在障碍物内部直接可以进行判断，判断一个点是否在多边形内的算法很简单），问题是寻求s和t之间的最短路径。解决这个问题的一种方法，其思路是先求可视图，然后由可视图寻找最短路径。
（一）移动点：
先讨论两个基本问题
a. 可视图及其构造
一组多边形的可视图G=(V，E)，其中结点v∈V对应于多边形的顶点，边e∈E对应于可以互相“看见”的顶点对(u,v)。注意，边e可能与多边形边重叠，这样多边形的边也在可视图中。
从s至t的最短路径是由线段组成的一条折线，折线的两端点或者是s、t，或者是多边形的顶点，也就是说，多边形的顶点可以取为起点和终点。这样，最短路径可以看成是障碍多边形顶点的序列，或者最短路径是由可视图中边组成的序列。基于这个观察，有下面的结论：
定理1
最短路径是障碍多边形顶点可视图的一条子路径。
下面分三步证明该定理的正确性:
(1)路径是折线的。假设相反，即路径不是折线的，该路径包含弯曲部分C。这样，不可能是C的所有部分都沿着多边形边界，因为多边形边界不是弯曲的，因此，必定有一个不与任何多边形相接触并且可以用直线段代替的C的凸子部分，这与路径是最短的假设相矛盾。
(2)路径的拐弯点是多边形的顶点：自由空间中的任何拐弯可以抄近路。
(3)路径的线段是可视图的边：由可视的定义以及构成自由路径的定义可以推出。
由于可视图是有穷的，依据定理1，从s至t的最短路径必由一有穷路径集合中可以搜索得到。但该路径集合可以表示为多级多叉树结构，因此路径的数目可能以n的指数增长。为了获得有效的最短路径算法，先考虑可视图的构造。
构造一组多边形可视图的边几乎与寻找多边形对角线相同，唯一差别是：多个多边形与一个多边形，外部可视与内部可视。一种算法是对于不同多边形的每个顶点对p(k,i)和p(k+1,j)，检查线段是否与多边形边相交，如果都不相交，则线段是可视图的一条边；否则，就不是可视图的边。由于顶点对数目可以达到0(n^2)，而多边形边数为O(n)，所以该算法的复杂性为O(n^3)。另外，可视图边的数目为0(n^2)，因此，0(n^2)是寻找可视图的任意算法的一个下界。利用预先确定线段排列排列的方法可以导致一个最佳算法，时间复杂性为0(n^2)。经过长期的研究之后，Ghosh和Mount找到了一个关于输出规模敏感的算法(参考论文[1])，复杂性是O(nlogn+|E|)，当然，|E|=O(n^2)，但是多数情况下，|E|比n^2小得多。
[1] Ghost S K, Mount D M. An output sensitive algorithm for computing visibility graphs, Proc. of Comput., 1991, 20(5):888~910
b. Dijkstra算法
假设已构造出一组多边形的可视图，在该图中如何寻找出一条最短路径，这是图论中的问题：寻找加权图中的最短路径。加权是指边的长度，在这里我们用欧几里德距离度量边的长度（当然在RPG游戏中每条路径的权可以考虑地形，可移动力等因素）。解决这个问题的一个经典算法是Dijkstra算法单源最短路径算法，这个算法大家都很熟悉了，我就不再介绍了。
至此我们得出机器人是一个点的情况下最短路径算法：
S1。构造可视图；
S2。用Dijkstra算法求s到t的最短路径；
由于已假设多边形组有n个顶点，因此图G有n个结点，并且至多有C(n,2)条边。Dijkstra算法每循环一次，处理1个结点，向已经标号的最短路径集合T中加入1条边，所以Dijkstra算法至多需要循环n次。每次循环中要检验的候选边的数目大约是0(n^2)，因为可视图可能有平方阶条边。这样，粗略分析Dijkstra算法的时间复杂性是0(n^3)。如果注意到每次循环中不必重新检验这些边，那么在0(n^2)时间内可以运行Dijkstra算法，加之可视图的构造需要 0(n^2)时间，故而有下面的定理。
定理2
在有n个顶点的多边形组中移动一个点，其最短路径可以在0(n^2)时间和空间内找到。
（二）移动圆盘
下面讨论的运动规划的算法，目的是寻找任意路径(如果一条路径存在的话)，而不是最短路径。
假设机器人R是一个中心在s，半径为ρ的圆盘，移动R一段距离之后，使R的中心位于t并且R不穿透任意障碍物。仍设障碍物是分离的多边形。如果机器人太宽，可能不能通过所指示的通道。下面的方法用于判定圆盘机器人R能否通过指定通道是非常有效的：设圆盘R的中心为r那么r不能离任意特定多边形P太近，也就是说，圆盘R在移动的过程中不可能移动到距P边的距离小于圆盘半径ρ的位置。这样，我们考虑一个扩展的障碍物P‘（P向外扩充距离ρ）以便移动点r，即将机器人R收缩成一个点，并且把障碍物向外扩充ρ。因此，上述问题化为（一）中移动点的问题。
圆盘环绕P的边界移动时，圆盘中心r留下的轨迹便是P‘的边界。如果r位于P‘的外部，那么R与P不相交；否则就相交。显然，障碍物增大之后如果通道重叠，则R无法通过所指示的路径。以上描述P‘的方式不清晰，使用两个点集的闵可夫斯基(Minkowski)和的概念来描述P‘将更明确。
给定平面上两个点集S1和S2，如果在平面上建立一个坐标系，那么便可以把点看成该坐标系中的矢量。定义S1与S2的和：
S1+S2={x+y|x∈S1, y∈S2}，
其中x+y是点x和点y的矢量和，这称为S1和S2的闵可夫斯基和。另外，点x与集合S2的闵可夫斯基和为x+S2={x+y|y∈S2}，因此，对于每个x∈S1,S1+S2 = ∪(x+S2），for each x∈S1， 是S2的复制的并。如果对数字图像处理中的形态学有印象的话可以发现，闵可夫斯基和与形态学中的扩张运算很相近。
现设S1是一个多边形P,并且S2是中心在原点的圆盘R，那么对于所有x∈P，可以把P+R看成是依据x转换的R的复制。由于R的中心在原点，x+R的中心将在x，因此P+R相当于放置中心在P的每个点之上的R的复制，故P+R是P的扩展域P‘。
给定一组离散的多边形和半径为ρ的一个圆盘，圆盘R的中心r放在始点s上，t为终点，寻找由s至t的一条路径，使得圆盘R沿该路径从s可以移动到t(即中心r落在t上)。下面叙述解决该问题的一种算法的粗略步骤。
寻找圆盘R从s移动到t的路径的算法：Top
ZhangYv（迎着朝阳,走向地狱）回复于 2003-11-16 20:35:36 得分 0
S1. 利用阂科夫斯基和及圆盘R扩大每个障碍物。
S2. 构造已扩大障碍物的并。
S3. 如果终点t与始点s位于平面上相同的部分之中，则由s至t有一条路径存在，并且通过改进可视图使之包含圆的弧可以找到最短路径；否则，s与t之间不存在路径。
这个算法的时间复杂性为0(n^2*logn)。
（三） 平移凸多边形
当机器人R是一个凸多边形时，机器人可以采取旋转的运动方式从一个位置移到另一个位置，但这里将将机器人的运动方式限制为平移。显然，凸多边形比圆盘复杂些，但利用闵可夫斯基和扩展障碍物的思想仍然有效。
在R是一个圆盘的情况下，P‘=P+R，其中"+"是闵可夫斯基和，但这个关系式在R是凸多边形的情况下不成立，这点可以举例证明（这里没法显示图形，证明略）
。这里的计算是要通过参考点r(可取凸多边形的某个固定的顶点)用R的反射取P的闵可夫斯基和。因为对于闵可夫斯基和形式来说r是原点，R的这种反射形式只不过是-R，即求反R的每个点。因此P‘‘是P+(-R)=P-R。而圆盘关于其圆心是中心对称的，R=-R，因此这个新的闵可夫斯基和形式与上讨论圆盘移动的时候的闵可夫斯基和表示是一致的。因为闵可夫斯基减法就是反射域的加法，我们仍将称它为闵可夫斯基加法。
定理3
设R是包含原点(参考点)的一个域(机器人)，而P是一个障碍物，那么在下述意义下r不可能穿透域P‘=P-R：
(1)如果平移R使得r进入P‘的内部，那么R穿透P。
(2)如果平移R使得r位于δ(P‘)上，则δ(R)与δ(P)相切，其中δ(X)表示X的边界；
(3)如果平移R使得r在P‘的外部，则R∩P=Φ。
实际上，R和P可以不是凸的，也不必是多边形。但这里的讨论仍设两者是多边形，并且R是凸的。
关于构造两个多边形的闵可夫斯基和的算法，可以参考相关的数学资料（或者计算机形态学的资料），这里不作详细介绍（不用图示很难说清楚）。
下面直接给出定理4作为结论：
定理4
如果P有n个顶点，而R的顶点数是一个常数；那么构造闵可夫斯基和P-R的时间复杂性如下:
┌──┬──┬────┬──────┐
│..R.│.P..│和的规模│.时间复杂度.│
├──┼──┼────┼──────┤
│.凸.│.凸.│..O(n)..│..O(n)......│
├──┼──┼────┼──────┤
│.凸.│非凸│..O(n)..│O(n^2*logn).│
├──┼──┼────┼──────┤
│非凸│非凸│..O(n^2)│O(n^2*logn).│
└──┴──┴────┴──────┘
下面给出凸多边形R规划运动的算法概要。设障碍物P1,P2,...Pm，共有n个顶点，算法描述如下：
S1. 增大所有的障碍物: Pi‘= Pi-R, i=1,2,..m；
S2. 构造它们的并P‘=∪Pi‘, i=1,2,...m；
S3. 寻找包含s和t的连通域，设为k；
S4. 在k中寻找s和t之间的一条路径（先建立可视图，然后用Dijkstra算法）。
定理5
设多边形障碍物顶点总数为n，机器人R为凸多边形，寻找R由起点s到终点t的平移路径在O(nlogn)时间内可以完成。如果R有k个顶点，则时间复杂性是O(knlog(kn))。
该定理由Kedem和Sharir(1990)证明，见参考论文[2]。
[2] Kedem K, Sharir M. An efficient motion planning algorithm for a convex rigid polygons object in 2-dimensional polygonal space. Disc. Comp. Geom. 1990,(5):43~75
==============================================================================
以上都是先前“数据算法版”的旧贴，不知为何后来这些好东东都没了，我把它们都整理出来了。很幸运的，我看见了以前聚集着世界级IOer的算法版，水平之高另我辈恐惧,敬佩～
唉唉，路漫漫，其修远兮...
最小生成树Prim 算法
基本思想：
T为最小生成树的边集；
U为一个顶点集
V为图的顶点集
图的顶点标号为1..n
procedure Prim;
begin
T:=Φ；
U:={1};
while U<>V do
begin
(u,v):= u∈U且v∈V-U的最小权边;
T:=T∪{(u,v)};
U:=U∪{v};
end;
end;
======================}
procedure Prim(var G:adj_matrix;size:integer);{G为图，size为图的节点数目;注意：假设输入的图是连通图}
var
lowcost:array [1..maxsize] of integer;
used:array [1..maxsize] of boolean;
closeset:array[1..maxsize] of integer;
i,j,k,min:integer;
begin
for i:=2 to size do {初始化，此时U只含有顶点1}
begin
lowcost[i]:= G[1,i];
closeset[i]:=1;
used[i]:=false;
end;
used[1]:=true;
for i:=2 to size do
begin
min:=maxint;
j:=i;
for k:=2 to size do {用选择法寻找顶点分别在V-U与U中权最小的边}
if (not used[k])and(lowcost[k]
min:=lowcost[k];
j:=k;
end;
writeln(fout,‘(‘,closeset[j],‘,‘,j,‘)‘); {输出找到的最小生成树的一条边，此处可根据情况修改}
used[j]:=true; {将j填加到U}
for k:=2 to size do {调整lowcost和closeset}
if (not used[k])and(G[j,k]
lowcost[k]:=G[j,k];
closeset[k]:=j;
end;
end;
end;
{==========================================
每对节点间最短路径
Flod-Warshall 算法
===========================================}
procedure Flod_Warshall(var G:adj_matrix;size:integer;var D,P:adj_matrix);
{D[i,j]表示从i到j的最短距离；P[i,j]表示从i到j的最短路径上j 的父节点}
var
i,j,k:integer;
begin
{初始化}
for i:=1 to size do {这里假设i,j不相邻时G[i,j]=∞。注意：为了防止溢出，无穷大不能取maxint，可以取maxint div 2}
for j:=1 to size do
begin
D[i,j]:=G[i,j];
P[i,j]:=i; {P[i,j]=0表示不存在从i到j的路径}
end;
for i:=1 to size do
begin
D[i,i]:=0;
P[i,i]:=0;
end;
for k:=1 to size do {进行size次迭代}
for i:=1 to size do
for j:=1 to size do
if (d[i,j]>d[i,k]+d[k,j]) then
begin
d[i,j]:=d[i,k]+d[k,j];
p[i,j]:=p[k,j];
end;
end;
{==========================================
求有向图的传递闭包
G[i,j]=1表示i,j相邻；G[i,j]=0表示i,j不相邻
===========================================}
procedure Transtive_Closure(var G:adj_matrix;size:integer;var T:TranstiveClosureType);
var
i,j,k:integer;
begin
for i:=1 to size do
for j:=1 to size do
if G[i,j]<>0 then //若i与j不相邻则G[i,j]=0，此处可根据情况修改
T[i,j]:=true;
for i:=1 to size do T[i,i]:=true;
for k:=1 to size do
for i:=1 to size do
for j:=1 to size do
T[i,j]:=T[i,j] or (T[i,k] and T[k,j]);
end;
{======================================================================
深度优先搜索，找出关于图的结构的信息
存储结构信息的变量说明如下：
/ =0 顶点i到顶点j无边
G-邻接矩阵表示的图，g[i,j]= -| >0 边(i,j)存在且允许访问
\ <0 边(i,j)存在但不允许访问
/ 0 顶点i到j没有边
| 1 (i,j)为树枝边
EdgeType - 边的类型，EdgeType[i,j]=| 2 (i,j)为反向边
| 3 (i,j)为正向边
\ 4 (i,j)为交叉边
d[u] - 第一次访问顶点u时给u盖上的时间戳
f[u] - 当访问完了以u为根的子树上的所有顶点后给u盖上的时间戳
/ 0 白色，未被访问过的节点标白色
c - 顶点颜色表 c[u] = | -1 灰色，已经被访问过一次的节点标灰色
\ 1 黑色，当该节点的所有后代都被访问过标黑色
p - 顶点的前驱表 p[u] - u在深度优先树中的父节点
b - 顶点的度数表 b[u] - 深度优先树中顶点u的度数
l - 顶点的low值表，
l[u]用来纪录顶点u或u的后代所能追溯到的最早（最先被访问）的祖先节点v的d[v]值
/ d[u] u首次被访问
l[u]= | min(l[u],d[v]) 访问反向边(u,v)时
\ min(l[u],l[s]) u的儿子s的关联边全部被访问时
边的分类方法：
1。树枝：
深度优先森林中的边。如果V是在访问边(u,v)时第一次被发现(此时v是白色的)，那么
(u,v)是一个树枝。在树枝边中，我们称u为v的父母，既作p[v]=u；
2。反向边：
在深度优先树种连接顶点u到他的祖先的那些非树枝边。环也被认为是反向边。显然，
如果第一次访问(u,v)时v为灰色，则(u,v)为反向边。在对图的深度优先搜索中没有发现
反向边，则该图没有回路。
3。正向边
深度优先树中连接顶点u到他的祖先的那些非树枝边。当第一次访问(u,v)时，v为黑色
且d[u]
其它类型的边。他们既可以连接一棵深度优先树中的两个顶点，只要一顶点不是另一
个顶点的祖先，也可以连接分属两棵深度有线数的顶点。当第一次访问(u,v)时，v为黑色
且d[u]>d[v]，则(u,v)为交叉边。
*深度优先搜索的复杂度为 θ(V+E)
*有向图或无向图G的深度优先森林中，节点v是节点u的后裔当且仅当 d[u]
S1. 调用DFS(G)以计算出每个节点u的完成时刻f[u];
S2. 计算出G的转置G‘，其中G‘是将G的每一条边反向后得到；
S3. 调用DFS(G‘)，但在DFS的主循环里按照f[u]递减的顺序考虑各节点；
S4. 输出S3中产生的深度优先森林中每棵树的节点，作为各自独立的强连通分支。
*根据f[v]从大到小对顶点排序，即得到有向图的拓扑排序；
*在对无向图G进行深度优先搜索时，G只有树枝和反向边两种边。
*若无向图的树枝边(u,v)满足l[v]>d[u]，即从v及其后代不存在一条连接u的祖先的反向边，
则(u,v)为桥；
* 无向图的节点v是割点当且仅当v具备以下条件成立：
若v是深度优先树的根(p[v]=0)，则v的子节点数目超过1；
若v不是深度优先树的根(p[v]>0)，则v存在一个子节点w,满足l[w]>=d[v]。
}
Top
ZhangYv（迎着朝阳,走向地狱）回复于 2003-11-16 20:08:17 得分 0
{==========================================
!!!!IMPORTANT
对于有向图，请把前面有!!!的行删去；
对于权可以为负的图，请修改前面有!!!的行。
============================================}
procedure DFS(var G:adj_matrix;size:integer);
const
white=0;
gray=-1;
black=1;
var
EdgeType:adj_matrix;
d,f,c,p,b,l:array[1..MaxSize] of integer;
u,time:integer;
procedure DFS_visit(u:integer);
var
v:integer;
begin
c[u]:=gray;
inc(time);
d[u]:=time;
l[u]:=time;
for v:=1 to size do
if G[u,v]>0 then {G[u,v]>0表示边(u,v)存在且未被访问，当边(u,v)不存在时G[u,v]=0}
case c[v] of
white: begin
{!!!} {G[u,v]:=-G[u,v]; {设置(u,v)暂时不可访问的标志，对于有向图，请把此行删去}
EdgeType[u,v]:=1; {(u,v)为树枝边}
inc(b[u]); {深度优先树中顶点u的度数加1}
p[v]:=u; {深度优先树中顶点v的父亲是u}
DFS_visit(v); {深度优先搜索顶点v}
if l[v]
end;
gray: begin
EdgeType[u,v]:=2; {(u,v)为反向边}
if d[v]
black: begin
if d[v]>d[u] then EdgeType[u,v]:=3 {(u,v)为正向边}
else EdgeType[u,v]:=4; {(u,v)为交叉边}
end;
end; {end of case}
c[u]:=black;
inc(time);
f[u]:=time;
end;
{===============================================
最大流算法
基于Ford-Fulkerson 算法的 Edmonds-Karp 实现
求出以s为源，以t为汇的最大网络流 时间复杂度为O(VE^2)
C为容量网络，如果(u,v)没有边，规定c[u,v]=0;
注意，Flow是一个已经求出的可行流，一般可以取Flow[i,j]=0;
================================================}
procedure Edmonds_Karp(var C:adj_matrix;size:integer;s,t:integer;var Flow:adj_matrix);
var
L:array [1..maxsize,1..2] of integer; {记录标号}
Q:array [1..maxsize] of integer; {队列}
u,v,head,tail:integer;
begin
repeat
fillchar(L,sizeof(L),0); {初始化，所有点标号为0}
L[s,1]:=0;
L[s,2]:=maxint;
head:=0;
tail:=1;
Q[tail]:=s; {s入队}
while (head
inc(head);
u:=Q[head];
for v:=1 to size do
if (Flow[u,v]
inc(tail);
Q[tail]:=v;
L[v,2]:=min(C[u,v]-Flow[u,v],L[u,2]); {L[v,2]记录下从s到v的增广路径中最小的可改进流量}
L[v,1]:=u; {L[v,1]记录下从s到v的增广路径中v的前驱}
end;
end; {while}
if L[t,2]>0 then {如果汇点已标号}
begin
v:=t;
u:=L[v,1];
while v<>s do
begin
Flow[u,v]:=Flow[u,v]+L[t,2];
Flow[v,u]:=-Flow[u,v];
v:=u;
u:=L[v,1];
end; {while}
end; {then}
until L[t,2]=0; {直到汇点未标号}
end;
{=================================================
容量有上下界的最大流问题
B为容量下界矩阵；
C为容量上界矩阵；
如果存在可行流，返回值为真
===================================================}
function Max_Flow_With_Limt(var B,C:adj_matrix;size:integer;s,t:integer;var Flow:adj_matrix):boolean;
var
new_c:adj_matrix; {新的容量网络}
i,j:integer;
begin
fillchar(new_c,sizeof(new_c),0);
{构造一个新的容量网络new_c}
for i:=1 to size do {增加一个新汇点size+2}
for j:=1 to size do
new_c[i,size+2]:=new_c[i,size+2]+B[i,j];
for i:=1 to size do {增加一个新源点size+1}
for j:=1 to size do
new_c[size+1,i]:=new_c[size+1,i]+B[j,i];
for i:=1 to size do
for j:=1 to size do
new_c[i,j]:=C[i,j]-B[i,j];
new_c[s,t]:=maxint;
new_c[t,s]:=maxint;
{用Edmonds_Karp算法在新的容量网络中求最大流}
fillchar(flow,sizeof(flow),0);
Edmonds_Karp(new_c,size+2,size+1,size+2,flow);
{检验原容量限制网络是否有可行流}
for i:=1 to size do
if flow[size+1,i]
result:=false;
exit;
end;
result:=true;
{将新容量网络中求出的可行流化为原来的容量网络中的可行流}
flow[s,t]:=C[s,t];
flow[t,s]:=-flow[s,t];
for i:=1 to size do
for j:=1 to size do
if flow[i,j]>=0 then
begin
flow[i,j]:=flow[i,j]+B[i,j];
flow[j,i]:=-flow[i,j];
end;
{用Edmonds_Karp将求出的可行流进行放大}
Edmonds_Karp(c,size,s,t,flow);
end;
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
程序效率常用时间复杂度与空间复杂度衡量，现在我把一个递归程序用一个非递归算法实现了（非自己处理栈的那种方法），我想写一个报告说明其效率的提高，但不知道该有什么方法分析比较递归算法与实现相同功能的非递归程的效率才能让人信服。
我没有做软件项目的经验，不知是否有标准的做法?请高人不吝赐教。
分析一下你的非递归算法的复杂度，然后再分析一下递归算法的复杂度，比较一下不就知道了吗
递归算法用空间复杂度分析较合适，而改成的非递归算法用时间复杂度分析较合适。但这两种复杂度怎么放到一起比较呢？
对递归而言，时间主要花费在函数的调用上。其空间复杂度是很大的。非递归的算法的
效率一般比递归要高的多。而非递归算法又要去模似栈就必须要有一个循环。所以时间
复度杂度是比较大的。因此我同意楼上人的说法
递归算法用空间复杂度分析较合适，而改成的非递归算法用时间复杂度分析较合适。
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 这话说得没有道理
你已经说了你的非递归并非自己处理堆栈的方法，一般来说在这种情况下递推算法要比等价的递归算法效率高很多，比如计算斐波拉契数列，如果直接利用F(n+2) =F(n)+F(n+1)递归计算效率很低，但是改成一个循环（也就是递推）效率就高很多了。所以你应该首先分析你的时间复杂度。当然递推的空间效率一般也比递归高，所以你也可以同时推导一下它们的空间复杂度，作个比较。
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
证明题：
投100次硬币，出现的正反面排列组合情况为C(101,100)=C(101,1)=101.
然后得到推论，m个相同的球放进n个相同的盒子(可以一个盒子放多个)的排列组合为
C(m+n-1,m)。
最好不要用累加的方式推导，给出个简单的等价转换就可以得分。
公布答案，有m+n个盒子，有m+n-1个球排满前m+n-1个盒子，最右边的盒子为空现在我要你任意拿走n-1个球.然后有这样一个定义，从左至右，应该有n个空盒子。这n个空盒子分别代表一个分类，它前面的有球盒子的个数为这个分类的球的个数。则共有C(m+n-1,m)个分法Top
ZhangYv（迎着朝阳,走向地狱）回复于 2003-11-16 20:10:39 得分 0
猎人要带一条狼、一只羊和一棵大白菜过河。船太小，一次只能带一样。但猎人不在场的情况下，狼要吃羊，羊要吃白菜。请设计一个C++程序为猎人指出一个安全的渡河放案。
给你一个Pascal编的,自己改吧!
{*
Title : 主人和佣人过河问题
File : MasterAndServant.pas
Author : Arter
Date : 2001/08/04
*}
program MasterAndServant;
uses Dijkstra;
const
MaxNum = 300 ;
type
TStatus = Array [ 1..MaxNum ]
of Record
x : integer;
y : integer;
z : integer;
end ;
var
status : TStatus ;
procedure CreateDataFile;
var
i , j , count: integer ;
deltaX,deltaY :integer;
fin : Text ;
n , k : integer;
begin
write( ‘ 请输入商人数(n) 和 船上的最大装载量 (k) ‘);
readln( n , k );
for i := 1 to n+1 do
begin
status[ i ].x := n;
status[ i ].y := n+1-i;
status[ i ].z := 1;
status[ 3*n+i ].x := n;
status[ 3*n+i ].y := n+1-i;
status[ 3*n+i ].z := 0;
end;
status[ 3*n+1 ].x := 0;
status[ 3*n+1 ].y := 0;
status[ 3*n+1 ].z := 0;
for i := n+2 to 2*n do
begin
status[ i ].x := 2*n+1-i;
status[ i ].y := 2*n+1-i;
status[ i ].z := 1;
status[ 3*n+i ].x := 2*n+1-i;
status[ 3*n+i ].y := 2*n+1-i;
status[ 3*n+i ].z := 0;
end;
for i := 2*n+1 to 3*n do
begin
status[ i ].x := 0;
status[ i ].y := 3*n+1-i;
status[ i ].z := 1;
status[ 3*n+i ].x := 0;
status[ 3*n+i ].y := 3*n+1-i;
status[ 3*n+i ].z := 0;
end;
{write(‘Input created data file name ‘);
readln(inFileName);}
inFileName := ‘temp.dat‘;
assign(fin,inFileName );
rewrite(fin);
writeln( fin , 6*n ) ;
count := 0;
for i := 1 to 3*n do
for j := 3*n+1 to 6*n do
begin
deltaX := status[ i ].x - status[ j ].x ;
deltaY := status[ i ].y - status[ j ].y ;
if ( deltaX + deltaY > 0 )
and ( deltaX + deltaY <= k )
and ( (deltaX >= 0 )
and (deltaY >= 0 )
{ ( deltaX >= deltaY )
or ( deltaX = 0 )
or ( deltaY = 0 ) }
)
then begin
writeln(fin, i,‘ ‘ ,j , ‘ ‘ , 1);
end;
end;
close( fin );
end;
procedure ReadData;
var i , j :Integer ;
begin
{write(‘Input the input data file name: ‘);
readln(inFileName);}
assign(inFile,inFileName);
reset(inFile);
read(inFile,vectexNum);
if (vectexNum < 1) or (vectexNum > MaxVectexNum)
then
begin
writeln(‘The count of vectex is out of range!‘);
exit;
end
else
begin
for i := 1 to vectexNum do vectex[i] := i; { Init vectex[] }
for i := 1 to vectexNum do { Init edge[,] }
for j := 1 to vectexNum do
if i = j then edge[ vectex[i],vectex[j] ] := 0
else edge[ vectex[i],vectex[j] ] := MaxDistance;
repeat
read(inFile,i,j,edge[ vectex[i],vectex[j] ]);
edge[vectex[j],vectex[i]] :=
edge[ vectex[i],vectex[j]]; { No dection graph }
until ( eof(inFile));
close(inFile);
end ;
end ;
procedure PrintPath;
var
outFileName : String ;
outFile : Text ;
i : Integer ;
procedure PrintSinglePath( beginVertexPos : Integer ; endVertexPos : Integer );
begin
if preVectexPos[ endVertexPos ] = beginVertexPos
then
begin
write(outFile,‘[‘,status[beginVertexPos].x,‘,‘);
write(outFile,status[beginVertexPos].y,‘,‘);
write(outFile,status[beginVertexPos].z,‘]‘);
end
else
begin
PrintSinglePath( beginVertexPos , preVectexPos[ endVertexPos ] );
end;
write(outFile,‘-->‘);
write(outFile,‘[‘,status[endVertexPos].x,‘,‘);
write(outFile,status[endVertexPos].y,‘,‘);
write(outFile,status[endVertexPos].z,‘]‘);
end;
{PrintPath}
begin
write(‘ 请输入输出文件名：‘);
readln(outFileName);
assign(outFile,outFileName);
rewrite(outFile);
writeln(outFile,‘Shortest Path By DijkStra ‘);
{for i:= (vectexNum div 2) + 1 to vectexNum do }
for i:= (vectexNum div 2) + 1 to (vectexNum div 2) + 1 do
begin
write(outFile,‘d(‘,vectex[beginVectexPos]:2,‘,‘,vectex[i]:2,‘)=‘);
if dist[vectex[i]] < MaxDistance
then
begin
write(outFile,dist[vectex[i]]:7);
write(outFile,‘‘:2,‘ path: ‘);
PrintSinglePath(beginVectexPos , i);
writeln( outFile );
end
else
begin
write(outFile ,‘ +‘,Chr(236),‘‘:3);
writeln(outFile,‘‘:2,‘ No path ! ‘);
end ;
end;
close(outFile);
end;
begin
About;
CreateDataFile ;
ReadData ;
Dijk;
PrintPath ;
end.
Top
ZhangYv（迎着朝阳,走向地狱）回复于 2003-11-16 20:11:27 得分 0
(接上贴）
{*
Title : Dijksta for Master&Servent
File : Dijkstra.pas
Author : Arter
Date : 2001/08/04
*}
Unit Dijkstra;
{$X+,S-}
{$M 16384,16384,655360}
interface
const
MaxVectexNum = 150;
MaxDistance = 10000;
type
TRange = 1..MaxVectexNum ;
TVectexName = Integer ;
TWeight = Integer ;
TVectex = Array [TRange] of TVectexName ;
TEdge = Array [TRange,TRange] of TWeight;
TDistance = Array [TRange] of TWeight;
TSetOfVectex = Set of TRange;
var
vectex,preVectexPos : TVectex;
dist : TDistance;
edge : TEdge;
setOfVectex : TSetOfVectex;
beginVectexPos : Integer;
vectexNum : Integer;
minDist,distTemp: TWeight;
inFileName , outFileName : String ;
inFile , outFile : Text ;
procedure About;
procedure ReadData;
procedure PrintPath;
procedure Dijk;
implementation
procedure About;
begin
writeln;
writeln(‘{*****************************************}‘);
writeln(‘{* *}‘);
writeln(‘{* Master&Servent by Dijkstra *}‘);
writeln(‘{* Copyright(c) by Arter *}‘);
writeln(‘{* 2001/08/04 *}‘);
writeln(‘{* E-mail:javaart@263.net *}‘);
writeln(‘{* *}‘);
writeln(‘{*****************************************}‘);
end;
procedure ReadData;
var i , j :Integer ;
begin
write(‘Input the input data file name: ‘);
readln(inFileName);
assign(inFile,inFileName);
reset(inFile);
read(inFile,vectexNum);
if (vectexNum < 1) or (vectexNum > MaxVectexNum)
then
begin
writeln(‘The count of vectex is out of range!‘);
exit;
end
else
begin
for i := 1 to vectexNum do vectex[i] := i; { Init vectex[] }
for i := 1 to vectexNum do { Init edge[,] }
for j := 1 to vectexNum do
if i = j then edge[ vectex[i],vectex[j] ] := 0
else edge[ vectex[i],vectex[j] ] := MaxDistance;
repeat
read(inFile,i,j,edge[ vectex[i],vectex[j] ]);
edge[vectex[j],vectex[i]] :=
edge[ vectex[i],vectex[j]]; { No dection graph }
until ( eof(inFile));
close(inFile);
end ;
end ;
procedure PrintPath;
var
i : Integer ;
procedure PrintSinglePath( beginVertexPos : Integer ; endVertexPos : Integer );
begin
if preVectexPos[ endVertexPos ] = beginVertexPos
then
begin
write(outFile,beginVertexPos);
end
else
begin
PrintSinglePath( beginVertexPos , preVectexPos[ endVertexPos ] );
end;
write(outFile,‘-->‘);
write(outFile,endVertexPos);
end;
{PrintPath}
begin
write(‘Input the output data file name:‘);
readln(outFileName);
assign(outFile,outFileName);
rewrite(outFile);
writeln(outFile,‘Shortest Path By DijkStra ‘);
for i:= 1 to vectexNum do
begin
write(outFile,‘d(‘,vectex[beginVectexPos]:2,‘,‘,vectex[i]:2,‘)=‘);
if dist[vectex[i]] < MaxDistance
then
begin
write(outFile,dist[vectex[i]]:7);
write(outFile,‘‘:2,‘ path: ‘);
PrintSinglePath(beginVectexPos , i);
writeln( outFile );
end
else
begin
write(outFile ,‘ +‘,Chr(236),‘‘:3);
writeln(outFile,‘‘:2,‘ No path ! ‘);
end ;
end;
close(outFile);
end;
procedure Dijk;
var
i , j , nextI : Integer;
count : Integer ;
begin
{write(‘Input the begin vectex postion:‘);
readln(beginVectexPos);}
beginVectexPos := 1;
setOfVectex := [];
for i:=1 to vectexNum do
begin
setOfVectex := setOfVectex+[ vectex[i] ];
dist[vectex[i]] := edge[ vectex[i],vectex[beginVectexPos] ];
preVectexPos[i] := beginVectexPos;
end;
i := beginVectexPos;
count := 1;
setOfVectex:= setOfVectex-[ vectex[i] ];
repeat
minDist := MaxDistance;
for j := 1 to vectexNum do
begin
if vectex[j] in setOfVectex
then
begin
distTemp := dist[vectex[i]]+edge[vectex[i],vectex[j]];
if( (dist[vectex[j]] > distTemp ))
and ( edge[vectex[i],vectex[j]] < MaxDistance )
then
begin
dist[vectex[j]] := distTemp;
preVectexPos[j] := i;
end;
if (dist[vectex[j]]>0) and (dist[vectex[j]]
minDist := dist[vectex[j]];
nextI := j;
end;
end;
end;
if minDist<>MaxDistance then dist[vectex[nexti]] := minDist;
i := nextI;
inc( count );
setOfVectex := setOfVectex-[vectex[i]];
until ( count = vectexNum ) ;
end;
end.
Top
ZhangYv（迎着朝阳,走向地狱）回复于 2003-11-16 20:17:10 得分 0
两个自然数可以用一个自然数来表示，谁知道么？
书上说一对自然书a和b，可以用自然书((a+b)^2+3a+b)/2来表示，我试了试，好像是这样，可是怎么才能翻过来求出a和b呢？
即假如某人用这种办法把两个数变成一个数，我怎么通过这个书回到原来的两个数？
是这样的。若a=b，则变成一元二次方程很简单的就能解决（2a^2+2a-z=0,参数z即已知的那个数，下同）；否则：可以设a=(x+y)/2 b=(x-y)/2.(x,y是自然数,且x>y.即任何二个自然数均可表示二个自然数的这种形式，道理很明显吧。）。代入你的那个算式得：(x+1)^2=(2*z+1)-y
观察这个式子，可以做个循环：即对x from i(i是（2*z+1）的2次正根向下取整) to i-1 逐个验证。
令a+b=x1，3a+b=x2,联立得a=(x2-x1)/2,b=(3*x1-x2)/2,x1和x2要么都为奇数要么都为偶数，且x1
(a+b)^2/2+(a-b)/2+(a+b)=n
x^2+y+2*x=2*n
(x+1)^2=2*n+1-y
此题不需要穷举，只需一些数学运算即可：
begin
令x=a+b，y=a-b，(x，y为整数)；
原式可化为：(x+1)^2=2*n+1-y，n为要转化的自然数；
令p=(2*n+1)开方向上取整；
if p^2-(2*n+1)<=p-1 then { x=p-1；y=(2*n+1)-p^2；}
else { x=p-2；y=(2*n+1)-(p-1)^2；}
a=(x+y)/2；b=(x-y)/2；
end；
提示：a，b为自然数则|a+b|>=|a-b|；
证明略。
---------------------------------------------------------------------------
请详细介绍贪心算法
贪心算法
1．概念
贪心算法是从问题的某一个初始解出发逐步逼近给定的目标，以
尽可能快地求得更好的解。当达到某算法中的某一步不能再继续
前进时，算法停止。这时就得到了问题的一个解，但不能保证求
得的最后解是最优的。在改进算法中，贪心算法演化为爬山法。
2．特点及使用范围
贪心算法的优点在于时间复杂度极底。贪心算法与其他最优化算
法的区别在于：它具有不可后撤性，可以有后效性，一般情况下
不满足最优化原理。贪心算法的特点就决定了它的适用范围，他
一般不适用于解决可行性问题，仅适用于较容易得到可行解的最
优性问题。这里较容易得到可行解的概念是：当前的策略选择後，
不会或极少使后面出现无解的情况。另外，对于近年来出现的交
互性题目，贪心算法是一个较好的选择。这是因为，在题目中，
一个策略的结果是随题目的进行而逐渐给出的，我们无法预先知
道所选策略的结果，这与贪心算法不考虑策略的结果和其具有后
效性的特点是不谋而合的。当然，贪心算法还可以为搜索算法提
供较优的初始界值。
-------------------------------------------------------------------
有一张M*N的矩形纸，要求裁出K[i]个A[i]*B[i]的小矩形，其中i = 1,2,...t， 问能否办到？是不是这样的题目呀？
这个题目似乎是个NP问题，可能根本没有多项式的解法。
m*n的棋盘的p*q矩形完全覆盖的充要条件
我先研究了大矩形可以被小矩形完全覆盖（不留空隙）的充要条件。先用数学语言定义几个概念：
m*n的棋盘是指由m行n列方格构成的棋盘。
所谓棋盘的覆盖，是指用若干个相同的图形去覆盖m*n的棋盘，覆盖棋盘的每个图形也由若干个方格组成，称之为覆盖形。在棋盘的覆盖中，约定任意两个覆盖形互不相重叠，且任意一个覆盖形的任何一个方格与棋盘的某个方格重合。
下面先研究简单的情况，当p=1,q=k的情况。
定理一：
m*n的棋盘存在1*k矩形的完全覆盖的充要条件是k|m或者k|n。 （其中a|b表示a整除b）
证：充分性显然。下面证明必要性。
假设m*n的棋盘存在1*k矩形的完全覆盖。在m*n棋盘的各个格中填数：第一列的格从上至下依次填1,2,..m，此外，对于其中的任何一行，所填的各数从左至右构成公差为1的等差数列。这样，每一个1*k矩形在棋盘的覆盖中所盖住的格所填的数字恰好构成模k的一个完系（如果一个整数集中的每一个数模k得到的集合是{0,1,...,(k-1)}，则称该集合为模k的完系）。因为m*n的棋盘存在1*k矩形的完全覆盖，所以m*n的棋盘中所填的数字中属于模k的不同剩余类的数的个数相等，也就是说，m*n的棋盘上所填的数字中，所有模k得到0的数字的个数=所有模k得到1的数字的个数=...=所有模k得到k-1的数字的个数。
设m=pk+s,n=qk+t，假设s*t<>0，则不妨设0
| | |
| s*t | s*pk |
| | |
+---------+------------+
| |
| pk*n |
| |
+----------------------+
显然，pk*n的矩形和s*pk的矩形可被1*k矩形完全覆盖（由充分性知），所以这两个矩形中属于模k的不同剩余类中的数的个数相等，从而s*t的矩形中属于模k的不同剩余类中的数的个数也应该相等。考察s*t的矩形中所填的数字：
1 2 3 .... t-1 t
2 3 4 .... t t+1
............................
s-1 s s+1 .... s+t-3 s+t-2
s s+1 s+2 .... s+t-2 s+t-1
将上述的数表作如下改造：对于表中的每一个数a，如果a>k，则将a换作a-k，这并不改变该数模k的余，这样得到一个新的数表，记作A。考察数t与t+1在表A中出现的次数。观察上图可以注意到每一条从右上方到左下方的对角线上的数字都相同，我们从左到右给这些对角线标号。显然，在前t条对角线上不出现t+1。又s+t-1
所以s*t<>0不成立，即s*t=0。必要性得证。
下面利用定理一将结论扩展到m*n的棋盘的p*q矩形完全覆盖。
定理二：m*n的棋盘的p*q矩形完全覆盖的充要条件是m,n满足下列条件之一：
(i) p|x且q|y
(ii)p|x,q|x且存在自然数a,b，使y=ap+bq
其中{x,y}={m,n}
证：充分性：
若条件(i)满足，不妨设x=m，y=n，令m=ps,n=qt,则m*n的棋盘可以划分为s*t个p*q矩形，结论成立；若条件(ii)满足，不妨设x=m,y=n，即p|m,q|m,且存在自然数a,b使得n=ap+bq。那么，将m*n的棋盘划分为两个棋盘：一个m*ap棋盘，一个m*bq棋盘，这两个棋盘均可以被p*q矩形完全覆盖，所以结论成立。
必要性：
设m*n的棋盘可被p*q矩形完全覆盖，从而m*n棋盘存在1*p矩形的完全覆盖，由定理一知p|m或p|n，同理q|m或q|n，这有以下两种情况：
(1)p,q可以分别整除m,n中的各一个，即有p|x,q|y且{x,y}={m,n}，则结论成立；
(2)p,q只能同时整除m,n中的同一个，不妨设p|m,q|m，且p\n,q\n(用符号a\b表示a不整除b)。考察至少盖住第一行中一个格的那些覆盖形，设其中以"p*q"方式覆盖的矩形有b块，以"q*p"方式覆盖的矩形有a块，再注意到第一行共有n个格，所以n=ap+bq，结论成立。
必要性得证。
根据上面定理很容易求出一个m*n的棋盘最多可被多少个p*q的矩形覆盖，
我以前写了个程序的，但是找不到了。目前只找到这么多东西了：（
拿到此问题的思路
此问题很复杂。设大矩形为m*n,小矩形为p*q，即使不考虑小矩形斜放的问题，如果m,n,p,q不是整数（或者不能化为整数），此问题还是没有好办法解决。此问题称为m*n棋盘的p*q骨牌饱和覆盖问题，用纯粹的数学方法解决很麻烦，而且对m,n,p,q都有一定的限制，完全无限制的情况还未求出解来。我现在正在努力求出其上下界，有了成果会贴出来的。
如果考虑用计算机来做，就只能采用搜索法。这里关键的难点在于如何在当前的状态下生成新的子状态。
下面的叙述中称m*n的大矩形为棋盘，p*q的小矩形为骨牌。规定骨牌不能旋转，只能横放或竖放。注意：这里用计算机搜索骨牌的覆盖，可以不必限制m,n,p,q都为整数。
定理一：
一定存在一种最优的布局，使得每一块骨牌至少有两条边与其他骨牌的边或者棋盘的边相邻。
证明：这时显然的，如果某种最优的布局中有一块骨牌至少有三条边与其他边有空隙，可以将该骨牌平移，使得该骨牌至少有两条边与其他骨牌的边或者棋盘的边相邻，这样还是得到一个最优覆盖方案。
定理二：
一定存在一种最优布局，使得棋盘的某个角的顶点被骨牌覆盖。
这也是显然的。
下面可以根据这两个定理设计一个生成新结点的方法。
1。首先检查棋盘是否可以被骨牌完全覆盖，检查方法我已经在上一张贴子中给出了。
2。初始状态棋盘为空；
3。取棋盘的左上角，放第一张骨牌，使骨牌的一个顶点与棋盘的角的顶点重和。第一张骨牌有横放和竖放两种情况，因此得到两个初始状态的子结点；
4。对于当前的状态，已经放置的骨牌的围成一个多边形（其中可能有空隙），该多边形的边和棋盘的边又将棋盘中的空地围成一个多边形，下面只要在这个多边形内部贴着边放置一个骨牌就可以了。
其实完全没必要考虑得那么复杂。
我去年作了一个排料方面的模块，也是要求在大的矩形板上裁减出足够多的小矩形板。我采用的是近似穷举的办法。速度很快，效果很好。作为商业软件已运行了一年多。
提醒各位一句：作软件最重要的是能实现功能，而不是沉迷于使用的多少技巧，多少高深的理论。
Top
ZhangYv（迎着朝阳,走向地狱）回复于 2003-11-16 20:19:34 得分 0
什么是优先队列？
怎么用“数组实现的二叉树”来实现优先队列？
希望得到具体回答
下面是数组实现的二叉堆，其中MAX_SIZE是数组的最大长度；ElementType是其中元素的类型；Priority(x: ElementType) 是一个函数，返回值是元素x的优先级，当然也可以用一个Priority数组来保存每个元素的优先级(在这个打字员问题中就应该用一个数组来保存每个元素的优先级，在这个问题中优先级就是从初始密码转换到该密码所需的操作的数目)。
type
PriorityQueue = record
contents: array [1..MAX_SIZE]of ElementType;
last : integer;
end;
{ 将一个优先队列变空 }
procedure MakeNull(var A: PriorityQueue);
begin
A.last := 0;
end;
{ 向优先队列A中插入一个元素x }
procedure Insert(x: ElementType; var A: PriorityQueue);
var
i: integer;
temp:ElementType;
begin
if A.last = MAX_SIZE then
Error(‘Priority Queue is full.‘)
else begin
A.last := A.last + 1;
A.contents[A.last] := x;
i := A.last;
while (i > 1) and ( Priority(A.contents[i]) < Priority(A.contents[i div 2]) do
begin
temp := A.contents[i];
A.contents[i] := A.contents[i div 2];
A.contents[i div 2] := temp;
i := i div 2;
end; { end of while }
end; { end of else }
end; { end of Insert }
{ 删除优先队列对头的那个优先级最小的元素，并将其值返回 }
function DeleteMin(var A: PriorityQueue): ElementType;
var
minimun : ElementType;
i : integer;
begin
if A.last = 0 then
Error(‘Priority Queue is empty. ‘)
else begin
minimun := A.contents[1];
A.contents[1] := A.contents[A.last];
A.last := A.last - 1;
i := 1;
while i < (A.last div 2) do
begin
if (Priority(A.contents[2*i]) < Priority(A.contents[2*i+1])) or (2*i = A.last)
then j := 2*i;
else j := 2*i + 1;
{ j节点是i节点具有较高优先级的儿子，当i节点只有一个儿子的时候，j节点是i节点的唯一儿子 }
if Priority(A.contents[i]) > Priority(A.contents[j]) then
begin
temp := A.contents[i];
A.contents[i] := A.contents[j];
A.contents[j] := temp;
i := j;
end
else begin { 不能再向下推了 }
DeleteMin := minimum;
exit;
end;
end; { end of while }
{ 这时已经到达叶结点 }
DeleteMin := minimum;
exit;
end; { end of else }
end; { end of DeleteMin }
优先队列插入和删除元素的复杂度都是O(lgn)，所以很快。
在计算机算法的书中，所有的log,lg只要没有说明，都是以2为底的；在数学书中lg是指以10为底的对数。每本算法书中的记号不同，有的喜欢用lg，有的喜欢用log，其实没有区别，都是以2为底的；另外，就算是以10为底的对数，和以2为底的对数没有渐进阶的差别，因为根据对数公式： log(a,b) = log(c,b) /log(c,a)， （这里log(a,b)是指以a为底的对数），所以无论以什么为底，只相差一个常数的倍数。
优先队列用C++描述如下
#define MAX_SIZE 100
typedef int ElementType; // 定义元素的类型，这里假设是int类型
struct PriorityQueue { // 定义优先队列
ElementType contents[MAX_SIZE];
int size;
};
int P[MAX_SIZE];
// 返回元素x的优先函数值，这个值越小说明优先级越高
int Priority(const ElementType& x)
{
return P[x]; // 实际应用中通常用数组P来存储每个元素的优先级，
// 但是实际上也可以用其他方法（比如通过公式）计算出优先级
}
// 将一个优先队列变空
void MakeNull(PriorityQueue& Q)
{
Q.size = 0;
}
// 向优先队列Q中插入一个元素x
void Insert(const ElementType& x, PriorityQueue& Q)
{
int i;
ElementType temp;
if (Q.size == MAX_SIZE) {
throw "Priority Queue is full.";
} else {
Q.contents[Q.size++] = x;
i = Q.size - 1; // 从最后一个元素开始
while( ( i > 0 ) && ( Priority( Q.contents[i] ) < Priority( Q.contents[(i-1)/2] ) ) )
{
temp = Q.contents[i];
Q.contents[i] = Q.contents[(i-1)/2];
Q.contents[(i-1)/2] = temp;
i = (i-1) / 2;
}
}
}
// 删除优先队列对头的那个优先函数值最小的元素，并将其值返回
ElementType DeleteMin(PriorityQueue& Q)
{
ElementType result;
int i, j;
if (Q.size == 0) {
throw "PriorityQueue& Q";
} else {
result = Q.contents[0];
Q.contents[0] = Q.contents[Q.size - 1];
Q.size--;
i = 0;
while (2*i + 1 < Q.size) {
// 节点i的左右儿子分别是2i+1和2i+2
if( (2*i+1 == Q.size-1) ||
( Priority(Q.contents[2*i+1]) < Priority(Q.contents[2*i+2]) ) )
{
j = 2*i + 1;
} else {
j = 2*i + 2;
}
// j节点是i节点具有较小优先函数值的儿子，当i节点只有一个儿子的时候，j节点是i节点的唯一儿子
if( Priority(Q.contents[i]) > Priority(Q.contents[j]) ) {
temp = Q.contents[i];
Q.contents[i] = Q.contents[j];
Q.contents[j] = temp;
i = j;
} else {
return result;
}
}
return result;
}
}
Top
ZhangYv（迎着朝阳,走向地狱）回复于 2003-11-16 20:30:52 得分 0
如何算不规则多边形的面积?
1.把（xi,yi)按逆时针排好。(i=1,2,3,....n, x(n+1)=x1);
2.计算它的有向面积:
(1)先看:(0,0),(xj,yj),(xk,yk)三点的面积S=
¦ 0 0 1 ¦
¦ xj yj 1 ¦*(1/2) =(xj*yk-yj*xk)/2
¦ xk yk 1 ¦
(2)多边形面积可以划分为三角形面积的和:
S[（0，0），（x1,y1),(x2,y2)]+S[（0，0），（x2,y2),(x3,y3)]+...
+ S[（0，0），（x(n-1),y(n-1),(xn,yn)]+S[（0，0），（xn,yn),(x1,y1)]
=((x1*y2-x2*y1)+(x2*y3-x3*y2)+...+(x(n-1)*yn-xn*y(n-1))+(xn*y1-x1*yn))/2
=(x1*(y2-yn)+x2*(y3-y1)+x3*(y4-y2)+...+x(n-1)*（yn-y(n-2))+xn*(y1-y(n-1)))/2
（或：(y1*(xn-x2)+y2*(x1-x3)+y3*(x2-x4)+...+y(n-1)*(x(n-2)-xn)+yn*(x(n-1)-
x1))/2 )
/******************************************** * *
* 计算多边形的面积 *
* *
* 要求按照逆时针方向输入多边形顶点 *
* 可以是凸多边形或凹多边形 *
* *
\********************************************/
float area_of_polygon(int vcount,float x[],float y[])
{
int i;
float s;
if (vcount<3) return 0;
s=y[0]*(x[vcount-1]-x[1]);
for (i=1;i
return s/2;
}
----------------------------------------------------------------------
Top
ZhangYv（迎着朝阳,走向地狱）回复于 2003-11-16 20:32:38 得分 0
===========================================================
问题：
在RPG游戏中精灵要从A走到B，其中有若干的障碍物，如何寻找最短路径？注意这里的地图是以像素为单位，而不是划分格子的（传统的日式RPG是划格子法，那要简单得多）
==============================================================
这个问题是计算几何学中的一个经典课题：算法的运动规划问题。
计算几何中的一些研究问题来源于机器人学领域，这些问题称为运动规划或者更准确地称为算法的运动规划。假设二维和三维空间中存在多个障碍物，这些障碍物呈多边形或者多面体。另外，一个可运动的物体从空间中的点s移动到另一点t，运动的物体碰到障碍物时必须绕过它。这里可以提出许多问题，例如，求从s至t的最短路径；运动物体的形状是点、一条线段、一个凸多边形、一个圆或者任意多边形，求从s至t的路径等等。物体在运动过程中，要避免与所有障碍物的碰撞，也就是说，物体边缘上的任一点a与障碍物的一个内点重合时，就发生碰撞；点a沿障碍物边界的滑动是允许的。没有碰撞的路径称为自由路径。这个课题主要讨论以下三类问题:
(l)判定问题:运动物体(即机器人)R能够从s移动到t吗？即从s至t是否存在一条自由路径。
(2)构造路径:寻找机器人R从s移动到t的一条自由路径。
(3)最短路径:寻找机器人R从s移动到t的一条最短自由路径。
另外，当R具有不同几何外形时，可以再次提出上述三个问题。问题(1)比问题(2)容易(可以举出例子来说明这一点)，而问题(2)又比问题(3)简单。问题(3)中“最短”的含义，一般是指自由路径长度最短。但进一步研究发现“最短”与R的外形也存在一定关系，如果R是一个圆，那么“最短”的含义是清楚的；而R是一条可以旋转的线段时，理解“最短”的含义就不那么简单了，这时先给出几个不同的定义，在此定义下求最短路径。
根据你的问题的实际情况，下面仅讨论平面中最短路径问题的几种情况：
1。机器人是一个点；
2。机器人是一个圆盘；
3。机器人是一个多凸边形；
其他的情况（机器人是线、任意多边形，杆状、机器人臂，etc）都比较复杂，好在上面的三种情况对于一般的平面RPG游戏已经足够了。
下面的讨论中假设障碍物是多个离散的多边形，而且多边形顶点总数为n，给定起点s和终点t，s和t不在任一障碍物多边形内部（如果起点终点在障碍物内部直接可以进行判断，判断一个点是否在多边形内的算法很简单），问题是寻求s和t之间的最短路径。解决这个问题的一种方法，其思路是先求可视图，然后由可视图寻找最短路径。
（一）移动点：
先讨论两个基本问题
a. 可视图及其构造
一组多边形的可视图G=(V，E)，其中结点v∈V对应于多边形的顶点，边e∈E对应于可以互相“看见”的顶点对(u,v)。注意，边e可能与多边形边重叠，这样多边形的边也在可视图中。
从s至t的最短路径是由线段组成的一条折线，折线的两端点或者是s、t，或者是多边形的顶点，也就是说，多边形的顶点可以取为起点和终点。这样，最短路径可以看成是障碍多边形顶点的序列，或者最短路径是由可视图中边组成的序列。基于这个观察，有下面的结论：
定理1
最短路径是障碍多边形顶点可视图的一条子路径。
下面分三步证明该定理的正确性:
(1)路径是折线的。假设相反，即路径不是折线的，该路径包含弯曲部分C。这样，不可能是C的所有部分都沿着多边形边界，因为多边形边界不是弯曲的，因此，必定有一个不与任何多边形相接触并且可以用直线段代替的C的凸子部分，这与路径是最短的假设相矛盾。
(2)路径的拐弯点是多边形的顶点：自由空间中的任何拐弯可以抄近路。
(3)路径的线段是可视图的边：由可视的定义以及构成自由路径的定义可以推出。
由于可视图是有穷的，依据定理1，从s至t的最短路径必由一有穷路径集合中可以搜索得到。但该路径集合可以表示为多级多叉树结构，因此路径的数目可能以n的指数增长。为了获得有效的最短路径算法，先考虑可视图的构造。
构造一组多边形可视图的边几乎与寻找多边形对角线相同，唯一差别是：多个多边形与一个多边形，外部可视与内部可视。一种算法是对于不同多边形的每个顶点对p(k,i)和p(k+1,j)，检查线段
[1] Ghost S K, Mount D M. An output sensitive algorithm for computing visibility graphs, Proc. of Comput., 1991, 20(5):888~910
b. Dijkstra算法
假设已构造出一组多边形的可视图，在该图中如何寻找出一条最短路径，这是图论中的问题：寻找加权图中的最短路径。加权是指边的长度，在这里我们用欧几里德距离度量边的长度（当然在RPG游戏中每条路径的权可以考虑地形，可移动力等因素）。解决这个问题的一个经典算法是Dijkstra算法单源最短路径算法，这个算法大家都很熟悉了，我就不再介绍了。
至此我们得出机器人是一个点的情况下最短路径算法：
S1。构造可视图；
S2。用Dijkstra算法求s到t的最短路径；
由于已假设多边形组有n个顶点，因此图G有n个结点，并且至多有C(n,2)条边。Dijkstra算法每循环一次，处理1个结点，向已经标号的最短路径集合T中加入1条边，所以Dijkstra算法至多需要循环n次。每次循环中要检验的候选边的数目大约是0(n^2)，因为可视图可能有平方阶条边。这样，粗略分析Dijkstra算法的时间复杂性是0(n^3)。如果注意到每次循环中不必重新检验这些边，那么在0(n^2)时间内可以运行Dijkstra算法，加之可视图的构造需要 0(n^2)时间，故而有下面的定理。
定理2
在有n个顶点的多边形组中移动一个点，其最短路径可以在0(n^2)时间和空间内找到。
（二）移动圆盘
下面讨论的运动规划的算法，目的是寻找任意路径(如果一条路径存在的话)，而不是最短路径。
假设机器人R是一个中心在s，半径为ρ的圆盘，移动R一段距离之后，使R的中心位于t并且R不穿透任意障碍物。仍设障碍物是分离的多边形。如果机器人太宽，可能不能通过所指示的通道。下面的方法用于判定圆盘机器人R能否通过指定通道是非常有效的：设圆盘R的中心为r那么r不能离任意特定多边形P太近，也就是说，圆盘R在移动的过程中不可能移动到距P边的距离小于圆盘半径ρ的位置。这样，我们考虑一个扩展的障碍物P‘（P向外扩充距离ρ）以便移动点r，即将机器人R收缩成一个点，并且把障碍物向外扩充ρ。因此，上述问题化为（一）中移动点的问题。
圆盘环绕P的边界移动时，圆盘中心r留下的轨迹便是P‘的边界。如果r位于P‘的外部，那么R与P不相交；否则就相交。显然，障碍物增大之后如果通道重叠，则R无法通过所指示的路径。以上描述P‘的方式不清晰，使用两个点集的闵可夫斯基(Minkowski)和的概念来描述P‘将更明确。
给定平面上两个点集S1和S2，如果在平面上建立一个坐标系，那么便可以把点看成该坐标系中的矢量。定义S1与S2的和：
S1+S2={x+y|x∈S1, y∈S2}，
其中x+y是点x和点y的矢量和，这称为S1和S2的闵可夫斯基和。另外，点x与集合S2的闵可夫斯基和为x+S2={x+y|y∈S2}，因此，对于每个x∈S1,S1+S2 = ∪(x+S2），for each x∈S1， 是S2的复制的并。如果对数字图像处理中的形态学有印象的话可以发现，闵可夫斯基和与形态学中的扩张运算很相近。
现设S1是一个多边形P,并且S2是中心在原点的圆盘R，那么对于所有x∈P，可以把P+R看成是依据x转换的R的复制。由于R的中心在原点，x+R的中心将在x，因此P+R相当于放置中心在P的每个点之上的R的复制，故P+R是P的扩展域P‘。
给定一组离散的多边形和半径为ρ的一个圆盘，圆盘R的中心r放在始点s上，t为终点，寻找由s至t的一条路径，使得圆盘R沿该路径从s可以移动到t(即中心r落在t上)。下面叙述解决该问题的一种算法的粗略步骤。
寻找圆盘R从s移动到t的路径的算法：Top
ZhangYv（迎着朝阳,走向地狱）回复于 2003-11-16 20:35:36 得分 0
S1. 利用阂科夫斯基和及圆盘R扩大每个障碍物。
S2. 构造已扩大障碍物的并。
S3. 如果终点t与始点s位于平面上相同的部分之中，则由s至t有一条路径存在，并且通过改进可视图使之包含圆的弧可以找到最短路径；否则，s与t之间不存在路径。
这个算法的时间复杂性为0(n^2*logn)。
（三） 平移凸多边形
当机器人R是一个凸多边形时，机器人可以采取旋转的运动方式从一个位置移到另一个位置，但这里将将机器人的运动方式限制为平移。显然，凸多边形比圆盘复杂些，但利用闵可夫斯基和扩展障碍物的思想仍然有效。
在R是一个圆盘的情况下，P‘=P+R，其中"+"是闵可夫斯基和，但这个关系式在R是凸多边形的情况下不成立，这点可以举例证明（这里没法显示图形，证明略）
。这里的计算是要通过参考点r(可取凸多边形的某个固定的顶点)用R的反射取P的闵可夫斯基和。因为对于闵可夫斯基和形式来说r是原点，R的这种反射形式只不过是-R，即求反R的每个点。因此P‘‘是P+(-R)=P-R。而圆盘关于其圆心是中心对称的，R=-R，因此这个新的闵可夫斯基和形式与上讨论圆盘移动的时候的闵可夫斯基和表示是一致的。因为闵可夫斯基减法就是反射域的加法，我们仍将称它为闵可夫斯基加法。
定理3
设R是包含原点(参考点)的一个域(机器人)，而P是一个障碍物，那么在下述意义下r不可能穿透域P‘=P-R：
(1)如果平移R使得r进入P‘的内部，那么R穿透P。
(2)如果平移R使得r位于δ(P‘)上，则δ(R)与δ(P)相切，其中δ(X)表示X的边界；
(3)如果平移R使得r在P‘的外部，则R∩P=Φ。
实际上，R和P可以不是凸的，也不必是多边形。但这里的讨论仍设两者是多边形，并且R是凸的。
关于构造两个多边形的闵可夫斯基和的算法，可以参考相关的数学资料（或者计算机形态学的资料），这里不作详细介绍（不用图示很难说清楚）。
下面直接给出定理4作为结论：
定理4
如果P有n个顶点，而R的顶点数是一个常数；那么构造闵可夫斯基和P-R的时间复杂性如下:
┌──┬──┬────┬──────┐
│..R.│.P..│和的规模│.时间复杂度.│
├──┼──┼────┼──────┤
│.凸.│.凸.│..O(n)..│..O(n)......│
├──┼──┼────┼──────┤
│.凸.│非凸│..O(n)..│O(n^2*logn).│
├──┼──┼────┼──────┤
│非凸│非凸│..O(n^2)│O(n^2*logn).│
└──┴──┴────┴──────┘
下面给出凸多边形R规划运动的算法概要。设障碍物P1,P2,...Pm，共有n个顶点，算法描述如下：
S1. 增大所有的障碍物: Pi‘= Pi-R, i=1,2,..m；
S2. 构造它们的并P‘=∪Pi‘, i=1,2,...m；
S3. 寻找包含s和t的连通域，设为k；
S4. 在k中寻找s和t之间的一条路径（先建立可视图，然后用Dijkstra算法）。
定理5
设多边形障碍物顶点总数为n，机器人R为凸多边形，寻找R由起点s到终点t的平移路径在O(nlogn)时间内可以完成。如果R有k个顶点，则时间复杂性是O(knlog(kn))。
该定理由Kedem和Sharir(1990)证明，见参考论文[2]。
[2] Kedem K, Sharir M. An efficient motion planning algorithm for a convex rigid polygons object in 2-dimensional polygonal space. Disc. Comp. Geom. 1990,(5):43~75
==============================================================================
以上都是先前“数据算法版”的旧贴，不知为何后来这些好东东都没了，我把它们都整理出来了。很幸运的，我看见了以前聚集着世界级IOer的算法版，水平之高另我辈恐惧,敬佩～
唉唉，路漫漫，其修远兮...
【精华】数据结构和算法版旧的精华贴 数据结构与算法 第二帖
数据结构与算法（Ｃ++版）
算法与数据结构——高德纳的二十年计划
数据结构与算法分析 学习笔记
通过对web日志的挖掘来实现内容推荐系统 - 数据结构和算法 - Tech - JavaE...
请问如何判断2个多边形相交？ 专题开发/技术/项目 / 数据结构与算法
锁无关的数据结构与Hazard指针
有关数据结构方面的基本概念
有关数据结构方面的基本概念
数据结构排序
TIN数据结构
数据结构 课程设计
DSP算法精华资料
一个好的接口设计原则(数据结构)
Linux驱动学习 重要的数据结构
数据结构中的copy构造函数和赋值重载函数-坚强的心-搜狐博客
、《数据结构与问题求解（C++版）》，Mark Allen Weiss，清华大学出版社
搜索引擎蜘蛛的爬行规律和算法
搜索引擎蜘蛛的爬行规律和算法
本科成绩单与GPA的算法_
排序（数据结构）
《数据结构》课程教学大纲
数据结构---顺序表
排序（数据结构）