IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 动态规划|最短Hamilton路径 -> 正文阅读

[数据结构与算法]动态规划|最短Hamilton路径

2022年12月22日11:23:10

“n个点,从0开始,到n结束,求涵盖所有点的最短路径”
有n个点,有n!条路径可以选择,不过题目中要求是0开始,n-1点结束,因此一共是(n-2)!条路径,在(n-2)!条路径中选择一条最短的路径即为答案,但是时间复杂度太高了。

使用动态规划来减少重复。

设w[][]为图的邻接表,用以表示点与点之间的权值;

f[j]为终点为j时的所有路线的集合(起点先不关注),而终点为j时,前面点的数量还是没有确定的,需要进行确定才可以进一步减少集合的范围。此时引入一个路径状态state[],即终点为j时,前面走了几个点,走了哪些点,这样的话,f[j]的集合就划分的比较小了,可以思考如何转移状态了。
举个具体的路径看看如何转移:有这么一条路径,我称之为f[j],这条路径走到了点j,状态为state[]{1,3,6,7,j},说明此时j前面走过1,3,6,7这四个点,而这四个点的顺序并未定下来,这四个点每个点可以作为j前一步的点(设为k)。也就j前有这么四种情况:(x,x,x指的是除k外的另3个数)
x,x,x,1,j
x,x,x,3,j
x,x,x,6,j
x,x,x,7,j
因此只要知道哪个k的路径最短,即
x,x,x,1
x,x,x,3
x,x,x,6
x,x,x,7
那么f[k]+w[k][j]就是最短的f[j]。

这里的f[k]是指在状态state[]{x,x,x,k}时的f[k]
那么状态转移方程如下:
f[j] = f[k] + w[k][j]

其中:
j的路径状态state{1,3,6,7,j};
k的路径状态state{x,x,x,k}

这样看来是有点麻烦,状态表示还需要用二维数组去存储,不如把状态压缩一下,使用二进制位表示状态。即如果第x个点在路径上,则在二进制位上,第x个位置为1。

eg.state{1,3,6,7}表示为1100101,十进制是101
然后使用二维数组f[i][j]表示,就可以表示为f[101][7],101是状态,7是最后一个点。

这样上面的转移方程就可以写成
f[i][j] = f[i-(1<<j)][k] + w[k][j];
其中i-(1<<j)是指把i这个数上面二进制位中的第j位的1减掉,把路径状态变成k的;就好比把state{1,3,6,7,j}中的j去掉,成为点7的路径状态了,即state{1,3,6,7}。

由于f[i][j]依赖于f[i-(1<<j)][k],而i-(1<<j)≤i,因此需要先对i进行遍历。

f[i][j]中不止有一个k,因此需要循环所有的k进行比较,求得最少值,落到代码实现上面时,f[i][j]的初始值应该为一个非常大的值才好,这样求min时方便把初始值覆盖掉。
好了,马上要结束了,现在关注一下初始化的问题,由于题目中要求从点0开始,而不能是任意点开始,因此把f[1][0]设为0,其他的初始值为MAX_VALUE就可了。

Java 代码

import java.util.*;

/**
 * @desc 使用acwing(oj)用的模板
 */
public class Main {

    //定义容器、常数、读入
    int[][] w;
    int[][] f = new int[1<<21][21];
    Scanner jin = new Scanner(System.in);

    //oj要用的main方法
    public static void main(String[] args) {new Main().run();}//在oj中调用题解方法

    void run() {
        
        //读入题目数据
        int n = jin.nextInt();
        w = new int[n+1][n+1];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                w[i][j] = jin.nextInt();
            }
        }
        for(int i = 0; i < 1<<n; i++){
            for(int j = 0; j < n; j++){
                f[i][j] = Integer.MAX_VALUE>>1;
            }
        }        

        //调用解题方法
        int res = dp(n);
        //输出题解答案
        System.out.println(res);
    }



    int dp(int n) {
        f[1][0] = 0;
        for(int i = 0; i < 1<<n; i++){
            for(int j = 0; j < n; j++){
                if ((i >> j & 1) == 1){//点j必须在路径里面才可以
                    for(int k = 0; k < n; k++){
                        if(((i - (1 << j)) >> k & 1) == 1){//寻找一个k点,k必须存在于i中
                            f[i][j] = Math.min(f[i][j], f[i - (1 << j)][k] + w[k][j]);
                        }
                    }
                }
            }
        }

        return f[(1<<n)-1][n-1];
    }
}


  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-12-25 11:33:24  更:2022-12-25 11:38:37 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年5日历 -2024/5/25 12:01:56-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码