《算法导论》习题解答 Chapter 22.1-6(求universal sink 通用汇点)
算法 通用 习题 解答 导论 Chapter universal Sink
2023-09-27 14:22:35 时间
思路:设置两个游标i指向行,j指向列,如果arr[i][j]==1,则i=max{i+1,j},j++;如果arr[i][j]==0,则j=max{i+1,j+1}。
伪代码:
has_universal_sink() for i=1 to N //对角线检查是否全是0 if A[i][i]==1 return false; i=1,j=2 while(i<=N && j<=N) if(A[i][j]==1) i=max{i+1,j} j++ else j=max{i+1,j+1} if i<=N if check arr[i][*]=0,arr[*(except i)][i]=1 return true; else return false; else return false;
命题:如果A[i][j]=0,则j不是通用汇点。
因为A[i][j]=0,说明i到j没有边,而通用汇点的定义是一定要每个点都要有一条指向他的边,因此j不是通用汇点。
命题:如果A[i][j]=1,则i不是通用汇点。
因为A[i][j]=1,所以i到j有一条边,所以i不是通用汇点。
循环不变式:每次迭代前,i之前和j之前但不包括i的点都不是通用汇点。
初始:i=1,j=2,i之前为空,j之前但不包括i的点也为空,因此成立。
保持:在迭代开始时,已知i之前和j之前但不包括i的点都不是通用汇点,当进入循环体后,如果A[i][j]==1,则说明i肯定不是通用汇点,并且已知j之前不包括i的点不是通用汇点,因此i=max{i+1,j},j++后仍然保持不变式;如果A[i][j]==0,则j不是通用汇点,如果j原本小于i,则j要到i+1,因为已知i之前的点肯定不是通用汇点,所以现在仍然保持不变式成立。
终止:如果i<=N,j=N+1,j之前除了i其他点都不是通用汇点,因此需要去全面检查i是不是通用汇点。如果i=N+1,则不需要检查了,没有通用汇点。
命题:如果A[i][j]=1,则j之前的点都不是通用汇点。
命题:如果A[i][j]=0,则i之前的点都不是通用汇点。
输入:
4 3
a c
b c
d c
源代码:
package C22; import java.io.ObjectInputStream.GetField; /** * 此处提供两种方法,一种是网上的方法,一种是自己想的方法, * 经过测试,如果同时执行100000000次,则网上的方法速度是3.6秒,我的方法速度是3秒 * @author xiazdong * */ public class C1_6 { private static int sink_index = -1; public static void main(String[] args) throws Exception { Adjacent_Matrix adj_matrix = GraphFactory.getAdjacentMatrixInstance("input\\22.1-6.txt"); boolean flag = has_universal_sink(adj_matrix); if(flag)System.out.println(adj_matrix.getVertexValue(sink_index)); } /** * 自己的方法 * @return */ public static boolean has_universal_sink(Adjacent_Matrix g){ int i=0,j=0; boolean flag = true; while(j<=g.getSize()-1){ if(g.getElement(i, j)==1){ i = j; } j++; } //检查arr[i][*]==0 arr[*(except i)][i]==1 for(int a=0;a<g.getSize();a++){ if(g.getElement(i, a)==1&&i!=a){ flag = false; } if(g.getElement(a, i)==0&&i!=a){ flag = false; } } if(flag) sink_index = i; return flag; } /** * 网上的方法 * @return */ public static boolean has_universal_sink2(Adjacent_Matrix g){ int i=0,j=0; boolean flag = true; while(j<=g.getSize()-1){ if(g.getElement(i, j)==1){ i++; } else j++; } //检查arr[i][*]==0 arr[*(except i)][i]==1 for(int a=0;a<g.getSize();a++){ if(g.getElement(i, a)==1&&i!=a){ flag = false; } if(g.getElement(a, i)==0&&i!=a){ flag = false; } } if(flag) sink_index = i; return flag; } }
这边还有一篇跟通用汇点有关的博文,说实话,通用汇点的o(v)的求法我还不是搞的很懂,有空值得研究一下。
相关文章
- .Net Core ORM选择之路,哪个才适合你 通用查询类封装之Mongodb篇 Snowflake(雪花算法)的JavaScript实现 【开发记录】如何在B/S项目中使用中国天气的实时天气功能 【开发记录】微信小游戏开发入门——俄罗斯方块
- 决策树算法简介
- 相移波束形成算法的MATLAB仿真
- 145 Mahout协同过滤算法
- R语言数据挖掘2.2.2.4 Apriori算法的变体
- 拉斯维加斯随机化算法求解整数因子分解
- 动态规划算法之图像压缩问题
- 基于C语言处理机调度算法的实现【100010769】
- baselines算法库common/vec_env/dummy_vec_env.py模块分析
- 华为OD机试 - 乱序整数序列两数之和绝对值最小(JavaScript) | 机试题+算法思路+考点+代码解析 【2023】
- 算法(一)时间复杂度
- 白话经典算法系列之六 高速排序 高速搞定
- 全排列算法 --javascript 实现
- php与java通用AES加密解密算法