0

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

- (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-hard 意味着对于输入的大小（网格中的数字数量）没有已知的多项式时间（即快速）解。对大哦符号的理解是利用这些知识的基本知识，因此这似乎是一个很好的起点。

但是，由于您只使用正整数，并且目标数始终在 [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 回答
1

基于@torquestomp 的想法，这是我能够快速组合的一些 C 代码。对于 48 个数字（范围从 1 到 21）的网格，寻找小于 203 的目标几乎不会花费超过百分之几秒的时间。当您允许更长的解决方案（超过 5 或 6 个数字）时，运行时间将增加。请注意，我尚未完全测试此功能。报告的时间是在 Mac 上。在 iPhone 上，它们会更慢。

编辑：如果您按降序对数字列表进行排序，您应该首先找到“最佳”（总数字较少）解决方案。

typedef void(^execution_block_t)(void);

double time_execution(execution_block_t aBlock);
double time_execution(execution_block_t aBlock)
{
    uint64_t time0 = mach_absolute_time();
    aBlock();
    uint64_t time1 = mach_absolute_time();
    return (double)(time1 - time0)/NSEC_PER_SEC;
}

static int totalTests = 0;

int findPartialSum(int target, int *grid, int gridCount, int startIndex, int *solution, int depth, int maxDepth)
{
    for (int i=startIndex;  i<gridCount;  i++) {

        int newTarget = target - grid[i];
        totalTests++;

        if (newTarget == 0) {
            solution[depth-1] = i;
            return 1;
        }

        if (newTarget > 0 && depth < maxDepth) {
            int found = findPartialSum(newTarget, grid, gridCount, i+1, solution, depth+1, maxDepth);
            if (found > 0) {
                solution[depth-1] = i;
                return found + 1;
            }
        }
    }
    return 0;
}


int main (int argc, const char * argv[])
{
    @autoreleasepool {

        static const int gridSize = 48;
        static const int solutionSize = 5;

        int *solution = calloc(sizeof(int), solutionSize);
        int *grid     = calloc(sizeof(int), gridSize);
        int  target   = arc4random_uniform(200) + 3;

        for (int i=0;  i<gridSize;  i++)
            grid[i] = arc4random_uniform(20) + 1;

        NSMutableArray *numbers = [NSMutableArray array];
        for (int i=0;  i<gridSize;  i++)
            [numbers addObject:@(grid[i])];

        NSLog(@"\nTarget = %d\nGrid = %@", target, [numbers componentsJoinedByString:@","]);

        __block int count = 0;
        double elapsedTime = time_execution(^(void) {
            count = findPartialSum(target, grid, gridSize, 0, solution, 1, solutionSize);
        });

        NSLog(@"Looking for solution with up to %d numbers", solutionSize);
        if (count > 0) {

            [numbers removeAllObjects];
            for (int i=0;  i<count;  i++)
                [numbers addObject:@(grid[solution[i]])];

            NSLog(@"Found solution with %d numbers: %@", count, [numbers componentsJoinedByString:@","]);

        } else {
            NSLog(@"No solution found");
        }

        NSLog(@"After looking at %d possible sums",totalTests);
        NSLog(@"Elapsed time was %fs", elapsedTime);

        free(solution);
        free(grid);
    }
    return 0;
}

一些示例输出：

Target = 159
Grid = 16,18,19,6,18,5,12,7,7,4,18,3,7,13,10,19,7,14,19,6,16,4,8,4,3,17,11,16,5,8,18,9,4,13,14,8,17,18,13,5,20,14,4,5,13,20,17,1
Looking for solution with up to 5 numbers
No solution found
After looking at 1925356 possible sums
Elapsed time was 0.014727s


Target = 64
Grid = 4,6,1,1,13,12,15,10,11,6,18,6,8,2,15,3,18,5,20,1,3,12,20,3,18,5,1,12,15,14,2,20,9,1,14,9,6,1,2,10,12,7,7,4,2,12,20,6
Looking for solution with up to 5 numbers
Found solution with 5 numbers: 4,6,18,18,18
After looking at 7271 possible sums
Elapsed time was 0.000048s
于 2013-05-16T16:37:27.933 回答
0

您还可以尝试生成包含所有加法组合的集合，并检查您的目标编号是否在该集合（列表）中。生成这样一个集合需要很长时间，但这会给您带来在 O(logn) 中针对同一集合查找多个目标的好处 - 从而更有效地针对您的网格运行多个查询。

每次您想根据相同的数字网格检查新目标时，而不是重新添加数字并基本上重新生成集合。

于 2013-05-16T17:20:14.407 回答