Warning : Undefined variable $type in /home/users/1/sub.jp-asate/web/wiki/extensions/HeadScript/HeadScript.php on line 3 Warning : "continue" targeting switch is equivalent to "break". Did you mean to use "continue 2"? in /home/users/1/sub.jp-asate/web/wiki/includes/json/FormatJson.php on line 297 Warning : Trying to access array offset on value of type bool in /home/users/1/sub.jp-asate/web/wiki/includes/Setup.php on line 660 Warning : session_name(): Session name cannot be changed after headers have already been sent in /home/users/1/sub.jp-asate/web/wiki/includes/Setup.php on line 834 Warning : ini_set(): Session ini settings cannot be changed after headers have already been sent in /home/users/1/sub.jp-asate/web/wiki/includes/session/PHPSessionHandler.php on line 126 Warning : ini_set(): Session ini settings cannot be changed after headers have already been sent in /home/users/1/sub.jp-asate/web/wiki/includes/session/PHPSessionHandler.php on line 127 Warning : session_cache_limiter(): Session cache limiter cannot be changed after headers have already been sent in /home/users/1/sub.jp-asate/web/wiki/includes/session/PHPSessionHandler.php on line 133 Warning : session_set_save_handler(): Session save handler cannot be changed after headers have already been sent in /home/users/1/sub.jp-asate/web/wiki/includes/session/PHPSessionHandler.php on line 140 Warning : "continue" targeting switch is equivalent to "break". Did you mean to use "continue 2"? in /home/users/1/sub.jp-asate/web/wiki/languages/LanguageConverter.php on line 773 Warning : Cannot modify header information - headers already sent by (output started at /home/users/1/sub.jp-asate/web/wiki/extensions/HeadScript/HeadScript.php:3) in /home/users/1/sub.jp-asate/web/wiki/includes/Feed.php on line 294 Warning : Cannot modify header information - headers already sent by (output started at /home/users/1/sub.jp-asate/web/wiki/extensions/HeadScript/HeadScript.php:3) in /home/users/1/sub.jp-asate/web/wiki/includes/Feed.php on line 300 Warning : Cannot modify header information - headers already sent by (output started at /home/users/1/sub.jp-asate/web/wiki/extensions/HeadScript/HeadScript.php:3) in /home/users/1/sub.jp-asate/web/wiki/includes/WebResponse.php on line 46 Warning : Cannot modify header information - headers already sent by (output started at /home/users/1/sub.jp-asate/web/wiki/extensions/HeadScript/HeadScript.php:3) in /home/users/1/sub.jp-asate/web/wiki/includes/WebResponse.php on line 46 Warning : Cannot modify header information - headers already sent by (output started at /home/users/1/sub.jp-asate/web/wiki/extensions/HeadScript/HeadScript.php:3) in /home/users/1/sub.jp-asate/web/wiki/includes/WebResponse.php on line 46
https:///mymemo.xyz/wiki/api.php?action=feedcontributions&feedformat=atom&user=117.55.68.141
miniwiki - 利用者の投稿記録 [ja]
2024-06-04T20:51:17Z
利用者の投稿記録
MediaWiki 1.31.0
制約充足問題
2014-08-22T21:58:59Z
<p>117.55.68.141: /* 外部リンク */</p>
<hr />
<div>'''制約充足問題'''（せいやくじゅうそくもんだい、{{lang-en-short|Constraint satisfaction problem, CSP}}）は、複数の制約条件を満たすオブジェクトや状態を見つけるという[[数学]]の問題を指す。CSPは特に[[人工知能]]や[[オペレーションズ・リサーチ]]で研究されている。多くのCSPでは、それなりの時間内に解くのに[[ヒューリスティクス]]と[[組合せ最適化]]手法を組み合わせる必要がある。<br />
<br />
制約充足問題の具体例:<br />
* [[エイト・クイーン]]<br />
* [[四色定理|四色問題]]<br />
* [[数独]]<br />
* [[充足可能性問題]]<br />
<br />
制約充足問題を解く[[アルゴリズム]]としては、[[AC-3アルゴリズム]]、[[バックトラッキング]]、[[制約違反最小化]]などがある。<br />
<!-- 計算複雑性理論との関係を述べた部分があったが、通常 CSP は NP-完全とされているのに対して、どうもPでもNP完全でもない場合があると言っているようなので真偽が判断できないため、省略（訳者） --><br />
<br />
== 関連項目 ==<br />
* [[制約充足]]<br />
* [[宣言型プログラミング]]<br />
* [[制約プログラミング]]<br />
* [[DisCSP]]（分散制約充足問題）<br />
<br />
== 参考文献 ==<br />
*{{cite book | first=Edward | last=Tsang | title=Foundations of Constraint Satisfaction | date=1993年 | publisher=Academic Press | url=http://www.bracil.net/edward/FCS.html |id=ISBN 0-12-701610-4}}<br />
*{{cite book | first=Rina | last=Dechter | title=Constraint processing | publisher=Morgan Kaufmann | date=2003年 | url=http://www.ics.uci.edu/~dechter/books/index.html |id=ISBN 1-55860-890-7}}<br />
*{{cite book | first=Krzysztof | last=Apt | title=Principles of constraint programming | publisher=Cambridge University Press | date=2003年 |id=ISBN 0-521-82583-0}}<br />
<br />
== 外部リンク ==<br />
* Tomás Feder, [http://theory.stanford.edu/~tomas/consmod.pdf ''Constraint satisfaction: a personal perspective'']<br />
* [http://4c.ucc.ie/web/archive/index.jsp Constraints archive]<br />
* [http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/benchmarks.htm Forced Satisfiable CSP Benchmarks of Model RB]<br />
* [http://www.cril.univ-artois.fr/~lecoutre/research/benchmarks/benchmarks.html Benchmarks -- XML representation of CSP instances]<br />
<br />
{{DEFAULTSORT:せいやくしゆうそくもんたい}}<br />
[[Category:アルゴリズム]]<br />
[[Category:人工知能]]<br />
[[Category:オペレーションズリサーチ]]<br />
[[Category:数学の問題]]<br />
[[Category:数学に関する記事]]</div>
117.55.68.141
ビンパッキング問題
2014-08-22T21:55:10Z
<p>117.55.68.141: /* 関連項目 */</p>
<hr />
<div>'''ビンパッキング問題'''（ビンパッキングもんだい）とは、[[離散数学]]の[[組合せ数学|組合せ論]]の中の[[NP困難]]問題で、与えられた「荷物（重さや個数がついている）」をつめる「箱（ビンやコンテナなど）」の最小数を見つけるものである。問題を解くためにビン型（筒状型）の模型を使うのでこのように呼ばれる。<br />
<br />
様々な解決方法（[[アルゴリズム]]）が考案されているが、あらゆる場合の箱の最小数を効率的に見つけることができるような万能なアルゴリズムはない（NP困難問題）。<br />
<br />
== 単純な例 == <br />
8台の新車をトラックで移動する。新車の重量はそれぞれ100キログラム単位で 33, 61, 58, 41, 50, 21, 60, 64 である。各トラックが、12,000 kg の重量まで運べるとき、全ての新車を一度に移動させるのに必要とされるトラックの最小数は、いくつであるか考える。まず、トラックを容量120のビンとし、新車は、そのビンに詰める荷物とする。具体的に調べることによって必要な箱の最小数を見つけることができるが、ここでは決められた手順（アルゴリズム）を使って解いていく。2つのアルゴリズムを紹介する。<br />
<br />
'''アルゴリズムA'''<br />
# 荷物を空いている容量が最大のビンに詰める。<br />
# どのビンにも荷物が入らないとき、新しいビンに詰める。<br />
ビン1 ビン2 ビン3 ビン4 ビン5<br />
|00| |00| |00| |00| |00|<br />
|61| |41| |21| |00| |00|<br />
|33| |58| |50| |60| |64|<br />
この方法だと、ビンは5個（つまりトラック5台）必要となる。<br />
<br />
'''アルゴリズムB'''<br />
# 荷物を空いている容量が最小のビンに詰める。<br />
# どのビンにも荷物が入らないとき、新しいビンに詰める。<br />
ビン1 ビン2 ビン3 ビン4<br />
|00| |21| |00| |00|<br />
|61| |41| |60| |00|<br />
|33| |58| |50| |64|<br />
この方法だと、必要なビンは4個（トラック4台）である。<br />
<br />
2つを比べるとAよりもBの方が良いアルゴリズムである。実際にはもっと優良なアルゴリズムがあるかもしれない。<br />
<br />
== 関連項目 ==<br />
* [[ナップサック問題]]<br />
* [[部分和問題]]<br />
* [[パッキング問題]]<br />
<br />
{{DEFAULTSORT:ひんはつきんくもんたい}}<br />
{{Math-stub}}<br />
<br />
[[Category:離散数学]]<br />
[[Category:数学の問題]]<br />
[[Category:数学に関する記事]]</div>
117.55.68.141
部分和問題
2014-08-22T21:51:06Z
<p>117.55.68.141: /* 問題例 */</p>
<hr />
<div>'''部分和問題'''（ぶぶんわもんだい）は、[[計算複雑性理論]]・[[暗号理論]]における問題で、与えられた ''n'' 個の[[整数]] ''a''<sub>1</sub>,...,''a''<sub>''n''</sub> から部分集合をうまく選んで、その集合内の数の和が与えられた数 ''N'' に等しくなるようにできるかどうかを[[判定問題|判定する問題]]である。[[NP完全]]であることが知られている。<br />
<br />
この問題は、'''分割問題''' (Number Partitioning) の一般形でもある。分割問題とは、与えられた ''n'' 個の整数 ''a''<sub>1</sub>,...,''a''<sub>''n''</sub> を二つの集合に分け、各々の集合内の数の和がもう一方の集合内の数の和と等しくなるようにできるかどうかを判定する問題である。この問題も、NP完全であることが示されている。<br />
<br />
部分和問題は、[[ナップサック問題]]に含まれるため、[[動的計画法]]等の手法で解くことができる。（詳しくは、ナップサック問題の項を参照。）<br />
<br />
==問題例==<br />
*問題1: {1,3,7,10,13} の部分和で、和が 21 になるものは存在するか？<br />
**答え: 存在する。{1,7,13}<br />
*問題2: {2,4,6,8,10} の部分和で、和が 19 になるものは存在するか？<br />
**答え: 存在しない。（偶数の和は偶数にしかならないから。）<br />
<br />
{{デフォルトソート:ふふんわもんたい}}<br />
[[category:計算複雑性理論]]<br />
[[category:群論]]<br />
[[Category:数学の問題]]<br />
[[Category:数学に関する記事]]</div>
117.55.68.141
最小頂点被覆問題
2014-08-22T21:42:07Z
<p>117.55.68.141: /* 外部リンク */</p>
<hr />
<div>'''最小頂点被覆問題'''（さいしょうちょうてんひふくもんだい）は、[[計算複雑性理論]]における[[NP困難]]な問題の一つ。<br />
<br />
問題: [[グラフ理論|グラフ]] ''G''(''V'', ''E'') の各枝 ''e'' について端点のいずれか少なくとも一方が、''V''&prime; に含まれるような ''V'' の部分集合 ''V''&prime; のうち、|''V''&prime;| が最小になるものを求めよ<br />
<br />
この問題の最適解を求めるのは、NP困難なため、決定性の[[多項式時間アルゴリズム]]は存在しないと考えられている。[[近似アルゴリズム]]に関して言えば、近似度2の[[貪欲アルゴリズム]]が存在することが知られているが、任意の &epsilon; &gt; 0 について、近似度 2 - &epsilon; の近似度を達成するアルゴリズムも存在しないだろうと考えられている。[[2005年]]現在の最良の近似度の下限は、<math>10\sqrt{5}-21 (>1.36)</math> である。<br />
<br />
== 関連項目 ==<br />
* [[頂点被覆]]<br />
* [[最適化問題]]<br />
* [[完全被覆問題]]<br />
* [[最大独立集合問題]]<br />
<br />
== 外部リンク ==<br />
* [http://www.nada.kth.se/~viggo/wwwcompendium/node10.html MINIMUM VERTEX COVER]<br />
<br />
{{DEFAULTSORT:さいしようちようてんひふくもんたい}}<br />
[[Category:グラフ理論]]<br />
[[Category:計算複雑性理論]]<br />
[[Category:数学の問題]]<br />
[[Category:数学に関する記事]]<br />
<br />
[[en:Covering (graph theory)]]<br />
[[es:Covering]]<br />
[[he:כיסוי (תורת הגרפים)]]</div>
117.55.68.141
最大独立集合問題
2014-08-22T21:39:27Z
<p>117.55.68.141: /* 外部リンク */</p>
<hr />
<div>'''最大独立集合問題'''（さいだいどくりつしゅうごうもんだい）は、[[グラフ理論]]において、与えられたグラフ G(V,E) に対して、頂点集合 V'⊆V のうち V' 内の頂点間に枝が存在しないようなもの（[[独立集合]]）で大きさが最大のものを求める問題。'''最大安定集合問題'''とも言う。この問題は、[[NP困難]]であることが知られている。<br />
<br />
この問題は、[[補グラフ]]に対する[[最大クリーク問題]]と等価である。また、独立集合に含まれない頂点は[[頂点被覆]]をなし、逆も成り立つので、[[最小頂点被覆問題]]とも等価である。<br />
<br />
[[近似アルゴリズム]]についても、基本的に最大クリーク問題と同じである。グラフの頂点数を n とするとき、[[近似度]] O(n / (log n)^2) が達成されている。また、P=[[NP]] が成り立たないとき、任意の ε>0 について、近似度 n^(1/2-ε) の近似アルゴリズムが存在しないことが示されている。NP=[[ZPP]]が成り立たない場合、近似度 n^(1-ε) の近似アルゴリズムが存在しないことも示されている。<br />
<br />
グラフの最大[[次数 (グラフ理論)|次数]]を制限した場合は、以下の結果が知られている。<br />
*次数2: [[多項式時間アルゴリズム]]が存在<br />
*次数3: 1.2-近似アルゴリズムが存在。近似度の下限 1.0071<br />
*次数4: 1.4-近似アルゴリズムが存在。近似度の下限 1.0136<br />
*次数5: 1.6-近似アルゴリズムが存在。近似度の下限 1.0149<br />
<br />
==関連項目==<br />
*[[NP困難]]<br />
<br />
==外部リンク==<br />
*MAXIMUM INDEPENDENT SET [http://www.nada.kth.se/~viggo/wwwcompendium/node34.html]<br />
<br />
{{デフォルトソート:さいたいとくりつしゆうこうもんたい}}<br />
[[Category:グラフ理論]]<br />
[[Category:数学の問題]]<br />
[[Category:数学に関する記事]]<br />
<br />
[[en:Independent set problem]]</div>
117.55.68.141
関数問題
2014-08-22T21:35:51Z
<p>117.55.68.141: /* 関連項目 */</p>
<hr />
<div>'''関数問題'''（かんすうもんだい、function problem）とは、[[計算量理論]]において、各入力に対してある出力を返す形式の問題をいう。'''評価問題'''とも呼ばれる。文字列上の写像<math>\Sigma ^* \to \Sigma ^*</math>で表される。主に[[判定問題]]（関数問題のうち出力が<math>\{0, 1\}</math>であるようなもの）と対比して用いられることが多い。<br />
<br />
== 関数問題の主なクラス ==<br />
; FP (Function P, P Search Problem)<br />
: 決定性[[チューリングマシン]]により多項式時間で解かれる関数問題のクラス。<br />
; FNP (Function NP, NP Search Problem)<br />
: 非決定性チューリングマシンにより多項式時間で解かれる関数問題のクラス。<br />
; TFP (Total FP)<br />
: FPに属するもののうち必ず解が存在するような問題のクラス。<br />
; TFNP (Total FNP)<br />
: FNPに属するもののうち必ず解が存在するような問題のクラス。<br />
; PLS (Polynomial Local Search)<br />
; PPP (Polynomial Pigeonhole Principle)<br />
; PPA (Polynomial Parity Argument)<br />
; PPAD (Polynomial Parity Argument with Directed graph)<br />
: PLS以下、TFNPに含まれるより具体的な問題のクラス。<br />
<br />
== 主な関数問題 ==<br />
; 充足割り当て問題<br />
: 決定問題である[[充足可能性問題]]と対比してこう書かれる。<br />
; [[最大クリーク問題]]<br />
; [[巡回セールスマン問題]]<br />
<br />
== 関連項目 ==<br />
*[[計算複雑性理論]]<br />
*[[最適化問題]]<br />
<br />
{{DEFAULTSORT:かんすうもんたい}}<br />
[[Category:計算複雑性理論]]<br />
[[Category:数学の問題]]<br />
[[Category:数学に関する記事]]</div>
117.55.68.141
Warning : Cannot modify header information - headers already sent by (output started at /home/users/1/sub.jp-asate/web/wiki/extensions/HeadScript/HeadScript.php:3) in /home/users/1/sub.jp-asate/web/wiki/includes/WebResponse.php on line 46