ブログ「サイバー少年」

ブログ「サイバー少年」へようこそ!
小学六年生ごろからプログラミングを趣味にしている高校生のブログです。
勉強したことについての記事などを書いています。フリーソフトも制作、公開しています。
(当ブログについて詳しくは「ブログ概要紹介」を参照)

サイバー少年が作ったフリーソフトは「サイバー少年の作品展示場」へ

順序集合を並べるアルゴリズム

たいした内容ではないのですが、また数学のネタです。

今日は脳みそのコンディションが悪いので、読むに耐えないクソ記事になっているかもしれないですが…。

半順序関係が与えられた集合に対して、その半順序関係の情報に基づいて一列に並べるアルゴリズムについて考えていました。

その集合は“有限”の集合であると但し書きしないといけませんね。
なんか全部、有限であることが前提みたいに考えてしまうのは、情報系の人間の悪い癖だと思います。


さてしかし、普通、全順序関係じゃないと一列に並べられないんじゃないかということなのですが、

ここでは任意の元x,yについて、x <= yという順序関係があるとき、yは必ずxの右(上でもいいからとにかく大きい側の方向を定める)に来るという条件を充足するように、半順序集合の全ての元を一列に並べることを、一列に並べることとします。


つまり、大小比較できない二つの元については、どんな順番でもいいから無理やり一列に並べて、
大小比較できる二つの元については確実に、大きい元が大きい側になるように並べるということです。


このような一列を生成するアルゴリズムを、考えたわけなのですが、アルゴリズム自体はクソ簡単なものです。

そもそも私は難しいアルゴリズムを考案できるほどの脳みそがないので…。



それはどういうアルゴリズムかというと、まず処理対象の順序集合が与えられていて、その中の任意の二つの元x,yを取り出したとき、
x >=yなのか、x <=yなのか、もしくはどちらの関係でもないのかが分かるものとします。

そして、まず処理結果の入れ物として連結リスト的なものを用意します。(“リスト”という名前にします)
リストの後ろのほうにある要素が、より大きい元であるとします。


順序集合の特定の元をaとする。
n個の要素があるリストの1個目からn個目まで走査して、下記の処理を繰り返す。
(現在見ている、リストの要素をxとする。)

a >= xの場合: 何もせず次のループ処理へ行く。
aとxに関係がない場合: 何もせず次のループ処理へ行く。
a <= xの場合: xの直前にaを挿入してループを終わる。

これをaにすべての元を代入して繰り返す。



というアルゴリズムになります。

これ自体は、めちゃくちゃ単純なアルゴリズムですが、果たしてこのアルゴリズムで、本当に正しく動くのかどうか。


そして、もしかしたら数学的帰納法でこのアルゴリズムが正しく動くことを証明できるんじゃないかと思いました。

それが本記事の本題です。


リストの要素数がn個ならリストにある全ての元が順序関係を充足しているとき、
上のアルゴリズムによってリストにn+1個目の元aを追加しても、順序関係を充足することを示します。


リストの先頭からn+1個目の元aの直前までの部分は、aを挿入する前、つまりリストの要素数がnだったときと変わらないので、仮定よりこの部分は順序関係を充足する。

ここでaは初めてa <= xとなった要素xの直前に挿入されたのだから、
aより前のほうにある要素yはすべて、a >= yまたはa,yは無関係であったはず。

a >= yのとき、aはyの後ろにあるので順序関係を充足しなくなることはない。
a,yが無関係のとき、aはyの後ろにあるが、どの順番でも順序関係を充足しなくなることはない。

よってaを挿入したことで(もともと充足していた)順序関係を充足しなくなるということはないので、リストの先頭からxまでの要素が順序関係を充足していることは証明された。

ここでaの直後の要素xからリストの末尾までの部分は、aを挿入する前、つまりリストの要素数がn個だったときと変わらないので、仮定よりこの部分は順序関係を充足している。

よってn+1個目の元を追加したリストが全体として順序関係を充足していることが証明された。



ここで、n = 1のときリストが順序関係を充足することは自明なので、このアルゴリズムが正しいことの証明になる、

…というふうに思ったんですが、どうなのでしょうか。

リストの一部分について充足しているという言い方は、詭弁を招くかもしれないとは思いますが、判断ができない…。


さて、なんでこんなアルゴリズムを考えるに至ったのかというと、地図を作るアルゴリズムを考えていたわけです。


もし未開の地を発見して開拓しようとなったときに(そんなときないだろとか言わない)

「ある目印xは目印yの北にある」だとか、「目印yは目印zの西にある」だとかいう情報を元に、それらを充足するような格子状の地図を出力するアルゴリズムを考えていたのです。

これは、東西だけとか南北だけとか一次元でまず考えれば、上の問題なので、まず一次元の基準で並べられます。

そして、ある目印が横の並びではm番目、縦の並びではn番目になるなら、格子の(m,n)のマスにその目印を配置すれば、なんとなくの地図が完成するのではないかと思いました。

これは、正しいんでしょうか…。


というわけで、正確性皆無のクソ記事をまた作りだしてしまったのですが、誰かご意見お待ちしております…。

tag: 数学 集合 順序 関係 アルゴリズム 計算 帰納法 証明 地図

コメント

コメントの投稿

トラックバック

トラックバック URL
http://cyberboy6.blog.fc2.com/tb.php/459-a280f5cd
この記事にトラックバックする(FC2ブログユーザー)

当ブログをご利用(閲覧等)になる場合は必ず「当ブログの利用規定」をお守りください。