2013年09月01日

遺伝的アルゴリズムで巡回セールスマン問題を解く

   このエントリーをはてなブックマークに追加 Clip to Evernote
僕のもう一つのサイト「Gushwell's C# Programming Page」に、

遺伝的アルゴリズムで巡回セールスマン問題を解く

を掲載しました。
この手のアルゴリズムの専門家ではないので、間違っている所があるかもしれません。
気がついた点があれば、指摘していただけると嬉しいです。

  

Posted by gushwell at 17:28Comments(0)TrackBack(0)

2011年07月18日

部分和問題を動的計画法で解く

   このエントリーをはてなブックマークに追加 Clip to Evernote
部分和問題とは、
「与えられた n 個の整数(集合A)と 整数 X があった時に、集合Aから任意の数の整数を選び、
その数の和(部分和)が、X に等しくなるような、部分集合を求める」 というものです。

たとえば、 [3,7,8,12,13,18] の部分和が 27 になる部分集合は、[7,8,12] となります。

このような問題を解くには、バックトラックでも解くことは可能ですが、要素の数が多くなると
組合せの数が増えすぎて、対応できなくなることもあり得ます。
このような時に利用するのが、動的計画法です。

僕のWebサイト「Gushwell's C# Programming Page」に、この部分和問題を解くプログラムコードを掲載しました。

興味のある方はどうぞ。

  
Posted by gushwell at 20:30Comments(0)TrackBack(0)

2011年07月03日

C#プログラマーのための再帰処理・超入門

   このエントリーをはてなブックマークに追加 Clip to Evernote
いげ太さんの記事に触発されて僕も書いてみた。

岩波国語辞典には、再帰→回帰 とあり、回帰の意味を見てみると、

(2) 〔名〕処理手続きや規則の定義に、それ自身を繰り返し使うような仕方。

とあります。
つまり、C#での再帰処理とは、ある処理をするのに、自分自身のメソッドを繰り返し呼び出す処理のことです。

なお、再帰は、処理だけではなく、構造においても使われます。コンピュータのフォルダ構造が
その身近な例ですね。

さて、それでは、1 から n までの整数の合計(これを sum(n)と表す)を求める処理
について考えてみます。

sum(n) = 1 + 2 + 3 + 4 + ... + (n-2) + (n-1) + n

と表せます。

1 から (n-1) までの合計は、というと、sum(n-1) であらわすことができます。

つまり、

sum(n) = sum(n-1) + n

と定義できるわけです。
これが、分かれば、再帰コードを書くことが出来ます。

次のようなコードを書いてみました。

int Sum(int n) {
    int result = Sum(n-1) + n;
    return result;
}

何をやっているかと言えば、
Sum(n) を求めるには、Sum(n-1) で自分自身のメソッドを呼び出し、1から n-1 の
合計を求め、その結果に n を加えた値を結果として、返しています。

しかし、これには、大きな欠陥があります。
実際に、動かしてもらえば、分かると思いますが、スタックオーバーフローの例外が発生してしまいます。

なぜならば、Sumメソッドが呼ばれたら、その中で、Sumメソッドを呼び出し、さらに、
その中で、Sumメソッドを呼び出し.... を繰り返すわけですから、無限に、Sum を呼び
続けてしまうわけです。

さて、ここで、While 文を使った、同様のコードを見てみましょう。

        static int WhileSum(int n) {
            int result = 0;
            int i = 0;
            while (i < n) {
                result = result + i;
                i++;
            }
            return result;
        }

このコードでは、無限ループにならないように、i < n でループの終了判定を行っていますね。

再帰のコードも同様に、再帰の終了判定を行わないと、無限にメソッドを呼び続ける
ことになるのです。

ためしに、

    class Program {
        static void Main(string[] args) {
            Console.WriteLine(Sum(5));
        }

        static int Sum(int n) {
            Console.Write("{0} ", n);
            System.Threading.Thread.Sleep(100);
            int result = Sum(n - 1) + n;
            return result;
        }
    }

とし、実行してみましょう。Sum メソッドに渡ってきた 引数 n をConsole.WriteLineで
表示するコードと、Sleepメソッドを追加しています。

※ 途中で、Ctrl+Cを押して、プログラムを終了させてください。

5 4 3 2 1 0 - 1 - 2 -3 ...

と表示され、Sumの引数に 0 以下の値が渡ってきていることが確認できます。
これを見れば、1 がきたところで、再帰呼び出しをストップすれば良いことがわかります。

それでは、再帰版のSumメソッドに終了判定を入れたいと思います。

        static int Sum(int n) {
            if (n == 1)
                ;  // ここに何を書く?
            else 
                return Sum(n - 1) + n;
        }

※ 一時変数の resultは取り除いています。

問題は、コメントにも書いたように、n が 1の時に何を書くかです。

具体的に、Sum(1) の結果が何かを考えてみると、1 が返ればよいわけですから、
最終的なコードは、次のようになります。

        static int Sum(int n) {
            if (n == 1)
                return 1;
            else 
                return Sum(n - 1) + n;
        }
なお、最初に、Sum(n)は、

sum(n) = sum(n-1) + n

と定義できると書きましたが、これはより正確には、

 n == 1 の時
   Sum(n) = 1
 n > 1 の時
   Sum(n) = Sum(n-1) + n


となります。
この定義をそのまま、C#のコードに書き下したものが、上記Sumメソッドとなります。
これは、メソッドの定義が、手続き的な「処理の記述」から、問題の構造そのものを表す
「問題の定義」に近くなっていることを示しています。(言い換えると、HowからWhatですね)
コード自体も、とてもすっきりしていますね。whileをつかったコードのごちゃごちゃ感が
こちらにはありません。

ただ、手続きを書くことに慣れているプログラマーには、これでは、どう動くのかが
良くわからないという方も多いと思います。実際に、僕が若いころに再帰を学んだ時はそうでした。

ということで、どう動いているのかを確認してみましょう。
以下のようにデバッグ行を追加してみます。

        static void Main(string[] args) {
            Console.WriteLine(Sum(5));
            Console.ReadLine();
        }

        static int Sum(int n) {
            Console.WriteLine("Sum({0}) called", n);
            if (n == 1) {
                return 1;
            } else {
                int a = Sum(n - 1);
                Console.WriteLine("Sum({0}) -> {1}", n - 1, a);
                return a + n;
            }
        }

この結果は、
Sum(5) called
Sum(4) called
Sum(3) called
Sum(2) called
Sum(1) called
Sum(1) return 1
Sum(2) return 3
Sum(3) return 6
Sum(4) return 10
Sum(5) return 15
15
となります。
これを言葉で言い換えると、次のようになるかと思います。


1. Sum(5)を求めるには、そのひとつ前のSum(4)を知らなければならない、だからSum(4)を呼ぶ。
2. Sum(4)を求めるには、そのひとつ前のSum(3)を知らなければならない、だからSum(3)を呼ぶ。
3. Sum(3)を求めるには、そのひとつ前のSum(2)を知らなければならない、だからSum(2)を呼ぶ。
4. Sum(2)を求めるには、そのひとつ前のSum(1)を知らなければならない、だからSum(1)を呼ぶ。
5. Sum(1) は、1だから、1 を返す。
6. Sum(1)が求まったから、Sum(2) は、Sum(1) + 2 で 1 + 2 になるので、3を返す。
7. Sum(2)が求まったから、Sum(3) は、Sum(2) + 3 で 3 + 3 になるので、6を返す。
8. Sum(3)が求まったから、Sum(4) は、Sum(3) + 4 で 6 + 4 になるので、10を返す。
9. Sum(4)が求まったから、Sum(5) は、Sum(4) + 5 で 10 + 5 になるので、15を返す。


これからわかるように、C#における再帰呼び出しは、メソッドをどんどん深く呼び出し続けるため、
スタックを消費することになります。
大抵の場合は、これでも問題はありませんが、解くべき問題によっては、スタックオーバーが 起こりえます。この点は注意が必要です。

しかし、その欠点を補ってあまりあるパワーが再帰にはあります。
それは、再帰的な構造のデータを処理する際に、発揮されます。
先ほどあげた、フォルダ構造を扱ったり、家系図のような階層構造(Tree構造)のデータを扱う際には、 再帰はとても有効な手段となります。

ボードゲームのような先読みを処理を行うにも、再帰は有効(というか必須)です。
また、リンクリストを扱ったり、今回のような通常の繰り返し処理や、リトライ処理などでも 再帰が使えますね。

なお、いげ太さんの記事では、末尾再帰によるコードが示されていますが、
C#のコンパイラには、末尾再帰の最適化が組み込まれていません。 そのために、ここでは、末尾再帰のコードは示していません。
末尾再帰について知りたければ、こことかここを見てください。



ちなみに、僕のWebサイト「Gushwell"s C# Programming Page」の「C# プログラム小品集」
に掲載したプログラムでも、再帰を使っているプログラムがたくさんあります。
例えば、

階乗の計算
http://gushwell.ifdef.jp/etude/Factorial.html

すべての順列を求める
http://gushwell.ifdef.jp/etude/Permutation.html

ヒルベルト曲線
http://gushwell.ifdef.jp/etude/HirbertCurve.html

8-Queenパズル
http://gushwell.ifdef.jp/etude/nQueen.html

最大面積の領域を求める
http://gushwell.ifdef.jp/etude/MaxArea.html

などです。興味がありましたら、読んでみてください。

  
Posted by gushwell at 23:00Comments(2)

2011年06月14日

stringの配列からDictionary<string, string>への変換をやってみた

   このエントリーをはてなブックマークに追加 Clip to Evernote
元ネタ:stringの配列からDictionaryへの変換
http://d.hatena.ne.jp/okazuki/20110609/1307577527
http://d.hatena.ne.jp/okazuki/20110609/1307580225
http://d.hatena.ne.jp/okazuki/20110609/1307590523
http://d.hatena.ne.jp/okazuki/20110609/1307590592

僕もやってみました。
奇数番目の要素のシーケンスと偶数番目の要素のシーケンスを作成し、
Zipメソッドで、Tupleに変換したものを ToDictionaryメソッドで、Dictionaryに変換しています。
この例では、Zipメソッドは、拡張メソッドとして使うよりも、静的メソッドとして使った方が、
可読性が高くなると思います。

ジェネリックにしているので、文字列以外のシーケンスに対しても、利用できます。

もっと簡単に書けないかなー。
配列限定ならば、やはりfor文かな。

  
Posted by gushwell at 22:36Comments(0)TrackBack(0)

2011年06月11日

「エマープでかつ上昇数である自然数を求める」を掲載しました

   このエントリーをはてなブックマークに追加 Clip to Evernote
Web Site 「Gushwell's C# Programming Page」に 「エマープでかつ上昇数である自然数を求める」を掲載しました。
Silverlightで書いているので、実際にブラウザで動くプログラムを掲載しています。

エマープ(Emirp)とは、素数を逆転させた数もまた素数である自然数のことです。
例えば、167 は、素数ですが、これを反転した 761 も素数であり、この2つはエマープです。
Prime(素数)という単語を 反転させると Emirp になるので、そう呼ばれているそうです。

また、1479のように、左から右へどんどん大きな数字になってゆく数を、ここでは「上昇数」と呼んでいます。
正式には、上昇数というのかどうか分かりません。もしご存知の方がいれば教えてください。

興味のある方は、ご自身でプログラムを書いてみてください。
  
Posted by gushwell at 11:26Comments(0)TrackBack(0)

2011年03月31日

N寄生数

   このエントリーをはてなブックマークに追加 Clip to Evernote
Webサイト Gushwell's C# Programming Pageに『N寄生数』の記事を掲載しました。
C#のソースコードも載せています。

N寄生数とは、

ある整数をA 、Aの一桁目の数値を N としたときに、 A を N 倍すると、右へ一桁分ローテートシフトし、
Nが最上位桁に移る数 のなかで最小の数を言います。 ただし、2<=N<=9 とします。

例えば、N=4 の時は、102564 となります。
102564 * 4 = 410256
となり、右にローテートシフトします

興味のある方は、N=6の時の値を求めてみてください。


  
Posted by gushwell at 21:26Comments(0)TrackBack(0)

2011年02月27日

カプレカ数

   このエントリーをはてなブックマークに追加 Clip to Evernote
Gushwell's C# Programming Pageの「C#プログラム小品集」に、「カプレカ数」を求めるプログラムを掲載しました。

カプレカ数とは、

2乗した値を前の部分と後ろの部分に分けて、その和を取ったとき、元の値に等しくなる数

のことです。

  
Posted by gushwell at 21:25Comments(6)TrackBack(1)

2011年02月16日

Silverlightでドラゴン曲線

   このエントリーをはてなブックマークに追加 Clip to Evernote
Webサイト - Gushwell's C# Programming Pageの「C#プログラム小品集」にドラゴン曲線の記事をアップしました。
DragonCurve
実際にブラウザで動くSilverlightプログラムは、こちらをどうぞ。C#のコードも公開しています。   
Posted by gushwell at 22:41Comments(0)TrackBack(0)