专栏首页null的专栏数据结构和算法——用动态规划求解最短路径问题

数据结构和算法——用动态规划求解最短路径问题

一、动态规划求解问题的思路

    在《算法导论》上,动态规划的求解过程主要分为如下的四步:

  • 描述最优解的结构
  • 递归定义最优解的值
  • 按自底向上的方式计算最优解的值
  • 由计算出的结果构造一个最优解

    在利用动态规划求解的过程中值得注意的就是是否包含最优子结构,简单来讲就是一个问题的最优解是不是包含着子问题的最优解。利用求解子问题的最优解最后得到整个问题的最优解,这是利用动态规划求解问题的基本前提。

二、最短路径问题

    在http://iprai.hust.edu.cn/icl2002/algorithm/algorithm/technique/dynamic_programming/introduction.htm#example1上有一道最短路径的问题:

    现有一张地图,各结点代表城市,两结点间连线代表道路,线上数字表示城市间的距离。如图1所示,试找出从结点A到结点E的最短距离。

图 1

三、利用动态规划求解最短路径问题

    在解决这个问题的过程中,我其实是在尝试着使用不同的工具,首先我想对这种图处理,我使用了Gephi,Gephi是我在学习复杂网络的时候学会的一个工具,这个工具可以很方便的处理网络数据,能够动态的生成图的结构,下面是我用Gephi画出的图:

图 2

    Gephi的另一个比较重要的工具就是可以在生成图的过程中,将图的数据导出,导出的数据可以方便的使用。

    还是重点说说我是怎么利用动态规划的思想去求解这样的最短路径问题的:

1、描述最优解的结构

   要使得从0到10的距离最短,令

为到第

个节点的最短距离,则

,用同样的方法可以求得

等。

2、递归定义最优解的值

其中

表示与

边有连接的节点,而且

3、按自底向上的方式计算每个节点的最优值

   此时我们就得利用递归公式分别求解

,这样最终便能得到最终的解。

   结果为:

JAVA实现:

package org.algorithm.dynamicprogramming;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.Reader;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Stack;

/**
 * 利用动态规划求解最短路径问题
 * 
 * @author dell
 * 
 */

public class CalMinDistance {
	// 计算最短的距离
	public static int[] calMinDistance(int distance[][]) {
		int dist[] = new int[distance.length];
		dist[0] = 0;
		for (int i = 1; i < distance.length; i++) {
			int k = Integer.MAX_VALUE;
			for (int j = 0; j < i; j++) {
				if (distance[j][i] != 0) {
					if ((dist[j] + distance[j][i]) < k) {
						k = dist[j] + distance[j][i];
					}
				}
			}
			dist[i] = k;
		}
		return dist;
	}

	// 计算路径
	public static String calTheRoute(int distance[][], int dist[]) {
		Stack<Integer> st = new Stack<Integer>();
		StringBuffer buf = new StringBuffer();
		int j = distance.length - 1;
		st.add(j);// 将尾插入
		while (j > 0) {
			// int num = 0;
			for (int i = 0; i < j; i++) {
				if (distance[i][j] != 0) {
					// num++;
					if (dist[j] - distance[i][j] == dist[i]) {
						st.add(i);
					}
				}
			}
			j = st.peek();
		}
		while (!st.empty()) {
			buf.append(st.pop()).append("-->");
		}
		return buf.toString();
	}

	// 读取文件
	@SuppressWarnings("resource")
	public static int[][] readTheFile(File f) {
		Reader input = null;
		try {
			input = new FileReader(f);
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		BufferedReader buf = null;
		buf = new BufferedReader(input);
		List<String> list = new ArrayList<String>();
		try {
			String str = buf.readLine();
			while (str != null) {
				list.add(str);
				str = buf.readLine();
			}
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}

		Iterator<String> it = list.iterator();
		int distance[][] = new int[11][11];
		while (it.hasNext()) {
			String str1[] = it.next().split(",");
			int i = Integer.parseInt(str1[0]);
			int j = Integer.parseInt(str1[1]);
			distance[i - 1][j - 1] = Integer.parseInt(str1[2]);
		}
		return distance;

	}

	public static void main(String args[]) {
		// 读文件
		File f = new File("D:" + File.separator + "distance_1.csv");
		int distance[][] = readTheFile(f);
		int dist[] = calMinDistance(distance);
		System.out.println("最短路径长度为:" + dist[distance.length - 1]);
		System.out.println("最短路径为:" + calTheRoute(distance, dist));
	}
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 数据结构和算法——用动态规划求解最短路径问题

    一、动态规划求解问题的思路     在《算法导论》上,动态规划的求解过程主要分为如下的四步: 描述最优解的结构 递归定义最优解的值 按自底向上的方式计算最优解的...

    zhaozhiyong
  • 数据结构和算法——动态规划

    一、动态规划的思想     动态规划(dynamic programming)是一种算法设计的思想,主要是将一个问题划分成几个更小的问题,并对这样更小的问题进行...

    zhaozhiyong
  • 数据结构和算法——动态规划

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    zhaozhiyong
  • 数据结构和算法——用动态规划求解最短路径问题

    一、动态规划求解问题的思路     在《算法导论》上,动态规划的求解过程主要分为如下的四步: 描述最优解的结构 递归定义最优解的值 按自底向上的方式计算最优解的...

    zhaozhiyong
  • Codeforces Round #491 (Div. 2)部分题解

    attack
  • UVA Dividing coins

    题目链接: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page...

    ShenduCC
  • P1824 进击的奶牛

    题目描述 Farmer John建造了一个有N(2<=N<=100,000)个隔间的牛棚,这些隔间分布在一条直线上,坐标是x1,...,xN (0<=xi<=1...

    attack
  • ZOJ 3631 Watashi's BG(01dp)

    01dp不过由于数组过于大,开不开,学了搜索过了,先记录下 还有一种方法 #include<stdio.h> #include<algorithm> using...

    用户1624346
  • POJ 刷题系列:1083. Moving Tables

    POJ 刷题系列:1083. Moving Tables 传送门:POJ 1083. Moving Tables 题意: 一条走廊,两栏房间。搬运工每次从房价...

    用户1147447
  • P3834 【模板】可持久化线段树 1(主席树) (多次查询第k大或第k小)

    用户2965768

扫码关注云+社区

领取腾讯云代金券