精华内容
下载资源
问答
  • 最短哈密顿回路,在无向图中由一个顶点出发,不重复的遍历所有顶点,最后回到出发点,找到最短的回路,用C语言实现,
  • 哈密顿回路算法详解

    2016-10-29 18:46:00
    【转】哈密顿回路 原文链接:http://www.cnblogs.com/Ash-ly/p/5452580.html 概念:  哈密顿图:图G的一个回路,若它通过图的每一个节点一次,且仅一次,就是哈密顿回路.存在哈密顿回路的图就是哈密顿图....

    【转】哈密顿回路


    原文链接:http://www.cnblogs.com/Ash-ly/p/5452580.html

     

    概念:

      哈密顿图:图G的一个回路,若它通过图的每一个节点一次,且仅一次,就是哈密顿回路.存在哈密顿回路的图就是哈密顿图.哈密顿图就是从一点出发,经过所有的必须且只能一次,最终回到起点的路径.图中有的边可以不经过,但是不会有边被经过两次.

      与欧拉图的区别:欧拉图讨论的实际上是图上关于边的可行便利问题,而哈密顿图的要求与点有关.

    判定:

    一:Dirac定理(充分条件)

      设一个无向图中有N个顶点,若所有顶点的度数大于等于N/2,则哈密顿回路一定存在.(N/2指的是⌈N/2⌉,向上取整)

    二:基本的必要条件

      设图G=<V, E>是哈密顿图,则对于v的任意一个非空子集S,若以|S|表示S中元素的数目,G-S表示G中删除了S中的点以及这些点所关联的边后得到的子图,则W(G-S)<=|S|成立.其中W(G-S)是G-S中联通分支数.

    三:竞赛图(哈密顿通路)

      N(N>=2)阶竞赛图一点存在哈密顿通路.

    算法:

    一:在Dirac定理的前提下构造哈密顿回路

    过程:

      1:任意找两个相邻的节点S和T,在其基础上扩展出一条尽量长的没有重复结点的路径.即如果S与结点v相邻,而且v不在路径S -> T上,则可以把该路径变成v -> S -> T,然后v成为新的S.从S和T分别向两头扩展,直到无法继续扩展为止,即所有与S或T相邻的节点都在路径S -> T上.

      2:若S与T相邻,则路径S -> T形成了一个回路.

      3:若S与T不相邻,可以构造出来一个回路.设路径S -> T上有k+2个节点,依次为S, v1, v2, ..., vk, T.可以证明存在节点vi(i属于[1, k]),满足vi与T相邻,且vi+1与S相邻.找到这个节点vi,把原路径变成S -> vi -> T -> vi+1 -> S,即形成了一个回路.

      4:到此为止,已经构造出来了一个没有重复节点的的回路,如果其长度为N,则哈密顿回路就找到了.如果回路的长度小于N,由于整个图是连通的,所以在该回路上,一定存在一点与回路之外的点相邻.那么从该点处把回路断开,就变回了一条路径,同时还可以将与之相邻的点加入路径.再按照步骤1的方法尽量扩展路径,则一定有新的节点被加进来.接着回到路径2.

    证明:

      可利用鸽巢原理证明.

    伪代码:

      设s为哈密顿回路的起始点,t为哈密顿回路中终点s之前的点.ans[]为最终的哈密顿回路.倒置的意思指的是将数组对应的区间中数字的排列顺序方向.

      1:初始化,令s = 1,t为s的任意一个邻接点.

      2:如果ans[]中元素的个数小于n,则从t开始向外扩展,如果有可扩展点v,放入ans[]的尾部,并且t=v,并继续扩展,如无法扩展进入步骤3.

      3:将当前得到的ans[]倒置,s和t互换,从t开始向外扩展,如果有可扩展点v,放入ans[]尾部,并且t=v,并继续扩展.如无法扩展进入步骤4.

      4:如果当前s和t相邻,进入步骤5.否则,遍历ans[],寻找点ans[i],使得ans[i]与t相连并且ans[i +1]与s相连,将从ans[i + 1]到t部分的ans[]倒置,t=ans[i +1],进如步骤5.

      5:如果当前ans[]中元素的个数等于n,算法结束,ans[]中保存了哈密顿回路(可看情况是否加入点s).否则,如果s与t连通,但是ans[]中的元素的个数小于n,则遍历ans[],寻找点ans[i],使得ans[i]与ans[]外的一点(j)相连,则令s=ans[i - 1],t = j,将ans[]中s到ans[i - 1]部分的ans[]倒置,将ans[]中的ans[i]到t的部分倒置,将点j加入到ans[]的尾部,转步骤2.

    时间复杂度:

      如果说每次到步骤5算一轮的话,那么由于每一轮当中至少有一个节点被加入到路径S -> T中,所以总的轮数肯定不超过n轮,所以时间复杂度为O(n^2).空间上由于边数非常多,所以采用邻接矩阵来存储比较适合.

    代码:

     
     1 const int maxN = 100;
     2 inline void reverse(int arv[maxN + 7], int s, int t){//将数组anv从下标s到t的部分的顺序反向
     3     int temp;
     4     while(s  < t){
     5         temp = arv[s];
     6         arv[s] = arv[t];
     7         arv[t] = temp;
     8         s++;
     9         t--;
    10     }
    11 }
    12 
    13 void Hamilton(int ans[maxN + 7], bool map[maxN + 7][maxN + 7], int n){
    14     int s = 1, t;//初始化取s为1号点
    15     int ansi = 2;
    16     int i, j;
    17     int w;
    18     int temp;
    19     bool visit[maxN + 7] = {false};
    20     for(i = 1; i <= n; i++) if(map[s][i]) break;
    21     t = i;//取任意邻接与s的点为t
    22     visit[s] = visit[t] = true;
    23     ans[0] = s;
    24     ans[1] = t;
    25     while(true){
    26         while(true){//从t向外扩展
    27             for(i = 1; i <= n; i++){
    28                 if(map[t][i] && !visit[i]){
    29                     ans[ansi++] = i;
    30                     visit[i] = true;
    31                     t = i;
    32                     break;
    33                 }
    34             }
    35             if(i > n) break;
    36         }
    37         w = ansi - 1;//将当前得到的序列倒置,s和t互换,从t继续扩展,相当于在原来的序列上从s向外扩展
    38         i = 0;
    39         reverse(ans, i, w);
    40         temp = s;
    41         s = t;
    42         t = temp;
    43         while(true){//从新的t继续向外扩展,相当于在原来的序列上从s向外扩展
    44             for(i = 1; i <= n; i++){
    45                 if(map[t][i] && !visit[i]){
    46                     ans[ansi++] = i;
    47                     visit[i] = true;
    48                     t = i;
    49                     break;
    50                 }
    51             }
    52             if(i > n) break;    
    53         }
    54         if(!map[s][t]){//如果s和t不相邻,进行调整
    55             for(i = 1; i < ansi - 2; i++)//取序列中的一点i,使得ans[i]与t相连,并且ans[i+1]与s相连
    56                 if(map[ans[i]][t] && map[s][ans[i + 1]])break;
    57             w = ansi - 1;
    58             i++;
    59             t = ans[i];
    60             reverse(ans, i, w);//将从ans[i +1]到t部分的ans[]倒置
    61         }//此时s和t相连
    62         if(ansi == n) return;//如果当前序列包含n个元素,算法结束
    63         for(j = 1; j <= n; j++){//当前序列中元素的个数小于n,寻找点ans[i],使得ans[i]与ans[]外的一个点相连
    64             if(visit[j]) continue;
    65             for(i = 1; i < ansi - 2; i++)if(map[ans[i]][j])break;
    66                 if(map[ans[i]][j]) break;
    67         }
    68         s = ans[i - 1];
    69         t = j;//将新找到的点j赋给t
    70         reverse(ans, 0, i - 1);//将ans[]中s到ans[i-1]的部分倒置
    71         reverse(ans, i, ansi - 1);//将ans[]中ans[i]到t的部分倒置
    72         ans[ansi++] = j;//将点j加入到ans[]尾部
    73         visit[j] = true;
    74     }
    75 }
     

     

    二:N(N>=2)阶竞赛图构造哈密顿通路

    N阶竞赛图:含有N个顶点的有向图,且每对顶点之间都有一条边.对于N阶竞赛图一定存在哈密顿通路.

    数学归纳法证明竞赛图在n >= 2时必存在哈密顿路:

    (1)n = 2时结论显然成立;

    (2)假设n = k时,结论也成立,哈密顿路为V1, V2, V3, ..., Vk;

      设当n = k+1时,第k + 1个节点为V(k+1),考虑到V(k+1)与Vi(1<=i<=k)的连通情况,可以分为以下两种情况.

        1:Vk与V(k+1)两点之间的弧为<Vk, V(k+1)>,则可构造哈密顿路径V1, V2,…, Vk, V(k+1).

        2:Vk与V(k+1)两点之间的弧为<V(k+1),Vk>,则从后往前寻找第一个出现的Vi(i=k-1,i>=1,--i),满足Vi与V(k+1)之间的弧为<Vi,V(k+1)>,则构造哈密顿路径V1, V2, …, Vi, V(k+1), V(i+1), …, V(k).若没找到满足条件的Vi,则说明对于所有的Vi(1<=i<=k)到V(k+1)的弧为<V(k+1),V(i)>,则构造哈密顿路径V(k+1), V1, V2, …, Vk.

    证毕.

    竞赛图构造哈密顿路时的算法同以上证明过程.

     

    用图来说明:

    假设此时已经存在路径V1 -> V2 -> V3 -> V4,这四个点与V5的连通情况有16种,给定由0/1组成的四个数,第i个数为0代表存在弧<V5,Vi>,反之为1,表示存在弧<Vi,V5>

     

     

     

     

    sign[]={0, 0, 0, 0}.

    很显然属于第二种情况,从后往前寻找不到1,即且不存在弧<Vi, V5>.

    则构造哈密顿路:V5 -> V1 -> V2 -> V3 -> V4.

     

     

     

    sign[]={0, 0, 0, 1}.

    属于第一种情况,最后一个数字为1,即代表存在弧<Vi, V5>且i=4(最后一个点)

    则构造哈密顿路: V1 -> V2 -> V3 -> V4 -> V5.

     

     

     

     

    sign[]={0, 0, 1, 0}.

    属于第二种情况,从后往前找到1出现的第一个位置为3.

    构造哈密顿路: V1 -> V2 -> V3 -> V5 -> V4.

     

     

     

     

    sign[]={0, 0, 1, 1}.

    属于第一种情况,最后一个数字为1,即代表存在弧<Vi, V5>且i=4(最后一个点)

    则构造哈密顿路: V1 -> V2 -> V3 -> V4 -> V5.

     

     

     

     

    sign[]={0, 1, 0, 0}.

    属于第二种情况,从后往前找到1出现的第一个位置为2.

    构造哈密顿路: V1 -> V2 -> V5 -> V3-> V4.

     

     

     

     

    sign[]={0, 1, 0, 1}.

    属于第一种情况,最后一个数字为1,即代表存在弧<Vi, V5>且i=4(最后一个点)

    则构造哈密顿路:V1 -> V2 -> V3 -> V4 -> V5.(就不举末尾为1的栗子了~~)

     

     

     

     

    sign[]={1, 0, 1, 0}.

    属于第二种情况,从后往前找到1出现的第一个位置为3.

    构造哈密顿路: V1 -> V2 -> V3 -> V5-> V4.

     

     

     

     

    sign[]={1, 1, 1, 0}.

    属于第二种情况,从后往前找到1出现的第一个位置为3.

    构造哈密顿路: V1 -> V2 -> V3 -> V5-> V4.

     

     

     

     

    (还是举一个吧~~~)

    sign[]={1, 1, 1, 1}.

    同样最后一位为1,代表存在<Vi, V5>且i=4(最后一位)

    则构造哈密顿路:V1 -> V2 -> V3 -> V4 -> V5.以上是当N=4时(N+1=5),用图来阐述算法的过程.

    注意从后往前找不是找这个点编号之前的点,即不是按照编号来的,而是按照当前哈密顿序列从后往前找的.举个栗子:

    4

    2 1

    1 3

    3 2

    4 1

    4 2

    4 3

    第一步ans={1}

    第二步ans={2,1}

    第三步sign={0, 1}(map[3][2] = 0,map[3][1] = 1,当前序列为2,1) ,而不是{1, 0}(1,2),因为存在弧<V1, V3>和<V3, V2>.这里需要注意下.

    代码:

     

     
     1 #include <iostream>
     2 #include <cmath>
     3 #include <cstdio>
     4 #include <cstring>
     5 #include <cstdlib>
     6 #include <algorithm>
     7 #include <queue>
     8 #include <stack>
     9 #include <vector>
    10 
    11 using namespace std;
    12 typedef long long LL;
    13 const int maxN = 200;
    14 
    15 //The arv[] length is len, insert key befor arv[index] 
    16 inline void Insert(int arv[], int &len, int index, int key){ 
    17     if(index > len) index = len;
    18     len++;
    19     for(int i = len - 1; i >= 0; --i){
    20         if(i != index && i)arv[i] = arv[i - 1];
    21         else{arv[i] = key; return;}
    22     }
    23 }
    24 
    25 void Hamilton(int ans[maxN + 7], int map[maxN + 7][maxN + 7], int n){
    26     int ansi = 1;
    27     ans[ansi++] = 1;
    28     for(int i = 2; i <= n; i++){//第一种情况,直接把当前点添加到序列末尾
    29         if(map[i][ans[ansi - 1]] == 1)
    30             ans[ansi++] = i;
    31         else{
    32             int flag = 0;
    33             for(int j = ansi - 2; j > 0; --j){//在当前序列中,从后往前找到第一个满足条件的点j,使得存在<Vj,Vi>且<Vi, Vj+1>.
    34                 if(map[i][ans[j]] == 1){//找到后把该点插入到序列的第j + 1个点前.
    35                     flag = 1;
    36                     Insert(ans, ansi, j + 1, i);
    37                     break;
    38                 }
    39             }
    40             if(!flag)Insert(ans, ansi, 1, i);//否则说明所有点都邻接自点i,则把该点直接插入到序列首端.
    41         }
    42     }
    43 }
    44 
    45 int main()
    46 {
    47     //freopen("input.txt", "r", stdin);
    48     int t;
    49     scanf("%d", &t);
    50     while(t--){
    51         int N;
    52         scanf("%d", &N);
    53         int M = N * (N - 1) / 2;
    54         int map[maxN + 7][maxN + 7] = {0};
    55         for(int i = 0; i < M; i++){
    56             int u, v;
    57             scanf("%d%d", &u, &v);
    58             //map[i][j]为1说明j < i,且存在弧<Vi, Vj>,因为插入时只考虑该点之前的所有点的位置,与之后的点没有关系.所以只注重该点与其之前的点的连通情况.
    59             if(u < v)map[v][u] = 1;
    60         }
    61         int ans[maxN + 7] = {0};
    62         Hamilton(ans, map, N);
    63         for(int i = 1; i <= N; i++)
    64             printf(i == 1 ? "%d":" %d", ans[i]);
    65         printf("\n");
    66     }
    67     return 0;
    68 }
     

     代码2:

     
     1 void Hamilton(int ans[maxN + 7], int map[maxN + 7][maxN + 7], int n){
     2     int nxt[maxN + 7];
     3     memset(nxt, -1, sizeof(nxt));
     4     int head = 1;
     5     for(int i = 2; i <= n; i++){
     6         if(map[i][head]){
     7             nxt[i] = head;
     8             head = i;
     9         }else{
    10             int pre = head, pos = nxt[head];
    11             while(pos != -1 && !map[i][pos]){
    12                 pre = pos;
    13                 pos = nxt[pre];
    14             }
    15             nxt[pre] = i;
    16             nxt[i] = pos;
    17         }
    18     }
    19     int cnt = 0;
    20     for(int i = head; i != -1; i = nxt[i])
    21         ans[++cnt] = i;
    22 }
     

    代码三:

     
     1 void Hamitton(bool reach[N + 7][N + 7], int n)  
     2 {    
     3     vector <int> ans; 
     4     ans.push_back(1);  
     5     for(int i=2;i <= n;i++)  
     6     {  
     7         bool cont = false;  
     8         for(int j=0;j<(int)ans.size()-1;j++)  
     9             if(reach[ ans[j] ][i] && reach[i][ ans[j+1] ])  
    10             {  
    11                 ans.insert(ans.begin()+j+1,i);  
    12                 cont = true;  
    13                 break;  
    14             }  
    15         if(cont)  
    16             continue;  
    17         if(reach[ ans.back() ][i])  
    18             ans.push_back(i);  
    19         else  
    20             ans.insert(ans.begin(),i);  
    21     } 
    22     for(int i=0;i<n;i++)  
    23                    printf("%d%c",ans[i],i==n-1?'\n':' ');   
    24 } 
     

    转载于:https://www.cnblogs.com/dragonir/p/6011561.html

    展开全文
  • 哈密顿回路问题 算法设计与分析 回溯法
  • 最短哈密顿回路

    2020-05-18 09:01:48
    最短哈密顿回路 算法的实现,我就是用这个的,很完善
  • 该程序用C语言编写(在VC++环境下运行即可),使用贪心算法求得最短哈密顿回路的近似解,简单易懂。 该程序用C语言编写(在VC++环境下运行即可),使用贪心算法求得最短哈密顿回路的近似解,简单易懂。
  • 1. 通过贪心算法对可以回到起点的环游解——哈密顿回路 进行了优化。当棋盘规模小于12时,能够迅速给出任意一个节点的一条哈密顿解 2. 若不要求回到起点最大规模可达60 3. 可以自定义是否回到起点,棋盘规模以及是否...
  • 提供一种求解最优哈密尔顿的算法---三边交换调整法,要求在运行jiaohuan3(三交换法)之前,给定邻接矩阵C和节点个数N,结果路径存放于R中。 bianquan.m文件给出了一个参数实例,可在命令窗口中输入bianquan,得到...
  • 用递增算法求完 全图的所有哈密顿回路
  • 目录 1 问题描述 2 解决方案 ...什么是哈密顿回路?...哈密顿图(哈密尔顿图)(英语:Hamiltonian path,或Traceable path)是...在图论中是指含有哈密顿回路的图,闭合的哈密顿路径称作哈密顿回路(Hamiltonian c...

    目录

    1 问题描述

    2 解决方案

     


    1 问题描述

    什么是哈密顿回路?

    引用自百度百科:

    哈密顿图(哈密尔顿图)(英语:Hamiltonian path,或Traceable path)是一个无向图,由天文学家哈密顿提出,由指定的起点前往指定的终点,途中经过所有其他节点且只经过一次在图论中是指含有哈密顿回路的图,闭合的哈密顿路径称作哈密顿回路(Hamiltonian cycle),含有图中所有顶点的路径称作哈密顿路径。

    现在本文要解决的问题:给定一个图,判断这个图是否包含哈密顿回路?如果包含,输出其中一条哈密顿回路,如果不包含,则无任何输出。

     


    2 解决方案

    本文寻找哈密顿回路,运用了深度优先搜索方法,即递归和回溯法思想。

    下面代码所用图数据如下:

     

    具体代码如下:

    package com.liuzhen.chapter12;
    
    public class HamiltonCircuit {
        /*
         * 参数adjMatrix:给定图的邻接矩阵,其中值为1表示两个顶点可以相通,值为-1表示两个顶点不能相通
         */
        public void getHamiltonCircuit(int[][] adjMatrix) {
            boolean[] used = new boolean[adjMatrix.length];       //用于标记图中顶点是否被访问
            int[] path = new int[adjMatrix.length];       //记录哈密顿回路路径
            for(int i = 0;i < adjMatrix.length;i++) {
                used[i] = false;     //初始化,所有顶点均未被遍历
                path[i] = -1;        //初始化,未选中起点及到达任何顶点
            }
            used[0] = true;          //表示从第1个顶点开始遍历
            path[0] = 0;             //表示哈密顿回路起点为第0个顶点
            dfs(adjMatrix, path, used, 1);     //从第0个顶点开始进行深度优先遍历,如果存在哈密顿回路,输出一条回路,否则无输出
        }
        /*
         * 参数step:当前行走的步数,即已经遍历顶点的个数
         */
        public boolean dfs(int[][] adjMatrix, int[] path, boolean[] used, int step) {
            if(step == adjMatrix.length) {     //当已经遍历完图中所有顶点
                if(adjMatrix[path[step - 1]][0] == 1) { //最后一步到达的顶点能够回到起点
                    for(int i = 0;i < path.length;i++)
                        System.out.print(((char)(path[i] + 'a'))+"——>");
                    System.out.print(((char)(path[0] + 'a')));
                    System.out.println();
                    return true;
                }
                return false;
            } else {
                for(int i = 0;i < adjMatrix.length;i++) {
                    if(!used[i] && adjMatrix[path[step - 1]][i] == 1) {
                        used[i] = true;
                        path[step] = i;
                        if(dfs(adjMatrix, path, used, step + 1))
                            return true;
                        else {
                            used[i] = false;    //进行回溯处理
                            path[step] = -1;
                        }
                    }
                }
            }
            return false;
        }
        
        public static void main(String[] args) {
            HamiltonCircuit test = new HamiltonCircuit();
            int[][] adjMatrix = {{-1,1,1,1,-1,-1},
                    {1,-1,1,-1,-1,1},
                    {1,1,-1,1,1,-1},
                    {1,-1,1,-1,1,-1},
                    {-1,-1,1,1,-1,1},
                    {-1,1,-1,-1,1,-1}};
            test.getHamiltonCircuit(adjMatrix);
        }
    }

    运行结果:

    a——>b——>f——>e——>c——>d——>a

     

     

     

    参考资料:

    1.基于回溯法寻找哈密顿回路

    2.《算法设计与分析基础》第3版   Anany Levitin 著  潘彦 译

     

     

    转载于:https://www.cnblogs.com/liuzhen1995/p/6541285.html

    展开全文
  • 哈密顿回路来历: 天文学家哈密顿(William Rowan Hamilton) 提出,在一个有多个城市的地图网络...哈密顿回路问题已被证明是NP问题,具有这样性质的问题,很难找到一个有效的算法。实际上对于某些顶点数不到100的网...

    哈密顿回路来历:

    天文学家哈密顿(William Rowan Hamilton) 提出,在一个有多个城市的地图网络中,寻找一条从 给定的起点 到 给定的终点 沿途恰好经过所有其他城市一次的路径。

    这个问题和著名的七桥问题的不同之处在于,七桥问题过桥只需要确定起点,而不用确定终点。

    哈密顿回路问题已被证明是NP问题,具有这样性质的问题,很难找到一个有效的算法。实际上对于某些顶点数不到100的网络,利用现有最好的算法和计算机也需要比较荒唐的时间(比如几百年)才能确定其是否存在一条这样的路径。

    今天,我们就来看看这类问题是什么样的呢?(“这类问题”说明不一定只是问你是否存在这样一条路径)

    由于这是个NP问题,因此我目前的菜鸡水平只能做简化版的。

    luogu1523.旅行商简化版

    题目背景

    欧几里德旅行商(Euclidean Traveling Salesman)问题也就是货郎担问题一直是困扰全世界数学家、计算机学家的著名问题。现有的算法都没有办法在确定型机器上在多项式时间内求出最优解,但是有办法在多项式时间内求出一个较优解。

    为了简化问题,而且保证能在多项式时间内求出最优解,J.L.Bentley提出了一种叫做bitonic tour的哈密尔顿环游。它的要求是任意两点(a,b)之间的相互到达的代价dist(a,b)=dist(b,a)且任意两点之间可以相互到达,并且环游的路线只能是从最西端单向到最东端,再单项返回最西端,并且是一个哈密尔顿回路。

     

    题目描述

    著名的NPC难题的简化版本

    现在笛卡尔平面上有n(n<=1000)个点,每个点的坐标为(x,y)(-2^31<x,y<2^31,且为整数),任意两点之间相互到达的代价为这两点的欧几里德距离,现要你编程求出最短bitonic tour。

     

    输入输出格式

    输入格式:

    第一行一个整数n

    接下来n行,每行两个整数x,y,表示某个点的坐标。

    输入中保证没有重复的两点,

    保证最西端和最东端都只有一个点。

     

    输出格式:

    一行,即最短回路的长度,保留2位小数。

     

    输入输出样例

     

    输入样例#1:

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

    输出样例#1:

    25.58

     

     

    这就是哈密顿问题的简化版。它把所有点放在了坐标轴上,并且规定了必须从最左端到最右端再回到最多段(就是规定了方向)。
    由于题目中没有给每个点的坐标排序,我们可以先以横坐标x为第一关键字,纵坐标y为第二关键字从小到大排序。
    这些点排好序之后,由于规定了方向,问题就转化成了求2条从最左上端(第一个点)到最右下端(最后一个点)的不相交的路径,且这两条路径经过所有点。把这两条路径都看做向右走的即可。
    由于规定了方向,如果两条路径分别到达了第i、j个点,那么说明1到max(i,j)号点一定都经过了(因为只能向右走而不能折返,为了经过所有的点,左边的点必须都经过了才能到达本列)。
    总结做法:
      f[i][j]表示第一条路径走到第i个点,第二条路径走到第j个点的最短路径,要求i<j(这样max(i,j)就是j,能保证第二条路径一定走在前面),且第1到j个的点都被经过了。这样很容易想到,第j+1个点不是被第一个人走,就是被第二个人走,所以有转移方程
      $f[i][j+1] = \min\{ f[i][j+1], f[i][j]+dis[j][j+1] \}$
      $f[j][j+1] = \min\{ f[i][j+1], f[i][j]+dis[i][j+1] \}$
    第一个方程是让第二条路径走到第j+1个点,没啥问题。
    第二个方程是让第一条路径走到第j+1个点,但不好理解,且这么走后是不是违反了 第一条路径到达的点i < 第二条路径到达的点j 的原则?但我没有明确指定哪条路径是第一条,哪条路径是第二条呀!因此当第一条路径跑到前面(即第j+1个点)时,我们可以把两条路径“交换”一下,而这样做不会影响状态,相当于第一条路径成了第二条路径,走到了第j个点;而第二条路径成了第一条路径,走到了第j+1个点。如此即可确保第二条路径仍在第一条路径前面了!

     

     1 #include<bits/stdc++.h>
     2 #define maxn 1001
     3 #define inf 1e30
     4 using namespace std;
     5 struct data
     6 {
     7     double x,y;
     8 }g[maxn];
     9 double d[maxn][maxn],f[maxn][maxn];
    10 int i,j,k,n;
    11 bool cmp(const data &a,const data &b)
    12 {
    13     if(a.x==b.x) return a.y<b.y;
    14     return a.x<b.x;
    15 }
    16 double mdis(const data &a, const data &b)
    17 {
    18     return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
    19 }
    20 int main()
    21 {
    22     scanf("%d",&n);
    23     for(i=1;i<=n;++i) scanf("%lf%lf",&g[i].x,&g[i].y);
    24     sort(g+1,g+n+1,cmp);//按横坐标x从小到大排序 
    25     for(i=1;i<=n;++i)
    26         for(j=i+1;j<=n;++j)
    27         {
    28             d[i][j]=mdis(g[i],g[j]); //求任意两点的距离 
    29             f[i][j]=inf;
    30         }
    31     f[1][2]=d[1][2];
    32     for(i=1;i<n;++i)
    33         for(j=i+1;j<=n;++j)
    34         {
    35             f[i][j+1]=min(f[i][j+1],f[i][j]+d[j][j+1]);
    36             f[j][j+1]=min(f[j][j+1],f[i][j]+d[i][j+1]);
    37         }
    38     printf("%.2lf\n",f[n-1][n]+d[n-1][n]);
    39     return 0;
    40 }
    View Code

     

     

    旅行商问题

    题目描述

    给定一个n个顶点组成的带权有向图的距离矩阵d(i,j)(INF表示没有边)。要求从顶点0出发,经过每个顶点恰好一次后再回到顶点0.问所经过的边的总权重的最小值是多少?

    输入样例#1:

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

    输出样例#1:

    25.58

     

    转载于:https://www.cnblogs.com/scx2015noip-as-php/p/Hamilton.html

    展开全文
  • 2 POJ - 2438 哈密顿回路 3 图的可行遍问题:一般就是哈密顿图和欧拉图 4 这类问题,代码和算法本身简单,关键就在于建模。 5 一般判断问题只要判断是否可行遍历! 6 但是有的时候会有奇葩的要求: 7 ...
      1 /*
      2 POJ - 2438 哈密顿回路
      3 图的可行遍问题:一般就是哈密顿图和欧拉图
      4 这类问题,代码和算法本身简单,关键就在于建模。
      5 一般判断问题只要判断是否可行遍历!
      6 但是有的时候会有奇葩的要求:
      7 例如:遍历一张欧拉回路图:深度遍历不回溯法,o(n)
      8       遍历哈密顿回路:这道题
      9 言归正传:
     10 1、哈密顿图定义:从一个点出发、经过所有的点必须且只能一次,最终回到起点。图中有边可以不经过,但是不能经过两次。
     11 2、存在的充分条件:图有n个顶点,如果图中任意两个不同的顶点的度数之和大于等于n,则图是哈密顿图。
     12 3、遍历哈密顿图的算法:如下
     13 
     14 解题思路:
     15 1、题目是说,小朋友围一圈坐着,仇恨的不能坐在一起,让你安排座位。
     16 2、建图:可以连着坐的点连一条线,这道题就是求一个哈密顿的可行遍历。
     17 3、判断是否有解:因为每个人最多有n-1个敌人,然而有2*n个小朋友,满足上述充分条件,必然有解。
     18 
     19 */
     20 #include <iostream>
     21 #include <string.h>
     22 #include <stdio.h>
     23 #include <cmath>
     24 #include <vector>
     25 #define LL long long
     26 #define maxn 410
     27 using namespace std;
     28 
     29 bool map[maxn][maxn];
     30 int ans[maxn];
     31 inline void reverse(int s,int t){
     32     while(s<t){
     33         swap(ans[s],ans[t]);
     34         s++;t--;
     35     }
     36 }
     37 void Hamilton(int n){
     38     int s=1,t;
     39     int ansi=2;
     40     int w,i,j;
     41     bool visit[maxn]={false};
     42     for(i=1;i<=n;i++){
     43         if (map[s][i]) break;
     44     }
     45     t=i;
     46     visit[s]=visit[t]=true;
     47     ans[0]=s;
     48     ans[1]=t;
     49     while(1){
     50         while(1){
     51             for(i=1;i<=n;i++){
     52                 if (map[t][i] && !visit[i]){
     53                     ans[ansi++]=i;
     54                     visit[i]=true;
     55                     t=i;
     56                     break;
     57                 }
     58             }
     59             if (i>n) break;
     60         }
     61         w=ansi-1;
     62     i=0;reverse(i,w);
     63     swap(s,t);
     64     while(1){
     65         for(i=1;i<=n;i++){
     66             if (map[t][i] && !visit[i]){
     67                 ans[ansi++]=i;
     68                 visit[i]=true;
     69                 t=i;
     70                 break;
     71             }
     72         }
     73         if (i>n) break;
     74     }
     75     if (!map[s][t]){
     76         for(i=1;i<ansi-2;i++) if (map[ans[i]][t] && map[s][ans[i+1]]) break;
     77         w=ansi-1;
     78         i++;
     79         t=ans[i];
     80         reverse(i,w);
     81     }
     82     if (ansi==n) return ;
     83     for(j=1;j<=n;j++){
     84         if (visit[j]) continue;
     85         for(i=1;i<ansi-2;i++) if (map[ans[i]][j]) break;
     86         if (map[ans[i]][j]) break;
     87     }
     88     s=ans[i-1];
     89     t=j;
     90     reverse(0,i-1);
     91     reverse(i,ansi-1);
     92     ans[ansi++]=j;
     93     visit[j]=true;
     94     }
     95 }
     96 int n,m;
     97 int main(){
     98     while(cin>>n>>m){
     99         if (n==0 && m==0) break;
    100         memset(map,0,sizeof(map));
    101         for(int i=1;i<=m;i++){
    102             int u,v;
    103             scanf("%d%d",&u,&v);
    104             map[u][v]=map[v][u]=true;
    105         }
    106         for(int i=1;i<=2*n;i++){
    107             for(int j=1;j<=2*n;j++)
    108             if (i==j) continue;
    109             else map[i][j]=!map[i][j];
    110         }
    111         Hamilton(2*n);
    112         for(int i=0;i<2*n;i++)
    113         if (i!=2*n-1) printf("%d ",ans[i]);else printf("%d\n",ans[i]);
    114     }
    115     return 0;
    116 }

     

    转载于:https://www.cnblogs.com/little-w/p/3614994.html

    展开全文
  • 我的机器学习教程「美团」算法工程师带你入门机器学习 以及 「三分钟系列」数据结构与算法 已经开始更新了,欢迎大家订阅~这篇专栏整合了这几年的算法知识,简单易懂,也将是我实体书的BLOG版...1.哈密顿通路 设G=...
  • 二、子问题(1)哈密顿回路 1.问题建模描述 给定一个n个结点,m条有向边(边权为正)的图,求出一条路径满足如下条件: 条件一:该路径可以从任意节点开始,不过起点和终点必须相同。 条件二:该路径除了起点和...
  • 刚刚搞了篇欧拉回路,现在趁热再搞个哈密顿回路…… 欧拉回路是跑光所有的边再跑回来,一条边跑且仅跑一遍 哈密顿回路是跑完所有的点再跑回来,路过的节点,跑且只跑一次 哈密顿路径问题在上世纪七十年代初,...
  • 给出了求解任意图的所有哈密顿回路逐点循环递归算法, 用于处理复杂的旅行商问题, 证明了一个图是否是哈密顿图在算法中, 用结点标号数组存储一个回路, 无向图的正向表存储初始图
  • 哈密顿回路的其中一种找法,可供大家参考. 另外对算法有兴趣的同学也可以看看
  • Problem Description 一个规则的实心十二面体,它的 20个顶点标出世界著名的20个城市,你从一个城市出发经过每个城市刚好一次后回到出发的城市。 Input ...前20行的第i行有3个数,表示与第i个城市相邻的3个城市....
  • 数据1 0 1 0 数据2 -1 数据3 0 1 3 2 0 数据4 0 1 2 4 9 3 6 13 10 5 11 7 15 14 12 8 0 数据规模和约定 对于15%的数据2对于30%的数据2对于100%的数据2思路:转化一下我们就可以发现是求0-0的哈密顿回路。...

空空如也

空空如也

1 2 3 4 5 ... 14
收藏数 265
精华内容 106
关键字:

哈密顿回路算法