逻辑上确定最短路径

Question

到目前为止，我已经为位置创建了所有名称，现在我正在编写一个方法，该方法将 return 一个数组 "positions" 需要采取的方式到达最终目标。然后这个数组将被用于一个方法来确定到达那里应该花费多少"time"。但是，我现在被困在确定逻辑路径的方法中。

所以，每个位置都会有它连接的相对位置。例子;

NSArray *posAlphaConnections = [[NSArray alloc] initWithObjects:@"posDelta",@"posBravo",@"posFoxtrot", nil];

NSDictionary *posAlpha = @{@"connections":posAlphaConnections,
                           @"time":positionCrossTimeAlpha};

_positions = @{     @"posAlpha":posAlpha,
                    @"posBra....
                    }; //NSDictionary

所以你最终找到了一条路

问题是

-(NSArray *)returnPathWithPlayer:(PlayerClass *)player andGoal:(NSString *)goal {

    NSString *currentPosition = player.position;

    //Up to here

    return 0;
}

我目前在想..我应该运行为每个可能的连接建立一个循环..在达到目标之前的每个可能的下一个连接中，然后保持[=35]的路线=] 是最短的距离..？那就用那个路由吧。。不过逻辑上想不出怎么写。

PS：我还要补充一点，每个仓位都有一个大小变量，用于跨越该仓位所需的 "length of time"。所以这也应该考虑到，而不是位置最少，时间最少应该是优先考虑的。

编辑：

-(NSArray *)returnPathWithPlayer:(PlayerClass *)player andGoal:(NSString *)goal {

    NSString *currentPosition = player.position;

    NSLog(@"current Position %@", currentPosition);

    NSArray *connections = [[_positions valueForKey:currentPosition] valueForKey:@"connections"];

    __block BOOL pathFound = false;

    for (int i = 0; i < [connections count]; i++) {
        if ([connections[i] isEqualToString:goal]) {
            pathFound = true;
        } else {
            for (int j = 0; j < [[[_positions valueForKey:connections[i]] valueForKey:@"connections"] count]; j++) {
                if ([[[_positions valueForKey:connections[i]] valueForKey:@"connections"][j] isEqualToString:goal]) {
                    pathFound = true;
                }
            }
        }
    }

    if (pathFound) {
        NSLog(@"path to %@ found", goal);
    } else {
        NSLog(@"path to %@ not-found", goal);
    }

    return 0;
}

这就是我的逻辑所带我去的地方，但是，每个其他人都代表了一种新的可能性。这可能比我预期的要多。那么我怎样才能写得更好？

Answer 1

您正在寻找图中两个节点之间的最短路径。 Dijkstra's Algorithm 是针对此问题的一个很好且简单的广度优先搜索。

逻辑上确定最短路径

Logically determine shortest path

ios

objective-c

loops

logic

path-finding