数学の難問「巡回セールスマン問題」の近似解を求める最良のアルゴリズムが数十年ぶりに更新される
巡回セールスマン問題とは、「複数の都市を移動するセールスマンが全都市をちょうど一度ずつ巡り、総移動コストが最小の経路を求める」という数学の難問です。長年にわたり「クリストフィードのアルゴリズム」が巡回セールスマン問題の近似度が最も高いアルゴリズムとされてきましたが、新たに「クリストフィードのアルゴリズムを上回る近似度のアルゴリズムがあると証明された」という論文を、コンピューターサイエンスの研究者が発表しています。 [2007.01409] A (Slightly) Improved Approximation Algorithm for Metric TSP https://arxiv.org/abs/2007.01409 Computer Scientists Break Traveling Salesperson Record | Quanta Magazine https://www
解けたら賞金1億円！ 数学の7つの未解決問題のひとつ「P≠NP」問題へのアプローチがもたらすもの | ログミーBusiness
情報処理における全国のエキスパートが一堂に会したリクルート主催の「春の情報処理祭」。20世紀末のミレニアム懸賞にも選ばれた「P≠NP」という未解決問題に対して、アルゴリズムを用いたアプローチ方法を電気通信大学准教授の岡本吉央氏が解説しました。 P≠NP問題、進捗どうですか？岡本吉央氏：よろしくお願いします。電気通信大学の岡本です。アルゴリズム分野の話をしたいんですが、なぜかP≠NP問題の話を今日はしようと思います。「みなさん、進捗どうですか？」というのがこの祭りのテーマなので、「P≠NP問題、進捗どうですか？」ということを話したいんですが、このP≠NP問題というのは、すごく大きな未解決問題なんです。 いろんなところで、これは未解決だと言われているんですけれども、これが今どのぐらい解決に向かって進んでいるのかということをお話ししたいと思います。私自身は計算幾何学とかグラスアルゴリズムとか、グ
Google Chromeが採用した、擬似乱数生成アルゴリズム「xorshift」の数理
2015年12月17日、Google Chrome の JavaScript エンジン（処理系）である V8 の公式ブログにて、 JavaScript の標準的な乱数生成APIである Math.random() の背後で使われているアルゴリズムの変更がアナウンスされました。 Math.random() 関数は JavaScript を利用する際には比較的よく使われる関数ですので、親しみのある方も多いのではないかと思います。 新たなバグの発見や、従来より優秀なアルゴリズムの発見によってアルゴリズムが変更されること自体はそれほど珍しくはないものの、 技術的には枯れていると思われる Math.random() のような基本的な処理の背後のアルゴリズムが変更されたことに驚きを感じる方も少なくないかと思いますが、 それ以上に注目すべきはその変更後のアルゴリズムです。 実際に採用されたアルゴリズムの原
行列分解ライブラリredsvdを公開しました - DO++
大規模疎行列向けの行列分解ライブラリredsvdを公開しました． redsvd 大規模疎行列向けの特異値分解や主成分分析，固有値分解を行うライブラリredsvdを公開しました． 修正BSDライセンスで公開しており，コマンドラインから使える他，C++ライブラリが用意されています． 例えば，行と列数がそれぞれ10万，非零の要素が1000万からなる疎行列に対する上位20位までの特異値分解を約2秒で処理します． 特異値分解とか，使っている技術の詳細とか応用事例を以下に簡単に紹介しましたので，興味のある方は参考にしてください． 特異値分解とは まず行列を適当に復習します．行列Xの転置をX^tと表すことにします．またIを単位行列とし，Oを全ての成分が0である零行列とします．また，行列XX^t=IであるようなXを直交行列と呼びます．Xが直交行列の時，Xvはベクトルvを長さを変えずに回転させます．ここでは
第11回 2進数と10進数のビミョーな関係
原始，人間は指を折って数を数えた。デジタルの語源であるdigitは「指」を意味する。11以上の数は，ほかの人の手を借りて数えた。要するに桁上がりだ。しかし，コンピュータは人間とは違って2進数で演算処理を行う。そんな「機械と人の数の数え方」について調査した。 2進数だって人間の都合でできている 2進数とは「0または1のどちらかの値しか持たない，数の数え方」だ。コンピュータの処理がこの2進数を基本にしていることは，皆さんご存じだろう。なぜ，コンピュータは10進数ではなくて2進数で計算するのだろう？ もしかすると，コンピュータの都合で決まっているように見えるかもしれない。 実のところ，0とか1とか2進数とかいった考え方自体もまた非常に人間寄りなものだ。CPUは，自分の扱っているデータが0か1か，ましてや，それに基づく数の数え方が2進数かどうかなんて，みじんもわかっていない。 CPUに判断できるの
PythonでPLSAを実装してみる
probabilistic latent semantic analysis (PLSA)は、 ・文書dがP(d)で選ばれる ・潜在変数zがP(z|d)で選ばれる ・語wがP(w|z)で生成される というプロセスを経て、結果として(d,w)のペアが観測されるという文書と語の生成モデル。 式で表すと (1) となる。P(d,w)の尤もらしい確率分布を見つけたい。対数尤度関数は (2) となる。n(d,w)は語wが文書dに出現する回数。この式は訓練データn(d,w)（;どの語がどの文書に何回出現したか）が尤もらしい確率分布P(d,w)に従うとき最大になる。ベイズの定理を用いると (3) となることを利用して、この尤度関数を最大化するためにEMアルゴリズムを用いて実装してみる。（過学習を回避するために文献ではTempered EM (TEM)を用いている。）尤度関数が収束するまで以下のE-ste
綱引きに蛇口当てゲーム？！ 楽しく学ぶベイズフィルターの仕組み
付き合いたくないスパムと付き合うために 受信者の意向を無視して、一方的に送りつけられる迷惑メール（スパム）は、いまやメールボックスを雑音でいっぱいにしてしまい、大事なメールを見過ごしかねないほどの量に膨れ上がり、大きな問題となっています。 残念ながら、このようなスパムを発生源から断つような根本的な対策はいまだになく、私たちは、せめてメールサーバで受け取った大量のメール群からスパムと大事なメールを仕分けしてくれる仕組みに頼らざるを得ません。 スパムを判定する方法は、次の2つに大別することができます。 本稿では前者の方法に着目します。メールを受け取った人にとっては、メールの中身を読めば、そのメールがスパムかそうでないかを判定するのは容易なことです。スパムの定義は、メールを読む人によって変わる可能性があります。例えば、まったくゴルフをしない人にゴルフの勧誘メールが来た場合はスパムといえるでしょう
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
長文日記