比较各种Dijkstra最短路算法的matlab代码

整整一天,我都在网络上寻找Dijkstra算法的matlab代码。我找到了许多,然而,它们全部都不能满足我的需要。
后来我只好参考wiki给出的正确的dijkstra算法,自己写了个代码。wiki给出的算法在此:
http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
摘录如下。

1 function Dijkstra(Graph, source):
2 for each vertex v in Graph: // Initializations
3 dist[v] := infinity // Unknown distance function from source to v
4 previous[v] := undefined // Previous node in optimal path from source
5 dist[source] := 0 // Distance from source to source
6 Q := the set of all nodes in Graph
// All nodes in the graph are unoptimized – thus are in Q
7 while Q is not empty: // The main loop
8 u := vertex in Q with smallest dist[]
9 if dist[u] = infinity:
10 break // all remaining vertices are inaccessible
11 remove u from Q
12 for each neighbor v of u: // where v has not yet been removed from Q.
13 alt := dist[u] + dist_between(u, v)
14 if alt < dist[v]: // Relax (u,v,a)
15 dist[v] := alt
16 previous[v] := u
17 return previous[]

作为教训,我总结一下网络上能找到的大多数dijkstra算法的matlab代码的优劣。
1.“Dijkstra最短路算法通用Matlab程序”
这套代码可以说是国内传播最广的dijkstra算法的matla实现,可以在许多网站找到,例如这里:
http://www.labfans.com/bbs/t3095/
它的输入是赋权邻接矩阵和起始点,输出是起始点到各点的距离和最短路树。代码在这里
然而!它是错的!
用这套代码可以得出起始点到各点的距离,然而算法得出的最短路树完全是错的,甚至用示例数据得到的最短路树都根本不可理解。算法根本就没按正确的dijksta算法的思路走。
2.Dijkstra 算法 matlab程序
这套算法也流传甚广,链接在这里:
http://www.9414.net/Article/jsjjjs/biafh/200504/735.html
这套算法很简短,功能也很简单。它的输入是赋权邻接矩阵,输出是起始点到各点的距离和最短路树。使用示例数据可以得到正确的结果。缺点是它仅能算出从点1到其他各点的距离。
代码在这里
后来我又发现了第二个缺点:这算法也是错的。从根本上就是错的,只是恰好能把示例数据算对而已。
3~4.来自mathworks的各种dijkstra代码
它们应该都是对的,然而太复杂,不适合我的应用;它们各自具有其应用范围,我没有依次尝试,就放在这里而已。
代码A只能提供从某点到某点的距离,然而不提供从某点到其它任意点的最短路树。
代码B能够提供从某点到其它任意点的最短路树,但是它是基于地图的,需要提供每个点的坐标。
5.正确的,可以给出从某点到其它任意点的最短路树的dijkstra算法代码
我写的,应该没问题了。
输入是赋权邻接矩阵和起始点,输出起始点到其他各点的距离和最短路树。
代码在此

数据预处理初见成果

在长达数月的时间里,我都在与java和oracle搏斗。开始的时候,把所有数据直接写进数据库,一天的数据要算大半天。往后一点,先进行预处理再写进去,需要六小时左右。再后来,换了一台更好的电脑,同时发现一个巨大bug,于是一个正面因素和一个反面因素导致我的程序还是得运行五六个小时。
直到今天。
上周基本上都在赋闲状态,因为实在被自己的程序折磨惨了。用了Jprofile优化程序,却发现绝大多数的时间都花在读文件和写数据库的过程中。跟导师说实在是没有进一步优化的空间了,导师说那就把这两个过程优化下呗,总是有法子的。
好吧,他是对的。
我从那天起才开始认识到,其实这两个过程也是可以优化的啊。读文件慢,因为我是一个变量一个变量地读。查了查资料,网上说你可以一下子读几个k么。写数据库确实慢,我大不了直接写进文件里去嘛。
于是我花了大约大半个小时,把读文件的过程重写了一遍,然后删除了所有跟数据库有关的代码。
我计算了一天的数据,居然只需要11分钟!!!!
这是个重要的启示。
无论如何,太阳终于出来了。

JProbe Plugins for Eclipse 安装体验

JProbe Version: 8.1.0
软件简介:一款Java代码、内存和覆盖率分析工具。
主要特性:覆盖浏览器和源代码视图-快速分离未检测代码和死代码;
批处理模式-能以批处理模式运行,方便的集成建立/测试系统;
报表-以XML、纯文本、CSV或者HTML格式输出覆盖范围报告,用以定制分析;
快照合并-合并多个平台运行的整个覆盖数据;
Eclipse IDE集成,提供了Eclipse插件,可在Eclipse中直接进行内存分析和代码覆盖率测试。
下载:
JProbe for AIX – BIN Format
JProbe for Linux for x86 and x64 – BIN Format
JProbe for Solaris – BIN Format
JProbe for Solaris x86 – BIN Format
JProbe for Windows – EXE Format
JProbe Plugins for Eclipse
JProbe Installation Guide
JProbe Release Notes
JProbe User Guide
JProbe Reference Guide
JProbe Plugins for Eclipse Guide
JProbe Demos and Tutorials
破解方法(请使用正版软件):
安装Jprobe后,
方法1:替换client-support.jar目录中的\com\sitraka\licensing\ValidateSignature.class文件。
方法2:替换client-support.jar目录中的\com\sitraka\licensing\ LicenseProperties.class文件。
破解文件:
Jprobe_v8.0.0_Crack
JProbe.Suite.v8.1.0.Cracked-FALLEN

按照说明,这似乎是个有用的东西。等我试用之后才能确定。
然而,安装过程实在太麻烦了。
体会1:插件其实是不能单独安装的。必须同时安装软件本身和插件。有消息说只用插件不需要注册码,但我尝试的结果是不注册不能用。网上找不到8.1版本的密钥,所以不建议安装8.1版本。8.0即可。
体会2:虽然User Guide里面给出了详细的使用说明,但我使用这个插件的过程还是困难无比。核心部分在于,在敲所有命令的时候,一定不能用键盘上的空格。必须把有空格的目录名复制粘贴。这一点折磨了我整个晚上。
网上给出的注册码使用过程是这样的:首先将crack中提供的jar文件复制到jprobe安装目录,然后运行console程序,将crack中的license加进去即可。

近日的工作进展:21st-25th

5月21日

写代码!
读数据流程:
1. 从文件到表,直接读入。以天为单位。保留一个最终的“目前在线”。
2. 统计用户。更新用户表。
3. 确定时间间隔,区分会话。
4. 区分行为。

5月22日

使用read(byte[])读入数据,而后使用函数byte2int()和int2ip(),int2date()等做转换。用reverse()函数将byte[]倒过来。
连接Oracle数据库,使用PreparedStatement类执行SQL语句。conn.prepareStatement一次语句可以用无限次,每次只需要重新设定?的值。
每条数据写完后addBatch(),数量攒到差不多的时候再executeBatch(),等到全都做完再commit.
PreparedStatement和Connection用完了要记得close()一下。
该好好学SQL了……虽然就那么几句,可是妙用无穷啊。
Oracle跟Java的数据类型差异:使用Timestamp和Number,放弃boolean。

5月25日

尝试AddBatch()和ExecuteBatch()。
读入100万条,每500条提交一次,所需时间为302031ms,即约5分钟。
将所有数据删除过程也为约5分钟……
此时数据库文件夹848M。删除所有100万条数据后为1.01G……由于出现了新的undo文件。
读入数据3000万条,耗时9414609ms即2.6h。每1000条提交一次。最后才commit一次。
每条0.31ms,每秒3200条。
最后一条记录时间为下午1点29分。
3.83G。还可以接受。

数据读入模块代码

import java.io.*;
import java.util.Date;
import java.text.SimpleDateFormat;
import java.sql.*;
import oracle.jdbc.driver.*;
public class read{
Connection conn;
public void FileRead(String f) throws IOException
{
Date StartTime=new Date();
FileInputStream fin = new FileInputStream(f);
converter C=new converter();
byte[] head=new byte[20];
byte[] Bip1=new byte[4];
byte[] Bip2=new byte[4];
byte[] Bport1=new byte[2];
byte[] Bport2=new byte[2];
byte[] Bendtype=new byte[1];
byte[] Bconnecttype=new byte[1];
byte[] Bempty1=new byte[2];
byte[] Btime1=new byte[4];
byte[] Btime2=new byte[4];
byte[] Binpack=new byte[4];
byte[] Boutpack=new byte[4];
byte[] Binbyte=new byte[4];
byte[] Boutbyte=new byte[4];
byte[] Bidl=new byte[1];
byte[] Bempty2=new byte[11];
StringBuilder ip1=new StringBuilder(15);
StringBuilder ip2=new StringBuilder(15);
int port1, port2, endtype, inpack, outpack, inbyte, outbyte;
boolean connecttype,idl;
Date time1=new Date();
Date time2=new Date();
SimpleDateFormat DF=new SimpleDateFormat();
DF.applyPattern(“yyyy.MM.dd HH:mm:ss”);
fin.read(head); //文件头
long N=0; //记录条数
PreparedStatement tt;
try
{
tt=conn.prepareStatement(“INSERT INTO ORIGINDATA1 VALUES(?,?,?,?,?,?,?,?,?,?,?,?,?,?)”);
while(fin.read(Bip1)!=-1&&N<30000000)
{
fin.read(Bip2);
fin.read(Bport1);
fin.read(Bport2);
fin.read(Bendtype);
fin.read(Bconnecttype);
fin.read(Bempty1);
fin.read(Btime1);
fin.read(Btime2);
fin.read(Binpack);
fin.read(Boutpack);
fin.read(Binbyte);
fin.read(Boutbyte);
fin.read(Bidl);
fin.read(Bempty2);
ip1.delete(0, 15);
ip1.append(C.int2IP(C.byte2int(C.reverse(Bip1))));
ip2.delete(0, 15);
ip2.append(C.int2IP(C.byte2int(C.reverse(Bip2))));
port1=C.short2int(C.byte2short(C.reverse(Bport1)));
port2=C.short2int(C.byte2short(C.reverse(Bport2)));
endtype=(int)Bendtype[0];
connecttype=C.byte2bool(Bconnecttype);
time1=C.int2Date(C.byte2int(Btime1));
time2=C.int2Date(C.byte2int(Btime2));
inpack=C.byte2int(Binpack);
outpack=C.byte2int(Boutpack);
inbyte=C.byte2int(Binbyte);
outbyte=C.byte2int(Boutbyte);
idl=C.byte2bool(Bidl);
N++;
/*
if (N%1000>0)
{
System.out.println(N);
System.out.print(ip1);
System.out.print(” “);
System.out.print(ip2);
System.out.print(” “);
System.out.print(port1);
System.out.print(” “);
System.out.print(port2);
System.out.print(” “);
System.out.print(endtype);
System.out.print(” “);
System.out.print(connecttype);
System.out.print(” “);
System.out.print(DF.format(time1));
System.out.print(” “);
System.out.print(DF.format(time2));
System.out.print(” “);
System.out.print(inpack);
System.out.print(” “);
System.out.print(outpack);
System.out.print(” “);
System.out.print(inbyte);
System.out.print(” “);
System.out.print(outbyte);
System.out.print(” “);
System.out.print(idl);
System.out.println();
}
*/
tt.setLong(1, N);
tt.setString(2, ip1.toString());
tt.setString(3, ip2.toString());
tt.setInt(4, port1);
tt.setInt(5, port2);
tt.setInt(6, endtype);
tt.setInt(7, C.bool2int(connecttype));
tt.setTimestamp(8, new java.sql.Timestamp(time1.getTime()));
tt.setTimestamp(9, new java.sql.Timestamp(time2.getTime()));
tt.setLong(10, inpack);
tt.setLong(11, outpack);
tt.setLong(12, inbyte);
tt.setLong(13, outbyte);
tt.setInt(14, C.bool2int(idl));
tt.addBatch();
if(N%1000==0)
{
tt.executeBatch();
System.out.print(N);
System.out.print(”  “);
System.out.println(new Date());
}
}
tt.executeBatch();
conn.commit();
System.out.print(N);
System.out.println(new Date());
tt.close();
conn.close();
fin.close();
Date EndTime=new Date();
System.out.println(EndTime.getTime()-StartTime.getTime());
}
catch (SQLException e)
{
System.out.println(e);
}
}
public void read(){}
public void initialize() throws Exception
{
DriverManager.registerDriver(new oracle.jdbc.driver.OracleDriver());
conn=DriverManager.getConnection(“jdbc:oracle:thin:@192.168.75.128:1521:flow”,”sysman”,”********”);
conn.setAutoCommit(false);
System.out.println(“Connected!!”);
}
public void closeDB() throws Exception
{
conn.close();
conn=null;
}
public static void main(String[] args)
{
String Fi=”E:\\log\\20090408\\NetFlow20090408_connect.log”;
read r=new read();
try
{
r.initialize();
}
catch(Exception e)
{System.out.println(e);}
try
{
r.FileRead(Fi);
}
catch(IOException e)
{System.out.println(e);}
try
{
r.closeDB();
}
catch(Exception e)
{System.out.println(e);}
}
}

人工神经网络算法应用

同样是廖貅武教授的软计算方法课程作业。两个小作业之一。考虑到上一个遗传算法的作业做得实在太没有含量了,我决定把这个人工神经网络做得原创性高一点。
于是,OK,我就原创一个题目吧。
问题:
    给定一个超越函数在某些采样点的取值,使用人工神经网络模拟出这个超越函数。以Matlab自带的函数peaks()为例。peaks()在[0,30]的图像如下:

数据:
    产生一个数组r,结构为3*300,内容为从peaks()上随机采样的300个点的x,y,z坐标。我将把x,y坐标作为输入变量,z坐标作为输出变量构建一个BP人工神经网络。结构如下:
 
工具:
    Matlab 6.5+神经网络工具箱。
    这里出现了我遇到的最大教训。教训是:装软件一定要装完整版。我开始写了个ANN的程序,结果发现运行不了,提示函数未知。我以为要加载个什么工具包,于是在整个网络上搜,搜了两小时也没搜出来,似乎所有人都直接用了,根本不存在什么加载或调用的问题。然后,我才认识到我的matlab是个不完整版,没有NN工具包……我愤而下载了一个Matlab7,决意把这可恶的6.5彻底抛弃。然后……花了一小时下载的M7居然不能装!原因未知!我只好又花了半小时下了一个matlab6.5的完整版,这才把问题解决。
细节不再赘述,直接上程序。
 
train.m:训练函数
load r.mat;
[P,minp,maxp,T,mint,maxt]=premnmx(r(1:2,:),r(3,:));
 
%建立网络
S=6; %隐含神经元数
L=1; %输出神经元数
net=newff([minp,maxp],[S,L],{‘logsig’,’tansig’,’purelin’},’traincgb’,’learngdm’);
 
%初始化
net=init(net);
 
%网络训练
net.trainParam.show=20;%设置训练显示间隔次数
net.trainParam.epochs=600;%设置最大训练循环次数
net.trainParam.goal=0.0001;%设置性能目标值
net.trainParam.lr=0.1;%设置学习系数
[net,tr]=train(net,P,T);%网络训练
 
test.m:测试函数
te=[0 0];
for i=0:30;
for j=0:30;
tt=[i j];
te=[te;tt];
end;
end;
fi=sim(net,te’);
aa=zeros(30,30);
s=1;
for i=1:31;
for j=1:31;
aa(i,j)=fi(s);
s=s+1;
end;
end;
mesh(aa);
 
运算结果:
 
训练效果

绘制出神经网络所模拟的函数图像:

 
    经过多次计算,发现每次计算绘出的函数图样差异较大,同时与peaks函数本身也有较大的差异。
    运用人工神经网络算法对此超越函数的模拟效果较差,可能是由于多个原因。首先,对函数值的随机采样可能没有体现函数的全部特征;其次,神经网络结构较为简单,可能难以模拟一个如此复杂的函数;第三,输入变量较少,可能不适合使用神经网络进行计算。
 
=====================郁闷的分割线======================
就这样,我发现人工神经网络根本模拟不出这个复杂的peaks函数……可能是这神经网络的智商太低,也可能是我的智商问题……不过,反正是交作业,这也无所谓。

简单的遗传算法应用

  廖貅武教授的软计算方法课程,作业包括两个小作业和一个大作业。这是其中的一个小作业,花费时间大约2.5h。
  考虑到我是以一种应付差事的心态来做作业,因而我选择了一种最省力最没有技术含量的方法。使用Matlab的GAOT工具箱。
  基于Matlab的遗传算法工具箱有好多种,是不同的人在不同的时间开发的,现在已知的有:
  (1)GAOT,中国学术期刊网上大部分研究遗传算法的中文论文都是使用的这个工具箱这个工具箱用的似乎是最广的,虽然不是Matlab自带的,但在网上也很容易下载到。然而它的版本实在是太老了,是适用于Matlab5.0版的,因为它的全名是The Genetic Algorithm Optimization Toolbox (GAOT) for Matlab 5,而且似乎到目前为止还没有更新版本发布。
  (2)SGALAB 是在研学论坛上看到的,我对它并不了解,只是知道个名字而已,研学论坛的”遗传算法”板上有一些帖子是介绍这个工具箱的,有兴趣的话可以去看看。
  (3)GADS 这个是Matlab7.0版本自带的工具箱,全名叫Genetic Algorithm and Direct Search Toolbox。在Matlab7.0的Help里面有对这个工具箱的详细介绍,还有很多例子作演示。
  GAOT工具箱可以在http://www.ise.ncsu.edu/mirage/GAToolBox/gaot/ 下载。按照其中的readme所说,将压缩包解压到任意目录,然后在matlab的命令行输入如 >>path(path,’E:/GAToolBox/gaot’); ,其中引号内部分改为你的gaot文件夹位置。然后GAOT工具箱就可用了。
  GAOT工具箱中有一个求函数f(x)=x+10*sin(5*x)+7*cos(4*x)最大值的示例,网上讲GAOT的中文资料几乎全都拿这个例子来说事。考虑到作业应该有那么一点原创性,因而我把它改成了求f(x)=x+30*sin(0.5x)+16*cos(0.4x)的最大值……
  建立m文件fitness.m,内容为
    function[sol,eval]=fitness(sol,options)
    x=sol(1);
    eval=x+30*sin(0.5*x)+16*cos(0.4*x);
  建立m文件Gene.m,内容为
    initPop=initializega(20,[0 100],’fitness’);%生成初始种群,大小为20
    [x endPop,bPop,trace]=ga([0 100],’fitness’,[],initPop,[1e-4 1 1], ‘maxGenTerm’, 100, ‘normGeomSelect’,…
    [0.08],[‘arithXover’],[2],’nonUnifMutation’,[2 100 3])
  运行Gene.m,结果就出来了。
  Plot(:,2:3);就画出了历史最优值和当前代最优值的曲线。计算出最优结果为
  x = 91.9436 129.0239
即当x= 91.9436时,有最大值129.0239。

image002

  附上关于GAOT的简易说明:
核心函数:
(1)function [pop]=initializega(num,bounds,eevalFN,eevalOps,options)–初始种群的生成函数
【输出参数】
pop–生成的初始种群
【输入参数】
num–种群中的个体数目
bounds–代表变量的上下界的矩阵
eevalFN–适应度函数
eevalOps–传递给适应度函数的参数
options–选择编码形式(浮点编码或是二进制编码)[precision F_or_B],如
precision–变量进行二进制编码时指定的精度
F_or_B–为1时选择浮点编码,否则为二进制编码,由precision指定精度)
(2)function [x,endPop,bPop,traceInfo] = ga(bounds,evalFN,evalOps,startPop,opts,…
termFN,termOps,selectFN,selectOps,xOverFNs,xOverOps,mutFNs,mutOps)–遗传算法函数
【输出参数】
x–求得的最优解
endPop–最终得到的种群
bPop–最优种群的一个搜索轨迹
【输入参数】
bounds–代表变量上下界的矩阵
evalFN–适应度函数
evalOps–传递给适应度函数的参数
startPop-初始种群
opts[epsilon prob_ops display]–opts(1:2)等同于initializega的options参数,第三个参数控制是否输出,一般为0。如[1e-6 1 0]
termFN–终止函数的名称,如[maxGenTerm]
termOps–传递个终止函数的参数,如[100]
selectFN–选择函数的名称,如[normGeomSelect]
selectOps–传递个选择函数的参数,如[0.08]
xOverFNs–交*函数名称表,以空格分开,如[arithXover heuristicXover simpleXover]
xOverOps–传递给交*函数的参数表,如[2 02 32 0]
mutFNs–变异函数表,如[boundaryMutation multiNonUnifMutation nonUnifMutation unifMutation]
mutOps–传递给交*函数的参数表,如[4 0 06 100 34 100 34 0 0]