图论10-哈密尔顿回路和哈密尔顿路径+状态压缩+记忆化搜索

这篇具有很好参考价值的文章主要介绍了图论10-哈密尔顿回路和哈密尔顿路径+状态压缩+记忆化搜索。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1 哈密尔顿回路

求解哈密尔顿回路

如何求解一个图是否存在哈密尔顿回路呢?

一个最直观的想法就是暴力求解。暴力求解的思路也很简单:我们遍历图的每一个顶点 v,然后从顶点 v 出发,看是否能够找到一条哈密尔顿回路。

暴力求解的代价同求解全排列问题是等价的,其时间复杂度为 O ( N ! ) O(N!) O(N!),N 为图的顶点的个数。

那么除了暴力求解哈密尔顿回路问题,是否存在更好的算法?

很遗憾我们只能在暴力破解的基础上,尽量去做到更多的优化,譬如回溯剪枝,记忆化搜索等,但是,还没有找到一种多项式级别的算法来解决哈密尔顿问题。

通常,这类问题也被称为 NP(Non-deterministic Polynomial)难问题。

综上所述,求解哈密尔顿回路,我们可以采用回溯+剪枝的思想来进行求解。

图论10-哈密尔顿回路和哈密尔顿路径+状态压缩+记忆化搜索,图论,图论,深度优先,算法

2 哈密尔顿回路算法实现

2.1 常规回溯算法

package Chapter07_Hamilton_Loop_And_Path.Hamilton_Loop;

import java.util.ArrayList;
import java.util.Collections;

public class HamiltonLoop {

    private Graph G;
    private boolean[] visited;
    private int[] pre;
    private int end; //用来表示最后一个被遍历的顶点

    public HamiltonLoop(Graph G){

        this.G = G;
        visited = new boolean[G.V()];
        pre = new int[G.V()];
        end = -1;
        dfs(0, 0);
    }

    private boolean dfs(int v, int parent){

        visited[v] = true;
        pre[v] = parent;

        for(int w: G.adj(v))
            if(!visited[w]){
                if(dfs(w, v))
                    return true;
            }
            else if(w == 0 && allVisited()){ //如果回到起始点0并且所有的点都被访问过了,则找到了哈密尔回路
                end = v;
                return true;
            }

        // 回溯
        visited[v] = false;
        return false;
    }

    public ArrayList<Integer> result(){

        ArrayList<Integer> res = new ArrayList<>();
        if(end == -1) return res;

        int cur = end;
        while(cur != 0){
            res.add(cur);
            cur = pre[cur];//上一个节点
        }
        res.add(0);

        Collections.reverse(res);
        return res;
    }

    private boolean allVisited(){
        for(int v = 0; v < G.V(); v ++)
            if(!visited[v]) return false;
        return true;
    }

    public static void main(String[] args){

        Graph g = new Graph("g9.txt");
        HamiltonLoop hl = new HamiltonLoop(g);
        System.out.println(hl.result());

        Graph g2 = new Graph("g10.txt");
        HamiltonLoop hl2 = new HamiltonLoop(g2);
        System.out.println(hl2.result());
    }
}

图论10-哈密尔顿回路和哈密尔顿路径+状态压缩+记忆化搜索,图论,图论,深度优先,算法

2.2 引入变量记录剩余未访问的节点数量

package Chapter07_Hamilton_Loop_And_Path.Hamilton_Loop;

import java.util.ArrayList;
import java.util.Collections;

public class HamiltonLoop_Optimization {

    private Graph G;
    private boolean[] visited;
    private int[] pre;
    private int end;

    public HamiltonLoop_Optimization(Graph G){

        this.G = G;
        visited = new boolean[G.V()];
        pre = new int[G.V()];
        end = -1;

        //dfs的过程记录剩余未访问的节点的数量
        dfs(0, 0, G.V());
    }

    private boolean dfs(int v, int parent, int left){
        visited[v] = true;
        pre[v] = parent;
        left --;

        //出口:如果未访问的节点是0,并且当前节点和初始节点有边
        if(left == 0 && G.hasEdge(v, 0)){
            end = v;
            return true;
        }

        for(int w: G.adj(v))
            if(!visited[w]){
                if(dfs(w, v, left)) return true;
            }
//            else if(w == 0 && left == 0){
//                end = v;
//                return true;
//            }

        visited[v] = false;
        return false;
    }

    public ArrayList<Integer> result(){

        ArrayList<Integer> res = new ArrayList<>();
        if(end == -1) return res;

        int cur = end;
        while(cur != 0){
            res.add(cur);
            cur = pre[cur];
        }
        res.add(0);

        Collections.reverse(res);
        return res;
    }

    public static void main(String[] args){

        Graph g = new Graph("g9.txt");
        HamiltonLoop hl = new HamiltonLoop(g);
        System.out.println(hl.result());

        Graph g2 = new Graph("g10.txt");
        HamiltonLoop hl2 = new HamiltonLoop(g2);
        System.out.println(hl2.result());
    }
}

3 哈密尔顿路径问题

根据出发位置的不同,路径也会不一样。但是算法实现还是一致的,只需要修改构造函数,传入起点位置。

package Chapter07_Hamilton_Loop_And_Path.Hamilton_Loop;

import java.util.ArrayList;
import java.util.Collections;

public class HamiltonPath {

    private Graph G;
    private int s;
    private boolean[] visited;
    private int[] pre;
    private int end;

    public HamiltonPath(Graph G, int s){

        this.G = G;
        this.s = s;
        visited = new boolean[G.V()];
        pre = new int[G.V()];
        end = -1;
        dfs(s, s, G.V());
    }

    private boolean dfs(int v, int parent, int left){

        visited[v] = true;
        pre[v] = parent;
        left --;
        if(left == 0){
            end = v;
            return true;
        }

        for(int w: G.adj(v))
            if(!visited[w]){
                if(dfs(w, v, left)) return true;
            }

        visited[v] = false;
        return false;
    }

    public ArrayList<Integer> result(){

        ArrayList<Integer> res = new ArrayList<>();
        if(end == -1) return res;

        int cur = end;
        while(cur != s){
            res.add(cur);
            cur = pre[cur];
        }
        res.add(s);

        Collections.reverse(res);
        return res;
    }

    public static void main(String[] args){

        Graph g = new Graph("g10.txt");
        HamiltonPath hp = new HamiltonPath(g, 0);
        System.out.println(hp.result());

        HamiltonPath hp2 = new HamiltonPath(g, 1);
        System.out.println(hp2.result());
    }
}

图论10-哈密尔顿回路和哈密尔顿路径+状态压缩+记忆化搜索,图论,图论,深度优先,算法

4 状态压缩

图论10-哈密尔顿回路和哈密尔顿路径+状态压缩+记忆化搜索,图论,图论,深度优先,算法

4.1 查看第i位是否为1

图论10-哈密尔顿回路和哈密尔顿路径+状态压缩+记忆化搜索,图论,图论,深度优先,算法

4.2 设置第i位是为1或者0

图论10-哈密尔顿回路和哈密尔顿路径+状态压缩+记忆化搜索,图论,图论,深度优先,算法

4.3 小结

图论10-哈密尔顿回路和哈密尔顿路径+状态压缩+记忆化搜索,图论,图论,深度优先,算法

4.4 状态压缩在哈密尔顿问题中的应用

在我们的代码中,一直都使用布尔型的 visited 数组来记录图中的每一个顶点是否有被遍历过。

在算法面试中,对于像哈密尔顿回路/路径这样的 NP 难问题,通常都会有输入限制,一般情况下,求解问题中给定的图不会超过 30 个顶点。

这样,在算法笔试/面试中,我们就可以对 visited 数组进行状态压缩来优化算法类执行的效率。我们知道一个 int 型的数字有 32 位,每一位不是 1 就是 0,这正好对应了布尔型的 true 和 false。

所以,我们可以将 visited 数组简化成一个数字,该数字的每一个比特位用来表示 visited 数组的每一个 true 或 false 值。

来看一下我们的 HamiltonLoop 中 dfs 的代码:

    public HamiltonLoop_StateCompression(Graph G){

        this.G = G;
        pre = new int[G.V()];
        end = -1;

        int visited = 0; //用一个数的比特位来表示是否被访问过
        dfs(visited, 0, 0, G.V());
    }

    private boolean dfs(int visited, int v, int parent, int left){

        visited += (1 << v); //第v位置设置为1
        pre[v] = parent;
        left --;
        if(left == 0 && G.hasEdge(v, 0)){
            end = v;
            return true;
        }

        for(int w: G.adj(v))
            if((visited & (1 << w)) == 0){ //看数字的第w个位置是否为 0
                if(dfs(visited, w, v, left)) return true;
            }

        visited -= (1 << v); //回溯,第v位置恢复为0
        return false;
    }

5 记忆化搜索

记忆化搜索是动态规划的一种实现方式。

在记忆化搜索中,当算法需要计算某个子问题的结果时,它首先检查是否已经计算过该问题。如果已经计算过,则直接返回已经存储的结果;否则,计算该问题,并将结果存储下来以备将来使用。

举个例子,比如「斐波那契数列」的定义是: f ( 0 ) = 0 , f ( 1 ) = 1 , f ( n ) = f ( n − 1 ) + f ( n − 2 ) f(0) = 0, f(1) = 1, f(n) = f(n - 1) + f(n - 2) f(0)=0,f(1)=1,f(n)=f(n1)+f(n2)。如果我们使用递归算法求解第 n n n 个斐波那契数,则对应的递推过程如下:

图论10-哈密尔顿回路和哈密尔顿路径+状态压缩+记忆化搜索,图论,图论,深度优先,算法
从图中可以看出:如果使用普通递归算法,想要计算 f ( 5 ) f(5) f(5),需要先计算 f ( 3 ) f(3) f(3) f ( 4 ) f(4) f(4),而在计算 f ( 4 ) f(4) f(4) 时还需要计算 f ( 3 ) f(3) f(3)。这样 f ( 3 ) f(3) f(3) 就进行了多次计算,同理 f ( 0 ) f(0) f(0) f ( 1 ) f(1) f(1) f ( 2 ) f(2) f(2) 都进行了多次计算,从而导致了重复计算问题。

为了避免重复计算,在递归的同时,我们可以使用一个缓存(数组或哈希表)来保存已经求解过的 f ( k ) f(k) f(k) 的结果。如上图所示,当递归调用用到 f ( k ) f(k) f(k) 时,先查看一下之前是否已经计算过结果,如果已经计算过,则直接从缓存中取值返回,而不用再递推下去,这样就避免了重复计算问题。

5.1 记忆化搜索与递推区别

  • 记忆化搜索:「自顶向下」的解决问题,采用自然的递归方式编写过程,在过程中会保存每个子问题的解(通常保存在一个数组或哈希表中)来避免重复计算。

  • 优点:代码清晰易懂,可以有效的处理一些复杂的状态转移方程。有些状态转移方程是非常复杂的,使用记忆化搜索可以将复杂的状态转移方程拆分成多个子问题,通过递归调用来解决。

  • 缺点:可能会因为递归深度过大而导致栈溢出问题。

  • 递推:「自底向上」的解决问题,采用循环的方式编写过程,在过程中通过保存每个子问题的解(通常保存在一个数组或哈希表中)来避免重复计算。

  • 优点:避免了深度过大问题,不存在栈溢出问题。计算顺序比较明确,易于实现。

  • 缺点:无法处理一些复杂的状态转移方程。有些状态转移方程非常复杂,如果使用递推方法来计算,就会导致代码实现变得非常困难。

  • 记忆化搜索解题步骤

我们在使用记忆化搜索解决问题的时候,其基本步骤如下:

  1. 写出问题的动态规划「状态」和「状态转移方程」。 定义一个缓存(数组或哈希表),用于保存子问题的解。
  2. 定义一个递归函数,用于解决问题。在递归函数中,首先检查缓存中是否已经存在需要计算的结果,如果存在则直接返回结果,否则进行计算,并将结果存储到缓存中,再返回结果。
  3. 在主函数中,调用递归函数并返回结果。

5.2 记忆化搜索的实现 - 力扣980

 memo = new int[1 << (R * C)][R * C];
  • 第一个维度是顶点数量的2倍,因为一个位置有两种可能——访问过/未访问过。

    • 假设顶点数量为1,则第一个维度未2: 0, 1.
      假设顶点数量为2,则第一个维度未4: 00, 01, 10, 11.
  • 第二个维度表示顶点数量,记录当前状态对应顶点是否被访问过。

图论10-哈密尔顿回路和哈密尔顿路径+状态压缩+记忆化搜索,图论,图论,深度优先,算法文章来源地址https://www.toymoban.com/news/detail-756648.html

package Chapter07_HamiltonLoop_And_StateCompression_And_MemoizationSearch.Memoization_Search;

import java.util.Arrays;

// Leetcode 980
class Solution {

    private int[][] dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    private int R, C;
    private int[][] grid;
    private int start, end;
    private int[][] memo;

    public int uniquePathsIII(int[][] grid) {

        this.grid = grid;
        R = grid.length;
        C = grid[0].length;
        int left = R * C;
        memo = new int[1 << (R * C)][R * C];
        for(int i = 0; i < memo.length; i ++)
            Arrays.fill(memo[i], -1);

        for(int i = 0; i < R; i ++)
            for(int j = 0; j < C; j ++)
                if(grid[i][j] == 1){
                    start = i * C + j;
                    grid[i][j] = 0;
                }
                else if(grid[i][j] == 2){
                    end = i * C + j;
                    grid[i][j] = 0;
                }
                else if(grid[i][j] == -1)
                    left --;

        int visited = 0;
        return dfs(visited, start, left);
    }

    private int dfs(int visited, int v, int left){

        if(memo[visited][v] != -1) return memo[visited][v];

        visited += (1 << v);
        left --;
        if(v == end && left == 0){
            visited -= (1 << v);
            memo[visited][v] = 1;
            return 1;
        }

        int x = v / C, y = v % C;
        int res = 0;
        for(int d = 0; d < 4; d ++){
            int nextx = x + dirs[d][0], nexty = y + dirs[d][1];
            int next = nextx * C + nexty;
            if(inArea(nextx, nexty) && grid[nextx][nexty] == 0 && (visited & (1 << next)) == 0)
                res += dfs(visited, next, left);
        }

        visited -= (1 << v);
        memo[visited][v] = res;
        return res;
    }

    private boolean inArea(int x, int y){
        return x >= 0 && x < R && y >= 0 && y < C;
    }
}

到了这里,关于图论10-哈密尔顿回路和哈密尔顿路径+状态压缩+记忆化搜索的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 离散数学 | 图论 | 欧拉图 | 哈密顿图 | 割点 | 桥(欧拉图和哈密顿图有没有割点和桥?)

    本文主要解决以下几个问题: 1.欧拉图能不能有割点,能不能有桥? 2.哈密顿图能不能有割点,能不能有桥? 首先我们要明白几个定义 割点 的定义就是在一个图G中,它本来是连通的,去掉一个点v以后这个图G就不连通了,那么点v就被叫做 割点 。 桥 的定义就是在一个图G中

    2024年02月08日
    浏览(34)
  • C++ 动态规划 状态压缩DP 最短Hamilton路径

    给定一张 n 个点的带权无向图,点从 0∼n−1 标号,求起点 0 到终点 n−1 的最短 Hamilton 路径。 Hamilton 路径的定义是从 0 到 n−1 不重不漏地经过每个点恰好一次。 输入格式 第一行输入整数 n 。 接下来 n 行每行 n 个整数,其中第 i 行第 j 个整数表示点 i 到 j 的距离(记为 a[

    2024年02月19日
    浏览(38)
  • 【图论】欧拉回路

    你的qq密码是否在圆周率中出现? 一个有意思的编码问题:假设密码是固定位数,设有 n n n 位,每位是数字0-9,那么这样最短的“圆周率”的长度是多少?或者说求一个最短的数字串定包含所有密码。 一些定义: 通过图中所有边恰好一次且行遍所有顶点的通路称为欧拉通路

    2023年04月09日
    浏览(48)
  • 图论中回路与圈的概念区分

    第一种定义方法 迹 是边不重复的通路,但是顶点可以重复。 回路 是首尾顶点相同的迹。 路 是顶点不重复的迹,即边和顶点都不重复的通路,但是首尾顶点可以相同。 圈 是首尾顶点相同的路。 第二种定义方法 回路:起点终点相同 简单通路:起点到终点所经过的 边不同 

    2024年02月04日
    浏览(42)
  • C++ [图论算法详解] 欧拉路&欧拉回路

    蒟蒻还在上课,所以文章更新的实在慢了点 那今天就来写一篇这周刚学的欧拉路和欧拉回路吧 在 一个风雪交加的夜晚 18世纪初普鲁士的哥尼斯堡,有一条河穿过,河上有两个小岛,有七座桥把两个岛与河岸联系起来。有个人提出一个问题:一个步行者怎样才能不重复、不遗

    2023年04月14日
    浏览(41)
  • 408【数据结构】图、生成树、图的出度和入度、路径and路径长度和回路、简单路径和简单回路概念整理 和 错题整理

            图由顶点集V和边集E组成,记为G=(V,E),使用 V(G) 表示 所有顶点的集合(不能为空) ;使用 E(G) 表示 各个顶点之间的关系(可以为空) 。若用V={v1,v2,v3,....,vn}来表示图,则使用 |V|表示图中顶点的个数, 使用E={(vi,vj)|vi∈V,vj∈V},用 |E| 表示图中 边的条

    2024年02月03日
    浏览(42)
  • 离散数学 --- 图论基础 --- 图的同构,通路与回路,可达性与最短通路

    同一个图(这里的图是抽象的数学定义)可以有不同的图形表示方法 1.重数:两点之间的平行边的个数   1.得到 n! 的过程,一个图中的一个结点在另一个图中对应的结点有n种可能(黄框中定义的图来讨论),这个对应好后下一个结点有 n - 1 种可能,再下一个有n-2种,直到最

    2024年01月25日
    浏览(41)
  • matlab自动控制状态反馈 设计PID控制回路、保证控制效果

    1、内容简介 略 36-可以交流、咨询、答疑 2、内容说明 系统描述 已知系统的传递函数为  ,以T=0.25s对系统采样,要求: 1)设计PID控制回路,能够实现闭环系统   ,稳态误差在斜坡输入情况下为0。 理论分析 2.1 极点求解 已知闭环系统的性能要求为  , ,则系统的2个闭环极

    2024年01月23日
    浏览(39)
  • 欧拉路径和欧拉回路(Euler Path and Euler Circuit)解释

    欧拉路径(欧拉回路)是图论非常重要的组成部分,欧拉路径是数学家欧拉在研究著名的德国哥尼斯堡(Koenigsberg)七桥问题时发现的。这一发现直接导致了一门新的理论研究的诞生-图论问题。 欧拉路径和欧拉回路区别 在一个连通图上,如果从一个顶点出发,历经访问所有的边

    2024年02月11日
    浏览(38)
  • 图论(欧拉路径)

    理论: 所有边都经过一次,若欧拉路径,起点终点相同,欧拉回路 有向图欧拉路径:恰好一个out=in+1,一个in=out+1,其余in=out 有向图欧拉回路:所有in=out 无向图欧拉路径:两个点度数奇,其余偶 无向图欧拉回路:全偶 基础练习 P7771 【模板】欧拉路径 P2731 [USACO3.3] 骑马修栅栏

    2024年02月05日
    浏览(33)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包