algorithm - 数组中给定边的唯一三角形的数量

Question

我想通过蛮力（O（N ^ 3）或递归回溯）找到“唯一”三角形的最大数量（每个数组元素只能使用一次）。应该采取什么方法？

Answer 1

首先假设所有边的长度都是正整数。（对于实数，区间是半开半闭的，这使得推理变得更加混乱。）

[a,b]基本上，如果我们找到一种有效的方法来获取每个长度在范围内的边数0<=a<=b，我们可以将其处理为：

    edgeList = sort edgeList by length ascending order
    foreach ( edge1 in edgeList )
        foreach ( edge2 in edgeList where [edge2 >= edge1] )
            answer = answer + count_edge_number ( edge2 , edge1+edge2-1 );
    return answer;

因此，我们只需要这样一种方式。为此，您只需按长度按升序对边进行排序，对相关区间的下限和上限的索引（订阅）使用二进制搜索。（也就是说，对于任何一个[a,b]，使用二分查找找到最大i的element[i]<a和最小j的element[j]<=b）。这适用于O(logN).

所以你的任务可以完成O(N^2LogN)，比稻草人好多了O(N^3)。

Answer 2

创建一个地图（哈希图应该没问题），端点映射到侧面。所以每一方都有 2 个条目 - 每个端点都有一个条目。现在，您可以高效地查找从任何给定端点开始的所有面。

一些基本的伪代码：

// map[X] is all unused sides with X as end-point
// markAsUsed should also remove the side from the map
// markAsUnused should also add the side to the map

// initial function call for any unused side
backTrackFunction(anyUnusedSide)

backTrackFunction(side AB)
  if map.isEmpty
    Found a solution.
  markAsUsed(AB)
  for each side AC in map[A]
    if map[C].contains(CB)
      // AB, CB and AC form a triangle
      markAsUsed(CB)
      markAsUsed(AC)
      backTrackFunction(anyUnusedSide)

      // Backtrack
      markAsUnused(CB)
      markAsUnused(AC)

以上可能有一些问题，但这只是一个起点。