https://twitter.com/kinaba のログ (twilog の方が便利です。)
@natsutan 僕が今までに見た最短路を求める"アルゴリズム"で一番好きなのは、まさにそれですね | |
(1) 迷路の、隣り合ってるマスの中心と中心をヒモで結びます。迷路がヒモネットワークになりました。 (2) スタートマスの結び目と、ゴールマスの結び目を引っ張って、ピンと張るようにします。 (3) この時のスタート結び目とゴール結び目のあいだの直線が、最短路です。おわり | |
たなかのか先生のブログができとる http://nakanotana.blog110.fc2.com/ | |
おきました | |
@misagosan @zakkas783 おはようございました | |
定期横から『最短経路の本』 http://www.amazon.co.jp/dp/4431100113 をオススメするタイム @finalfusion http://twitter.com/finalfusion/statuses/7846953249 | |
アルゴリ妻 | |
昨晩書いた( http://twitter.com/kinaba/statuses/7828946380 )この手の"アルゴリズム"は、『データ構造とアルゴリズム http://www.amazon.co.jp/dp/4320120345 』のコラムが全部この系統で、初めて知った | |
スタートとゴールを両方引っ張るんじゃなくて、各結び目に重りを付けておいて、スタートだけ持ってぶら下げると、一発でスタートから全点への最短路が求まる!という応用もあるんだけど、自分としては、最初の一点to一点最短路の方が興味深かった | |
というのは、"普通の"方法(BFS, Dijkstra。A*もある程度)は、スタートから、ゴールより近い場所全部への最短路を(必要もないのに)求め"てしまう"、のでむしろ後者の1点ぶら下げ式に近い。余計な方向への最短路を求めずにスタートtoゴールの間の道だけを提示できる方が不思議 | |
自然にはものすごい並列性があるということを利用したアルゴリズム、と見ることが思うので、逆にコンピュータ上でも、超並列性を仮定すればスタートtoゴールの道だけを出すようなアルゴリズムが考えられたりするのかなあとか、そういう風に妄想が広がる | |
@finalfusion コラム部分以外はごく普通のデータ構造とアルゴリズムの本で、他の同様のタイトルの書籍と大差ないとは思います(^^; むしろああいうHW化によるアルゴリズムだけを集めた本があれば読んでみたいのですけど、寡聞にしてよく知らず…。絶対なにかあるとは思うんですが | |
@keigoi そうそうまさにそういう方向の話 | |
@ufcpp なんとなく http://favotter.matope.com/status.php?id=6115086200 この逸話を思い出しました。覚えていることに価値がある部分とない部分があって、云々 | |
@mzp ヒント:迷路の問題をCoqで解く | |
@natsutan なるほど!アルキメデスの原理は上手い例ですね。いろいろ考えてみます | |
なんの脈絡もなくぶらぶらしてきた。湯島天神→新宿のジュンク堂→帰宅。久しぶりにC++本の棚を見たかもしれないのだけどCoplien再復刊ブームなのか。マルチパラダイムデザインの第2版ってどのくらい第1版と変わっているんだろう。 | |
@takkanm うらやましい!筋と定石の方はちょうど絶版になってて入手しにくい時期に買いたくなって買ったので、古本屋で探してみつけた結構色あせてる感じのしか手元になくて…買い換えようかなあ | |
@apstndb あれ、さっき序文だけ立ち読みしたらそんな感じの記述があった記憶が…と思ったんですけど、元々最初の日本語訳が原著第1版より内容が増えてる http://www.ogis-ri.co.jp/otc/hiroba/technical/MPD/ とかその変の話だったかも | |
@finalfusion 行きは歩きで帰りは電車でした | |
歩いて行く→本買う→すぐ読みたいが歩きながら読めない/電車なら読める→電車で帰る、が基本的な僕の行動パターンです | |
@finalfusion え、僕が行ったときはめっちゃありましたよ(って遅いか(^^:)。数学書コーナーの(数学数学した本の方じゃなくて)数学史とかそっちの方の棚に表紙見せる感じで横にババーンと並んでました | |
宮増君と道玄坂さん http://opiumhero.web.fc2.com/dogen/top.html の存在に今頃はじめて気づいたのであわてて読んでいる。…アリだなこれは。 | |
@finalfusion 作中でもセルフ突っ込みが入ってましたw | |
かわさきくんが饅頭怖いらしい RT @kinaba @suztomo web漫画のリンク張るの禁止。 (via @kawasy) | |
@niam 初(赤)favがTLで話題になってる → 自分のは… http://favotter.net/status.php?id=843764214 → そういえば堀宮読み始めたのってtwitter始めた直後だったなあ → 改めてしみじみHEROさんのサイトを隅まで巡回してたらこんな漫画が!! という流れでした | |
v∈n+1距離集合≡∃p:List.p.head=S&p.last=v&isPath(p)&len(p)=n+1 ← ∃q:List.q.head=S&isPath(q)&len(q)=n&conn(q.last,v)≡∃u∈n距離集合.conn(u,v)が一番簡単と思うのだけど | |
n-距離集合の定義を @ranha さんのと変えていて、長さnの経路で到達できれば最短でなくてもいい、(というようにアルゴリズムを書く。多少効率は悪いけどまあ多項式時間ならなんでもよかった。今は反省している)。 | |
@kawasy 読んだ読んだ!これもたしかに面白かった |