収穫逓減 - Wikipedia
収穫逓減（しゅうかくていげん、英: diminishing returns）は、経済学用語であり、収穫逓減の法則とも呼ばれる。 固定および可変の入力（例えば工場規模と労働者数）のある生産システムで、可変入力がある点を過ぎると、入力の増加が出力の増加に結びつかなくなっていく。逆に製品をより多く生産するのにかかるコストは増大していく。これを相対費用逓増の法則[1]あるいは機会費用逓増の法則[2]、限界生産力逓減の法則[3]とも呼ぶ。 表面上は完全に経済的概念だが、収穫逓減はテクノロジ的関係も暗示している。収穫逓減の法則は、企業の短期限界費用曲線が結局は増大することを示している。 歴史[編集] 収穫逓減の概念の起源を遡ってみると、ヨハン・ハインリヒ・フォン・チューネン、ジャック・テュルゴー、トマス・ロバート・マルサス、デヴィッド・リカードといった初期の経済学者の懸念にたどり着く。 マルサスとリカ
グスタフソンの法則 - Wikipedia
グスタフソンの法則（英: Gustafson's law、Gustafson-Barsis' law としても知られる）は、計算機工学における法則で、「十分に大きな規模の問題は、効率的に並列化して解くことができる」事を示すものである。グスタフソンの法則は、並列化によってプログラムが高速化できる限界を示したアムダールの法則と密接に関係している。本法則は、ジョン・グスタフソンによって1988年に初めて示された。 P がプロセッサの数であり、S がSpeedup、α がプロセスの並列化できない部分であるとすると、下記が成立する。 グスタフソンの法則は、計算機の規模が大きくなると利用可能な計算能力を使い切るほど性能がスケールしないというアムダールの法則に欠けていた部分に対応するものである。グスタフソンの法則では、問題の規模が固定である、また並列プロセッサ上の計算の負荷が一定であるという仮定を取り除
アムダールの法則 - Wikipedia
複数のプロセッサを使って並列計算してプログラムの高速化を図る場合、そのプログラムの逐次的部分は、制限を受ける。例えば、仮にプログラムの95%を並列化できたとしても、残りの部分である5%は並列処理ができないため、どれだけプロセッサ数を増やしたとしても、図で示したように20倍以上には高速化しない。 アムダールの法則（アムダールのほうそく、英語: Amdahl's law）は、ある計算機システムとその対象とする計算についてのモデルにおいて、その計算機の並列度を上げた場合に、並列化できない部分の存在、特にその割合が「ボトルネック」となることを示した法則である。コンピュータ・アーキテクトのジーン・アムダールが主張したものであり、アムダールの主張（アムダールのしゅちょう、英語: Amdahl's argument）という呼称もある[1]。 複数のプロセッサを使い並列計算によってプログラムの高速化を図る
グラフの自動レイアウトに挑戦 #1 グラフ構造をSVGで表示 | matarillo.com
2022-08-12 13:50:22 作成したアプリケーションとソースコード アプリケーション： https://refd6y.csb.app/ （ブラウザで実行します） ソースコード： https://codesandbox.io/s/graph-layout1-refd6y はじめに 連載記事のトップのところに書いた図はこのようなものだ。 これをコンピュータに自動配置させたい。 Eadesのばねモデル このような、つながった複数の物体をコンピュータに自動配置させるのは「グラフ描画」または「グラフレイアウト」と呼ばれる分野であり、さまざまなアルゴリズムが研究されている。この連載記事では比較的単純な「Eadesのばねモデル」というアルゴリズムを採用する。 Eadesのばねモデルとは、次のようなモデルをつくって物理シミュレーションすることで、物体を配置するアルゴリズムだ。 各ノード(頂点)
おねえさんを組み合わせ爆発から救う：完結編おねえさんは星になった - きしだのHatena
おねえさんを組み合わせ爆発から救うために、経路をZDDとして表したら、すっきりと経路情報が扱えました。 http://d.hatena.ne.jp/nowokay/20121018#1350528607 あとは、このZDDを効率よく構築できれば、おねえさんを救えそうです。このZDDの構築には、クヌース先生の開発したSimpathアルゴリズムを使うと非常に効率よく構築できます。 前回生成したZDDを見ると、同じノードにまとまっているものがいくつかあることがわかります。特に後半になるとどんどん同じパターンになるものがまとめられていきます。 つまり、この経路問題のZDDを構築するときには、いかに同じパターンになるものをまとめるかが鍵になるということです。 Simpathでは、辺の端だけに注目して、同じパターンになっていればそれ以降のノードを使いまわすという考え方で、ノードをまとめていきます。 つ
メタヒューリスティクス - Wikipedia
この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "メタヒューリスティクス" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL（2023年8月） メタヒューリスティクスとは、組合せ最適化問題のアルゴリズムにおいて、特定の計算問題に依存しないヒューリスティクスのことである。 近年では、上記の定義から拡張され、特定の問題に依存しない、汎用性の高いヒューリスティクス全般を指すこともある。そのため、組合せ最適化問題のアルゴリズムに限らず、連続最適化問題に対するアルゴリズムも含む解釈も存在する。 概要[編集] 通常ある問題に対しての「解法」が存在するとき、その解法が適用できる範囲はその問題に対してのみで
最近傍探索 - Wikipedia
最近傍探索（英: Nearest neighbor search, NNS）は、距離空間における最も近い点を探す最適化問題の一種、あるいはその解法。近接探索（英: proximity search）、類似探索（英: similarity search）、最近点探索（英: closest point search）などとも呼ぶ。問題はすなわち、距離空間 M における点の集合 S があり、クエリ点 q ∈ M があるとき、S の中で q に最も近い点を探す、という問題である。多くの場合、M には d次元のユークリッド空間が採用され、距離はユークリッド距離かマンハッタン距離で測定される。低次元の場合と高次元の場合で異なるアルゴリズムがとられる。 ドナルド・クヌースは、The Art of Computer Programming Vol.3（1973年）で、これを郵便局の問題で表した。これはすな
組合せ爆発 - Wikipedia
組合せ爆発（くみあわせばくはつ、英: combinatorial explosion）は、計算機科学、応用数学、情報工学、人工知能などの分野では、解が組合せ（combination）的な条件で定義される離散最適化問題で、問題の大きさn に対して解の数が指数関数や階乗などのオーダーで急激に大きくなってしまうために、有限時間で解あるいは最適解を発見することが困難になることをいう。 概説[編集] それ以外の通信ネットワーク、情報システム開発、化学その他の分野ではより広義に、要素の数が多くなるとその組合せによって急激に、考えられる可能性の数、とりうる実現形の数、実行すべき手順の数、あるいは全体の複雑さが非常に巨大化してしまうことをいう。 組合せ的爆発（くみあわせてきばくはつ）、組合せ論的爆発（くみあわせろんてきばくはつ）ともいう。計算量の爆発（けいさんりょうのばくはつ）の方がより一般概念であり、そ
ヒューリスティック - Wikipedia
ヒューリスティック（英: heuristic、独: Heuristik）または発見的（手法）[1] [2]:7 [3]:272とは、必ずしも正しい答えを導けるとは限らないが、ある程度のレベルで正解に近い解を得ることができる方法である。発見的手法では、答えの精度が保証されない代わりに、解答に至るまでの時間が短いという特徴がある。 主に計算機科学と心理学の分野で使用される言葉であり、どちらの分野での用法も根本的な意味は同じであるが、指示対象が異なる。すなわち、計算機科学ではプログラミングの方法を指すが、心理学では人間の思考方法を指すものとして使われる。なお、論理学では仮説形成法と呼ばれている。 計算機科学[編集] 計算機科学では、コンピューターに計算やシミュレーションを実行させるときに、発見的手法を用いることがある。たいていの計算は、計算結果の正しさが保証されるアルゴリズムか、または計算結果が
動的計画法 - Wikipedia
動的計画法（どうてきけいかくほう、英: Dynamic Programming, DP）は、計算機科学の分野において、アルゴリズムの分類の1つである。対象となる問題を複数の部分問題に分割し、部分問題の計算結果の記録を利用して全体の問題を解く手法を総称してこう呼ぶ。 定義[編集] 細かくアルゴリズムが定義されているわけではなく、下記2条件を満たすアルゴリズムの総称である。 帰納的な関係の利用：より小さな問題例の解や計算結果を帰納的な関係を利用してより大きな問題例を解くのに使用する。 計算結果の記録：小さな問題例、計算結果から記録し、同じ計算を何度も行うことを避ける。帰納的な関係での参照を効率よく行うために、計算結果は整数、文字やその組みなどを見出しにして管理される。 概要[編集] 「動的計画法(dynamic programming)」という言葉は1940年代にリチャード・E・ベルマンが最初
組合せ最適化 - Wikipedia
この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "組合せ最適化" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL（2018年12月） 組合せ最適化（くみあわせさいてきか、英: combinatorial optimization、組み合わせ最適化、または組み合せ最適化とも表記される）は、応用数学や情報工学での組合せ論の最適化問題である。オペレーションズリサーチ、アルゴリズム理論、計算複雑性理論と関連していて、人工知能、数学、およびソフトウェア工学などの交差する位置にある。組合せ最適化では、厳密解が簡単に求まる場合もあれば、そうでない場合もある。厳密解を求めるのが難しいと思われる問題を解くた
シーケンスペア - Wikipedia
シーケンスペア（Sequence-pair）は、矩形配置の表現方法のこと。矩形同士の相対位置関係を矩形名の順列の対により表すことができる。集積回路設計の一工程である配置計画（フロアプラン）での利用を目的として開発されたが、発見的探索法（メタヒューリスティックアルゴリズム）である焼きなまし法と組合わせて用いると、離散数学の組合せ論でNP困難な問題である矩形パッキング問題に有効なことが知られている。 概要[編集] 技術的背景[編集] 集積回路設計の一工程である配置計画（フロアプラン）では、回路として実現するために必要な様々なモジュール（記憶素子や演算器など）を、シリコン基板上にどのように配置するかを検討する。半導体ビジネスでは、1枚のシリコンウェハーから出来るだけ多くの集積回路(IC, LSI)を製造することが収益面で不可欠である。そのため、集積回路そのものを出来るだけ小さく設計することが望ま
遺伝的アルゴリズム - Wikipedia
遺伝的アルゴリズム（いでんてきアルゴリズム、英語：genetic algorithm、略称：GA）とは、1975年にミシガン大学のジョン・H・ホランド（John Henry Holland）によって提案された近似解を探索するメタヒューリスティックアルゴリズムである。人工生命同様、偶然の要素でコンピューターの制御を左右する。4つの主要な進化的アルゴリズムの一つであり、その中でも最も一般的に使用されている。 概要[編集] 遺伝的アルゴリズムはデータ（解の候補）を遺伝子で表現した「個体」を複数用意し、適応度の高い個体を優先的に選択して交叉・突然変異などの操作を繰り返しながら解を探索する。適応度は適応度関数によって与えられる。 この手法の利点は、評価関数の可微分性や単峰性などの知識がない場合であっても適用可能なことである。 必要とされる条件は評価関数の全順序性と、探索空間が位相（トポロジー）を持っ
粒子群最適化 - Wikipedia
粒子群最適化（りゅうしぐんさいてきか、Particle Swarm Optimization、PSO）とは、群知能の一種。 昆虫の大群や魚群において、一匹がよさそうな経路を発見すると（すなわち、食料を発見したとか安全であるという場合）、群れの残りはどこにいても素早くそれに倣うことができる。 これは多次元空間において位置と速度を持つ粒子群でモデル化される。これらの粒子はハイパー空間を飛びまわり、最善な位置を探す。位置の評価は適応度関数で行う。群れのメンバーは良い位置について情報交換し、それに基づいて自身の位置と速度を調整する。このコミュニケーションは主に次の二種類の方法でなされる。 最も良い位置にいる粒子が全体に通知される。 ローカルなベストの位置にいる粒子が近傍の粒子群に通知される。 位置と速度の更新は以下の式で行われ、これが繰り返される。 は、慣性定数。多くの場合 1 より若干小さい値が
アルゴリズム入門
アルゴリズム入門はアルゴリズムを独学したい人のページです。アルゴリズムってなに？という人からフローチャートの書き方、ソートなどの一般的なアルゴリズムを解説しています。練習問題なども収録しています。
アルゴリズム - Wikipedia
アルゴリズム（英: algorithm[注 1]）とは、解が定まっている「計算可能」問題に対して、その解を正しく求める手続きをさす[注 2]。あるいはそれを形式的に表現したもの。 実用上は、アルゴリズムの実行に要する記憶領域の大きさや完了までに要する時間（空間計算量と時間計算量）が小さいこと、特に問題の規模を大きくした際に必要な記憶領域や計算量が急激に大きくならないことが重要となる。 アルゴリズムの実行は形態によらない。コンピュータプログラムはコンピュータ上に実装されたアルゴリズムの例である。 概要[編集] フローチャートはアルゴリズムの視覚的表現としてよく使われる。これはランプがつかない時のフローチャート。 岩波国語辞典「算法」に、まず「計算の方法」とした後に2番目の詳細な語義でalgorithmの訳として、 特に、同類の問題一般に対し、有限回の基本的操作を、指示の順を追って実行すれば、
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
