グラフ理論の紛らわしい言葉歩道とか経路とか小道とか紛らわしい用語の整理。こういう学術的な専門用語は日本語で覚えるより英語で覚えた方がいいと思っているので（英語で覚えると世界中のエンジニアと会話ができるから）、英語で書きます。
拡張ユークリッド互除法
ユークリッドの互除法は最大公約数を計算する効率的な方法として古くから知られている方法です。 これについては，ユークリッドの互除法の項で説明しました。ここでは，その発展系の一つで色々なところでよく使われている，拡張ユークリッド互除法について説明します。 ユークリッドの互除法は２つの自然数 x，y の最大公約数を効率的に計算する方法でした。 例えば，GCD(13,5) を計算するのに， 13=2*5+3 5=1*3+2 3=1*2+1 2=2*1 を求めて，GCD(13,5)=1 とするものでした。今の場合この計算は，全く自明で，互除法は不要な感じがします。しかし，少し視点を変えるとそうとも言えません。上の式のうち最後の項を除いて，それぞれ，移項すると， 13-2*5=3 5-1*3=2 3-1*2=1 が得られます。ここで，３行
ユークリッドの互除法
ユークリッドの互除法は最大公約数を計算する効率的な方法として古くから知られている方法です。最も古いしかし重要なアルゴリズムと言えます。ここではこれについて説明します。 ユークリッド（-３３０？〜-２７５）はユークリッド幾何学の名前で有名な古代ギリシアの数学者です。 ユークリッドは非常に有名ですが，ユークリッド自身についてはあまり知られていません。確実なことは彼が「原論」と言われる著作を 残したことぐらいです。 ユークリッドの「原論」は昔「幾何学原論」といわれたこともありましたが，「原論」はいわゆるユークリッド幾何学の原典です。このユークリッド「原論」は全１３巻からなる大著で，その全貌を見るのは大変ですが，幸い共立出版から日本語訳が出ていて，身近に触れることも出来ます。比較的大きな図書館には蔵書されていると思いますから，興味のある人は一度ご覧になってみると良いと思います。 この「原論
四捨五入 - inamori’s diary
銀行丸めと四捨五入。 | みむらの手記手帳 5を丸めるとき、偶数になるようにする。 2.5 -> 2 3.5 -> 4なぜそうするかというと、例えば、4.4445を丸めるとき、単純な四捨五入を次々と行っていくと、 4.4445 -> 4.445 -> 4.45 -> 4.5 -> 5 となってしまうからだ。上の仕様だと、 4.4445 -> 4.444 -> 4.44 -> 4.4 -> 4 となる。これは昔読んだこの本に書いてあった。 C言語による最新アルゴリズム事典 (ソフトウェアテクノロジー) 作者: 奥村晴彦出版社/メーカー: 技術評論社発売日: 1991/03/01メディア: 単行本購入: 20人 クリック: 396回この商品を含むブログ (95件) を見る 「銀行丸め」という言葉は知らなかったが、コンピュータではこれが標準だと思っていた。
焼きなまし法 - 大人になってからの再学習
最適化問題を解くための探索アルゴリズムの1つに焼きなまし法というものがある。 最急降下法のように、値が小さくなる方向に少しずつ探索を進めていくアルゴリズムでは、その出発点に依存して局所最適解に陥ることが多い。 その結果として、大域的最適解が求まらないという問題がある。 この問題を解決して、最終的に大域的最適解が求まりやすくなるように改良したのが焼きなまし法。 考え方は単純で、「たまには解から遠ざかる方向にも進んでみよっか」というもの。 常に値が小さくなる方向ではなくて、たまには逆向きに進んでみると、もっとよい解が見つかるのではないか、と考える。 しかしながら、この「たまには」という言葉はあいまいすぎるので、確率pで、という具合に確率の話で説明する必要がある。 焼きなまし法では、この確率pは、値の変化量にも影響を受けるけど（解から大きく遠ざかる方向には、あまり行かないように確率pを小さくする
円と円の交点
半径r1 中心(x1,y1) の円と半径r2 中心(x2,y2) の円との交点。 連立方程式による解法 円の方程式は (x-x1)^2+(y-y1)^2-r1^2 = 0 …(1) (x-x2)^2+(y-y2)^2-r2^2 = 0 …(2) (1)-(2): (2 x2-2 x1)x + (2 y2 - 2 y1)y + (x1-x2)(x1+x2)+(y1-2)(y1+y2)-(r1-r2)(r1+r2) = 0 …(3) これは円と円の2つの交点を通る直線になっているので、円と直線の交点の問題に帰着できる。(3)の係数を a = 2(x2-x1) b = 2(y2-y1) c = (x1-x2)(x1+x2)+(y1-y2)(y1+y2)-(r1-r2)(r1+r2) と計算しておくとax+by+c = 0の形になる。 解法 : 直線と円の交点 JavaScript 若干計算量削減
計算幾何学問題「キュラゲの最小包含円を求めよう」の解説記事です！キーワードは「乱択アルゴリズム」 #ゲーム開発 - CodeIQ Blog
CodeIQ中の人、millionsmileです。 出題者のstakemuraさんによる「計算幾何学」問題の解説記事です。 アクションゲームなどでキャラクターを攻撃するとき、ナイーブに１キャラクターごとに１ピクセル単位で処理していたら、計算時間は大変なことになります。さて、どうやったら物理演算を軽くできるのでしょうか？キーワードは「乱択アルゴリズム」です。 ゲーム開発をしている方は必見の記事です。 =============================== 高速化の秘訣は乱数にあり stakemuraです。 先月、「キュラゲの最小包含円を求めよう」というタイトルで、CodeIQでは初となる計算幾何学の問題を寄稿させて頂きました。いきなりの難問だったにも関わらず２４名もの方に挑戦して頂き、中には当方が驚かされるような回答もあったりして、達成感を噛み締めている今日この頃です。さて、挑戦者が
最適化アルゴリズム - sonoshouのまじめなブログ
集合知プログラミングの第５章最適化の一部を自分なりにまとめます。 ヒルクライム法（傾斜上り法） ヒルクライム法は、ある地点から少し値を変更し、 変更後の値が変更前の値より低ければ採用する。 これを繰り返して行けば、最小値へ近づくことが出来る。 ヒルクライム法には致命的な弱点がある。 例えば、下図のようなグラフを考える。 このように、局所的最小解があるようなグラフでは、 大局的最小解を発見することはできない。 ヒルクライム法は非常に単純な方法で一般的に使われることは無いが、 この後の手法の比較のために説明する。 アルゴリズム＜初期化処理＞ ランダムな値で変数を初期化。カウントを初期化。 ＜反復処理＞ 変更する変数を一つ選ぶ。 変数の値を増加させるか、減少させるかを決定する。 変数の値を変更後、新たな変数でコストを算出する。 変更前と変更後のコストの大小を比較する。 変更後のコストが小さければ
粒子フィルタ - Wikipedia
この項目「粒子フィルタ」は途中まで翻訳されたものです。（原文：en:Particle Filter 15:26, 20 September 2007） 翻訳作業に協力して下さる方を求めています。ノートページや履歴、翻訳のガイドラインも参照してください。要約欄への翻訳情報の記入をお忘れなく。（2007年10月） 粒子フィルタ（りゅうしフィルタ、英: particle filter）や逐次モンテカルロ法（ちくじモンテカルロほう、英: sequential Monte Carlo; SMC）とは、シミュレーションに基づく複雑なモデルの推定法である。1993年1月に北川源四郎がモンテカルロフィルタの名称で[1]、1993年4月にN.J. Gordonらがブートストラップフィルタの名称で[2]それぞれ同時期に同様のものを発表した。 この手法はふつうベイズモデルを推定するのに用いられ、バッチ処理である
メタヒューリスティクス - Wikipedia
この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "メタヒューリスティクス" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2023年8月) メタヒューリスティクスとは、組合せ最適化問題のアルゴリズムにおいて、特定の計算問題に依存しないヒューリスティクスのことである。 近年では、上記の定義から拡張され、特定の問題に依存しない、汎用性の高いヒューリスティクス全般を指すこともある。そのため、組合せ最適化問題のアルゴリズムに限らず、連続最適化問題に対するアルゴリズムも含む解釈も存在する。 通常ある問題に対しての「解法」が存在するとき、その解法が適用できる範囲はその問題に対してのみである。 と
4段階の思考スキルレベル - Chikirinの日記
将棋ソフトに関しておもしろかったのは、先日も書いた「探索」と「局面評価」という思考プロセスです。 １）探索＝とりうる選択肢を、自分の選択肢→相手の対応策（選択肢）→自分の選択肢、と深掘りしつつリストアップ ２）局面評価＝上記の過程で現れる局面を、どの程度、自分に有利か（不利か）評価する ３）その上で、自分にとって最も有利な局面につながる選択肢を選ぶ 探索とは、下記のような図＝探索木＝ツリーのイメージです。 （『人間に勝つコンピュータ将棋の作り方』より） この探索と局面評価というステップは、ビジネスや個人生活などあらゆる意思決定の場面で使われてます。 将棋のような完全情報ゲームでないため、より複雑ですが、ビジネスでは、 ・自社が値段を下げる→他社が対抗してくる→自社はどうする？・・・であったり、 ・自社が買収を提案する→第三者が価格を釣り上げる→公正取引委員会がいちゃっもんをつける→自社はど
暗記なんかで勝てたりしません - Chikirinの日記
今日は、将棋ソフトがどのように“将棋を学んできたのか”について、まとめておきます。 今から40年ほど前の 1975年頃、人工知能研究の一環として将棋ソフトの開発は始まったそうです。 その進化の流れは、ざっくり言えばこんな感じ？ １．ルールを覚えさせる ２．金言などをプログラム化する ３．探索と駒得で手を選ばせる ４．局面評価について、機械学習をさせる １の「ルールを覚えさせる」というのは、各駒の動ける場所を教え、“二歩”など反則となるルールを教えるってことです。 でも、駒の動かし方がわかるようになっただけでは勝てたりはしません。今の私と同じです。 ちなみに「反則にならない手」は合法手と呼ばれます。 次に「金言をプログラム化する」ってことが行われたみたいです。 将棋には勝ちやすくなるための格言がたくさんあります。 「玉飛接近すべからず」「二枚替えなら歩ともせよ」みたいな言葉ですが、そういうの
力まかせ探索 - Wikipedia
力まかせ探索（ちからまかせたんさく、英: brute-force search）またはしらみつぶし探索（英: exhaustive search）は、単純だが非常に汎用的な計算機科学の問題解決法であり、全ての可能性のある解の候補を体系的に数えあげ、それぞれの解候補が問題の解となるかをチェックする方法である。 バックトラッキングと混同されやすいが、バックトラッキングでは解候補の大部分を明示的に探索することなく捨てることができる。例えば、エイト・クイーンは、8個のクイーンをチェスボード上で互いに取り合えない状態で配置するものである。力まかせ探索では 通りの配置を全て順にチェックしていく。バックトラッキングでは、2つのクイーンが互いに取り合える状態なら他のクイーンがどう配置されていても考慮に値しないという事実を使って、チェックすべき配置数を大幅に減らし、高速に解くことができる。 力まかせ探索は実
推移関係 - Wikipedia
英語版記事を日本語へ機械翻訳したバージョン（Google翻訳）。 万が一翻訳の手がかりとして機械翻訳を用いた場合、翻訳者は必ず翻訳元原文を参照して機械翻訳の誤りを訂正し、正確な翻訳にしなければなりません。これが成されていない場合、記事は削除の方針G-3に基づき、削除される可能性があります。 信頼性が低いまたは低品質な文章を翻訳しないでください。もし可能ならば、文章を他言語版記事に示された文献で正しいかどうかを確認してください。 履歴継承を行うため、要約欄に翻訳元となった記事のページ名・版について記述する必要があります。記述方法については、Wikipedia:翻訳のガイドライン#要約欄への記入を参照ください。 翻訳後、{{翻訳告知|en|Transitive relation|…}}をノートに追加することもできます。 Wikipedia:翻訳のガイドラインに、より詳細な翻訳の手順・指針につい
SRM580 - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ
SRM580のwriterをしていました。 点数はsolveまでの時間にも依存するので必ずしも600が激ムズという訳では一応ないです。 Div2 Easy 概要：区間が与えられるので重なってるペアの個数を数えよ。 解法：区間が50個しかないので全ペアについて試す。 Div2 Medium, Div1 Easy 概要：うなぎが区間として与えられるので、２点を選んでそれらのうちどちらか又は両方を含む 区間を最大化せよ。 解法：tから２つ選ぶのを全て試す。 Div2 Hard 概要：コストまたは通れないマスが書かれたgridがあるので、うまく横方向の壁を置いて左上のマスから下の段までの上移動を使わないpathのコストを最大化せよ。 解法：dp[i][j] = i段目に初めて到達したマスが左からj個目である時のコスト Div1 Medium 謝罪：TCでO(N^2)という制約はこういう入力にするし
ヒルベルト曲線 | じゃりてん日記
２次元のヒルベルト曲線というかヒルベルト走査・・・。 大学のときちょっとやったのを思い出しながら自力で考えた。 要は再帰使ってぐにゃぐにゃ動いていけばいいわけで、最初はぐにゃぐにゃの基本パターンを全部配列にしてたけど、規則性が分かればテーブルなしでもOK。 ヒマがあれば３次元にも挑戦。。。したいかも Cのソースリストのインデントがまともにでません。。 スペース2個じゃだめ？ 一応 BLOCKQUOTE してみたのだけど・・・だめだこりゃ 念のため著作権表示を入れてみました。使う人いないと思うけど。 これ、okWebという質問サイトに投稿したのと一緒のものです。あっちではJaritenCatと名乗ってますです。 #include <stdio.h> #include <stdlib.h> /* データ用変数 */ struct xy { int x; int y; } *hil; int i
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Sweep and prune - Wikipedia
Convex hull trick - PEGWiki
焼きなまし法 | プログラミング!?で遊ぶ
2021年に人工頭脳で東大入試を突破、数学担当で富士通研究所が開発に参画 