求算法：优化图元分布

显示全部楼层 · 2021-1-27 06:31:05

问题来源：
工业控制方面，需要将某个工程中所有的控制器的网络连接情况用图示表示出来。这个图称之为“网络拓扑图”。通俗一点，就是用图的形式将某些有关联的元素表示出来，有些类似于全国航线图。
问题分析：
该问题分解为2步：画图元和连线，图元表示控制器，连线表示某2个控制器之间有网络连接。重点和难点在图元分布。
根据图元的多少需要将图元绘制在页面上，涉及到怎么放的问题。现要求图元分布尽可能的匀称，尽可能避免有些地方拥挤又有些地方稀疏的情况。
问题抽象
这里我对问题作了进一步的抽象：根据图元个数将页面分为若干块方格，然后将图元均匀的分布在方格中。
引申为数学问题：m个球，放在一个正方形的棋盘里，每个棋盘格子或为空或最多放一个球，要求棋盘的行数最少且在某行或某列中的球数之和做少。
举例：3个球，分布在2×2的棋盘里，10个球分布在4×4的棋盘，17个球分布在5×5的棋盘里，……
问题抽象为函数：输入m(球个数)，输出一个矩阵，初始化为0.有球的位置置1。拜求各位仁兄，给予算法解答。万分感谢！！
CMatrix&Disp(uintcount)
{
……//求算法
};
分 -->

千问 · 2021-1-27 06:31:05

根号（m），如果是整数，设为n，那就是n*n的矩阵。如果不是整数，向上取整，设为n，也是n*n的矩阵。

千问 · 2021-1-27 06:31:05

感谢上楼，n*n的矩阵可以容易求的，这个矩阵怎么填呢，就是矩阵中哪些元素设为1？

千问 · 2021-1-27 06:31:05

引用2楼wawjliu的回复:感谢上楼，n*n的矩阵可以容易求的，这个矩阵怎么填呢，就是矩阵中哪些元素设为1？
在n*n的矩阵中，从左上角开始往右填1，如果遇到右边界，那么换行填，一直填到m个1用完。
自动布线不是应该与线有关的吗？但你的问题抽象已经不考虑线的排布了。