サルでも分かるwaifu2xのアルゴリズム.pdf - Google ドライブログイン
SATをサッと解く 〜乱択アルゴリズムで遊んだ話〜 - kivantium活動日記
ミレニアム問題と呼ばれる数学の7つの難問がある。各分野で重要かつ難しい問題が選ばれており、解決するとクレイ研究所から100万ドルの賞金を得ることができるということで有名だ。そのうちの1つポアンカレ予想は解決済みだが、残りの6つは未解決である。その中でもコンピュータ科学で非常に重要な問題が「P≠NP予想」である P≠NP予想とは コンピュータで問題を解決するときには一定の手続き（アルゴリズム）に従って問題を処理することになる。例えば数の集合の中からある特定の数字を見つけるという問題を考える。一番単純な解決方法は集合の要素を1つずつ調べていって値が求めたい数字になっているかどうかチェックすることだろう。この場合、集合がN個の数字からなるとすればおおよそNに比例する時間で求めたい数字の検索が終わることが予想できる。このようにだいたいNに比例する時間で終わるようなアルゴリズムについて、計算時間のオ
巡回セールスマン問題の意味と2近似アルゴリズム | 高校数学の美しい物語
都市の数 nnn と，二つの都市 iii と jjj の間を移動するのにかかる時間 dijd_{ij}dij が与えられる。このとき，全ての都市を巡ってもとの都市に戻ってくるような経路のうち，移動時間が最小なものを求めよ。 図は6都市の場合の例です（移動時間は図に書くのが難しいので，例えば二点間の距離と見てください）。青い経路はそれなりに合理的に見えますが，もっとよい経路があるかもしれません。 なお，グラフ理論の言葉を使うと「重み付きグラフに対して，重み最小のハミルトン閉路を求めよ」と述べることができます。
最短経路を見つけるアルゴリズムをビジュアルで見る「PathFinding.js」
カーナビやスマートフォンのマップアプリなど、目的地への最短ルートを一瞬で割り出してくれるサービスのお世話になっている人も多いと思いますが、その仕組みがどうなっているのかを知っている人はほとんどいないはず。その処理には、ルート探索専用のアルゴリズムが用いられているのですが、そんなアルゴリズムの動作する様子や、種類の違いによる結果の変化をわかりやすく見せてくれるサイトが「PathFinding.js」です。 PathFinding.js http://qiao.github.io/PathFinding.js/visual/ このサイトでは、スタート地点からゴール地点までの最短ルートを発見するさまざまなアルゴリズムを、自分で設定を変えながらインタラクティブに体験できるようになっています。2点の間に障害物を配置することも可能で、以下のムービーでは画面左下の緑色の地点から右上にある赤い地点までのル
正射影ベクトルの公式の証明と使い方 | 高校数学の美しい物語
物に光を当てたときにできる像を射影と言います。点光源を考える（点射影）ことも平行光線（無限遠点に光源があるとみなせる）を考えることもあります。特に，スクリーンに垂直な光線による射影を正射影と言います。 この記事ではベクトルを直線に射影したものを考えます。ベクトル aundefined\overrightarrow{a}a が定める直線とは，aundefined\overrightarrow{a}a （に対応する有向線分）を含む（向きのついた）直線 lll のことです。 lll はスクリーンの役割を果たします。例えば薄い青ベクトルの正射影は青いベクトル，薄い赤ベクトルの正射影は赤いベクトルです。 正射影ベクトルの公式は，ベクトル aundefined\overrightarrow{a}a とベクトル bundefined\overrightarrow{b}b が与えられたときに射影したベクト
Wikispaces
We are sorry, but the site you are looking for no longer exists Wikispaces was founded in 2005 and has since been used by educators, companies and individuals across the globe. Unfortunately, the time has come where we have had to make the difficult business decision to end the Wikispaces service. We first announced the site closure in January 2018, through a site-wide banner that appeared to all
AlphaBeta探索で経路依存の値を判定する方法 - Qiita
なんぞ？ AlphaBeta探索では、ゲーム木を木構造とみなして探索しているけど、現実的には合流があったりするので、それを効率的に処理するため(だけではないけど)に置換表があったりして、しかしゲームによっては辿った経路によって発動したりしなかったりするルールがあったりなんかもして、色々めんどくさいわけです。 そんなわけで、AlphaBeta探索をしていて、その時の評価値が経路に依存したものなのか否かを判定したくなったりすることもあるわけですが、割と頭がこんがらかるので、実装方法をまとめてみました。 どうやるの？ ↓こんな感じ。 末端では、それが経路依存な性質を持つか否かでフラグを設定する。 αを超えた場合(βカットを含む)は、αを超えた子ノードがtrueなときだけtrueにする。 αを超えなかった場合は、子ノードがどれか一つでもtrueならtrueにする。 β以上の子ノードがあった場合、そ
adilet.org - adilet リソースおよび情報
This webpage was generated by the domain owner using Sedo Domain Parking. Disclaimer: Sedo maintains no relationship with third party advertisers. Reference to any specific service or trade mark is not controlled by Sedo nor does it constitute or imply its association, endorsement or recommendation.
Hallの結婚定理とその証明 | 高校数学の美しい物語
まず，条件1を理解するためにマッチングについて説明します。 （追記：二部グラフの最大マッチングと増加道） マッチングとは端点がかぶらないように辺をいくつか取ってきたものです。また，マッチングの端点に属する頂点を「マッチングでカバーされている」と言います。 例えば，図では緑の辺がマッチングの一例です。頂点集合 UUU の中で上三つはカバーされていますが，一番下はカバーされていません。 VVV は全てカバーされています。 UUU の各頂点を男性，VVV の各頂点を女性，男性 aaa が女性 bbb とお互いに結婚してもよいと思うとき (a,b)(a,b)(a,b) に辺を引いたグラフを考えてみます。このときマッチングは結婚成立の一例を表しています。 すなわち条件1は， 「うまいマッチングを選べば男がみんな結婚できる」という条件になります。 次は条件2について説明します。 UUU の部分集合 A
Algorithms for calculating variance - Wikipedia
Algorithms for calculating variance play a major role in computational statistics. A key difficulty in the design of good algorithms for this problem is that formulas for the variance may involve sums of squares, which can lead to numerical instability as well as to arithmetic overflow when dealing with large values. A formula for calculating the variance of an entire population of size N is: Usin
Web広告配信における多腕バンディット問題、Mortal Multi-Armed Bandits Problemとアルゴリズム - CARTA TECH BLOG
こんにちは@hagino3000です。Zucks Ad Networkという広告配信サービスの開発をしています。最近はアドネットワークの広告配信最適化に利用できるアルゴリズムの調査もしています。 本稿では調査で読んだ論文の一つ、オンライン広告配信を想定した多腕バンディット問題である、Mortal Multi-Armed Banditsを紹介します。多腕バンディット問題になじみがある読者を想定しています。 papers.nips.cc オンライン広告と多腕バンディット問題 ここでは簡単のために、クリック課金型のディスプレイ広告を前提に説明します。オンライン広告配信システムにおける問題として「最初はどの広告がどれだけクリックされるかわからないが、なるべくクリックされる広告を多く配信したい。」という物があります。これは多腕バンディット問題として知られており、探索はCTRが推定できるまで配信する事
最小カットについて - よすぽの日記
わっけわかんねえほど沢山の制約ドパァな問題を解く一般的なテクとして、 なんかいい感じのグラフを作ったらなんかそれの最小カットが答え というのがあります 最小カットで解ける問題はどんなのなのか考えてみました 頂点がたくさんあって、それを赤と青に塗り分けるという問題を考えます。燃やすと埋めるでも大丈夫です 最小カットで解ける問題というのは、実は 頂点がたくさんある。それを赤と青に塗り分ける。全部の頂点を必ず赤か青に塗らなくてはいけない 必ず赤色に塗らなくてはいけない頂点(Sとする)と青色に塗らなくてはいけない頂点(Tとする)が存在する 「Xが赤で、Yが青の時にZ円の罰金がかかる」という制約が沢山ある 罰金の最小値は？ という問題だけです。 これの解法は、 「Xが赤で、Yが青の時にZ円の罰金がかかる」ならX->Yに容量Zの辺を貼る SからTに最大流 流せた量が答え 処理できる条件は「Xが赤で、Y
「第2回 プログラマのための数学勉強会」開催しました！（動画＆資料つき） - 34歳からの数学博士
どうも、佐野です。 3/27(金)「第2回 プログラマのための数学勉強会」が開催されました。今回も多くの方にご参加頂き、数学愛ほとばしるセッションの数々をお送りできて嬉しく思っております。各セッションの動画・資料と共に、簡単に内容のご紹介をさせて頂きます。 1. 「プログラマのための線形代数再入門 2」 - 佐野岳人 [資料] 線形代数再入門の続編として行列式・逆行列について発表しました。高校や大学で行列式を習うときは低次の場合の計算法だけか、あるいは置換を使ったガチな定義を習うかのどちらかと思うのですが、「そもそもこれは何なのか」をプログラマが納得できるように、普段見慣れているであろう「要件・仕様・実装」のフォーマットでその意味と計算法について解説することを試みました。 数学科卒というと計算が得意とか暗算が速いとか思われがちですが、僕は自分でも悲しくなるほど計算が遅くよく間違います。掃き
フーリエ変換と画像圧縮の仕組み
第2回 プログラマのための数学勉強会で発表した資料です http://maths4pg.connpass.com/event/11781/
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
高速フーリエ変換
歌舞伎座.tech#4「コンピュータ将棋プログラミング」【山本一成】
LCA and RMQ ~簡潔もあるよ！~
色々なダイクストラ高速化
コスト行列とハンガリー法
Is It New?