數(shù)據(jù)結(jié)構(gòu)和算法—用動(dòng)態(tài)規(guī)劃求解最短路徑問題

在利用動(dòng)態(tài)規(guī)劃求解的過程中值得注意的就是是否包含最優(yōu)子結(jié)構(gòu)，簡(jiǎn)單來(lái)講就是一個(gè)問題的最優(yōu)解是不是包含著子問題的最優(yōu)解。利用求解子問題的最優(yōu)解最后得到整個(gè)問題的最優(yōu)解，這是利用動(dòng)態(tài)規(guī)劃求解問題的基本前提。
二、最短路徑問題
    現(xiàn)有一張地圖，各結(jié)點(diǎn)代表城市，兩結(jié)點(diǎn)間連線代表道路，線上數(shù)字表示城市間的距離。如圖1所示，試找出從結(jié)點(diǎn)A到結(jié)點(diǎn)E的最短距離。

圖 1
三、利用動(dòng)態(tài)規(guī)劃求解最短路徑問題
    數(shù)據(jù)結(jié)構(gòu)和算法—用動(dòng)態(tài)規(guī)劃求解最短路徑問題

在解決這個(gè)問題的過程中，我其實(shí)是在嘗試著使用不同的工具，首先我想對(duì)這種圖處理，我使用了Gephi，Gephi是我在學(xué)習(xí)復(fù)雜網(wǎng)絡(luò)的時(shí)候?qū)W會(huì)的一個(gè)工具，這個(gè)工具可以很方便的處理網(wǎng)絡(luò)數(shù)據(jù)，能夠動(dòng)態(tài)的生成圖的結(jié)構(gòu)，下面是我用Gephi畫出的圖：

圖 2
    Gephi的另一個(gè)比較重要的工具就是可以在生成圖的過程中，將圖的數(shù)據(jù)導(dǎo)出，導(dǎo)出的數(shù)據(jù)可以方便的使用。
    還是重點(diǎn)說說我是怎么利用動(dòng)態(tài)規(guī)劃的思想去求解這樣的最短路徑問題的：
1、描述最優(yōu)解的結(jié)構(gòu)
   要使得從0到10的距離最短，令為到第個(gè)節(jié)點(diǎn)的最短距離，則，用同樣的方法可以求得等。數(shù)據(jù)分析師培訓(xùn)
2、遞歸定義最優(yōu)解的值

其中表示與邊有連接的節(jié)點(diǎn)，而且。
3、按自底向上的方式計(jì)算每個(gè)節(jié)點(diǎn)的最優(yōu)值
   此時(shí)我們就得利用遞歸公式分別求解，這樣最終便能得到最終的解。
   結(jié)果為：

JAVA實(shí)現(xiàn)：
[java] view plain copy 在CODE上查看代碼片派生到我的代碼片
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;  
 
/**
 * 利用動(dòng)態(tài)規(guī)劃求解最短路徑問題
 *  
 * @author dell
 *  
 */  
 
public class CalMinDistance {  
    // 計(jì)算最短的距離  
    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;  
    }  
 
    // 計(jì)算路徑  
    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("最短路徑長(zhǎng)度為：" + dist[distance.length - 1]);  
        System.out.println("最短路徑為：" + calTheRoute(distance, dist));  
    }  
}