3

タスクを実装しようとしています。円上に 2*n 点があります。したがって、それらの間に n 個の和音を作成できます。n 個の交差しない弦を描くすべての方法を出力してください。

例: n = 6 の場合、(1->2 3->4 5->6)、(1->4、2->3、5->6)、(1->6、2 ->3, 4->5), (1->6, 2->5, 3->4)

1-> 2、4、6 から和音を作成し、残りの 2 つの間隔の答えを生成することにより、再帰アルゴリズムを開発しました。しかし、より効率的な非再帰的な方法があることは知っています。NextSeq 関数を実装することによる可能性があります。

誰にもアイデアはありますか？

UPD:私は中間結果をキャッシュしますが、本当に欲しいのは、前のシーケンスによって次のシーケンスを生成できる GenerateNextSeq() 関数を見つけて、そのようなすべての組み合わせを生成することです

ちなみにこれは私のコードです

struct SimpleHash {
    size_t operator()(const std::pair<int, int>& p) const {
        return p.first ^ p.second;
    }
};

struct Chord {
    int p1, p2;
    Chord(int x, int y) : p1(x), p2(y) {};
};

void MergeResults(const vector<vector<Chord>>& res1, const vector<vector<Chord>>& res2, vector<vector<Chord>>& res) {
    res.clear();
    if (res2.empty()) {
        res = res1;
        return;
    }


    for (int i = 0; i < res1.size(); i++) {
        for (int k = 0; k < res2.size(); k++) {
            vector<Chord> cur;

            for (int j = 0; j < res1[i].size(); j++) {
                cur.push_back(res1[i][j]);
            }

            for (int j = 0; j < res2[k].size(); j++) {
                cur.push_back(res2[k][j]);
            }
            res.emplace_back(cur);

        }

    }
}

int rec = 0;
int cached = 0;

void allChordsH(vector<vector<Chord>>& res, int st, int end, unordered_map<pair<int, int>, vector<vector<Chord>>, SimpleHash>& cach) {
    if (st >= end)
        return;

    rec++;

    if (cach.count( {st, end} )) {
        cached++;
        res = cach[{st, end}];
        return;
    }

    vector<vector<Chord>> res1, res2, res3, curRes;
    for (int i = st+1; i <=end; i += 2) {
        res1 = {{Chord(st, i)}};
        allChordsH(res2, st+1, i-1, cach);
        allChordsH(res3, i+1, end, cach);


        MergeResults(res1, res2, curRes);
        MergeResults(curRes, res3, res1);

        for (auto i = 0; i < res1.size(); i++) {
            res.push_back(res1[i]);
        }

        cach[{st, end}] = res1;

        res1.clear(); res2.clear(); res3.clear(); curRes.clear();
    }
}

void allChords(vector<vector<Chord>>& res, int n) {
    res.clear();

    unordered_map<pair<int, int>, vector<vector<Chord>>, SimpleHash> cach; // intrval => result

    allChordsH(res, 1, n, cach);
    return;
}
4

1 に答える 1

0

動的計画法を使用します。つまり、部分的な結果をキャッシュします。

基本的に、1 つの和音から始めて、すべての回答を計算し、それらをキャッシュに追加します。次に、2 つの和音を取り、可能な限りキャッシュを使用してすべての回答を計算します。等。

再帰的な方法は O(n!) です (少なくとも n!、私は複雑な計算が苦手です)。

この方法は、各ステップと n ステップで n/2-1 操作であるため、O(n^2) であり、はるかに優れています。ただし、このソリューションはすべての組み合わせをキャッシュに保持する必要があるため、メモリに依存します。15 chords は 1GB のメモリを簡単に使用します (Java ソリューション)。

解決例: https://ideone.com/g81zP9

~306ms で 12 和音の計算を完了します。1GB の RAM を指定すると、約 8 秒で 15 の和音を計算します。

パフォーマンスを最適化するために、キャッシュは特定の形式で保存されます。配列に保存された数値は、リンクがどれだけ離れているかを示します。たとえば、[1,0,3,1,0,0] は次のことを意味します。

1  0  3  1  0  0
|--|  |  |--|  |
      |--------|

別のステップで、必要な形式に変換できます。

于 2015-09-07T10:16:25.820 に答える