ソフトウェアの品質を学びまくるソフトウェアの品質を学びまくる読者になるソフトウェアの品質を学びまくるソフトウェアの品質、ソフトウェアテストなどについて学んだことを記録するブログです。書評この記事では、「プログラミングじゃないんだけど、すごくアルゴリズムっぽいな!」と思った話を2つ紹介します。タイトルそのままですね。一つ目は、『ホルムヘッドの謎』という本からの紹介です。英国を舞台の中心とした一つ一つのエッセイが含蓄と味わい、知識と考察に満ちていて、あっ「エッセイ」って本来こういうものなんだよな、単にその日あったことを書くのは「日記」なんだよ・・・と思い知らせてくれます。文藝春秋Amazonエッセイの一つに、著者が絶賛してはばからない交通システム・「ラウンドアバウト」があります。こんな構造の道路構造です。2.0この写真だと四叉路くらいに見えますが信号はなく、入ってきた車が島の周りを回って、望む方向に出ていく、という形になっています。本書によると、交通ルールは以下の通りです。なにはともあれ、ラウンドアバウトは一切の例外無く時計回りの一方通行である。ラウンドアバウトの内部に既に進入している車が全ての周辺流入路に対して絶対的優先通行権を有する。右側から来る車が優先権を持つので、ラウンドアバウトに入ろうと思うときはまず右から車が来ないかどうか確かめて、たといそれが自転車であろうと十トントラックであろうと、何らかの車が右からこのラウンドアバウトを周回してくるのを認めたら、その車が自分の前を通過してしまうまで周回路内に入ってはいけない。右から車が来ないことが容易に確認できる場合には、ラウンドアバウトに入るに際して一時停止するには及ばないので、安全を確認しつつそのまま進入してよい。進入する道路から見てすぐ左隣の道に進みたいときは、左折信号を出しながら一番左の車線を進み、すぐに左折してラウンドアバウトを離脱する。それ以外の道に進みたいときは、右折信号を出しつつ進入してラウンドアバウトを周回し、目的の道の一つ前の道を過ぎたときに左折信号に切り換えて、目的の道に左折で入り、ラウンドアバウトを離脱する。これはもう絵がないことには説明のしようもないので、東京海上日動さんのサイトから引用させていただきます。(東京海上日動のサイトより)上の絵で、たとえば赤の車が右折したければ、ラウンドアバウトに進入して270度ぐるっと回って抜けていくことで、論理的な右折をすることができます。クルマは常に時計回りなので、万一接触した際にも2台の車の相対速度が小さいという特性もあります。右の道からの進入が続いたりすると、赤の車はいつまで経ってもラウンドアバウトに入れなくなるのではないか、と思えます。車は右からだけでなく、左の道からも上の道からも入ってくるわけです。上から入ってくると、内部を進行を優先する原則から、右からの進入は保留せざるを得ません。すると下の車に進入のチャンスが生まれるというわけです。面白いのは、「交通量の自然調節が行われる」(本書より)点。ラウンドアバウトでどれだけ車が通過するかは、経路によって異なります。上の図で、左右方向の交通量が多く、上下方向は少ないとしましょう。左右方向にひっきりなしに車が流れていくと、上下方向からの車がラウンドアバウトに進入するタイミングがなくなるではないかと。それでも、左右方向から来て上下方向に抜ける車がたまに現れるわけです。左からの緑の車が下に抜ける(論理的な右折をする)場合、その車が270度回る間に右からの流入をいったんせき止めることになります。その車が下に抜けることは左折信号から判断できるので、下からの赤の車は安心して進入できることになります。その赤の車がさらに左からの車の進入をせき止めて上の道に抜けるため、今度は上の道からの進入も可能になる、とこういうわけです。B→D街道を直進する車の量は右折車両やA→C道の車の数に比しては圧倒的に多いだろうから、それだけ優先的にどんどん進むことができるというあんばいになる。信号の時間をコンピュータで制御したりしなくとも、交通量の多寡によって、自然に自動的にラウンドアバウト内への流入量が制御される仕組みになっている*1。HACKS』からの紹介。統計の本というと、抽象的な概念と数式が淡々と書かれていてだんだんつらくなっていくものなのですが、本書はその理論的な部分を、具体例や興味深い応用例で味付けしてくれており、最後まで読む気にさせてくれます。くだけた語り口に、訳者の方の苦労が偲ばれます。Freyオライリー・ジャパンAmazon本書で紹介しているのが、「どんどん強くなる三目並べ」の仕組みです。用意するのは、以下だけ。各マッチ箱は、三目並べでありうる盤面287パターンに対応している*3。「真ん中にOが置かれて、あとはまだ空白」とか。これがマッチ箱の中に書かれている。9色の大量のビーズビーズの色は、三目並べの9つのマスに対応している。「真ん中のマスは赤」とか。各マッチ箱に、盤面に応じて選べるマスに対応するビーズだけを入れておく。初期状態はすべてのマスが空なので、9色すべてのビーズを入れておく。「最後の一手」に対応する盤面では選べるマスが1つしかないので、そのマスに対応する1色のビーズだけを入れておくことになる。ゲームの進め方を引用します*4。ゲーム自体は、地面の上にでも線を引いて行います。現在の盤面のマッチ箱を探す(第一手のときは、空白のもの)。目を閉じて適当にビーズを取り出す。ボード内の小石の色が示すマスにXを入れる。そのビーズを邪魔にならない場所に退ける。自分が選んだ場所にOと記し、自分の番をこなす。盤面は新しい配置になった。対応するマッチ箱の所に行って、ビーズを無作為に取り出す。勝負がつくまでステップ2からステップ4までを繰り返す。コンピュータが負けた場合、マッチ箱から無作為に取り出したビーズを手にして、海に投げ込むことで罰する。コンピュータが勝った場合、または引き分けた場合、ビーズを元のマッチ箱に戻し、同じ色のビーズを追加することで報酬を与える。最初のゲームでは、「コンピュータ」は可能な手すべてから、勝負の有利不利は関係なく、ランダムに(「目を閉じて」)手を選ぶことになります。ゲームのたびに、負けにつながった手に対応するビーズが破棄され、勝ちにつながった手に対応するビーズが追加されるので、2ゲーム目以降、勝ちにつながる手を選ぶ確率がどんどん高くなっていくという仕組みです。する」「報酬を与える」という言葉が出てくるので、強化学習そのものにも見えるのですが、本書の原著が2006年でああり、そもそもこの話が雑誌に載ったのは1963年とのことで・・・先進が過ぎる。まとめいかがでしたか?*5「コンピュータっぽいことを人力でやる」話は、SFアンソロジー『折りたたみ北京』の中の一作、劉慈欣氏の『円』にも出てきます。円周率を文字通り「人海戦術で」求める壮大なお話。早川書房Amazonこの『円』は、今話題の中国SF『三体』のエピソードを切り出したものとのこと。わたしの好きなSFの条件って、「予想の上を行くファーストコンタクト」と「想像もつかないガジェット」なのですが、『三体』は特に後者、「智子(ソフォン)」と「宇宙社会学」がめちゃくちゃ効いていて、物語にガッシリとした芯を通しています。*2:こういった特性をもつラウンドアバウトですが、たとえば「全ての人が完全にルールを遵守する」ことを前提にしているといった欠点も紹介されています。*3:ありうる盤面パターンのうち、回転・反転で同一になるものはを集約している。*4:本文の「ココナッツ」を「マッチ箱」に、「小石」を「ビーズ」に読み替えている。他、一部修正*5:未だにこの「いかがでしたか」ネタを愛している。次に来るキーテクノロジー2018-2019』という本を読み...2014-03-26シナリオベースの探索的テストとは何か。AdSenseを使用しています。AdSenseは、ユーザーの興味に応じた広告を配信するためにCookieを利用しデータを収集しています。Cookieを無効にする設定、およびGoogleアドセンスに関する詳細は、Googleのポリシーと規約をご覧ください。はてなブログをはじめよう!kz_suzukiさんは、はてなブログを使っています。ブログを報告する引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。