渋谷で働くSEのブログ

渋谷で働くSEのお粗末なブログです

グラフ理論、最適化問題

お久しぶりです(^^)/

実は、音楽の研究はあまりにも進まなかったもので、しばらくお休みにしてました。

そして、今は最適化問題にはまってます。

グラフ理論とか。

 

そんな中、最適化問題に関する面白い記事を見つけました。

原文はハングルですが、内容は以下のようなものです。

「ソウル市内の3箇所で同じ時間に結婚式が行われることになっています。どうしましょうか?」

その3箇所を地図上で見ると次のようになっています。

f:id:kyosuu1:20170219023621p:plain

この悩みを聞いた韓国の芸能人キム・スクさんは、次のように答えています。

ロッテワールドに、式の1時間前に言って、結婚するお友達に挨拶をし、一緒に写真を撮ってください。そして、彼らにバレないようにカンナムに移動します。カンナムでもまたお友達にちゃんと挨拶をし、結婚式に出席したことにしましょう。

そして次に、式が始まってから30分後にはホンデに着けるようにしましょう。この時間帯は、ちょうど式が終わって、写真を撮るためにバタバタする時間です。そこに紛れ込んで写真撮影ができたらミッションクリアです」

 

原文は

http://www.wikitree.co.kr/main/news_view.php?id=292256

ここにあります。

 

実は、これって、最適化問題の最も簡単な例です。

 

まず、前提として、日本と韓国の結婚式文化の違いだけ説明させてください。

日本では、結婚式に出席して、披露宴を行います。

しかし、韓国では、面白いことに、結婚式が行われている時間に結婚式場に付いている食堂で食事をすることができます。

(その食堂は、ご祝儀を出した人だけ利用できるようになっています)

なので、式はどうでもよくで、とにかくご祝儀出してご飯食べちゃう人もいたりします。

こんな文化ですから、式に出席しなくても、挨拶さえちゃんとすればバレないわけです。

 

そこで、結婚するお友達に挨拶できるポイントがどこにあるか。

ここでは、3箇所を見出しています。

1. 新郎新婦が待機している、挙式の1時間前

2. 結婚式が始まる直前

3. 集合写真を撮ろうとしている時間

 

この時間を合わせると、だいたい1時間半。

この制限時間と移動時間を考慮すると、

だいたい各結婚式場に滞在できる時間は約10分ずつです。

 

数学の言葉に直して見ると、次のような問題になります。

f:id:kyosuu1:20170219023316p:plain

実際、道はいっぱいあると思いますが、簡単のため1本ずつにしました。

往路と復路がそれぞれにあるので、ホンデ、カンナム、ロッテワールドを点とし、道のりを向きづけられたedgeとする有向グラフとして見なせます。

そして、各経路には、移動時間という重みが付いています。

各点にも、滞在時間という重みがついています。

 

制限時間の1時間半以内に、どうすれば3点全部回れるか。

という問題に帰着するわけです。

 

こんな問題を「巡回セールスマン問題」と言います。

特に、ここでは時間制約がついているので、特にこれを「時間制約の付いている巡回セールスマン問題」とも言うようです。

 

ここでは、点が3つのpath(グラフ理論でいうpathのこと)を考えているので、人の頭で十分計算できたんですが、

点がn個になると、人間の頭ではとても計算できなくなります。

 

そうなると、結局コンピュータの力を借りることになります。

「時間制約付き 巡回セールスマン問題」と検索したらたくさん出てきます。

滞在時間はさすがに10分よりも短いですし、各点の間の重みもさっきの結婚式問題よりはだいぶ小さくなってはいるんですけど、

結局考えてることは一緒です。

「一番時間かけない方法はどれだろう」

 

全部の組み合わせを試すなら、絶対爆発して行きます。

なので、爆発を防止するためにもいろんなアルゴリズムが研究されました。

 

最近はグラフ理論を勉強してますが、近いうちにこの最適化問題にも挑戦できるようになったらいいな、と思っています。

『Grit』を読み終えました

 

Grit: The Power of Passion and Perseverance

Grit: The Power of Passion and Perseverance

 

 昨日、ちょうどこの本を読み終えました。

ほぼ1ヶ月ぐらいかけていた気がします。

原文のまま読んでもすごくわかりやすい本ですし、さらにAmazon電子書籍で読むと長押しで単語の意味も表示してくれますので大変便利です。

 

「何かを成し遂げる人、成功を収める人にはどんな特徴があるか」について議論している本です。

 

この本のタイトルであります「Grit」は、日本語では「やり抜く力」と訳されます。

最初は、国の支援を受けて士官学校の生徒たちを対象に研究を行ったそうです。

優秀な軍人を育てるのに必要な研究ですから、国も喜んでこの研究を支援していたでしょう。(私も学振研究者でしたので、なんかよくわかります)

 

成功を収めた事業家やスペル大会で優勝した子供など、いろんな人たちを対象に研究し、筆者が出した結論は、

「成功を収めるには、素の才能よりも情熱(変わらない興味をもって仕事に取り組み続けること)と忍耐が大事」

ということだそうです。

 

そして筆者はまたgritの育て方についても述べています。

青少年期に自力で逆境を乗り越える経験をしていれば、大人になってからもgritな人になるそうです。

逆に、青少年期に逆境は経験したけれども、そのタフな環境が自力ではどうも解決できないようなものであったならば、大人になってからも無気力のままになってしまうそうです。

 

その「不可抗力」といえば、「子供の貧困」が挙げられるでしょう。

筆者はここも逃さず指摘しています。

しかし、この本は、あくまでもgritそのものについて語るものであって、子供の貧困問題に関する本ではないので、この部分はさらっと言って深入りはしない感じでした。

 

「逆境を乗り越える」「難しいことを続ける」経験をするには何がいいか。

筆者は、「課外活動」を取り上げています。

課外活動とは、学内外でのサークル活動のことです。

筆者によると、学年が変わってもサークルを変えていなかった生徒の方が、大学でもうまくやっていける可能性が高いそうです。

 

自分のGritだけでなく、「これから子供たちをどのように教えていくか」についても考えさせられる、大変よい本でした。

英文そのものも非常にわかりやすく書かれているので、英語の勉強にもおすすめです。

San Juanitoの楽譜作成が完了しました

ご無沙汰しております(^^)/

今更ですが、あけましておめでとうございます。

今年もよろしくお願いします。

 

研究のためのデータ作成にすご〜〜〜く時間をかけております。

やっとSan Juanitoの楽譜&距離行列の作成が完了しました。

 

今は実家にいますので、また戻ったらTobasの採譜を再開しようと思います。

ここに置いておきました。

MusicPersScripts/sj at master · kyosuu1/MusicPersScripts · GitHub

 

Tobasの採譜が完了したら、San JuanitoとTobasの位相的構造を比較していこうと思います。

全曲通しで見た方がいいとは思いますが、自宅のノートパソコンでは無理なようなので、

パートごとに見ていくしかないかな、と思います。

 

聞いた話だと、TDAの計算というのは組合せ爆発を起こすっぽいです。

だからか、maxdimensionやmaxscaleを上げすぎるとパソコンが止まってしまいます。

やっぱうちではちょっとずつ切って見てみるしかないかな…と思います;;;

 

またしばらく「昼は耕し、夜は誦す(??)」(本当かな???…なんだか昼も夜むやってること一緒の気がするけどね…)生活が続きそうですね^^;

TobasとSan Juanitoの研究のためにデータを作成しながら…

時間ができたら、ちょくちょくデータ(csv形式の楽譜)を作成しています。

とりあえずSan Juanitoの方のデータを作成しているんですが、本当にいろいろな形式のSan Juanitoがあるんだな…と感じました。

 

当初想定したIntro - A - A' - … - B(一瞬だけ長調に変わる)

形式だけでなく、A、B、C形式のもの(かな?)もあれば、

IntroとAしか存在せず、長調に変わるところがないSan Juanitoもたまにありました。

 

しかし…

その中でも私、異邦人の研究者のメンタルを崩壊させる曲がありましてですね…

 

これです!

 

youtu.be

 

え??

San Juanitoっていいながら、なんだか冗長性を感じさせます。

 

たしかに、フレーズそのものは長くないですが、

終結型(Am調だからAmで終わる)でないフレーズが3つあって、

4つ目でやっと終結型となるのがその原因です。

 

なかなかこんなのは…

私のメンタルを崩壊させます。

機械学習的にいえば、これをデータセットに入れると判別機の精度が逆に落ちるのではないかな、とも思われます。

 

いい歌なんですけど、真剣に研究しようとするとなかなか難しいかもしれませんね。

 

アワティーニャスのみなさんは、完全に「自分の世界」を構築したかのようにも見えます。

奏者のみなさんも、アワティーニャスのこんなところこそが大好きだ!と言っています。(私もです)

 

やっぱ音楽の研究って、真剣にしようとしたら意外と難しいもんですね。

でも、音楽そのものは好きですよ♪

工業英検準2級合格

工業英検準2級に合格しました。

f:id:kyosuu1:20161217163026j:image

 

正直、準2級はまだ和文英訳が多いので、院卒なら片手でとれてしまうぐらいです。

 

本当なら2級を受けたかったところですが、

残念ながら2級は土曜日にしかありません。

土曜日は教会で礼拝がありますのでちょっと無理です(ヾノ・∀・`)

だからといって1級受けるには…

受験料が痛いですね。

たしか1万越えてましたので。

 

合格率が思ったより低くてちょっとびっくりしました。

f:id:kyosuu1:20161217163218j:image

 

正直、数学の論文を書くぐらいなら、準2か2ぐらいで十分かな、と思います。

なので、これ以上工業英検を受けるつもりはありませんが、技術系ライティングの勉強はまだ続けたいと思います。

研究の進捗

ずっと前からSan JuanitoとTobasの位相的構造について研究しています。

今はまずデータをとる段階で、曲の主旋律を全部csvファイルに打ち込んでいます。

5,6曲ぐらいやると眠くなります。

という感じなので、なかなか研究が進まないんですね。

それを毎日続けています。

続けていればいずれ終わるだろう、と。

 

なんかこれ…

仕事から帰ってきてまた仕事してるようなもんですが…

何人かでわけて作業したいな、と思ったり…

聞き慣れてない曲の採譜なんか苦痛だったり…

 

でもやっぱり始めたからには、結果が見たいもんです。

 

これからも頑張りますんで👊✨

be possessed with - この記事は備忘録です

In this cartoon, a boy found a Go board in his grandparents' house, and he was possessed with a ghost in the board.

The name of ghost was Sai, and he was a go instructor in ancient Palace.

What is this cartoon?

 

はい、ヒカルの碁です。

ここで出てくる、'be possessed with'ですが、これは「悪霊にとりつかれる」という意味だそうです。

 

今日の英会話ミートアップでこれがなかなか思い出せなかったので、ちょっと悔しくなって辞書を引いてみました。

 

あ、そういえばそうだったな。難しい単語でもなかったのに…

 

私はバイリンガルではありますが、両方とも漢字文化圏の言語なので、英語的な発想はとても難しいです。

でもゆっくりやっていきます。

目標は、少なくとも5か国語がしゃべれるようになることです。

ではまたー