精华内容
下载资源
问答
  • 题目大意:给定一个 N 个点的无向,点有点权,求从 0 号点走到 N-1 号点的最短哈密顿路径是多少。 题解:由于哈密顿路径的定义是每个顶点必须经过且仅能经过一次,因此,可用当前是否经过了这些点和当前在哪个点来...

    题目大意:给定一个 N 个点的无向图,点有点权,求从 0 号点走到 N-1 号点的最短哈密顿路径是多少。

    题解:由于哈密顿路径的定义是每个顶点必须经过且仅能经过一次,因此,可用当前是否经过了这些点和当前在哪个点来表示出一个状态,则一共有 \(O(n2^n)\) 个状态。考虑转移方式,对于在 j 这个点的情况来说,可以从以下与 j 相邻的节点 k 转移来,k 必须满足在当前状态已经走到。因此,时间复杂度为 \(O(n^22^n)\)

    update at 2019.3.29
    注意,由于状态转移方程为 \[dp[i][S]=min\{dp[k][S']+dis(i,k)\},k\in [1,n],S'\subset S\],从中可以看出 i 的决策是不具有阶段性的,即:i 并不是从小到大进行的,而对于集合来说是从小到大进行转移的,因此应该以走过的点的集合作为阶段,即:集合应该是循环的第一层。今天被这个搞到自闭了。。QAQ

    代码如下

    #include <bits/stdc++.h>
    using namespace std;
    
    int dp[1<<20][20];
    int n,G[20][20];
    
    int main(){
        scanf("%d",&n);
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                scanf("%d",&G[i][j]);
        memset(dp,0x3f,sizeof(dp));
        dp[1][0]=0;
        for(int i=1;i<1<<n;i++)
            for(int j=0;j<n;j++)if(i>>j&1)
                for(int k=0;k<n;k++)if((i^1<<j)>>k&1)
                    dp[i][j]=min(dp[i][j],dp[i^1<<j][k]+G[k][j]);
        printf("%d\n",dp[(1<<n)-1][n-1]);
        return 0;
    }

    转载于:https://www.cnblogs.com/wzj-xhjbk/p/10552681.html

    展开全文
  • 题意:给副n点的无向(完全),求从点0到n-1的最短哈密顿路径 思路:状压DP入门题,这题的子问题其实是每点的使用状况,这种集合类的DP一般都是状压DP,所以我们用dp[i][j]表示当前在第i点的时候,所有...

    题意:给一副n个点的无向图(完全图),求从点0到n-1的最短哈密顿路径

    思路:状压DP入门题,这题的子问题其实是每个点的使用状况,这种集合类的DP一般都是状压DP,所以我们用dp[i][j]表示当前在第i个点的时候,所有的点的使用状况,先枚举状态,然后枚举当前的点,再在剩下的点中枚举尚未使用过的点,复杂度O(n^2 * 2^n)

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    
    using namespace std;
    int a[25][25];
    int dp[22][1<<20];//当前第i个点,20个点的经过状态
    int main()
    {
       int n;
       cin>>n;
       memset(dp,0x3f,sizeof(dp));
       dp[1][1]=0;
       for(int i=1;i<=n;++i)
           for(int j=1;j<=n;++j)
               cin>>a[i][j];
       for(int i=1;i<(1<<n);++i)
       {
           for(int j=1;j<=n;++j)
           {
              if(i&(1<<j-1))
              {
                 for(int k=1;k<=n;++k)
                 {
                    if(!(i&(1<<k-1)))
                        dp[k][i|(1<<k-1)]=min(dp[k][i|(1<<k-1)],dp[j][i]+a[j][k]); 
                 } 
              } 
           } 
       } 
       cout<<dp[n][(1<<n)-1]<<endl;
       return 0; 
    }
    
    展开全文
  • 最短Hamilton路径

    2020-07-17 08:33:20
    给定一张nn点的带权无向,点 0~n-1 标号,起点 0 到终点 n-1 的最短Hamilton路径。 Hamilton路径的定义是 0 到 n-1 不重不漏地经过每点恰好次。 输入格式 第输入整数nn。 接下来nn行每行nn...

    给定一张 nn 个点的带权无向图,点从 0~n-1 标号,求起点 0 到终点 n-1 的最短Hamilton路径。 Hamilton路径的定义是从 0 到 n-1 不重不漏地经过每个点恰好一次。

    输入格式

    第一行输入整数nn。

    接下来nn行每行nn个整数,其中第ii行第jj个整数表示点ii到jj的距离(记为a[i,j])。

    对于任意的x,y,zx,y,z,数据保证 a[x,x]=0,a[x,y]=a[y,x] 并且 a[x,y]+a[y,z]>=a[x,z]。

    输出格式

    输出一个整数,表示最短Hamilton路径的长度。

    数据范围

    1≤n≤201≤n≤20
    0≤a[i,j]≤1070≤a[i,j]≤107

    输入样例:

    5
    0 2 4 5 1
    2 0 6 5 3
    4 6 0 8 3
    5 5 8 0 5
    1 3 3 5 0
    

    输出样例:

    18
    #include<iostream>
    #include<cstring>
    using namespace std;
    const int INF = 0x3f;
    
    const int N=20,M=1<<20;
    int f[M][N],weight[N][N];
    //哈密顿图最短路径:无向有权图,从0号点走到n-1号点,不走重复路径且总距离最小
    //解法:动态规划  确定状态与状态转移方程 初始状态
    //状态:f[i][j] 以j号点结尾的 包含i个点的 最短距离
    //用i的二进制表示当前所走过的点,j表示当前以j号节点结尾
    //f[5][2]=15   5=101 表示当前走过的节点为0 2 且以2号节点为当前的最后一个节点 的最优距离为 15
    //i = 1100110 则表示当前已经走过的点为 1 2 5 6号点,如果要去掉5号点:i-(1<<5) = 1000110
    //状态转移方程: f[i][j]=min(f[i][j],f[i-(1<<j)][k]+weight[k][j]
    //即 要求 以j号点为结尾的i个点的最短距离 = 于以j的前一个k点为结尾的i-1(去掉j这个点)的最短距离
    //j的前一个节点k可能存在多个,所以要用for循环
    int main(){
        
        int n;
        cin>>n;
        
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                cin>>weight[i][j];//i到j的边的权重
        
        memset(f,INF,sizeof(f));//0x表示16进制 3f最值
        f[1][0]=0;
        for(int i=0;i<(1<<n);i++){//从0-1<<n 所有点的所有包含情况 
                                  //1个 2个 3个点的情况
            for(int j=0;j<n;j++){ //在包含i个点对应情况下的j结尾
                
                if( (i>>j) & 1)//只有当前的i中包含了j才继续进行
                for(int k=0;k<n;k++){
                    
                    if( ( i- (1<<j) )>>k&1)//去掉j 且包含k 号节点
                    f[i][j]=min(f[i][j],f[i - (1<<j)][k]+weight[k][j]);
                }
            }
        }
        
        
        cout<<f[1<<20-1][n-1]<<endl;
        
        return 0;    
    }

     

    展开全文
  • 在这种情况下,两个城市组成一个矩形,如果矩形内包含其它点,根据贪心法,肯定不能直接左上角走到右下角,那样会白白错过一些城市。 import java.util.Arrays; import java.util.Scanner; public class Main { ...

    N个城市,要求走一条最短的回路

    问题特殊之处在于距离的定义。

    在这种情况下,两个城市组成一个矩形,如果矩形内包含其它点,根据贪心法,肯定不能直接从左上角走到右下角,那样会白白错过一些城市。

    import java.util.Arrays;
    import java.util.Scanner;
    
    public class Main {
    class Point {
        int x, y;
    
        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    
    //最终的答案
    int ans = Integer.MAX_VALUE;
    //visited[i]表示第i个地点被访问过
    boolean visited[];
    //存储全部地点
    Point[] a;
    //起点
    Point start = new Point(0, 0);
    
    //求两个点之间的距离
    int getDis(Point x, Point y) {
        return Math.abs(x.x - y.x) + Math.abs(x.y - y.y);
    }
    
    /**
     * 递归求解
     *
     * @param cur        当前所在位置
     * @param dis        当前已经走过的距离
     * @param visitCount 已经访问的城市个数,用来记录递归终点
     **/
    void go(Point cur, int dis, int visitCount) {
        if (visitCount == visited.length) {//如果已经访问完了,更新答案
            ans = Math.min(ans, dis + getDis(start, cur));
        }
        //利用到起点的距离剪枝
        if (dis > ans) {
            return;
        }
        //利用到终点的距离剪枝
        if (dis + getDis(cur, start) > ans) {
            return;
        }
        //对于每个未曾访问的城市进行处理
        for (int i = 0; i < visited.length; i++) {
            if (!visited[i]) {
                visited[i] = true;
                go(a[i], dis + getDis(cur, a[i]), visitCount + 1);
                visited[i] = false;
            }
        }
    }
    
    Main() {
        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt();
        a = new Point[n];
        visited = new boolean[n];
        for (int i = 0; i < n; i++) {
            int pos[] = Arrays.stream(cin.next().split(",")).mapToInt(Integer::parseInt).toArray();
            a[i] = new Point(pos[0], pos[1]);
        }
        go(new Point(0, 0), 0, 0);
        System.out.println(ans);
    }
    
    
    public static void main(String[] args) {
        new Main();
    }
    }
    

    转载于:https://www.cnblogs.com/weiyinfu/p/9462889.html

    展开全文
  • 哈密顿回路算法分析

    千次阅读 2021-07-03 14:58:08
    提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录前言一、哈密顿回路问题分析二、问题的...问题描述:哈密顿一个无向,由指定的起点前往指定的终点,途中经过所有其他节点且只经过
  • 哈密顿回路算法详解

    千次阅读 2016-10-29 18:46:00
     哈密顿:图G一个回路,若它通过的每一个节点一次,且仅一次,就是哈密顿回路.存在哈密顿回路就是哈密顿.哈密顿就是一点出发,经过所有的必须且只能一次,最终回到起点的路径.中有的边可以不经过,但是...
  • 哈密顿图

    千次阅读 2016-03-22 12:12:48
    一个判定条件是设图G具有n个定点的无向联通,如果图G任意两个定点度数之和大于n,则G具有哈密顿回路,满足这个条件则一定是哈密顿,但是哈密顿不一定满足这个条件,最简单的例子就是一个n阶圈 目前判断...
  • 离散数学图论和树的知识点总结

    千次阅读 2020-03-31 12:43:09
    本文主要复习图论中的一些主要知识点的概念,方面方便自己以后查阅,方面也是对自己的知识点进行整理
  • 的遍历整理

    2021-03-07 14:56:01
    指的是从图中的任一顶点出发,对图中的所有顶点访问次且只访问次。的遍历操作和树的遍历操作功能相似。的遍历是种基本操作,的许多其它操作都是建立在遍历操作的基础之上。 遍历可
  • 离散数学——图论

    2021-05-20 23:37:26
    无向 G=(V,E); 反自反 + 对称 有向 D=(V,A); 邻接矩阵 用布尔矩阵表示 子图 G的生成子:包含G所有顶点的子图 顶点的度 握手定理: 每条边对顶点的度的贡献为2 r-正则:每点的度都为 r 完全: p-1 正...
  • 1-4、数据结构——

    2017-09-04 11:21:46
    本文数据结构这门课的专业知识出发,第部分列举了一些与相关的一些基本概念,包括边、顶点、度等。第二部分列举了一些在计算机中的表示方法,如邻接矩阵法、关联矩阵法等。第三部分结合实际代码,讲述了...
  • 离散结构:图论与树

    2020-06-23 21:56:23
    离散结构:图论与树 、图论的定义 ...〉 于是欧拉便创建了两新的学科:图论和拓扑学 (Graph)的定义 〉 由结点和联结结点的边所构成的离散结构 〉 记做G = <V, E> 〉 结点 verte...
  • 旅行售货员问题一、基本介绍二、问题解法2.1 ...哈密顿(Hamilton)圈:给定一个图G(V,E),如果G中的圈C恰好经过每一个顶点仅一次,则称该圈C为哈密顿圈。 旅行售货员问题就是在一个赋权完全中找一个具有最小权哈
  • 贪心算法求解 TSP 旅行商问题及其实现

    千次阅读 多人点赞 2020-07-09 21:54:54
    贪心算法求解 TSP 问题得到局部最优解的具体实现,数据集来自 TSPLIB 的 att48 数据集。旅行商问题即 TSP(Traveling Salesman Problem),又称为货郎担问题,是数学领域中著名问题之
  • 文章目录的定义和术语无向有向 (directed graph 或 digraph)标号 (labeled graph)带权 (weighted graph)无向完全有向完全端点,关联边,相邻环,多重边,简单图次,奇点,偶点,孤立点链,圈,连通...
  • 1 概论 我们首先通过一些例子来了解网络优化问题。...某一地区有若干个主要城市,现准备修建高速公路把这些城市连接起来,使得其中任何一个城市都可以经高速公路直接或间接到达另一个城市。假定已经知道了任意
  • 离散数学复习题1

    千次阅读 2021-02-27 08:23:06
    逻辑1、给出的真值表2、证明为永真式 谓词量词和推理1、使用量词和谓词表达不存在这事实2、证明前提“在这班上的某个学生没有读过书”和班上的每学生都通过了第门考试蕴含结论“通过考试的某个人没有读过书...
  • 的分类--图论笔记

    2021-12-06 17:01:01
    -- 潘登同学的图论笔记无向(我们着重讨论简单图)的数学语言简单图:不存在自环和重边的无向简单图范畴下的其他有特点的二部(很经典)有向图图的同构与子图构造子图的几种方法道路、回路与连通性欧拉图`...
  • ACM所有算法

    2017-10-25 17:00:10
    转载自:http://blog.sina.com.cn/s/blog_adb6743801019h29.html ACM 所有算法 数据结构 栈,队列,链表 哈希表,哈希数组 ...二分的识别 平衡二叉树 二叉排序树 线
  • ACM用到的算法。先做笔记,记一下 ACM 所有算法 数据结构 栈,队列,链表 哈希表,哈希数组 堆,优先队列 双端队列 可并堆 左偏堆 二叉查找树 Treap...
  • 图论

    2016-07-13 00:55:00
    的表示、的搜索、图论知识点整理 1、的表示 1.1、邻接矩阵 mat[u][v]表示u到v边权为mat[u][v]。 1.2、邻接表 1.2.1、静态指针 //支持重边 struct Edge { int u, v, w,ne; Edge(int u, int v, int w, int ...
  • . 回答下列问题: (每小题5分) 1.陈述算法在最坏情况下的时间复杂度和平均时间复杂度;这两种评估算法复杂性的方法各自有什么实际意义? 最坏情况下的时间复杂度称最坏时间复杂度。一般不特别说明,讨论的时间...
  • 图论基础知识

    2020-08-12 11:10:43
    任两顶点间最多有一条边(两点间有不止一条边:重边),且每条边的两个端点皆不重合的(一条边围成圈,只过一个点:自边/圈),称为简单图图G的顶点数n和边数e的关系 若G是无向,则0≤e≤n(n-1)/2 恰有n(n-1)/...
  • 算法分类合集(转)

    2017-07-28 21:11:00
    并查集集合计数问题二分的识别 平衡二叉树 二叉排序树 线段树维线段树二维线段树 树状数组维树状数组N维树状数组 字典树 后缀数组,后缀树 块状链表 哈夫曼树 桶,跳跃表 Trie树(静态建树、动态建.....
  • .基本算法:   (1)枚举. (poj1753,poj2965)  (2)贪心(poj1328,poj2109,poj2586)  (3)递归和分治法.   (4)递推.   (5)构造法.(poj3295)  (6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996) 二....
  • 数据结构与算法分析:图论

    千次阅读 2016-12-27 14:51:30
    简单路径:不包含环,所有顶点是互异的,但是第一个和最后一个可以是相同的。 圈:满足的路径称为圈,若各该路径是简单路径,则为简单圈。 连通的无向:无向中的每个顶点之间都有路径。 强连通的有...
  • |A|<|B| \Rightarrow \exists x \in B/ A,A \cup \{x\} \in \mathfrak{I} A,B∈I,∣A∣<∣B∣⇒∃x∈B/A,A∪{x}∈I 可以用贪心算法出最优解的 带期限的单机作业调度问题 Kruskal算法对于每一个无向连通赋权图产生...

空空如也

空空如也

1 2 3 4 5 ... 8
收藏数 147
精华内容 58
关键字:

输入一个赋权简单无向哈密顿图g,求从指定节点出发的最短哈密顿回路