1

ブルートフォース（O（N ^ 3）または再帰的バックトラッキング）によって、「一意の」三角形の最大数（各配列要素は1回だけ使用できます）を見つけたいと思います。どのようなアプローチを取るべきですか？

4

2 に答える 2

2

最初に、すべてのエッジの長さが正の整数であると仮定します。(実数の場合、区間は半分開いて半分閉じており、推論が難しくなります。)

基本的に、[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)。

于 2013-07-05T13:01:39.720 に答える
0

エンドポイントがサイドにマップされたマップを作成します (ハッシュマップで問題ありません)。したがって、各サイドには 2 つのエントリがあり、各エンドポイントに 1 つです。これで、任意のエンドポイントから始めて、すべての側面を効率的に検索できるようになりました。

いくつかの基本的な擬似コード:

// 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)

上記にはいくつかの問題があるかもしれませんが、出発点になることを目的としています。

于 2013-07-05T12:34:12.410 に答える