小编win*_*ton的帖子

这是一个优化问题,我已经从我遇到的一个更具体的问题中简化了,但是我不确定这个问题在哪里被分类,或者获得解决方案的方法(强力,模拟退火,线性规划？ ).任何帮助或参考表示赞赏!

我们有两个MxN矩阵M1和M2,其中每个条目是1或0.

我试图在尽可能少的时间内从矩阵M1到矩阵M2.

目标是最小化总时间,其中时间由以下定义:

• 0 - > 1转换= 1s
• 1 - > 0转换= 0.1s

可以更改矩阵的唯一方法是选择一组行和列,并将拾取的行和列的交叉点处的所有元素切换为0/1,整个转换采用上面指定的时间.

例:

M1
1 1 1
1 1 0
1 0 0

M2
0 0 1
0 1 1
1 1 1

第一次迭代:

1. 选择第2行和第3行,以及M1的第 2列和第3列.

2. 将所有相交元素转换为1

   • 需要1s

M1
1 1 1
1 1 1
1 1 1

第二次迭代:

1. 选择M1的第 1行和第1列和第2列.

2. 将所有相交元素转换为0

   • 需要0.1秒

M1
0 0 1
1 1 1
1 1 1

第三次迭代:

1. 选择M1的第2行和第1列.

2. 将所选元素转换为0

   • 需要0.1秒

M1 …