如何在图表中规划多个形状？

Question

这是一个算法问题。 这是一个地图，它是一个大小为 m*n 的有界矩形多重连通区域，由于地图内的地形因素不同，每个网格都有不同的成本。地形“河流”的成本为无穷大，因为它被认为不可用，地形“山丘”的成本为10，“平原”的成本为1。并且有几个网格标记为矿井可以提供矿物。

这个类可以定义如下：

class MyMap {
  private _data: number[][];
  private _mine: [number, number][];
  constructor(width: number, height: number) {
    this._data = Array.from({ length: height }, () => Array(width).fill(0));
    this._mine = [];
  }

  getMine() {
    return this._mine;
  }

  setMine(mine: [number, number]) {
    this._mine.push(mine);
    this._data[mine[1]][mine[0]] = Infinity;
  }

  setCost(x: number, y: number, cost: number) {
    this._data[y][x] = cost;
  }

  getCost(x: number, y: number) {
    return this._data[y][x];
  }
}

现在这张地图上应该规划了好几个工厂，每个工厂都有不同的形状和面积，形状和面积是不允许改变的，但是你可以改变它们的方向。例如，这两个工厂被视为相同：

我们需要找到一个方案，在地图上定位几个指定的工厂，并规划一个路网，使所有工厂都与矿山相连，并使工厂和道路占用的总成本最小化。

我认为这个问题可能可以通过DP解决，但我现在还没有任何进展。

非常感谢您的评论@Dave。

这是一个简单的例子，地图上有 2 个地雷，需要放置 2 个工厂。这只是这张地图中的“平面”地形，但所有 3 个地形都可能出现在其他问题中。

这张地图的成本是32，其中17来自路网，15来自工厂。显然不是最优的，而最优的结果应该是这样的：

7 路网成本，15 工厂成本。最优成本是 22。

当然还有关于将工厂连接到不同矿山的规则，很抱歉我一开始就没有澄清。每个工厂至少有1个闸门，当至少1个闸门与路网相连时，该工厂被认为与路网相连。或者网关可以连接到已经联网的工厂，例如下图中的F3和F4。

由于矿井在地图中仅占 1 个网格，矿井周围 8 个网格中只有 1 个是道路，因此该矿井被认为与路网相连。

我不知道达到绝对最优解的时间复杂度，我认为接近最优解是可以接受的。

希望我蹩脚的英语没有让你感到困惑。

Answer 1

我认为不可能在多项式时间内找到最优解，除非使用线性规划。

假设您已经将工厂放置在地图上，那么找到最短路径就很容易了。这是一个简单的 BFS。

困难的部分是找到工厂的最佳布局。可能性的数量呈指数级增长，并且无法在多项式时间内尝试所有可能性。也许尝试一些启发式方法来遍历工厂布局。

您可以为某些工厂放置定义邻居，例如将一个工厂在一定维度上移动一格或旋转一个工厂。然后，从随机工厂布局开始，尝试所有邻居并评估它们。这应该很容易，因为对于工厂放置来说，找到路径只是 BFS，正如我之前所说的。选择哪些邻居可以通过一些启发式来决定。你可以看看禁忌搜索或模拟退火。这些通常对于这些类型的离散优化问题非常有效，并且非常容易实现。我还建议先尝试爬山搜索。爬山搜索只是简单地选择一直最好的邻居，收敛到一些局部最优。要最小化的成本函数当然是路径的成本。

这是一种启发式方法，通过实验来看看解决方案有多好，它将能够找到好的解决方案。

不同的方法是将这个问题映射为线性规划问题。如果你实现了这一点，我认为你就能够在多项式时间内找到全局最优值。