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

スマートフォンアプリエンジニアを募集しています | 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

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