哈密顿回路

核心提示最短路径问题分两类，一类是单源最短路径问题，就是从指定顶点出发到其他各点的最短距离，还有一类是每两个顶点之间的最短距离，当然第二类也可以通过对每个顶点做一次单源最短路径求解，但是还有一种更优雅的方法（Floyd算法），这种方法一般使用相邻矩

最短路径问题分两类，一类是单源最短路径问题，就是从指定顶点出发到其他各点的最短距离，还有一类是

每两个顶点之间的最短距离，当然第二类也可以通过对每个顶点做一次单源最短路径求解，但是还有一种更优雅的方法（Floyd算法），这种方法一般使用相邻矩阵的实现方式，对每个顶点看它是不是能作为其它没两对顶点间的直接中间节点，如果能，那么再看是不是通过它的两两顶点的距离是不是减小了，若果是就更新这两对顶点间的距离，这样通过每次“贪婪的”找出局部最优解来得到全局最优解，可以算是一个动态规划的解法。

首先我们需要一个辅助类来保存距离，以及回溯路径的类：

public static class Dist implements Comparable<Dist>

{

public int preV;

public int curV;

public int distance;

public Dist(int v)

{

this.curV=v;

this.preV=-1;

this.distance=Integer.MAX_VALUE;

}

@Override

public int compareTo(Dist other) {

return distance-other.distance;

}

}

下面给出第二类最短路径的解法（Floyd算法）Java实现：

@Override

public void floyd(Dist[][] dists) {

for(int i=0;i<numVertexes;i++)

{

dists[i]=new Dist[numVertexes];

for(int j=0;j<numVertexes;j++)

{

dists[i][j]=new Dist(-1);//

dists[i][j].preV=-1;

if(i==j)

dists[i][j].distance=0;

else

dists[i][j].distance=Integer.MAX_VALUE;

}

}

for(int v=0;v<numVertexes;v++)

{

for(Edge e=firstEdge(v);isEdge(e);e=nextEdge(e))

{

int to=toVertex(e);

dists[v][to].distance=e.getWeight();

dists[v][to].preV=v;

}

}

for(int v=0;v<numVertexes;v++)

{

for(int i=0;i<numVertexes;i++)

for(int j=0;j<numVertexes;j++)

{

if((dists[i][v].distance!=Integer.MAX_VALUE)&&(dists[v][j].distance!=Integer.MAX_VALUE)&&(dists[i][v].distance+dists[v][j].distance<dists[i][j].distance))

{

dists[i][j].distance=dists[i][v].distance+dists[v][j].distance;

dists[i][j].preV=v;

}

}

}

}

public static void testFloyd() {

DefaultGraph g=new DefaultGraph(15);

g.setEdge(0, 1, 8);

g.setEdge(1, 0, 8);//its a undirected graph

g.setEdge(1, 2, 4);

g.setEdge(2, 1, 4);

g.setEdge(2, 3, 2);

g.setEdge(3, 2, 2);

g.setEdge(3, 4, 7);

g.setEdge(4, 3, 7);

g.setEdge(0, 5, 3);

g.setEdge(5, 0, 3);

g.setEdge(1, 6, 3);

g.setEdge(6, 1, 3);

g.setEdge(2, 7, 1);

g.setEdge(7, 2, 1);

g.setEdge(3, 8, 2);

g.setEdge(8, 3, 2);

g.setEdge(4, 9, 5);

g.setEdge(9, 4, 5);

g.setEdge(5, 6, 2);

g.setEdge(6, 5, 2);

g.setEdge(6, 7, 6);

g.setEdge(7, 6, 6);

g.setEdge(7, 8, 7);

g.setEdge(8, 7, 7);

g.setEdge(8, 9, 2);

g.setEdge(9, 8, 2);

g.setEdge(10, 5, 6);

g.setEdge(5, 10, 6);

g.setEdge(11, 6, 1);

g.setEdge(6, 11, 1);

g.setEdge(12, 7, 1);

g.setEdge(7, 12, 1);

g.setEdge(13, 8, 1);

g.setEdge(8, 13, 1);

g.setEdge(14, 9, 2);

g.setEdge(9, 14, 2);

g.setEdge(10, 11, 5);

g.setEdge(11, 10, 5);

g.setEdge(11, 12, 1);

g.setEdge(12, 11, 1);

g.setEdge(12, 13, 3);

g.setEdge(13, 12, 3);

g.setEdge(13, 14, 3);

g.setEdge(14, 13, 3);

g.assignLabels(new String[]{"S","B","A","C","D","E","F","G","H","I","J","K","L","M","T"});

Dist[][] dists=new Dist[15][15];

g.floyd(dists);

System.out.println("Shortes path from S-T ("+dists[0][14].distance+")is:");

Stack<String> stack=new Stack<String>();

int i=0;

int j=14;

while(j!=i)

{

stack.push(g.getVertexLabel(j));

j=dists[i][j].preV;

}

stack.push(g.getVertexLabel(i));

while(!stack.isEmpty())

{

System.out.print(stack.pop());

if(!stack.isEmpty())System.out.print("->");

}

System.out.println();

}

单源最短路径问题的解法有Dijstra提出，所以也叫Dijstra算法。

它把顶点分为两个集合一个是已求出最短距离的顶点集合V1，另一类是暂未求出的顶点集合V2，而可以证明下一个将求出来（V2中到出发点最短距离值最小）的顶点的最短路径上的顶点除了该顶点不在V1中外其余顶点都在V1中。

如此，先把出发点放入V1中（出发点的最短距离当然也就是0），然后每次选择V2中到出发点距离最短的点加入V1，并把标记改点的最短距离.直到V2中没有顶点为止，详细的形式化证明见：

Dijstra算法证明

这里的实现我们使用最小值堆来每次从V2中挑出最短距离。

先给出最小值堆的实现：

package algorithms;

import java.lang.reflect.Array;

public class MinHeap<E extends Comparable<E>>

{

private E[] values;

int len;

public MinHeap(Class<E> clazz,int num)

{

this.values=(E[])Array.newInstance(clazz,num);

len=0;

}

public final E removeMin()

{

E ret=values[0];

values[0]=values[--len];

shift_down(0);

return ret;

}

//insert to tail

public final void insert(E val)

{

values[len++]=val;

shift_up(len-1);

}

public final void rebuild()

{

int pos=(len-1)/2;

for(int i=pos;i>=0;i--)

{

shift_down(i);

}

}

public final boolean isEmpty()

{

return len==0;

}

private final void shift_up(int pos)

{

E tmp=values[pos];

int index=(pos-1)/2;

while(index>=0)

{

if(tmp.compareTo(values[index])<0)

{

values[pos]=values[index];

pos=index;

if(pos==0)break;

index=(pos-1)/2;

}

else break;

}

values[pos]=tmp;

}

private final void shift_down(int pos)

{

E tmp=values[pos];

int index=pos*2+1;//use left child

while(index<len)//until no child

{

if(index+1<len&&values[index+1].compareTo(values[index])<0)//right child is smaller

{

index+=1;//switch to right child

}

if(tmp.compareTo(values[index])>0)

{

values[pos]=values[index];

pos=index;

index=pos*2+1;

}

else

{

break;

}

}

values[pos]=tmp;

}

}

下面是基于最小值堆的最短路劲算法以及一个测试方法：

public void dijstra(int fromV,Dist[] dists)

{

MinHeap<Dist> heap=new MinHeap<Dist>(Dist.class,numVertexes*2);

for(int v=0;v<numVertexes;v++)

{

dists[v]=new Dist(v);

}

Arrays.fill(visitTags, false);

dists[fromV].distance=0;

dists[fromV].preV=-1;

heap.insert(dists[fromV]);

int num=0;

while(num<numVertexes)

{

Dist dist=heap.removeMin();

if(visitTags[dist.curV])

{

continue;

}

visitTags[dist.curV]=true;

num++;

for(Edge e=firstEdge(dist.curV);isEdge(e);e=nextEdge(e))

{

if(!visitTags[toVertex(e)]&&e.getWeight()+dist.distance<dists[toVertex(e)].distance)

{

dists[toVertex(e)].distance=e.getWeight()+dist.distance;

dists[toVertex(e)].preV=dist.curV;

heap.insert(dists[toVertex(e)]);

}

}

}

}

public static void testDijstra()

{

DefaultGraph g=new DefaultGraph(15);

g.setEdge(0, 1, 8);

g.setEdge(1, 0, 8);//its a undirected graph

g.setEdge(1, 2, 4);

g.setEdge(2, 1, 4);

g.setEdge(2, 3, 2);

g.setEdge(3, 2, 2);

g.setEdge(3, 4, 7);

g.setEdge(4, 3, 7);

g.setEdge(0, 5, 3);

g.setEdge(5, 0, 3);

g.setEdge(1, 6, 3);

g.setEdge(6, 1, 3);

g.setEdge(2, 7, 1);

g.setEdge(7, 2, 1);

g.setEdge(3, 8, 2);

g.setEdge(8, 3, 2);

g.setEdge(4, 9, 5);

g.setEdge(9, 4, 5);

g.setEdge(5, 6, 2);

g.setEdge(6, 5, 2);

g.setEdge(6, 7, 6);

g.setEdge(7, 6, 6);

g.setEdge(7, 8, 7);

g.setEdge(8, 7, 7);

g.setEdge(8, 9, 2);

g.setEdge(9, 8, 2);

g.setEdge(10, 5, 6);

g.setEdge(5, 10, 6);

g.setEdge(11, 6, 1);

g.setEdge(6, 11, 1);

g.setEdge(12, 7, 1);

g.setEdge(7, 12, 1);

g.setEdge(13, 8, 1);

g.setEdge(8, 13, 1);

g.setEdge(14, 9, 2);

g.setEdge(9, 14, 2);

g.setEdge(10, 11, 5);

g.setEdge(11, 10, 5);

g.setEdge(11, 12, 1);

g.setEdge(12, 11, 1);

g.setEdge(12, 13, 3);

g.setEdge(13, 12, 3);

g.setEdge(13, 14, 3);

g.setEdge(14, 13, 3);

g.assignLabels(new String[]{"S","B","A","C","D","E","F","G","H","I","J","K","L","M","T"});

Dist[] dists=new Dist[15];

g.dijstra(0, dists);

System.out.println("Shortes path from S-T ("+dists[14].distance+")is:");

Stack<String> stack=new Stack<String>();

for(int v=dists[14].curV;v!=-1;v=dists[v].preV)

{

stack.push(g.getVertexLabel(v));

}

while(!stack.isEmpty())

{

System.out.print(stack.pop());

if(!stack.isEmpty())System.out.print("->");

}

System.out.println();

}

1. 十进制整数转换为二进制整数

十进制整数转换为二进制整数采用"除2取余，逆序排列"法。具体做法是：用2整除十进制整数，可以得到一个商和余数；再用2去除商，又会得到一个商和余数，如此进行，直到商为0时为止，然后把先得到的余数作为二进制数的低位有效位，后得到的余数作为二进制数的高位有效位，依次排列起来。

十进制整数转二进制

如：255=（11111111）B

原理：

众所周知，二进制的基数为2，我们十进制化二进制时所除的2就是它的基数。谈到它的原理，就不得不说说关于位权的概念。某进制计数制中各位数字符号所表示的数值表示该数字符号值乘以一个与数字符号有关的常数，该常数称为 “位权 ” 。位权的大小是以基数为底，数字符号所处的位置的序号为指数的整数次幂。十进制数的百位、十位、个位、十分位的权分别是10的2次方、10的1次方、10的0次方，10的-1次方。二进制数就是2的n次幂。

按权展开求和正是非十进制化十进制的方法。

下面我们开讲原理，举个十进制整数转换为二进制整数的例子，假设十进制整数A化得的二进制数为edcba 的形式，那么用上面的方法按权展开， 得

A=a(2^0)+b(2^1)+c(2^2)+d(2^3)+e(2^4) （后面的和不正是化十进制的过程吗）

假设该数未转化为二进制,除以基数2得

A/2=a(2^0)/2+b(2^1)/2+c(2^2)/2+d(2^3)/2+e(2^4)/2

注意：a除不开二，余下了！其他的绝对能除开，因为他们都包含2，而a乘的是1，他本身绝对不包含因数2，只能余下。

商得：

b(2^0)+c(2^1)+d(2^2)+e(2^3)，再除以基数2余下了b，以此类推。

当这个数不能再被2除时，先余掉的a位数在原数低，而后来的余数数位高，所以要把所有的余数反过来写。正好是edcba

2．十进制小数转换为二进制小数

十进制小数转换成二进制小数采用"乘2取整，顺序排列"法。具体做法是：用2乘十进制小数，可以得到积，将积的整数部分取出，再用2乘余下的小数部分，又得到一个积，再将积的整数部分取出，如此进行，直到积中的小数部分为零，此时0或1为二进制的最后一位。或者达到所要求的精度为止。

然后把取出的整数部分按顺序排列起来，先取的整数作为二进制小数的高位有效位，后取的整数作为低位有效位。

十进制小数转二进制

如：0.625=（0.101）B

0.625*2=1.25======取出整数部分1

0.25*2=0.5========取出整数部分0

0.5*2=1==========取出整数部分1

再如：0.7=（0.1 0110 0110...）B

0.7*2=1.4========取出整数部分1

0.4*2=0.8========取出整数部分0

0.8*2=1.6========取出整数部分1

0.6*2=1.2========取出整数部分1

0.2*2=0.4========取出整数部分0

0.4*2=0.8========取出整数部分0

0.8*2=1.6========取出整数部分1

0.6*2=1.2========取出整数部分1

0.2*2=0.4========取出整数部分0

 
版权声明 本文仅代表作者观点，不代表本站立场。
如遇本文系为网络转载到本站发表，图片或文章有版权问题的请联系客服确认后会立即删除文章。
如遇本文系作者授权本站发表，未经许可，不得转载。

--结束END--

有问题投稿请发送至: 邮箱/kf@guangfuqiang.com    QQ/162020580

本文标题: 哈密顿回路

本文链接: https://www.guangfuqiang.com/tndb/a825132.html (转载时请保留)

网站首页

返回栏目
今日推荐
新闻举报 返回首页
更多
友情链接
鄂ICP备19019357号-22