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

1ピースのすべての隣人ピースを計算することができました。

しかし今、私は与えられた 1 つのピースのすべてのパスを計算したいと思います。次に、すべてのピースについて。オブジェクト Path の使用:

@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に似たものを使用して、すべてのパスを見つけることができます。

まず、ストレージのアプローチを変更する必要があると思います。配列の配列に項目を格納する代わりに、頂点の概念に基づいてノード クラスを作成します。このノード クラスは、最も深い配列の要素の 1 つを表します。各ノードには、ノードの隣接ノードである他のノードを含む配列が必要です。また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

ダイクストラ アルゴリズムhttp://en.wikipedia.org/wiki/Dijkstra 's_algorithm 、またはA* 検索アルゴリズム http://en.wikipedia.org/wiki/A*_search_algorithm を考えていました。どちらもパスファインダーです。一般的に Dijkstra は少し遅くなりますが (計算量が多くなります)、実装は簡単です。Dijkstra は再帰的で、A* 検索については不明です。実装したことがないためです。グリッドが小さい場合、Dijkstra は本当に必要なものに適合します。また、パスだけでなく、他のすべてのパスも計算します。私は本当にそれが好き。

于 2013-03-28T09:27:42.900 に答える