《离散数学》作业——Raptor研究传递闭包算法

1. 题目内容

首先要明白传递闭包是什么意思，根据书上的定义：设R和R’是A上的关系，R’是传递的，R是R’的子集，对A上的任何包含R的传递关系R’’都有R’是R’’的子集，那么二元关系R’即为R的传递闭包。然后根据定义再来研究它的算法。在网上查阅资料后发现warshall是最简单的算法，于是在查找了相关例程后加以理解，最后用Raptor软件将流程图表达了出来。

2. 文献查阅情况

通过看《离散数学》了解到了闭包算法中的传递闭包的基本定义。通过看《Warshall传递闭包算法的学习与实现》和《离散数学之关系（传递闭包）》这篇网上博客了解到了warshall算法，该算法可以通过一系列n阶矩阵r（k）来构造最终阶段n阶传递闭包矩阵r（n）。

3. 问题解题思路

根据《Warshall传递闭包算法的学习与实现》这篇网上博客的做法，首先画一个关系例图，并将该图用关系矩阵表示出来，称作为邻接矩阵。因为矩阵的直观性的优点，接下来的研究在矩阵的基础上进行。然后再根据《离散数学之关系（传递闭包）》中的图片和代码的理解，k为整体循环的次数，假设[i,j]位置的元素所指[k,j]元素和[i,k]元素均为1，则该数也为1。