1

我有一个网格 NxN ：

2  1  
4  8

我想在这个网格中找到所有路径： 

{2,1}  
{2,1,8}  
{2,1,8,4}  
{1,8,4}
{1,8}
{8,4}
...

我的网格是这样定义的：

gridArray = [NSArray arrayWithObjects:
[NSArray arrayWithObjects:@"2", @"1", nil],  
[NSArray arrayWithObjects:@"4", @"8", nil],nil];

我有一个对象块（一个数字）：

@interface Piece : NSObject {
int numCol;
int numRow;
NSNumber * value;

int nbNeighborsPieces;      

NSMutableArray *neighborsArray; 
}

我能够计算出所有邻居的一块。

但是现在，我想计算给定一块的所有路径。然后每件。使用对象路径：

@interface Path : NSObject {

NSMutableArray * arrayOfPiece;
int sum;
}

有点儿 ：

for(Piece * pieces in pieceArray) {
[self path:piece];
}

我想我必须使用递归方法，但我不知道如何。

4

2 回答 2

0

解决这个问题的算法会很慢；我会认为一些在 O(n^n) 的范围内。

您可以使用类似于Depth First Search的方法找到所有路径。

首先，我认为你应该改变你的存储方式。不是将项目存储在数组的数组中，而是基于Vertex的概念创建一个节点类。该节点类将代表最深数组中的元素之一。每个节点都应该有一个数组，该数组将包含其他节点，这些节点是该节点的邻居。它还应该具有id您要存储的对象的类型。这将允许您创建有向图。它还将允许您更轻松地实现递归。

@interface Node : NSObject
{
    id object;
    NSMutableArray * neighbours;
}

就算法而言，这是我要开始的，我相信有一些修改可以使它更快。

首先创建一个数组来保存路径和一个数组来表示路径。

NSMutableArray *paths;
NSMutableArray *currentPath;

在 Node 类中添加将执行递归的方法

- (void)findAllPathsExtending:(NSMutableArray *)path filling:(NSMutableArray *)paths 
{
    if ( [path containsObject:self] )
    {
        return;
    }

    [path addObject:self];
    [paths addObject:[path copy]];

    for (Node *aNode in neighbours)
    {
        [aNode findAllPathsExtending:path filling:paths];
    }

    [path removeObject:self];

    return; 
}

但仅此一项并不能为您提供所有路径。您仍然需要为图中的每个节点执行此算法。正如我之前提到的，当你增加数组的大小时，这个任务会很快变得非常昂贵。

于 2013-03-28T01:27:23.257 回答
0

我在考虑 Dijkstra 算法http://en.wikipedia.org/wiki/Dijkstra的 s_algorithm，或A* 搜索算法 http://en.wikipedia.org/wiki/A*_search_algorithm。他们都是探路者。Generaly Dijkstra 稍微慢一些（计算量更大）但更容易实现。Dijkstra 是递归的，不确定 A* 搜索，因为我从未实现过。如果您有小网格，Dijkstra 将真正满足您的需求。并且不仅会计算您的路径，还会计算所有其他路径。我很喜欢。

于 2013-03-28T09:27:42.900 回答