问题标签 [triangular]

我正在尝试实现一些基本的线性代数运算，其中一个运算是三角（上和/或下）矩阵的求逆。有没有简单稳定的算法来做到这一点？

谢谢你。

假设我有一个像这样的向量：

这真的是：

而且我只想使用向量/矩阵函数和运算符来生成矩阵：

或以下矩阵：

有什么想法吗？

（我是 MATLAB 的新手，但我一直背负着这些东西......）

我需要在我加载的图像中绘制一个三角形。三角形应如下所示：

但我遇到的主要问题是我不知道如何创建这样的矩阵。我想将此矩阵与图像相乘，图像矩阵由 3 个参数（W、H、RGB）组成。

介绍

作为较大程序（与渲染体积图形相关）的一部分，我有一个小但棘手的子问题，其中需要以特定方式标记任意（但有限）三角形 2D 网格。不久前，我写了一个解决方案（见下文），这对于我当时的测试网格来说已经足够好了，尽管我意识到这种方法可能不适用于人们能想到的每一个可能的网格。现在我终于遇到了一个网格，目前的解决方案根本不能很好地执行它——看起来我应该想出一种完全不同的方法。不幸的是，我似乎无法重新调整我的思路，这就是为什么我想在这里问的原因。

问题

考虑下面的图片。（颜色不是问题的一部分；我只是添加它们以改善（？）可视化。此外，变化的边缘宽度是完全不相关的伪影。）

对于每个三角形（例如，橙色 ABC 和绿色 ABD），三个边中的每一个都需要被赋予两个标签之一，例如“0”或“1”。只有两个要求：

1. 并非三角形的所有边都可以具有相同的标签。换句话说，对于每个三角形，必须有两个“0”和一个“1”，或者两个“1”和一个“0”。
2. 如果一条边由两个三角形共享，则两者的标签必须相同。换句话说，如果图片中的边 AB 为三角形 ABC 标记为“0”，那么它也必须为 ABD 标记为“0”。

网格是真正的 2D 网格，它是有限的：即，它不包裹，并且具有明确定义的外边界。显然，在边界上满足要求很容易——但在内部就变得更加困难。

直觉上，看起来至少应该存在一种解决方案，即使我无法证明这一点。（通常有几个——任何一个都足够了。）

当前解决方案

我目前的解决方案是一个非常强力的解决方案（此处提供只是为了完整性——请随意跳过本节）：

• 维护四组三角形——每个可能计数 (0..3) 的剩余边要标记一组。一开始，每个三角形都在其中三个边需要标记的集合中。
• 只要存在带有未标记边的三角形：
  找到仍然存在三角形的最小非零数量的未分配边。换句话说：在任何给定时间，我们都尽量减少已部分完成标记的三角形的数量。剩余的边数将在 1 到 3 之间。然后，只需选择一个这样的三角形，其中剩余的特定边数要分配。对于此三角形，请执行以下操作：
  • 看看是否有任何剩余边的标签已经被其他三角形的标签强加了。如果是这样，请按照上述要求 #2 所暗示的方式分配标签。
  • 如果这导致了死胡同（即，对于当前三角形，要求#1 不能再满足），那么从头开始整个过程​​。
  • 按如下方式分配任何剩余边：
    • 如果到目前为止还没有标记边缘，则随机分配第一个。
    • 当一个边缘已经分配时，分配第二个边缘，使其具有相反的标签。
    • 当分配两条边时：如果它们具有相同的标签，则分配第三条具有相反的标签（显然）；如果两者有不同的标签，则随机分配第三个。
  • 为不同数量的未分配边更新三角形集。
• 如果我们到达这里，那么我们有一个解决方案——万岁！

通常这种方法只需要几次迭代就可以找到解决方案，但最近我遇到了一个网格，该算法仅在重试一两千次后才会终止......这显然表明可能存在它永远不会终止的网格.

现在，我希望有一个确定性算法，可以保证总能找到解决方案。计算复杂度不是那么大的问题，因为网格不是很大，并且标记基本上只需要在加载新网格时完成，这不会一直发生 - 所以具有（例如）指数的算法复杂性应该没问题，只要它有效。（当然：效率越高越好。）

谢谢你读到这里。现在，任何帮助将不胜感激！

编辑：基于建议解决方案的结果

不幸的是，我无法让Dialecticus 建议的方法起作用。也许我没弄对……不管怎样，考虑下面的网格，起点用绿点表示： 让我们放大一点…… 现在，让我们开始算法。第一步之后，标签看起来像这样（红色=“星号路径”，蓝色=“环形路径”）： 到目前为止一切都很好。第二步之后： 第三 步： ……第四 步： 但是现在我们有问题了！让我们再做一轮 - 但请注意以洋红色绘制的三角形： 根据我目前的实现，洋红色三角形的所有边都在环形路径上，所以它们应该是蓝色的——这实际上是一个反例。现在也许我弄错了……但无论如何，最接近起始节点的两条边显然不能是红色的；如果第三个被标记为红色，那么该解决方案似乎不再适合这个想法。

顺便说一句，这是使用的数据。每行代表一条边，列解释如下：

1. 第一个节点的索引
2. 第二个节点的索引
3. 第一个节点的x坐标
4. 第一个节点的y坐标
5. 第二个节点的x坐标
6. 第二个节点的y坐标

起始节点是索引为 1 的节点。

我想接下来我应该尝试Rafał Dowgird 建议的方法......但也许我应该在一段时间内做一些完全不同的事情:)

我需要为表示三角矩阵的非常大的数组分配内存。我写了以下代码：

问题是执行它（分配内存）所需的时间随着矩阵大小的增加而迅速增加。有谁知道这个问题的更好解决方案？

谢谢。

我正在做一个家庭作业，由两部分组成。首先是编写一个 Prolog 程序来检查某对 X, Y 是否属于http://en.wikipedia.org/wiki/Triangular_number。例如：(2, 3) = true; (4, 10) = true 等等。

第一个解决方案使用“普通”递归，我已经解决了这个问题：

第二部分是使用尾递归/累加器，使用三角形/3 谓词来解决这个问题。虽然我在另一个分配中使用了累加器，其中使用非常明显，所以我对如何使用累加器有一个大致的了解，但我对如何在这种情况下使用它感到很困惑。

所以，我不是在寻找一种算法，我更愿意自己解决这个问题，但更多的是关于如何在这种情况下应用累加器的实用建议。

可能重复：
从数组中查找三角形

我在这个论坛上发现了这个面试问题：http: //geeksforgeeks.org/forum/topic/check-for-triangular-triplet

我正在复制下面的描述（由 geeksforgeeks.org 和原始海报 Kapil 提供）

给出了一个由 N 个整数组成的零索引向量 A。

三元组 (P, Q, R) 是三角形的，如果并且

例如，考虑向量 A 使得

三元组 (0, 2, 4) 是三角形的。

编写一个程序：

这样，给定一个由 N 个整数组成的向量 A，如果该向量存在三角形三元组，则返回 1，否则返回 0。

编辑：不应修改输入向量。并且需要 O(1) 空间要求，因此我们无法复制数组！

假使，假设：

N 是 [0..100,000] 范围内的整数；向量 A 的每个元素都是 [-2,147,483,648..2,147,483,647] 范围内的整数。

例如，给定向量 A 使得

如上所述，该函数应返回 1。

另一个例子：

给定向量 A 使得

该函数应返回 0。

预期最坏情况时间复杂度：O(n log n) 预期最坏情况空间复杂度：O(1)

显然，对数组进行排序不是一种选择。关于我们如何解决这个问题的任何想法？

我有一个 3 维点的数据集，我想使用 python 为其构建一个网格。我见过的所有软件都需要您提供边缘。python中是否有一个程序将一组3D点作为输入并输出一组三角形网格？如果可能的话，我希望网格是均匀的。

谢谢你， - 伊莱。

MATLAB 代码中的问题，用于求解所需的“n”个 Ax = b 类型的联立方程，前提是求解涉及上三角矩阵的方法，并且 A 和 b 的值与 x 值一起演变为 Aprime 和 bprime。

问题是编写一个代码，可以使用上三角矩阵求解“n”个 Ax = b 类型的联立方程。A 和 b 的值在命令窗口中以矩阵形式给出。当程序成功运行时，代码应返回 Aprime、bprime 和 x 值作为答案。对于某些方程式，代码还应将输出显示为“错误，矩阵尺寸不匹配”（或其他任何东西！）！该代码工作正常，除了它显示错误以及上面给出的错误消息。

我使用的代码如下，

请提供适当的更正....

在命令窗口中获得的结果，

A = [1 1 0;2 1 1;1 2 3]

一个=

b= [3;7;14]

b =

[x, Aprime, bprime] = 已解决(A, b)

x =

素=

bprim =

-0.5000 -11.0000

第二种是，

A = [1 2 3; 4 5 6]

一个=

b = [7;8;9;10]

b =

[x, Aprime, bprime] = 已解决(A, b) 错误！！矩阵尺寸应该一致。已解决的错误（第 2 行） n = size(A); 在调用“C:\Users\Hari\Documents\solved.m>solved”期间未分配输出参数“x”（可能还有其他参数）。

我在 R 中有一个非常大（大约 9100 万个非零条目）的 sparseMatrix()，它看起来像：

我想将其转换为三角矩阵（上或下），但是当我尝试 myMatrix = myMatrix * lower.tri(myMatrix) 时，出现一个错误，即“问题对于 lower.tri() 来说太大了”。想知道是否有人可能知道解决方案。谢谢你的帮助！