F#与数学(II) – 在图形算法中使用矩阵(PartI)

在本系列的上篇文章中，我们了解了complex和BigRational类型，它们都是位于F# PowerPack中的数字类型。除了这两种，PowerPack库也包含了一种名为matrix的类型，此类型表示一种由浮点数组成的二维矩阵。

在这篇文章中，你将学会在F#中如何使用矩阵，如何使用F#PowerPack中提供的相关函数。我将用一个例子来介绍此语言库，此例子使用所谓的邻接矩阵来展示图。如果你对这些概念不熟悉，请不要担心。这个其实很简单，当看过这个例子后，你将会对它很清楚。此矩阵代表通过一条边连接两个顶点的图。很多矩阵类型中的标准操作在邻接矩阵中都是可用的，因此这篇指南将覆盖下面一些方面：

• 创建list类型的矩阵并使用来自Matrix模块的函数
• 使用slices来读或修改部分矩阵
• 展示矩阵之间的标准操作，如转置和矩阵相乘
• 在矩阵中使用更高级的功能函数

本文是介绍F#与F# PowerPack中数字计算功能系列文章中的一篇。此系列中的其他文章讨论了矩阵，自定义数字类型和编写范型代码。其它部分的链接请看F#数学-F# PowerPack概括。

使用矩阵实现图

下面的图展示了一个邻接矩阵。它表示一个有N个顶点以及用N*N大小的邻接矩阵来模拟的图。如果两个顶点间有一条边相连，那么对应的矩阵的列中包含1（顶点与右列的坐标相对应）。如果没有边相连，那么矩阵表中包含0：

如果你仔细看看上图中的邻接矩阵，你会发现一些有趣的东西。如，顶点0和3 在矩阵的对角线上都是1。这意味着从顶点到它自身有两条边。同时，这个图右分别包含1个和3个顶点的不相连的两部分组成。结果，此4x4的矩阵可以由大小分别为1x1和3x3的两个矩阵组成。第一个只包含一列（0，0），第二个应该包含从（1，1）到（3，3）的列。此合成矩阵所有剩下的列都应该包含0，因为此图的两个独立的组成部分之间没有边。下面的矩阵演示了它的组成方式：

在这篇指南的后面部分，我们将看看邻接矩阵的其他一些有趣的属性。首先，让我们看看构造矩阵的各种不同的方式，包括介绍中提到的用矩阵表示图。

创建矩阵

为了能使用矩阵类，首先，你需要将PowerPack.dll引用进来。矩阵的各种功能均位于Microsoft.FSharp.Math命名空间里，因此你也需要打开此命名空间。注意，matrix类型并非范型，因此它只能包含float类型。在大部分情况下，你需要使用浮点类型，因此，这并不算一种限制。如果你想在矩阵中存储其他类型的数据，你可以使用此类型的范型，我们将在此文的后面部分讨论它。下面的例子展示了创建矩阵最直接的方法：

1: open Microsoft.FSharp.Math 2: 3: let m1 = matrix [ [ 1. ] ] 4: let m2 = matrix [ [ 0.; 1.; 1. ] 5: [ 1.; 0.; 0. ] 6: [ 1.; 0.; 1. ] ]

代码中创建的两个矩阵对应了介绍部分所提到的那两个独立的矩阵。在本指南的后面部分，我们将用到它，如果你打算通读此指南中的代码，那么将它们存储在你的源代码文件中将显得很有帮助。

尽管上面的代码看起来像是用来创建矩阵的特别语法，其实不然。事实上，matrix是一个普通的函数，它接收一个浮点型序列的序列然后构造一个包含此值的矩阵。matrix是一个普通函数的事实意味着其参数不一定要是一个list原形数据。它可以使一个值或者任何F#中的表达式。然而，如果你调用一个包含不等长的一列链表的矩阵时，你将得到一个运行错误。

在Matrix模块中，同样有一些用来创建矩阵的函数：

1: Matrix.create 3 3 1.0 2: val it : matrix = matrix [ [1.0; 1.0; 1.0] 3: [1.0; 1.0; 1.0] 4: [1.0; 1.0; 1.0] ] 5: 6: Matrix.init 3 3 (fun i j -> 7: if i + j < 3 then 1.0 else 0.0) 8: val it : matrix = matrix [[1.0; 1.0; 1.0] 9: [1.0; 1.0; 0.0] 10: [1.0; 0.0; 0.0]]

Matrix.create函数用来创建一个给定元素值的给定大小的矩阵。在我们的这个例子中，我们使用了值1.0。如果我们将此矩阵当作一些图的邻接矩阵，那么其代表的结果将是一幅每个顶点都有一条连接其自身的边的图。

函数Matrix.init则更加的复杂——它接收一个需要指定维数的矩阵和一个函数作为参数。这个函数是用来计算矩阵中各元素的值。在我们的例子中，仅当目前坐标值的和小于3时，我们才返回1.0。其结果就是矩阵的左上三角形的值都是1.0，其余的皆为0.0。

下面的表简要的给出了其他可以用来创建矩阵的函数：

Matrix.identity int -> matrix

• 创建一个指定大小的方形矩阵，除对角线上的值为1.0外，其他的均为0.0。创建好的矩阵显得有点密集（意思是所有的元素都存储在一个二维数组中）。

Matrix.initDense int -> int -> seq -> matrix

• 创建一个指定大小的密集矩阵。然后将给定的序列迭代进去，方法是将元组前两个数字组合起来所对应的列的值设定为此元组的第三个元素。

Matrix.initSparse int -> int -> seq -> matrix

• 创建一个指定大小的稀疏矩阵，此矩阵的一些元素的值由序列中的第三个元素指定。创建的矩阵是用稀疏表示法,这是那些含有多个0的矩阵的一种高效使用内存表示法.有些操作运算对稀疏矩阵不可用并且它们可以使用Matrix.toDense方法来转化为密集表现形式。

Matrix.zero int -> int -> matrix

• 创建一个每个元素均包含0.0的指定大小的密集矩阵。