正規表現と有限オートマトン(番外)セルラーオートマタ

　一年近く更新しなかった理由、それは例のJABEEの審査に関わっていたからです。といっても一年中審査したわけでなく、要所要所ほんの数週間だけ作業があったのですが。そうこうする内に某学術雑誌に投稿していた論文に対し「大幅に修正を要す」という査読結果が来て、メゲながら修正していました。そうかと思うと、ひょんなことからやってみたセルラーオートマタの研究がうまくまとまり、専門誌に投稿するとサクッと掲載してもらえることになりました。別に時間がなかったわけではありません。基本的に暇人です。ただ、気になることがあると、こっちのブログまで手が回らないという「シングルタスク人間」なだけです。

　セルラーオートマタの研究について、以下簡単に紹介します。まず、セルラーオートマタとは下図の通りオートマトンがあるセルが並んだものです。オートマトンは有限種類の状態の一つを持ち、入力により状態が変化するものです。セルラーオートマタ*1では隣のオートマトンの状態が入力となります。そうして状態遷移関数(局所関数とも言う)により全てのオートマタが同時に状態遷移します。

セルラーオートマタの模式図と一斉射撃問題の初期様相

　セルラーオートマタの課題の一つに一斉射撃問題があります。上の図のように端っこのセルが将軍の状態で他のセルは全て兵士の状態から始めて、全てのセルが同じ状態(射撃状態)になるよう局所関数を工夫せよ、と言う問題です。下に解の一例を載せます。

一斉射撃の一例。青が射撃状態(Mazoyerという人が作った解を利用した)

この図は横はセルの状態配置を示し、下にいくとステップが進んだときの状態変化を示します。この問題は60年近くの歴史がありますが、今も多くの研究者を惹きつけています。隣同士の相互作用だけから全体が同期する現象はなんと言っても面白いし、応用もいっぱいありそうです。基本的な解はとっくに出尽くして、最近の関心はエラーから回復するかにあります。セルが完全にぶっ壊れてしまった場合については結果が多く出ています。ノイズなどで一時的にエラーが起こったとき、どう回復するか、これを今回私がやりました。一例を示します。

一時的なノイズによる誤動作から回復して同期を達成する

11ステップでエラーが起こっていますが、それがリセットされ、一斉射撃になっています。セルラーオートマタにもこういう研究もあるというご紹介でした。Journal of Cellular Automata という専門誌のvolume 17, 5-6 号に論文が掲載されました。ご興味のある方はリンクをクリックしてください(遅いので気長に)。

*1:オートマトンは単数形、オートマタは複数形、セルラーオートマタはオートマトンがいくつもあるから複数形です。

正規表現と有限オートマトン(その1)

　大変更新に間があったお詫びは次回に述べます。実は下書きは大体できていたのでそれをまずUPします。

　ネットワークアルゴリズムはひとまず中断し、これから有限オートマトンと正規表現について見ていきます。プログラミング技術的には正規表現がとても大切ですが、アニメーションの派手さ的には有限オートマトンが一押しです。有限オートマトンの考え方はすっきりしたプログラムを作る際に欠かせないものでもあります。と言うわけでまずは有限オートマトンのアニメーションを出します。

　ところで正規表現と有限オートマトンは何か関係あるの、とのお言葉、大変的確なご質問です。実はどちらも文字列、記号列を指定する方法で等しい能力を持つことがわかっています。正規表現は記号列が持つべきパターンを記述して、そのパターンに当てはまる記号列を取り出すことができます。有限オートマトンは、一言で言っちゃえば正規表現をコンピュータで実現したものです。コンピュータで文字列、記号列を処理するとき、最初に特定のパターンを持つ列を抜き出すのが普通です。と言うことで多くのプログラミング言語に正規表現は実装されていて、正規表現を使ったスマートなプログラムが作れます。プログラミング言語の処理系はプログラマが作った正規表現を有限オートマトンに変換して機械語プログラムとしています。

　まず、正規表現について極簡単に説明します。「a で始まる5文字の名

前（ファイル名や変数名など）」を考えてみます。X をアルファベットのa からz のいずれかとすれば

aXXXX

が「a で始まる5文字の名前」の共通パターンです。次に「a で始まる5文字かc で終わる3文字の名前」を考えます。 「か」という選択を表現するために記号+を導入します。すると、

aXXXX + XXc

というパターンになります。最後に「a で始まる名前」を考えましょう。長さはどれだけでもよいとします。a の後ろにa からz のいずれかを任意の回数付けられます。0 回でも良い。0回を含む任意回の繰り返しを示す記号を*とします すると「a で始

まる名前」に対応するパターンは

aX^*

となります。この式は最初がa で, あとX の中のどれかの文字が0回以上繰り返されることを意味しています。ところで X はa からz のいずれか一つの選択ですから

X=(a+b+ ・・・ +z)

とすべきです。上に出た3つのパターンのX のところにこれを「代入」してたとえば、

a(a+b+ ・・・ +z) ^*

などが「正式」のパターンの表現法になります。次に数の表現を見てみます。0と1で済ませられる2進数にします。符号なし2進数は0と1の列とはいえ、値0以外は1で始まります。だから

1(0+1)^*+0

となります。最後の"+0"はゼロは数字1で始まらないので「1で始まるかまたは0一つだけ」を示します。

　プログラムで使う正規表現を知る人は「選択が縦棒"|"でない」とおっしゃるでしょう。プラス記号+は1回以上の繰り返しにも使います。例えば1の後に0が一回以上繰り返すのは 10⁺ となります。ところがソースプログラムでは右肩に記号を載せることができません。そこでプログラムでは 10+ とかきます。すると選択と全く区別がつかないので、選択には縦棒|が当てられました。プログラミング言語では、パターンに一致した記号列を代入できる変数や行のはじめや終わりなどを指定する記号などパターン記述を便利にする仕掛けがたくさんあります。詳しくは下にリンクを貼った書籍をどうぞ。また、正規表現とオートマトンについて理論を解説した書籍へもリンクを貼ってあります。

詳説 正規表現 第3版

形式言語とオートマトン (Information Science&Engineering F 3)

巡回セールスマン問題に関して、アルゴリズムアニメーションなど

前に書いた膜アルゴリズムのブログ

で取り上げた巡回セールスマン問題に関するアルゴリズムアニメーションを作りました。貪欲算法で解くと失敗する様子がわかります。

この動画では他にも、頂点(都市)を少し動かしただけで解(巡回路)がガラッと変わる様子も示しています。巡回セールスマン問題の複雑さを感じていただけると幸いです。

　次にしらみつぶし(全数探索)法で問題の大きさが大きくなるとどのくらい計算時間がかかるようになるか体感できる動画をあげました。

問題のサイズ(頂点の数)が一つ増えるごとに計算時間は何倍にも長くなります。それと前のブログで紹介した膜アルゴリズムによる近似計算が速いことも見て取れると思います。一つ注意したいのは、アルゴリズムの計算時間評価をする時、実際に動かして何秒かかったというナイーブな方法は論外で、きちんと理論的に定まった手法があるということです。詳しくは教科書、参考書を参照ください。この動画はあくまで参考です。

最小スパニング木と貪欲算法(グリーディアルゴリズム)

　グリーディアルゴリズム(greedy algorithm)、直訳して貪欲算法と呼ばれるアルゴリズムのグループがあります。ネットワークアルゴリズムでは最小スパニング木を求めるアルゴリズムが貪欲算法の代表として有名です*1。今回はこれをアニメーションで紹介しましょう。

　最小スパニング木問題はネットワークのすべての頂点を結ぶ重みの和最小の辺の集合を求める問題です。次のネットワークでは

このネットワークの最小スパニング木を求める

の最小スパニング木は

最小スパニング木(太線の辺からなる)

こうなります。「重みの和最小」の条件から、ループ(閉路)ができることはないので*2、必然的に「木*3」になります。ネットワークの辺が通信路とか水道管で重みが設置費用とすれば、すべてのユーザをつなぐ建設費用最小の方法を求めたことになります。実用上大切ですね。

　さて、これを解く貪欲アルゴリズムは、重みの小さい辺からスパニング木に取り入れていきます。ループができるとダメなのでその時はスパニング木に入れません。アニメーションを次に示します。

いかにも貪欲そうな実行風景でした。このやり方で正しく最小スパニング木ができることは証明されています。興味のある方は教科書などを参照して下さい。

　こういう小さい例を見ているとループができるかどうかなど人間にはひと目でわかりますが、大きな例ではそうはいきません。また、アルゴリズム(コンピュータ)的には「ひと目でわかる」という手続きはありません。ですが、ループができるかどうかの判断は効率よくできます。前にも書きましたが、最小スパニング木問題は貪欲算法がハマる代表例です。

　しかし、貪欲算法では正しい解が得られない、最小なんとか、最大なんとか問題が多数あります。貪欲算法が常に正解をもたらす問題の方が例外と言って良い。あまり欲張ると思わぬところで足をすくわれる、次回はそんな問題を取り上げます。

*1:前回のダイクストラのアルゴリズムも貪欲算法に分類されます

*2:閉路ができるとその閉路を構成する辺を一つ除いても「すべての頂点を結ぶ」条件は満たされるので、辺を一つ除いてより重みの和が小さい集合ができる

*3:閉路のない連結グラフ

ダイクストラの最短路アルゴリズム

最短路問題は出発点の頂点から他の頂点への重みの和が最小の経路を見つける問題 です。ダイクストラ(Dijkstra)という人が考え出した次のアルゴリズム

ダイクストラのアルゴリズム

があります。上のアルゴリズムでは簡単のため最短路の長さd(v)だけ求めていますが、経路(頂点の系列)を出力するように変更するのは容易です。アニメーションでは経路も求めて表示します。

このアルゴリズムの一番大切なところは10行目で、まだ最短路が求まっていない頂点xについて、それまでのd(x)と新たに最短路が求まった頂点uを経由するd(u)+w(u, x)の小さい方を新たなd(x)にしているところです。

最短距離の更新

これで全ての頂点について最短路が求まることが厳密に証明できます。また、6行目ではd(v)が最小となる頂点を探しますが、ヒープという記憶装置を使うとごく少ない手数で実行できます。どちらも詳しくは教科書などを参照して下さい。ということで、このダイクストラのアルゴリズムは今までに知られている最も効率の良い最短路アルゴリズムです。カーナビなどに使われています。実行の様子は次のリンクから。

youtu.be

ネットワークアルゴリズム: ネットワーク(グラフ)の探索

　鉄道・道路・航空などの交通、通信・電気・ガス・水道などのインフラストラクチャなどなど、我々の生活にネットワークは欠かせません。ネットワークに対して行う処理は多岐にわたり、アルゴリズムの研究と応用の代表的分野になっています。前回に打ち上げた「アルゴリズムアニメーション」実例としてネットワークアルゴリズムを取り上げます。これからの説明は前回紹介した程度の教科書・参考書を一応見た方に、理解を確実にしていただくことを想定しています。まったく初めてという方はまず教科書を一読願います。

　いろんなネットワークがありますが、その本質は(V, E, w)という3つ組みで表現できます。V は頂点の集合、EはV✖️Vの部分集合で辺の集合、wはEからR(実数の集合)かN(自然数の集合)への関数で辺の重みを示します。(V, E) だけで w は考慮しない時はグラフと言います。次にネットワークの例を示します。

ネットワークの例

ここでは

• V={a,b,c,d,e,f}
• E = {(a,b), (a,c), (b,c), (b,d), (c,a), (d,f), (d,e), (e,b), (e,c), (e,f), (f,e)}
• w(a,b) = 4 など、あとは省略

となります。このネットワークは辺に矢印があり方向がついているので、有向ネットワーク(グラフ)と言います。辺の向きを無視した無向ネットワーク(グラフ)もあります。

ネットワーク(グラフ)について多くの問題が昔から研究されており、多くのアルゴリズムがあります。次のリストはほんの一例です。

• 探索(幅優先、深さ優先)
• 最短路
• 最大フロー
• 最小スパニング木
• 2連結成分
• マッチング
• オイラー閉路
• ハミルトン閉路
• 巡回セールスマン(重みの和最小のハミルトン閉路)
• 頂点彩色/辺彩色

これらの問題(の一部)を解くアルゴリズムをアニメーションで(動作のひとこまひとこまを逐次示す)お見せします。その前に例題としてネックワークを作らなくてはけ ません。そこで

A, ネットワーク編集 ←→ B, アルゴリズム実行

という機能を持つプログラムを作りました。A は一定で、B のアルゴリズムは様々なネットワークアルゴリズムに取り替えがきくよう作ってあります。有向/無向どちらのネットワークにも対応しています。ネットワークを作るところの動画へのリンクです。

youtu.be

探索アルゴリズム(辺をたどって行ける頂点をピックアップする)は最初に取り上げるのに向くアルゴリズムです。入力はネットワーク(重みはいらないのでグラフで良い)と出発点の頂点です。幅優先探索と深さ優先探索があります。幅優先は各頂点xの幅優先探索番号 fw(x) を出力します。fw(x) は初めはすべて0になっています。アルゴリズムは次のように表現されます。

幅優先探索アルゴリズム

ここでqはキュー(待ち行列)という記憶装置、cは補助変数、! は論理否定を表します。キューについて説明する前に深さ優先探索を紹介します。深さ優先探索は各頂点xの深さ優先探索番号fd(x)を出力します。fd(x)は初めは全て0になっています。

深さ優先探索アルゴリズム(再帰版)

非再帰版で使っているsはスタックという記憶装置です。次の図に示す通り、キューは「先入先出」、スタックは「先入後出し」で内容を管理します。

キュー(queue)とスタック(stack)

q.top(), s.top() はキューやスタックの次に出力すべきデータ項目を読み出す関数です。その項目はそのまま残ります。消すときはq.delete(), s.delete()を使います。q.isempty(), s.isempty()はキューやスタックが空(データが一つもない)どうか返す関数です。もちろん、空の時、真(true)が返ります。 再帰呼び出しはコンピュータ(プログラミング言語とコンパイラ)の側でスタックを使って実現されますから、再帰呼び出し版は内部でスタックを使っているのです。探索のアルゴリズムアニメーションはこちらでみることができます。

youtu.be

アルゴリズム学習のカベを乗り越える 〜自分に合った例題を作って納得〜

お詫び: 「天変地異」のシリーズは私よりもずっと上手に説明しているネットコンテンツが多数あり、私ごときがでしゃばるところでは無いとさとりました。というわけで一回だけで中止します。申し訳ありません。やはり、本業のコンピュータ関連で頑張ります。

　情報技術が注目され、プログラミング教育が小学校から始まる世の動きは、長年計算機・情報の分野にたずさわってきた者にとっては望ましいことです。しかし、情報技術をしっかり教えられる教員が不足しているのは心配です。私が最も懸念するのは、我流でプログラミングをやって(1日16時間✖️365日)それなりに動くソフトウェアを作るような方が増えていく。そのような方が我流で教えて同じ様なスキルの人を育てるわけですね。それでは、高度情報化、ソフトウェア化の世界に日本が食い込んで行けたとしても、中身は真っ黒け、超ブラック。その上、GAFA(Google、アップル、フェイスブック(現在メタ)、アマゾン)などが押さえる基本技術によって一番オイシイところは持っていかれる、というあまり嬉しくない未来が見えてきます。
 ある決まった問題を解くプログラムは、その問題を解くアルゴリズム、つまり解決の手順が厳密に示された手順書を、プログラミング言語の命令によって表現します。厳密なアルゴリズムは計算の理論により正しさ(常に与えられた問題の正しい解を出力する)の証明、停止すること(無限ループになったりしない)ことの保証、計算にかかる手順の総計が与えられるものです。もっとも、多くのプログラムには厳密なアルゴリズムは要りません。「ユーザがaを選んだら動作A、bを選んだらBを行う」「センサxの値が設定値yより大きければzに信号uを送る」といった手順を行うことが大半です。厳密なアルゴリズムを実行する場面、例えば、データを値が小さい順に並べ替えるとか、文字列が与えられたパターンを満足するかどうか判定する時も、それを行う出来合いのプログラムがライブラリにあることが多い。というわけで、アルゴリズムやその基礎である計算の理論をきちんと学ばなくても、我流である程度のプログラミングはできます。
　このように何んとなくわかってやっている状態では、新しいアルゴリズムを必要とする課題、性能をとことん追求する際には対応が難しくなるのはご理解いただけるでしょう。その前に、プログラミングでは同じことをやるにも方法が多数あるのが普通です。どのやり方を選ぶべきか、アルゴリズムの理論は一番良いやり方を教えてくれます。それにより「なんとなく」や「他の真似」するよりより、効率的で間違いも少ない、信頼できるプログラムが作成できます。きちんとアルゴリズム、計算の理論を学んだ技術者たちとそうでない人たちでは、一見同じ仕事をしている様で、実は差がついているのです。
　アルゴリズムを学習しようと思い立ったら、教科書はたくさんあります。例によって玉石混交ですが、下にリンクを貼った本はお勧めできます。アルゴリズムは解法を示した手順の集まりですから、理解するにはその手順を一つ一つ実行して例題を解いてみるのが一番です。教科書には例題は載っています。でもひとつか二つです。手順を実行する途中経過も飛び飛びにしか書いてありません。だから教師が役に立つわけで、途中経過を丁寧に説明したり、別の例ではどうなるか解説します。それで私もメシを食っていたわけです。これから何回かに分けて紹介するのは、アルゴリズムで解く問題例を自分で作成し、アルゴリズムの実行経過を1ステップずつ見ることができるプログラムです。アルゴリズムの動きをアニメーションのように見せるので「アルゴリズムアニメーション」*1と呼びます。解説入りのアルゴリズムアニメーションはYouTubeに投稿していく予定です*2。

アルゴリズムとデータ構造(第3版)

アルゴリズムデータ構造計算論 (Information & Computing)

*1:これは私の造語ではなく、文献にあった言葉ですがその文献を今持っていないので引用できません。アニメーションを作るアルゴリズムではありません。

*2:動画としてはショボイものですが