objective-c - 我怎样才能在 Objective-C 中加速这个强力加法算法？

Question

我正在尝试学习更多关于算法的知识，并构建了一个简单的算法来查看是否可以使用蛮力从随机创建的数字网格中生成目标数字。我已经做了足够多的工作来检查五个网格数字加在一起是否会创建目标，这应该足以满足我的目的，但是这个过程非常慢，在 iOS 模拟器上大约需要 11 秒。我怎样才能在这里加快速度？有没有比使用我正在使用的所有循环更有效的方法来做到这一点？这是我所有的代码，GridNumber是一个简单的NSObject包含两个整数的子类，number和 tag .

- (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;
 }

Answer 1

这被称为 Subset-Sum Problem ，并且众所周知它是 NP-hard，所以如果您正在寻找一个真正有效的解决方案，那么您就不走运了。 NP-hard 意味着关于输入的大小(网格中的数字数量)没有已知的多项式时间(即快速)解决方案。了解大 O 表示法是利用这些知识的基本知识，因此这似乎是一个不错的起点。

但是，由于您只使用正整数，并且目标数始终在 [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) 算法更好