DouKaku?beta

Comment detail

必ず解ける迷路 (Nested Flatten)

This comment is reply for 5299 horiuchi: 1024x1024を出力したら、Pen4...(必ず解ける迷路). Go to thread root. 

棒倒し法も空間計算量がO(n)ですね。
すみません勘違いしてました。

私の考えたアルゴリズムと同じです。
棒倒し法の1行バッファ版と言えるようです。

以下、n=5, m=5の迷路の例でアルゴリズムを解説します。

・最初の行
Ｓ■■■■■■■■■■■←
まずバッファを用意して、全て壁にします。

・1行目(奇数行)
Ｓ■■■■■■■■■■■
１■★■★■★■★■★■←
★の箇所に穴を開けます。

Ｓ■■■■■■■■■■■
１■Ａ■Ｂ■Ｃ■Ｄ■Ｅ■←
穴を開けた場所をＡ～Ｅとします。

Ｓ■■■■■■■■■■■
１■Ａ★Ｂ★Ｃ★Ｄ★Ｅ■←
★の箇所に穴を開けるかどうかを乱数で決定します。

Ｓ■■■■■■■■■■■
１■Ａ▲Ｂ★Ｃ★Ｄ★Ｅ■←
たとえば▲に穴を開ける場合。

Ｓ■■■■■■■■■■■
１■ＡＡＡ★Ｃ★Ｄ★Ｅ■←
ＡとＢの領域が結合されるため、Ｂ領域をＡ領域に統合します。
仮にＢ領域に飛び地があっても、それもＡ領域に統合します。
また、★の左右が同じ領域だった場合は、穴を開けてはいけません。
ループ経路が出来てしまうからです。

Ｓ■■■■■■■■■■■
１■ＡＡＡＡＡＡＡ■Ｅ■←
この調子で穴を開けていきます。
全ての★を乱数で決定したら1行確定です。

・2行目(偶数行)
Ｓ■■■■■■■■■■■
１■ＡＡＡＡＡＡＡ■Ｅ■
２■Ａ☆Ａ☆Ａ☆Ａ★Ｅ■←
☆の箇所を壁にします。

Ｓ■■■■■■■■■■■
１■ＡＡＡＡＡＡＡ■Ｅ■
２■Ａ■Ａ■Ａ■Ａ■Ｅ■←
★の箇所はすでに壁なので特に何もしません。

Ｓ■■■■■■■■■■■
１■ＡＡＡＡＡＡＡ■Ｅ■
２■☆■☆■☆■☆■Ｅ■←
☆の箇所を壁にするかどうかを乱数で決定します。

ただし、残り１つになっているＥの列は壁になってはいけません。
また、４つの☆は３つまでは壁にしてもよいですが、
最後のひとつは壁にしてしてはいけません。
４つとも壁にしてしまうと
　Ｓ■■■■■■■■■■■
　１■ＡＡＡＡＡＡＡ■Ｅ■
　２■■■■■■■■■Ｅ■←
こうなって、Ａの領域に侵入できなくなってしまうからです。

Ｓ■■■■■■■■■■■
１■ＡＡＡＡＡＡＡ■Ｅ■
２■Ａ■■■Ａ■■■Ｅ■←
乱数を使って結局２箇所を壁にすることになりました。
全ての☆を乱数で決定したら1行確定です。

・3行目(奇数行)
Ｓ■■■■■■■■■■■
１■ＡＡＡＡＡＡＡ■Ｅ■
２■Ａ■■■Ａ■■■Ｅ■
３■Ａ■★■Ａ■★■Ｅ■←
1行目と同じく、★の箇所に穴を開けてＢ,Ｃ領域と
します。

Ｓ■■■■■■■■■■■
１■ＡＡＡＡＡＡＡ■Ｅ■
２■Ａ■■■Ａ■■■Ｅ■
３■Ａ★Ｂ★Ａ★Ｃ★Ｅ■←
★の箇所に穴を開けるかどうかを乱数で決定します。


あとは同じように、
偶数行→奇数行→偶数行→・・・
と繰り返します。


・9行目(最後の一つ前の行&奇数行)
Ｓ■■■■■■■■■■■
１■ＡＡＡＡＡＡＡ■Ｅ■
２■Ａ■■■Ａ■■■Ｅ■
３■ＡＡＡ■Ａ■ＣＣＣ■
４■■■Ａ■■■■■Ｃ■
５■Ｂ■Ａ■ＤＤＤ■Ｃ■
６■Ｂ■Ａ■Ｄ■Ｄ■Ｃ■
７■ＡＡＡ■Ｃ■ＣＣＣ■
８■Ａ■Ａ■Ｃ■Ｃ■Ｃ■
９■Ａ■Ａ■Ｃ■Ｃ■Ｃ■←
最後の一つ前の行は辻褄あわせが必要です。
具体的には、すべての領域を統合しなければなりません。

Ｓ■■■■■■■■■■■
１■ＡＡＡＡＡＡＡ■Ｅ■
２■Ａ■■■Ａ■■■Ｅ■
３■ＡＡＡ■Ａ■ＣＣＣ■
４■■■Ａ■■■■■Ｃ■
５■Ｂ■Ａ■ＤＤＤ■Ｃ■
６■Ｂ■Ａ■Ｄ■Ｄ■Ｃ■
７■ＡＡＡ■Ｃ■ＣＣＣ■
８■Ａ■Ａ■Ｃ■Ｃ■Ｃ■
９■Ａ■Ａ★Ｃ■Ｃ■Ｃ■←
今回は、たまたまＡ領域とＣ領域しかないため、
★の箇所の壁を取り除けばＯＫです。

Ｓ■■■■■■■■■■■
１■ＡＡＡＡＡＡＡ■Ｅ■
２■Ａ■■■Ａ■■■Ｅ■
３■ＡＡＡ■Ａ■ＣＣＣ■
４■■■Ａ■■■■■Ｃ■
５■Ｂ■Ａ■ＤＤＤ■Ｃ■
６■Ｂ■Ａ■Ｄ■Ｄ■Ｃ■
７■ＡＡＡ■Ｃ■ＣＣＣ■
８■Ａ■Ａ■Ｃ■Ｃ■Ｃ■
９■Ａ★Ａ☆Ｃ★Ｃ★Ｃ■
★☆の箇所に穴を開けるか乱数で決定します。

Ｓ■■■■■■■■■■■
１■ＡＡＡＡＡＡＡ■Ｅ■
２■Ａ■■■Ａ■■■Ｅ■
３■ＡＡＡ■Ａ■ＣＣＣ■
４■■■Ａ■■■■■Ｃ■
５■Ｂ■Ａ■ＤＤＤ■Ｃ■
６■Ｂ■Ａ■Ｄ■Ｄ■Ｃ■
７■ＡＡＡ■Ｃ■ＣＣＣ■
８■Ａ■Ａ■Ｃ■Ｃ■Ｃ■
９■Ａ■ＡＡＡ★Ａ★Ａ■
☆確定まで。
この例では、☆以外はたまたま左右が同じ領域なので、
選択肢がありません。

Ｓ■■■■■■■■■■■
１■ＡＡＡＡＡＡＡ■Ｅ■
２■Ａ■■■Ａ■■■Ｅ■
３■ＡＡＡ■Ａ■ＣＣＣ■
４■■■Ａ■■■■■Ｃ■
５■Ｂ■Ａ■ＤＤＤ■Ｃ■
６■Ｂ■Ａ■Ｄ■Ｄ■Ｃ■
７■ＡＡＡ■Ｃ■ＣＣＣ■
８■Ａ■Ａ■Ｃ■Ｃ■Ｃ■
９■Ａ■ＡＡＡ■Ａ■Ａ■
Ａ領域とＣ領域が統合されたため、
残りの★も穴をあけられなくなりました。

・最後の行
Ｓ■■■■■■■■■■■
１■ＡＡＡＡＡＡＡ■Ｅ■
２■Ａ■■■Ａ■■■Ｅ■
３■ＡＡＡ■Ａ■ＣＣＣ■
４■■■Ａ■■■■■Ｃ■
５■Ｂ■Ａ■ＤＤＤ■Ｃ■
６■Ｂ■Ａ■Ｄ■Ｄ■Ｃ■
７■ＡＡＡ■Ｃ■ＣＣＣ■
８■Ａ■Ａ■Ｃ■Ｃ■Ｃ■
９■Ａ■ＡＡＡ■Ａ■Ａ■
Ｅ■■■■■■■■■■■
全て壁で埋めます。

これでおしまいです。


私の書いたJavaコードだと出力無しで1372ミリ秒でした。
　　PentiumM 2.1GHz
　　java version "1.6.0_02"
　　Java(TM) SE Runtime Environment (build 1.6.0_02-b05)
　　Java HotSpot(TM) Server VM (build 1.6.0_02-b05, mixed mode)

このアルゴリズムで組んでみました。Pentium2 266MHzで30秒です。きっともっと最適化の余地があることでしょう。。。。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
#include <vector>
#include <fstream>
#include <algorithm>
#include <cstdlib> // random, srand
#include <cassert> // assert
#include <ctime> // time

#define REP(i, b, e) for (size_t i = b; i < e; ++i)
#define STEP(i, b, e, step) for (size_t i = b; i < e; i += step)

const size_t wall = static_cast<size_t>(-1);

bool random()
{
    return std::rand() < RAND_MAX / 2;
}

void print(std::ostream& out, const std::vector<size_t>& map)
{
    REP(i, 0, map.size())
    {
        out << (map[i] == wall ? "¡" : "@");
    }

    out << std::endl;
}

void create_maze(const char* path, size_t n, size_t m)
{
    assert(n >= 1); assert(m >= 1);

    std::ofstream out(path);

    std::vector<size_t> areas(n); // identifers of areas

    REP(i, 0, n) areas[i] = i;

    std::vector<size_t> map(2 * n + 1, wall);

    print(out, map);

    for (--m; ; --m)
    {
        STEP(i, 1, 2 * n, 2) if (map[i] == wall)
        {
            assert(! areas.empty());

            map[i] = areas.back();

            areas.pop_back();
        }

        STEP(i, 2, 2 * n, 2) if (map[i - 1] != map[i + 1] && (m == 0 || random()))
        {
            const size_t old_area = map[i - 1];

            const size_t new_area = map[i + 1];

            areas.push_back(old_area);

            std::replace(map.begin(), map.end(), old_area, new_area); // caution! passed by reference

            map[i] = new_area;
        }

        print(out, map);

        if (m == 0)
        {
            break;
        }

        STEP(i, 2, 2 * n, 2)
        {
            map[i] = wall;
        }

        std::vector<size_t> count(n, 0);

        STEP(i, 1, 2 * n, 2)
        {
            ++count[map[i]];
        }

        STEP(i, 1, 2 * n, 2) if (count[map[i]] >= 2 && random())
        {
            --count[map[i]]; map[i] = wall;
        }

        print(out, map);
    }

    print(out, std::vector<size_t>(2 * n + 1, wall));
}

int main()
{
    std::srand(std::time(NULL));

    create_maze("result.txt", 1024, 1024);
}

最適化の余地があるというのは、アルゴリズムにではなく、私のコードに、です。念のため(^^;

C++, Pentium2 266MHzで30秒ですか。

私の使ったPentiumM 2100MHzとの性能差を約10倍とすると。
(クロック差8倍とメモリとかキャッシュとかで+2倍)
13秒ぐらいで生成できそうなんですが・・・。

あ、そういえば速度を計ったときには出力コードをコメント
にしてました。

純粋にバッファ操作の時間だけ計測すると何秒ぐらいになり
ますか？
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
// こんな感じで。
void print(std::ostream& out, const std::vector<size_t>& map)
{
    REP(i, 0, map.size())
    {
//      out << (map[i] == wall ? "■" : "　");
    }

//  out << std::endl;
}

23秒でした。ていうか、私のコード、日本語部分が化けてますね。すみません（汗）

#日ごろ秀丸＋欧文フォントで組んでるので、そのままコピーペーストするとこうなる

> 23秒でした。

（・３・）アルェー？
速くなったけど13秒には及ばないですね。
いくつもあるループを統合したら改善するのかも。

-------------
　STEP(x) {
　	A
　}

　STEP(x) {
　	B
　}
-------------

　　↓

-------------
　STEP(x) {
　	A
　	B
　}
-------------

> #日ごろ秀丸＋欧文フォントで組んでるので、
> そのままコピーペーストするとこうなる

シブイ！
Courierでしょうか？

私はプロポーショナルフォント(英字Tahoma + 日本語MSUIGothic)で
プログラムしてます。
周りからは変態呼ばわりされてます(笑)
>速くなったけど13秒には及ばないですね。

うーん、コンパイラが違うとか。g++ -O2 でコンパイルしました。まあ、色々古いパソコンなので他にも原因があるかも。

>シブイ！
>Courierでしょうか？

Courier Newです（笑）

>私はプロポーショナルフォント(英字Tahoma + 日本語MSUIGothic)で
>プログラムしてます。
>周りからは変態呼ばわりされてます(笑)

・・・変態（ぼそ）(^^;

Index

Feed

Other

Link

Pathtraq

loading...
Creative Commons License このサイトの内容は、 クリエイティブ・コモンズ・ライセンスの下でライセンスされています。 [詳細]