矩阵操作：逻辑不能为高阶NXN矩阵数据获取正确答案 [英] Matrix manipulation: logic not fetching correct answer for higher order NXN matrix data

问题描述

我遇到了以下与Matrix操作相关的问题。

问题陈述

<有一个NxN矩阵，分为N * N个单元。每个单元格都有一个预定义的值。其中将作为输入给出。迭代必须发生K次，这也在测试输入中给出。我们必须确保在每次迭代时选择行/列的最佳/最小值。最终输出是每次迭代结束时保存的最优值的累积和。

步骤1。汇总单个行和列，找到行和列的最小总和（它可以是行或列，只需要最小行或列）

步骤2. 分别存储上述总和。

步骤3。
求和行或列。乘以1

从1到Kth重​​复步骤1,2,3。

 在每次迭代中添加总和（在步骤2中指定）
  

 <$ c $ 
 c> 2 4 
 1 3 
 2 4 
  

22

我能够写一个代码对于一些样本测试用例。输出工作正常。该代码对于较低阶的采样数据矩阵（例如，2×2,4×4，即使直到44×40（其具有较少的迭代））也工作良好。但是，当矩阵大小增加到100X100（复数迭代）时，我看到预期的输出输出值在10s和数字位置与实际输出及其随机数不同。因为我不能找到一个正确的输出模式输入。现在，我正在采取一个费用，真正调试第500循环，以确定问题。是否有任何更好的方法或方法来解决这种与巨大的矩阵操作相关的问题。有任何人遇到类似的问题，并解决它。

我主要感兴趣的是知道正确的方法来解决给定的矩阵问题。在Java中使用什么数据结构。目前，我使用原始的DS和数组int []或long []来解决这个问题。

这里需要的是一个数据结构，可以让您有效地查询和更新最小金额。最常用的是堆 。

使用堆，每个步骤的 heapify 操作都是（二进制堆）。

这意味着总复杂度为 < img src =https://i.stack.imgur.com/7GGHY.gifalt =！[enter image description here]> ， FAR 较小。 max 术语是为了补偿在每次迭代时，可以是增加的行或列。

---

另外，还有其他堆结构类型比二进制堆有更好的时间复杂性，例如二项式树，斐波纳契堆等。然而，这些更复杂，并且具有更高的常数因子开销。因此，对于您的项目，我觉得他们不是必要的，因为他们中的许多需要数据集大小来证明常数因子开销。

此外，它们都支持与二进制堆相同的外部操作，如通过堆的抽象数据结构定义的。

（heapify是内部操作特定于二进制堆结构。其他几个在理论上是优越的，因为他们隐式和lazily）

I came across below problem related to Matrix Manipulation.

problem statement

There is a NxN matrix,divided into N * N cells. Each cell has a predefined value. Which would be given as an input. Iteration has to happen K number of times which is also given in the test input. We have to make sure that we pick the optimum/min value of rows/columns at each iteration. Final output is the cumulative sum of optimum value saved at the end of each iteration.

Steps 1. Sum up the individual row and column and find the min sum of rows and columns, (it could be a row or a column, just need the minimum row or a column)

Step 2. Store the sum found above separately

Step 3. Increment elements of the min. sum row or column. by 1

Repeat steps 1,2,3 from 1 to Kth value

add the sum at each iteration(specified in step2)

output is the sum obtained on on the Kth iteration.

Sample data

2 4
1 3
2 4

Output data

22

I was able to write a code (in java) and tested the same for some sample test cases. The output worked fine. The code works fine for sample data matrix of lower order, say, 2x2,4x4,even till 44x40 (that has less iteration). However, when the matrix size is increased to 100X100 (complex iteration), I see the expected output output values differ at 10s and hundreds place of the digit from the actual output and its random. Since I am not able to find a correct pattern of output vs input. Now, it is taking a toll on me to really debugging 500th loop to identify the issue. Is there any better way or approach to solve such problem related to huge matrix manipulation. Has anyone come across issues similar to this and solved it.

I am mainly interested in knowing the correct approach to solve given matrix problem. What Data structure to use in java. At present, I am using primitive DS and arrays int[] or long[] to solve this problem. Appreciate any help in this regard.

解决方案

Which data structure?

What you need here is a data structure which allows you to efficiently query and update the minimum sum line. The most commonly used for this is a heap https://en.wikipedia.org/wiki/Heap_(data_structure).

For your purposes it's probably best to just implement the simplest kind, an array-based binary heap:

• See here: https://en.wikipedia.org/wiki/Binary_heap
• And here: http://courses.cs.washington.edu/courses/cse373/11wi/homework/5/BinaryHeap.java

..for implementation details.

---

Procedure:

• Initialize your heap to size M + N where M, N are the number of rows and columns.
• Before the loop, pre-compute the sum of each row and column, and add them as objects to the heap. Also add two arrays A, B which store the row and columon objects separately.
• Now heapify the heap array with respect to the line sum attribute. This ensures the heap follows the criterion of the binary heap structure (parent always > children). Read the sources to find out more about how to implement this (quite easy for a fixed array)
• For each iteration, look at the first element in the heap array. This is always the one with the smallest line sum. If this is a row object, then increment the sum attribute by N (no. of columns), and increment each object in B (list of columns) by 1. Do the same if it's a column.
• After this, always heapify before the next iteration.

At the end, just return the first element's attribute.

---

Time complexity:

The original naive solution (looping through all columns and rows every time) is .

Using a heap, the heapify operation at each step is (for a binary heap).

This means the total complexity is , FAR smaller. The max term is to compensate for the fact that at each iteration it may be either rows or columns which are incremented.

---

As a side note, there are other heap structure types which have even better time complexity than the binary heap, e.g. binomial trees, Fibonacci heaps etc. These however are far more complicated, and have higher constant-factor overheads as a result. Thus for your project I feel they are not necessary, as many of them need phenomenal data set sizes to justify for the constant factor overhead.

Besides, they all support the same external operations as the binary heap, as defined by the Abstract Data Structure of Heap.

(heapify is an internal operation specific to the binary heap structure. Quite a few of the other ones are theoretically superior as they do this operation implicitly and "lazily")

这篇关于矩阵操作：逻辑不能为高阶NXN矩阵数据获取正确答案的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！