最長しりとり問題

アルゴリズム C

ある辞書が与えられていて、その辞書の中の単語でしりとりをする時、
しりとりの単語数が一番長くなる時の長さは？？？


という、おもしろい問題あったので、解いてみた。
もちろん「ん」で終わるので、逆から考えるのもアリやとは思うけど、
何で始めようと、最初に「i→あ」の単語で始めたと考えると、1ステップで
すべて「あ」スタートの問題に還元できるので、「あ」スタートとして考える。


まず辞書のすべての単語を単語の最初と最後の文字で分類して、それぞれその分類に含まれる数を数える。
例えば「あ」で始まって「い」で終わる単語は「あ」→「い」と表し、これを「あ」から「い」への遷移と呼ぶ。
これを縦軸と横軸に「あ〜ん」をとる表（配列）として考える。


アルゴリズムの流れとしては、

  1. 「あ」から始まって、遷移先を「あ」から順に探していって、単語が存在する遷移を探す。
  2. もしその遷移先が見つかっても、さらにその先他の文字への遷移がなければそこで終わってしまうのでそれを調べる。
  3. 遷移先の遷移先が存在する遷移が見つかれば、しりとりを1つ進めて、次は、遷移先から始まる単語を同様に探す(1へ戻る)
  4. 1〜3を繰り返していき、どこにも進めなくなったら最後に「ん」で終わる単語を付け加えて終わり。


例えば、まず
「あ」→「あ」を探し、さらに「あ」からの遷移で始まる単語を探すので、
「あ」→「あ」の遷移は全部最初に使う。
次に、「あ」→「あ」はもうないので、「あ」→「い」を探す。　　見つかった。
見つかれば、すぐ遷移したいところだが、もし遷移したところで、
「い」から遷移する単語が一つもない場合困るので、それを調べる。　
ちゃんと「い」からの遷移もあるなら、しりとりを1つ進めて、次は「い」で始まるものを調べる・・・・。


という感じですね。
以下、表が与えられているとして、最長単語数を出力するプログラムをCで書いてみた。


//任意の文字から「ん」への遷移は少なくとも1以上あると仮定。
//与えられた辞書の中でiで始まりjで終わる単語の数がそれぞれdict[i][j]に格納されているものとする。
//その辞書の中の単語を用いてしりとりをする際に、しりとりの単語数が最長となる時の単語数を求める。


#include 

#define SIZE 4

int max=0;

int main(){

  int dict[SIZE][SIZE]={{10,30,20,40},
			{20,20,40,80},
			{60,10,30,120},
			{130,140,150,160}};
  
  int max_length=0;

  //  max_length = rapid_search(&dict[0][0]);
  recursive_search(0,&dict[0][0]);
  max_length += max;
  
  printf("max = %d\n",max_length);


  int i,j;
  for(i=0;i

ここでは例として、
4文字しかないしりとりを考えてます。
表が
10,30,20,40
20,20,40,80
60,10,30,120
130,140,150,160
の場合。
これを実行すると190と表示され、確かに合ってますね。



不本意ながら大域変数を使うという、ダメっぷりw
オーダーは文字の種類をSIZE,辞書の単語数をNとすると、
O(N*SIZE^2)ですかね。
SIZE=50、N=1,000,000としても、
まぁ多くとも25億ステップ（約25秒)で終わるみたいなんでOK？w


最初に「あ」以外を選んだ場合の「あ」への遷移を無視してますが、
それはループで先頭に「あ」〜「を」をとった場合の最大値でも出せばいいですが、
本質的でないくせに、オーダーがSIZE倍されてしまい、なんか腹立たしいので書いてません。


あと、高速化用の関数を使えば、実行時間約半分になると予想されます。うん。