问题标签 [decomposition]

所以，我试图了解动态规划算法，以找到凸多边形的最小加权三角剖分分解。对于那些不知道的人，三角剖分是我们将凸多边形分解为三角形的地方。最小加权三角剖分是多边形的三角剖分，其中所有边（或每个三角形的周长）的总和最小。

它实际上是一个相当常见的算法，但是我无法掌握它。这是我试图理解的算法：

http://en.wikipedia.org/wiki/Minimum-weight_triangulation#Variations

这是我试图遵循的另一个描述（向下滚动到 5.2 Optimal Triangulations）：

http://valis.cs.uiuc.edu/~sariel/teach/notes/algos/lec/05_dprog_II.pdf

所以到目前为止我明白这一点。我取所有顶点，并确保它们围绕原始多边形的周边按顺时针顺序排列。我创建了一个返回最小权重三角剖分的函数，我将其称为 MWT(i, j) 从顶点 i 开始到顶点 j 的多边形。这个函数将是递归的，所以第一次调用应该是 MWT(0, n-1)，其中 n 是顶点的总数。MWT 应该测试由点 i、j 和 k 组成的所有三角形，其中 k 是它们之间的任何顶点。到目前为止，这是我的代码：

但是，当我运行它时，它会溢出堆栈。我完全迷失了，如果有人能帮助我朝着正确的方向前进，我将不胜感激。

如果你们需要更多信息，请询问。

所以我一直在用 Python 编写一个程序，该程序可以找到凸多边形的最小权重三角剖分。这意味着它找到了权重（所有三角形周长的总和），以及弦列表（穿过多边形的线将其分解为三角形，而不是边界）。

我的印象是我正在使用动态编程算法，但是当我尝试使用更复杂的多边形时，它需要很长时间（我不确定需要多长时间，因为我还没有完成它）。

它适用于 10 边多边形，但我正在尝试 25，这就是让它停滞的原因。我的老师给了我多边形，所以我认为 25 应该也可以工作。

由于该算法应该是O(n^3)，因此 25 边多边形的计算时间大约要长 15.625 倍，但是看到 10 边似乎是瞬时的，需要更长的时间。

我是否在那里进行了某种我没有意识到的 n 操作？我看不到我正在做的任何事情，除了最后一部分我通过将列表变成一个集合来消除重复项，但是在我的程序中，我在转换发生之前在 decomp 之后放置了一个跟踪，它不是甚至达到了那个地步。

这是我的代码，如果你们需要更多信息，请询问。里面的东西使它需要更长的时间O(n^3)，我需要找到它，这样我就可以把它修剪掉。

我将添加我正在使用的多边形，第一个多边形马上就解决了，而第二个多边形到目前为止已经运行了大约 10 分钟。

第一：

第二个：

我正在尝试通过部分旋转来实现我自己的 LU 分解。[L, U, P] = lu(A)我的代码在下面，显然工作正常，但是对于某些矩阵，与matlab中的内置函数相比，它会给出不同的结果

谁能发现哪里错了？

这是我测试过的两个矩阵。第一个是正确的，而第二个有一些元素倒置。

更新

我检查了我的代码并纠正了一些错误，但部分旋转仍然缺少一些东西。在第一列中，最后两行总是反转（与matlab中 lu() 的结果相比）

我似乎找不到太多关于这方面的信息，所以我想我会在这里提出来。我经常发现自己遇到的问题之一是在处理列表时对单个对象的创建进行单元测试。例如，我有一个方法签名，例如IEnumerable<Output> Process(IEnumerable<Input> inputs). 当对单个输入进行单元测试时，我会创建一个输入列表并简单地调用First()结果并确保它是我期望的。这将导致诸如：

我目前的想法是，也许一个类应该负责创建对象，而另一个类负责编排我的输入列表。请参见下面的示例。

通过上面发布的内容，我可以轻松测试我是否能够创建一个Output给定的Input. 请注意，除了 from 之外，我不需要调用SingleCreator代码库中的任何其他位置CompositeCreator。创建ICreator还可以让我在需要执行类似任务的其他时间重复使用它，我目前在当前项目中执行 2-3 次

有没有人有这方面的经验可以提供一些启示？我只是想太多了吗？非常感谢您的建议。

我在合成算法和寻找候选键方面遇到了一些问题，因为我觉得我课程中提供的幻灯片仅提供了如何推断它们的示例，没有任何解释。

因此，如果我们有一个具有单一关系 R[ABCDE] 的关系模式，其函数依赖关系为：{AB->CD, C->AD, E->B}，

到目前为止，我已经到了这里：规范的 shell 是：C={AB->C，C->D，E->B}，候选键是：EB AE 和 EC。

1) 应用合成算法找到无损且保持依赖关系的 3NF 分解。

我知道如何检查分解是否实际上是无损的和保持依赖关系，但不知道如何到达那里。请看下面：

i) 为 F 构造一个规范覆盖 C

ii) 定义 C'={X union Y | X->Y“属于”Consol(C)} 这个我知道

iii) 将 C 定义为 C' 的子集，其中删除了所有被另一个包含的关系。这我知道我是否认为正确。

iv) 如果 C 已经包含 R 的超键，则将 C2 定义为 C。否则，将 C2 定义为 C 并集 K 的某个键 K。这一步看不懂。

2）彻底激发3）中得到的分解是否也在BCNF中。

提前致谢！

感谢您对 Python 3 的翻译帮助，该 Python 3 将任意大小的输入数组分解为长度为 4 的较小方形数组。

我已经在 numpy 中尝试过块和数组函数，但它们对此毫无用处。

这是我在 Perl 中运行良好的代码，但我希望它与 Python 进行比较（在效率上）。

例如，我有以下 12 x 12 矩阵：

我希望它分解成 6 个长度为 4 的方形子矩阵：

原始矩阵来自以下格式的文件（程序应从文本文件中读取）：

所以程序需要用连字符分割它，并将每个块作为大矩阵的一行。这 6 个子矩阵应该采用相同的输入格式，因此第一个是：

程序应该将任何输入矩阵分解为长度为 j 的方阵，比如 4，如果原始矩阵的大小不是 4 的倍数，那么它应该忽略不能形成 4x4 矩阵的剩余块。

原始输入文件中可能会出现几个不同大小的大矩阵，并以断线作为分隔符。例如，原始大矩阵和另一个 rmatrix 在文本文件中看起来如下所示：

并检索 2 组子数组，6 个 4x4 数组中的一个，第二个 4x4 中的一个。如果你为单一情况解决它当然没问题。

我正在创建一个类来表示三对角矩阵。这些是在对角线上有一组非零值的方阵，在上下对角线上有一组非零值，然后在其他任何地方都为零。

为了存储它们，我使用了三个一维数组：每个对​​角线一个。

这是一个例子：

因此，a_i 有一个数组，u_i 有一个数组，l_i 有一个数组。不存储零。

我需要一个算法来执行 LU 分解。LU 分解通常会产生以下两个矩阵：

然而，1 和零一样没有用，它们只是浪费空间，所以我要求算法返回以下三对角矩阵作为 LU 分解：

我设法获得了以下等式：

但我不确定如何找到我需要的所有 a_i、b_i 和 c_i 的通用公式。

有谁知道一个很好的、易于编程的算法来为我做这件事。我不是在寻找任何有效的东西，只是最容易编程的东西。

首先十分感谢。

分解以下字符串的最佳方法是什么：

进入以下：

我目前正在使用一个用 C 语言编写的带有 MPI 并行化的程序。计算网格使用常见的域分解技术进行划分。关于 2D 分解（简化）的流程布局如下：

在代码中的某一时刻，我必须求解一系列仅具有 X 相关性的方程。使用当前形式的拓扑，由于 x 依赖性，它一次只能与 3 个进程并行化，这导致了我的问题......是否有一种方便/有效的方式将当前拓扑映射到另一个在代码中，哪个有利于完全并行化，即使用所有 9 个进程？例如，像这样：

有人可能会问，为什么不从这个开始……好吧，2D 域分解对于整个问题来说效率更高，而且我之后还有 y 依赖关系，我需要对拓扑做类似的事情，因此上图是转置。

因此，我需要使用一些通信例程将 2D 拓扑映射到代码中的 1D 拓扑（动态），以实现与 9 个进程的完全并行化，但我不确定是否有一种高效且有效的方法来做到这一点VS 并行运行 3 个进程的原始问题。任何的意见都将会有帮助。谢谢！！

我需要解析 SVG（只是简单的事情），剩下要做的就是从矩阵变换中正确提取位置和角度。我知道这个问题已经被问过很多次，我相信我已经阅读了很多答案、文件等，但仍然无法正确处理。这是我设法准备的最简单的例子：

我创建了 1000x1000 的文档（所有数字以 px 为单位），并在 100,100 位置放置了一个 100x100 大小的矩形。它生成了以下 SVG 文件（我已经删除了样式属性和父标签）。文件中的任何地方都没有其他转换：

然后我将矩形旋转了 33 度（使用“转换”inkscape 工具）。SVG 代码如下所示：

现在，我的目标是从矩阵中提取位置和角度，所以基本上我想取回以下值：x:100,y:100,angle:33。为了做到这一点，我假设了以下公式：

结果是：t = 0.575958787（即 33 度） - 非常好

但是 x'=-90.72230563 和 y'=128.8770646 这正是让我感到困惑的地方——为什么不是 100,100 ？