0

私はアルゴリズムについてもう少し学ぼうとしており、ランダムに作成された数値のグリッドからターゲット数値を作成できるかどうかをブルートフォースを使用して確認するための簡単なアルゴリズムを作成しました。合計した 5 つのグリッド番号がターゲットを作成するかどうかを確認するのに十分な作業を行いました。これは、念頭に置いていた目的には十分なはずですが、プロセスは非常に遅く、iOS シミュレーターで約 11 秒です。ここで物事をスピードアップするにはどうすればよいですか? 私が使用しているすべてのループを使用するよりも効率的な方法はありますか? これが私のすべてのコードです.2つの整数を含むGridNumber単純なNSObjectサブクラスです .numbertag

- (void)viewDidLoad
 {
      [super viewDidLoad];

      // 0. Set up target number.
      int random = arc4random() % 100 + 3;
      NSNumber *target = [NSNumber numberWithInt: random];

      // 1. Set up array of available numbers.
      NSMutableArray *grid = [[NSMutableArray alloc] init];
      for (int i = 1; i < 48; i++) {
           GridNumber *number = [[GridNumber alloc] initWithRandomIntegerAndTag: i];
           [grid addObject: number];
      }

      if ([self canTarget: target BeMadeFromGrid: grid]) NSLog(@"--- SOLVEABLE!");
      else NSLog(@"--- UNSOLVEABLE!");
 }

 - (BOOL) canTarget: (NSNumber *) target BeMadeFromGrid: (NSArray *) grid
 {
      NSLog(@"TARGET NUMBER IS: %d", target.intValue);

      // 2. See if the target already exists first.
      for (GridNumber *firstValue in grid) {
           if (firstValue.number == target.intValue) {
                NSLog(@"SOLVEABLE IN 1: Grid already contains target!");
                return YES;
           }
      }

      // 3. Add elements once, see if any of those give the result.
      for (GridNumber *firstValue in grid) {
           for (GridNumber *secondValue in grid) {
                int result = firstValue.number + secondValue.number;
                if (result == target.intValue && firstValue.tag != secondValue.tag) {
                     NSLog(@"SOLVEABLE IN 2: Adding %d and %d creates target!", firstValue.number, secondValue.number);
                     return YES;
                }
           }
      }

      // 4. Add elements twice, see if any of those give the result.
      for (GridNumber *firstValue in grid) {
           for (GridNumber *secondValue in grid) {
                for (GridNumber *thirdValue in grid) {
                     int result = firstValue.number + secondValue.number + thirdValue.number;
                     if (result == target.intValue && firstValue.tag != secondValue.tag && firstValue.tag != thirdValue.tag && secondValue.tag != thirdValue.tag) {
                          NSLog(@"SOLVEABLE IN 3: Adding %d, %d and %d creates target!", firstValue.number, secondValue.number, thirdValue.number);
                          return YES;
                     }
                }
           }
      }

      // 5. And three times..
      for (GridNumber *firstValue in grid) {
           for (GridNumber *secondValue in grid) {
                for (GridNumber *thirdValue in grid) {
                     for (GridNumber *fourthValue in grid) {
                          int result = firstValue.number + secondValue.number + thirdValue.number + fourthValue.number;
                          if (result == target.intValue && firstValue.tag != secondValue.tag && firstValue.tag != thirdValue.tag && firstValue.tag != fourthValue.tag &&
                              secondValue.tag != thirdValue.tag && secondValue.tag != fourthValue.tag && thirdValue.tag != fourthValue.tag) {
                               NSLog(@"SOLVEABLE IN 4: Adding %d, %d, %d and %d creates target!", firstValue.number, secondValue.number, thirdValue.number, fourthValue.number);
                               return YES;
                          }
                     }
                }
           }
      }

      // 6. And four times..
      for (GridNumber *firstValue in grid) {
           for (GridNumber *secondValue in grid) {
                for (GridNumber *thirdValue in grid) {
                     for (GridNumber *fourthValue in grid) {
                          for (GridNumber *fifthValue in grid) {
                               int result = firstValue.number + secondValue.number + thirdValue.number + fourthValue.number + fifthValue.number;
                               if (result == target.intValue && firstValue.tag != secondValue.tag && firstValue.tag != thirdValue.tag && firstValue.tag != fourthValue.tag &&
                                   firstValue.tag != fifthValue.tag && secondValue.tag != thirdValue.tag && secondValue.tag != fourthValue.tag && secondValue.tag != fifthValue.tag &&
                                   thirdValue.tag != fourthValue.tag && thirdValue.tag != fifthValue.tag && fourthValue.tag != fifthValue.tag) {
                                    NSLog(@"SOLVEABLE IN 5: Adding %d, %d, %d, %d and %d creates target!", firstValue.number, secondValue.number, thirdValue.number, fourthValue.number, fifthValue.number);
                                    return YES;
                               }
                          }
                     }
                }
           }
      }

      // 7. This is if it can't be made.
      return NO;
 }
4

3 に答える 3

2

これはSubset-Sum Problemとして知られており、NP 困難であることが知られているため、本当に効率的なソリューションを探している場合は不運です。NP 困難とは、入力のサイズ (グリッド内の数値の数) に関して既知の多項式時間 (つまり、高速) の解がないことを意味します。big-Oh 記法を理解することは、この知識を活用するための初歩的なことなので、そこから始めるのがよいでしょう。

ただし、正の整数のみを使用しており、ターゲット数は常に [3,102] の範囲内にあるため、動的計画法を使用して疑似多項式時間のソリューションを利用できます。@Sharkが述べたように、これはおそらく今のところ本当に集中したいことです-再帰的な問題解決の基本を理解していない場合、既知のNP困難な問題にすぐに取り組むことは最良のアイデアではありません;)

疑似コードでは、次のようなことをしたい:

Define array on [0,102] representing reachable numbers.  Set 0 to be reachable
for each NSNumber in grid:
    Looping upwards, for every reachable target in [3,102], set target + NSNumber to be reachable too
    If the sum exceeds 102, cut the loop
Return true if, after checking all numbers, target is reachable

この一般化されたアルゴリズムは、正の整数に対して O(N*M) 時間で実行されます。ここで、N はグリッド内の数値の数であり、M は可能な最大ターゲットです。N = 48 および M = 102 の場合、これは現在使用している O(N^5) アルゴリズムよりも優れたパフォーマンスを発揮するはずです。

于 2013-05-16T15:19:10.477 に答える
0

追加のすべての組み合わせを含むセットを生成し、目的の番号がそのセット (リスト) にあるかどうかを確認することもできます。このようなセットを生成するには長い時間がかかりますが、O(logn) で同じセットに対して複数のターゲットを検索できるという利点があり、グリッドに対して複数のクエリを実行する際の効率が向上します。

数値を再度追加して基本的にセットを再生成する代わりに、同じ数値グリッドに対して新しいターゲットをチェックします。

于 2013-05-16T17:20:14.407 に答える