Rで数理計画 - RjpWiki
Rで数理計画 (例題など、どんどん付け足してください。) ここでは、Rの関数を利用した数理計画問題の解法を説明します。 Rでも既存の関数を利用して、制約条件付き最適化問題を解くことができます。
最適化 (研究者向けの解説)
最適化 最適化とは、与えられた条件の中で、いろいろな選択肢の中から一番良いものを選ぶ問題の総称です。問題は数理的に与えて、数理的な方法で解きます。具体的には、n次元の実数ベクトル x (n個の数字の組：変数といいます)で、与えられた不等式・論理式など条件を全て満たすものの中で、ある、関数 f(x) (目的関数といいます)を最大にするようなものを求める、という問題です。世の中、数字で与えられるものばかりではない、とは思いますが、例えば、距離や、値段、時間などは数値で表せますし、ある事柄をやる／やらない、物を買う／買わないなどの選択も、0,1 の数字で表すことができます。 簡単な例を見てみましょう。今、あるとても広い長方形の土地のどこかに、ごみ処理場を作る計画があるとします。ただ、場所は決まっていません。土地の中には n 軒の家があります。どの家の人も、近くにごみ処理場があるといやなので、なる
計算量理論 - PukiWiki
と定義する．このとき，と なる のうちより良い方の解を選ぶ．（どちらも実行可能解であることに注意．） 計算時間 ソートにかかる時間，条件を満たすを求めるためにかかるので，合わせてである． 多項式時間． 近似値比 との二つの解の和は明らかに最適解以上のものとなっているので，近似値比はである． KNAPSACK問題はFPTASである． 近似値比アルゴリズムが存在することを示せばよい． 具体的なアルゴリズム 2近似値比アルゴリズムによる解をとする． 与えられたに対して， と置く． 各要素についてと修正したinstanceについて動的計画法を用いて得られる解をとする． とを比べ，大きいほうを出力する．また，その解をとする． 実行時間 動的計画法による計算時間が支配的． ． 近似値比 最適解をと書くことにすると， 内容 † 計算量理論とは、計算の難しさの学問。 例）n都市TSP n頂点の
Programs
オリジナル・ソフトウエア 以下のプログラムは私（山田）が自分の教育・研究活動のために作ったものです。すべて標準的な ANSI C 言語で書かれていて、正常に動作する事が（一応）確認されています。参考になるものがあれば自由にダウンロードしてお使い下さい。ただし、計算結果については当方は一切責任を負いませんので悪しからず。また、プログラムは「わかりやすさ」に重点を置いて書かれているため、必ずしも効率の面では必ずしもお薦めでないものが混じっていますが、これも悪しからず。 グラフ・ネットワーク関係 プログラム 最短経路問題 Dijkstra 法のプログラムです 全域木問題 Kruscal 法のプログラムです 全域木問題 Prim 法のプログラムです 割り当て問題 n x n 問題をハンガリー法で解きます （このプログラムの実行にはメルセンヌ・ツイスタ が必要です） 割り当て問題（画面表示版） （こ
NP完全問題 - Wikipedia
NP完全（な）問題（エヌピーかんぜん（な）もんだい、英: NP-complete problem）とは、(1) クラスNP（英: Non-deterministic Polynomial）に属する決定問題（言語）で、かつ (2) クラスNPに属する任意の問題から多項式時間還元（帰着）可能なもののことである。条件 (2) を満たす場合は、問題の定義が条件 (1) を満たさない場合にも、NP困難な問題とよびその計算量的な困難性を特徴づけている。多項式時間還元の推移性から、クラスNPに属する問題で、ある一つのNP完全問題から多項式時間還元可能なものも、またNP完全である。現在発見されているNP完全問題の証明の多くはこの推移性によって充足可能性問題などから導かれている。充足可能性問題がNP完全であることは1971年、スティーブン・クックによって証明され[1]、R. M. カープの定義した多項式時間
NP困難 - Wikipedia
P、NP、NP完全、NP困難の相関を表すベン図 NP困難（エヌピーこんなん、英: NP-hard）とは計算量理論において、問題が「NPに属する任意の問題と比べて、少なくとも同等以上に難しい」ことである[1]。正確にいうと、ある問題 H がNP困難であるとは、「NPに属する任意の問題 L が H へ帰着可能である」と定義される。この「帰着」の定義として何を用いるかにより微妙に定義が異なることになるが、例えば多項式時間多対一帰着や多項式時間チューリング帰着を用いる。もしもあるNP困難問題を解ける多項式時間の機械が存在すれば、それを利用すればNPに属する任意の問題を多項式時間で解くことができる。 NP完全問題とは、NP困難であり、かつNPに属する問題である。これとは異なり、ある問題がNP困難であってもNPに属するとは限らない。NPは決定問題のクラスなのでNP完全もまた決定問題に限られるが、定義に
Knapsack problem - Wikipedia
Example of a one-dimensional (constraint) knapsack problem: which books should be chosen to maximize the amount of money while still keeping the overall weight under or equal to 15 kg? A multiple constrained problem could consider both the weight and volume of the books. (Solution: if any number of each book is available, then three yellow books and three grey books; if only the shown books are av
ナップサック問題 - Wikipedia
この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "ナップサック問題" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2016年9月) ナップサック問題 ナップサック問題（ナップサックもんだい、Knapsack problem）は、計算複雑性理論における計算の難しさの議論の対象となる問題の一つで、n 種類の品物（各々、価値 vi、重量 wi）が与えられたとき、重量の合計が W を超えない範囲で品物のいくつかをナップサックに入れて、その入れた品物の価値の合計を最大化するには入れる品物の組み合わせをどのように選べばよいか」という整数計画問題である。同じ種類の品物を1つまでしか入れられない場
ORWiki
OR学会50年の歴史の中で，OR事典の編纂・改訂は通算３度目となる．いろいろな理由からOR事典編集委員会は，「OR事典」をWebに公開するという手段をとることになった．前回はCDによる出版であった． 資料編だけは「OR事典」から切り離して，OR学会の通常のホームページの中に移すことになった．これは逆瀬川浩孝委員長のアイディアである。内容の性格上，資料追加も間違いの訂正も広報委員会の責任で簡単に出来るようになる． 前回までの学会の歴史資料はそのまま残してある．今回はデータ追加作業を基本に多少の資料追加を行った．前事務局長の藤木秀夫さんには，その後の学会活動全般にわたる記録をまとめて原稿を作成してもらった．学術会議関係も藤木さんが前回の形式に習って資料原稿を作成し，FMES会長の高橋幸雄さんに目を通していただいた． 各支部から増補追加の原稿が送られてきた．Webのサンプルを見てくださいと言って
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
エラー | 無料ウェブサービス XREA.COM
最適化ソフトとテスト問題集
ログイン - 機械学習の「朱鷺の杜Wiki」
http://www.na.cse.nagoya-u.ac.jp/~reiji/lect/alg99/sec10-2.html
Loading...
Dismissed site: www.nada.kth.se
http://wiki.livedoor.jp/tzik/d/%B7%D7%BB%BB%CE%CC%CD%FD%CF%C0