稀疏矩阵的最小分量划分
如何将稀疏矩阵划分为最少数量的连接组件，这样每个组件在整个组件中都有一个公共行或列。我应该使用什么数据结构来在最短的时间内完成这个任务。我认为要做到这一点，我必须最大化每个组件中的元素数量，所以在输入时，我在每行和每列中存储了元素数量。我对列表进行排序，然后用max（min（行中的元素，列中的元素））进行行或列排序，即，
row 5-1 column 4-2
row 4-1 column 3-2
row 3-2 column 2-3
row 2-2 column 1-3
row 1-10
对于矩阵：
x
x
x x
x x
xxxxxxxxxx
然后我将首先删除第1列，然后我将不得不更新剩余的数组，这将占用大量的时间，并且为每一行和每列存储列表是不可行的，因为它会占用大量的内存。我只需要告诉矩阵的最小分区数，而不是实际的分区。在给定的矩阵中，可以用(row1,row2,row3,colum2-(1,2))作为分区对其进行分区。
Edit：或者等价地，我们可以把它看作是一个集合元素，它有两个与它们相关联的数字，并且我们输出了最小的分区数，这样每个分区都有两个公共数字中的一个。
共有1个答案
我相信你会发现这些讲座幻灯片是相关的:http://www.cs.indiana.edu/classes/b673/notes/graphpartitioning.pdf
-
稀疏矩阵(Sparse Matrix) 注：压缩存储的矩阵可以分为特殊矩阵和稀疏矩阵。对于那些具有相同元素或零元素在矩阵中分布具有一定规律的矩阵，被称之为特殊矩阵。对于那些零元素数据远远多于非零元素数目，并且非零元素的分布没有规律的矩阵称之为稀疏矩阵。 1. 稀疏矩阵的概念 在矩阵中，若数值为0的元素数目远远多于非0元素的数目时，则称该矩阵为稀疏矩阵。与之相反，若非0元素数目占大多数时，则称该矩阵
-
我正在实现一个稀疏矩阵类，使用映射向量来存储数据（映射表示矩阵的一行，其中键是列的索引，值是该位置的maitrix的值）我已经编写了计算行列式的函数，但我不知道是否有一种方法可以计算这种节省的时间（因为矩阵是稀疏的，大多数值为零）在这里我的实现： 这是类接口 我计算行列式的方式是什么？假设运算符（）以这种方式重载 提前感谢您的帮助
-
2.5.1 介绍 (密集) 矩阵是: 数据对象 存储二维值数组的数据结构 重要特征: 一次分配所有项目的内存 通常是一个连续组块，想一想Numpy数组 快速访问个项目(*) 2.5.1.1 为什么有稀疏矩阵？ 内存，增长是n**2 小例子（双精度矩阵）: In [2]: import numpy as np import matplotlib.pyplot as plt x = np.li
-
在课堂上，我必须为稀疏矩阵编写自己的线性方程求解器。我可以自由地使用任何类型的数据结构为稀疏矩阵，我必须实现几个解决方案，包括共轭梯度。 谢了！
-
问题内容： 我有一个很大的csv文件，其中列出了图中节点之间的连接。例： 0001,95784 0001,98743 0002,00082 0002,00091 因此，这意味着节点id 0001连接到节点95784和98743，依此类推。我需要将其读入numpy中的稀疏矩阵。我怎样才能做到这一点？我是python的新手，所以有关此的教程也将有所帮助。 问题答案： 使用scipy的lil_matri
-
如何在python中找到包含负数的稀疏矩阵的sqrt？和对负数不起作用。我还尝试使用。但它也不起作用。