搜索从矩阵的一个点到另一个点的最佳路线时内存使用率较低

Question

我有以下问题：

Tourist wants to create an optimal route for the hike. He has a terrain elevation map at a certain scale - an NxM-sized matrix containing the elevation values at the corresponding terrain points. Tourist wants to make a route from the start point to the end point in such a way that the total change in altitude while passing the route is minimal. The total change in altitude on the route is the sum of the changes in altitude modulo on each segment of the route. For example, if there is a continuous ascent or descent from the starting point of the route to the end point, then such a route will be optimal.

For simplicity, let's assume that you can only walk along the lines of an imaginary grid, i.e. from position (i, j), which is not on the edge of the card, you can go to position (i-1, j), (i + 1, j), (i, j-1), (i, j + 1). You cannot go beyond the edge of the map. On standard input: non-negative integers N, M, N0, M0, N1, M1 are entered. N is the number of rows in the heightmap, M is the number of columns. Point (N0, M0) is the starting point of route, point (N1, M1) is the end point of the route. Point coordinates are numbered starting from zero. The points can be the same. It is known that the total number of matrix elements is limited to 1,100,000.
After numbers height map is entered in rows - at first the first line, then the second, and so on. Height is a non-negative integer not exceeding 10000.

Print to standard output the total change in elevation while traversing the optimal route.

我得出结论，它是关于图形中的最短路径并写了this
但是对于 m=n=1000 程序吃太多（~169MiB，主要是堆）内存。
限制如下：

Time limit: 2 s
Memory limit: 50M
Stack limit: 64M

我也写了 C++ program 用 priority_queue 做同样的事情（只是为了检查，问题必须在 C 中解决），但它仍然需要 ~78MiB（主要是堆）

我应该如何解决这个问题（使用其他算法，优化现有的 C 代码或其他）？

Answer 1

您可以将高度值装入 16 位无符号整数（uint_16_t，如果使用 C++11）。要存储这些 2 字节值中的 1.1M，需要 2.2M 的内存。到目前为止一切顺利。

您的代码构建了一个包含链表和大量指针的内存图。您的基于堆的队列也有很多指针。您可以依靠更高效的表示来大大减少内存使用量 - 例如，您可以使用

构建一个 NxM 元素数组

  struct Cell {
      uint_32_t distance; // shortest distance from start, initially INF
      uint_16_t height;
      int_16_t parent;    // add this to cell index to find parent; 0 for `none`
  };

row, col 处的单元格将位于此数组中的索引 row + N*col 处。我强烈建议构建实用程序方法来查找每个邻居，这将 return -1 指示“越界”，否则为直接索引。两个索引之间的差异将在 parent.

中可用

您可以通过在节点索引数组上调用 stdlib 的“排序”并按距离对它们进行排序，在 C 中实现一个（效率不高的）优先级队列。这会减少很多额外开销，因为程序中的每个指针可能占用 8 个字节（64 位指针）。

通过避免大量指针，并使用内存中的描述而不是图表，您应该能够将内存消耗减少到

1.1M Cells x 8 bytes/cell                    = 8.8M
1.1M indices in the pq-array x 4 bytes/index = 4.4M

总共约 16 Mb w/overheads - 远低于规定的限制。如果时间太长，你应该使用更好的队列。

搜索从矩阵的一个点到另一个点的最佳路线时内存使用率较低

Lower memory usage when searching for optimal route from one point of matrix to another

c

dijkstra

shortest-path