2011年6月22日水曜日

スリープ探索アルゴリズム

スマートフォンアプリエンジニアを募集しています | Technology-Gym
最近、自分のTwitterのTLでこの問題ってどうやって解くんだろう?って話題になってた。いわゆる普通のパス探索アルゴリズムの話なんだけど、ゲーム業界とかなら普通にA*アルゴリズムダイクストラ法とかで解くんだろうな~と思ってたけど、普通の?プログラマはどうもA*とか知らないと総当りで(といっても、ループ排除やら計算済みコストからの分岐の刈りこみをしつつ)計算したコスト一覧をソートしてっていう力技が最初に思いつくみたいだ。

自分もA*アルゴリズムっぽい(どうやらA*とダイクストラ法がごっちゃになってたみたい 指摘されてちと直しました)ので解いてみたんだが、今日ふとあるブログのエントリーを思い出して「コレはいけるんじゃないか?」って思って実践したアルゴリズムがある。
常識を覆すソートアルゴリズム!その名も"sleep sort"! - Islands in the byte stream

思い出したブログのエントリーはこちら、そう、複数プロセスを走らせて数値の秒数だけSleepすることでソートをしてしまおうというスリープアルゴリズム!
これを応用して、スリープ探索アルゴリズムを組んでみた。

        class node
        {
            //ノードに付いてるアルファベット
            public string c;
            //パス一覧<次のノードのID, ノードへのコスト>
            public Dictionary<int, int> path = new Dictionary<int, int>();
        }
        static List<node> data = new List<node>();
まずは、この形のデータを用意する。いわゆる普通のノードデータ一覧だね

        class NemurinoKogoro
        {
            int Index;      //ノードのインデックス
            int SumCost;    //今までのトータルコスト
            int Cost;       //このノードに着くためのコスト
            string Answer;  //問題の答えとなるために経路でたされてきた文字列

            //スレッドに引数を渡すためにオブジェクトに値をコピー
            public NemurinoKogoro(int index, int sum_cost, int cost, string ans)
            {
                Index = index;
                SumCost = sum_cost;
                Cost = cost;
                Answer = ans;
            }
            //スレッドで実行
            public void Exec()
            {
                //答え文字列を追加
                Answer += data[Index].c;
                //トータルコスト計算
                SumCost += Cost;
                //コストの分お休み
                Thread.Sleep(100 * Cost);
                //ゴールのIndexなら出力して終了
                if (Index == 15)
                {
                    Console.WriteLine("ゴール!:{0}:{1}", Answer, SumCost);
                    return;
                }
                //自分のノードから伸びているパスの分だけ
                //眠りの小五郎クラスを複製してマルチスレッドで実行
                foreach (var item in data[Index].path)
                {
                    var t = new NemurinoKogoro(item.Key, SumCost, item.Value, Answer);
                    new Thread(new ThreadStart(t.Exec)).Start();
                }
            }
        }

引数付きでスレッド呼び出しをするためのクラスを作る。
そして、メインスレッドからは・・・
            //小五郎のおっちゃん頼む!
            new NemurinoKogoro(0, 0, 0, "").Exec();
            //あとは寝て待て
            Thread.Sleep(100 * 1000);

以下実行結果
ゴール!:XXXXXXXXX:XX //一応答えなので隠しておきます
ゴール!:SealthG:27
ゴール!:SheaeothG:27
ゴール!:SeaeothG:28
ゴール!:SjlthG:28
ゴール!:SheeothG:28
ゴール!:SeeothG:29
ゴール!:SjalthG:29
ゴール!:SjealthG:30
ゴール!:SjaeothG:30
ゴール!:ShealthhG:30
ゴール!:SjeaeothG:31
ゴール!:SheaeothhG:31
ゴール!:SealthhG:31
ゴール!:SjeeothG:32
ゴール!:ShunhG:32

おぉ、なんかちゃんとソレっぽい答えが出ましたw
このアルゴリズムだと、ノードが循環して無限ループするのとか気にすることも、ソートのためにデータを保持しておくことも、探索の刈りこみをすることもなーんもしないでも一応答えが出る。簡単だ
しかも、同一コストの別ルートも同時に表示できるね、面白い!

0 件のコメント: