2015年03月29日

C#でしりとりを続けるプログラムを書く の続き

   このエントリーをはてなブックマークに追加 Clip to Evernote
どう書く?orgに感謝を込めて」シリーズ その81

「C#でしりとりを続けるプログラムを書く」 の続きです。

前回示したプログラムでは、問題の趣旨どおり、もっとも長くしりとりができる単語列を作り出すことができましたが、使える単語数が増えると、極端に処理速度が遅くなるという欠点がありました。
そのため、今度は最長ではなく、しりとりをそれなりに長く続けることのできるプログラムを書いてみました。
つまり、前回はすべての手を読んで一番長くしりとりを続けられるものを解として求めたのですが、今度は、数手先まで読んで、その中から、もっとも良いと思われる一手(次の単語)を選ぼうというものです。
より現実的な時間で解が求まるはずです。ただし、最も長いしりとりとは限りませんが...

ここで重要なのは、選んだ単語が良い手かどうかを判断する評価関数をどうやって作成するかです。
この評価関数の良し悪しによって、結果が大きく変わってきます。

ここでは、現在の状態から、次に続けることができる単語の候補一覧を作成し、この候補ごとに、単語を4手先まで先読みし、5つ目にくる候補の単語がいくつあるかを数えてポイント化しています。
このポイントがもっとも高い手を選ぶようにすることで、解を求めています。
なお、4手先までしりとりが続かない場合は、見込みが無い手ということで、読んだ深さをマイナスした値をポイントとしてを返します。
この評価方法が果たしてよい評価関数なのかはなんともいえませんが、結果をみる限りそれなりに有効に動いているようです。

実際の実装では、MaxDepthという定数に 4を定義し、MaxDepth先まで読んでいます。
最初は、考慮すべき手が多いけれど、だんだんと考慮すべき手が少なくなってくるという性質を考慮すれば、すこしずつMaxDepth を増やしていくという方法も採れると思います。
そうすれば、もう少し良い解が得られるかもしれません。
ただ、急激にMaxDepthを増やすと現実的な時間で終わらなくなってしまうので注意か必要です。

このプログラムでは、単語リストが 400 でも、それなりの時間で解を得ることができました。
この記事の最後に、実行結果も載せておきます。

以下、実際に書いたコードです。前回と重複するクラスもありますが、それも含めて掲載します。
全部で、4つのCSファイルから成っています。
ちなみに評価関数Evaluateは、MaxDepth手まで先読みするのに、深さ優先の探索を行っています。

■Program.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;

namespace Doukaku.Org {
    class Program {
        static void Main(string[] args) {
                DateTime dt = DateTime.Now;
                var list = WordsFile.GetWordList(400);
                Word startWord = list[0];
                WordChainThinker wc = new WordChainThinker(list);
                var ans = wc.Solve(startWord);
                ans.ToList().ForEach(w => Console.Write(w.Text + " - "));
                Console.WriteLine("\n{0}", ans.Count);
                Console.WriteLine(DateTime.Now - dt);
                Console.ReadLine();
        }
    }
}
ここでは、WordListの先頭の単語からしりとりを始めています。

■Word.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Doukaku.Org {
    // 単語を表すクラス (最初と最後の文字を取得する機能がある)
    // ちょうちょ、きしゃ などは、「や」が最後の文字とする。
    public class Word {
        public string Text { get; set; }
        private char first;
        private char last;
        public Word(string word) {
            Text = word;
            first = ToChokuon(Text[0]);
            last = ToChokuon(Text[Text.Length - 1]);
            // 長音一文字の単語はない前提
            if (last == 'ー' || last == '−')
                last = ToChokuon(Text[Text.Length - 2]);
        }
        public char First {
            get {
                return first;
            }
        }
        public char Last {
            get {
                return last;
            }
        }

        // ッは促音だが、拗音(Youon)という変数名とする
        private const String Youon = "ァィゥェォヵヶッャュョヮ";
        private const String Chokuon = "アイウエオカケツヤユヨワ";
        private char ToChokuon(char c) {
            int ix = Youon.IndexOf(c);
            if (ix > 0)
                return Chokuon[ix];
            return c;
        }

        public override string ToString() {
            return this.Text.ToString();
        }

    }
}

■ WordChainThinker.cs  
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Doukaku.Org {
    class WordChainThinker {
        private List<Word> WordList { get; set; }
        private const int MaxDepth = 4;

        public WordChainThinker(List<Word> wordList) {
            WordList = wordList.ToList();
        }

        public List<Word> Solve(Word word) {
            List<Word> ans = new List<Word>();
            Word next = word;
            while (next != null) {
                WordList.Remove(next);
                ans.Add(next);
                next = SelectNextWord(WordList,next);
            }
            return ans;
        }

        // 次に続く単語を決定する。
        private Word SelectNextWord(List<Word> wordList, Word curr) {
            //DepthX5++;

            var candidates = Candidate(curr).ToList();
            Word best = null;
            int topPoint = int.MinValue;
            foreach (var word in candidates) {
                int pt = Evaluate(wordList, word, MaxDepth);
                if (pt > topPoint) {
                    topPoint = pt;
                    best = word;
                }
            }
            return best;
        }

        // startで示した単語を評価し、ポイント化する
        private int Evaluate(List<Word> wordList, Word start, int depth) {
            var candidates = Candidate(start).ToList();
            if (depth == 0)
                return candidates.Count;
            if (candidates.Count == 0)
                return -depth;
            int maxPoint = int.MinValue;
            foreach (var word in candidates) {
                wordList.Remove(word);
                int pt = Evaluate(wordList, word, depth - 1);
                if (pt > maxPoint) {
                    maxPoint = pt;
                }
                wordList.Add(word);
            }
            return maxPoint;
        }

        // 候補の単語を列挙する
        private Word[] Candidate(Word word) {
            return WordList.Where(x => word.Last == x.First).ToArray();
        }
    }
}

■WordsFile.cs
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;

namespace Doukaku.Org {
    // 単語ファイルの読み込み
    // tab, カンマ、空白で区切る。
    static class WordsFile {
        static public List<Word> GetWordList(int count) {
            List<Word> list = new List<Word>();
            using (StreamReader sr = new StreamReader(@"WordFile.Txt")) {
                while (sr.EndOfStream == false) {
                    string s = sr.ReadLine();
                    var words = s.Split('\t', ' ', ',');
                    list.AddRange(words.Where(t => !string.IsNullOrEmpty(t)).Select(w => new Word(w)));
                }
            }
            return list.Take(count)
                       .ToList();
        }
    }
}


実行結果


アイアイ - イリフネ - ネンブツ - ツユザム - ムササビ - ビンソク - クミダシ - シ
タヅミ - ミミアテ - テイテツ - ツジツマ - マヤカシ - シャクナゲ - ゲレツサ - サ
ンバシ - ショウワル - ルイベツ - ツイタチ - チャクフク - クチブリ - リンセツ -
ツイスト - トリタテ - テキシツ - ツキビト - トリモノ - ノリニゲ - ゲジゲジ - ジ
ャアクサ - ササヤブ - ブツヨク - クシガタ - タンパツ - ツミビト - トシガス - ス
ナヤマ - マタシタ - タチノミ - ミズバナ - ナカワタ - タカダイ - イワブロ - ロコ
ツサ - サシズメ - メイフク - クロヌリ - リョウヒザ - ザイバツ - ツケヒゲ - ゲツ
ガク - クニガラ - ランギリ - リクアゲ - ゲイフウ - ウラガネ - ネリミソ - ソトブ
ロ - ロマンハ - ハラダチ - チチカタ - タマジャリ - リンカク - クセモノ - ノリコ
ミ - ミチシオ - オソジモ - モノグサ - サワガニ - ニシガワ - ワリシタ - タイギゴ
- ゴウユウ - ウスカワ - ワニガワ - ワカアユ - ユウナギ - ギンパイ - イヌジニ -
ニシカゼ - ゼンニチ - チマナコ - コシヌケ - ケツゴウ - ウシノヒ - ヒャクニチ -
チャブダイ - イシバシ - シールド - ドウナガ - ガイユウ - ウワバミ - ミチスジ -
ジカバキ - キンツバ - バシャウマ - マタガシ - シャクハチ - チョサクカ - カザアナ
- ナニゴト - トリツギ - ギタイゴ - ゴクボソ - ソデナシ - シラナミ - ミズヒキ -
キュウシキ - キャクヒキ - キジバト - トリヨセ - セイユウ - ウレユキ - キャクマチ
- チカヅキ - キュウヨウ - ウキフネ - ネガイデ - デハジメ - メンモク - クタビレ
- レイブン -
121
00:00:07.2880000



 

この記事へのトラックバックURL

http://trackback.blogsys.jp/livedoor/gushwell/52411744