局所探索法 - Wikipedia
局所探索法（きょくしょたんさくほう、英: local search）や逐次改善法（ちくじかいぜんほう、英: iterative improvement）や近傍探索法（きんぼうたんさくほう）は、探索アルゴリズムの一種である。 局所探索法とは近似アルゴリズムの中でも最も単純なアルゴリズムの枠組みの一つである。広義には後述する手法の枠組みを持つアルゴリズムの総称として使われており、狭義には山登り法の意味で使われている。今日のメタヒューリスティクスの多くの手法がこの枠組みを使用している。 「局所探索法」という言葉は主に探索アルゴリズムに対しての言葉であり、数値解析の分野に於いては「反復法」という言葉が用いられる。両者の違いとしては反復法は対象となる関数の連続性や1階微分方程式などが解っていることが前提の場合が多く、また求める解も最適解を要求されることが多いのに対し、局所探索法では離散的な関数や関数
焼きなまし法 - Wikipedia
この項目では、確率的メタアルゴリズムについて説明しています。金属の熱処理については「焼きなまし」をご覧ください。 焼きなまし法（やきなましほう、英: Simulated Annealing、SAと略記、疑似アニーリング法、擬似焼きなまし法、シミュレーティド・アニーリングともいう）は、大域的最適化問題への汎用の乱択アルゴリズムである。広大な探索空間内の与えられた関数の大域的最適解に対して、よい近似を与える。 S. Kirkpatrick、C. D. Gelatt、M. P. Vecchiらが1983年に考案し[1]、1985年に V. Cerny が再発見した[2]。 その名称は、金属工学における焼きなましから来ている。焼きなましは、金属材料を熱した後で徐々に冷やし、結晶を成長させてその欠陥を減らす作業である。熱によって原子は初期の位置（内部エネルギーがローカルな極小状態）から離され、よりエ
整数計画問題 - Wikipedia
英語版記事を日本語へ機械翻訳したバージョン（Google翻訳）。 万が一翻訳の手がかりとして機械翻訳を用いた場合、翻訳者は必ず翻訳元原文を参照して機械翻訳の誤りを訂正し、正確な翻訳にしなければなりません。これが成されていない場合、記事は削除の方針G-3に基づき、削除される可能性があります。 信頼性が低いまたは低品質な文章を翻訳しないでください。もし可能ならば、文章を他言語版記事に示された文献で正しいかどうかを確認してください。 履歴継承を行うため、要約欄に翻訳元となった記事のページ名・版について記述する必要があります。記述方法については、Wikipedia:翻訳のガイドライン#要約欄への記入を参照ください。 翻訳後、{{翻訳告知|en|Integer programming|…}}をノートに追加することもできます。 Wikipedia:翻訳のガイドラインに、より詳細な翻訳の手順・指針につい
ナップサック問題 - Wikipedia
この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "ナップサック問題" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2016年9月) ナップサック問題 ナップサック問題（ナップサックもんだい、英: Knapsack problem）は、計算複雑性理論における計算の難しさの議論の対象となる問題の一つで、n 種類の品物（各々、価値 vi、重量 wi）が与えられたとき、重量の合計が W を超えない範囲で品物のいくつかをナップサックに入れて、その入れた品物の価値の合計を最大化するには入れる品物の組み合わせをどのように選べばよいか」という整数計画問題である。同じ種類の品物を1つまでしか入れられ
P、NP、NP完全、NP困難…似て非なる階層構造 - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? コンピューターに問題を解かせるときに、それがどの程度の時間を消費するのかも大きな問題です。この観点から、問題はいくつかのパターンに区分されています。ただし、ややこしいです。 #おことわり なお、分かりやすさを優先して、厳密でない説明となっている部分があります。たとえば、チューリング完全性を前提に、チューリング機械で計算するものを、通常のコンピューターで計算するものとしています。 P ある判定問題（yes/noで答えられる問題）があって、それを解くことのできる多項式時間アルゴリズム（問題の規模に対して、計算時間が規模の多項式で表現される上
The Existence of the Tau One-Way Functions Class as a Proof that P != NP
We prove that P != NP by proving the existence of a class of functions we call Tau, each of whose members satisfies the conditions of one-way functions. Each member of Tau is a function computable in polynomial time, with negligible probability of finding its inverse by any polynomial probabilistic algorithm. We also prove that no polynomial-time algorithm exists to compute the inverse of members
近似アルゴリズム - Wikipedia
近似アルゴリズム（きんじアルゴリズム、英: approximation algorithm）とは、組合せ最適化問題の近似解を得るためのアルゴリズムを言う[1][2][3][4]。近似解とは、実行可能解（かつ問題の何らかの制約を満たす解）ではあるが、正解（厳密解）ではないものを言う。これは組合せ最適化問題の正解（すなわち最適解）であることが（厳密には）保証されないところの解を得るものである。なお、問題を変形した近似問題に対する正解を得るアルゴリズムも、元の問題に対する近似アルゴリズムと言える。 近似アルゴリズムの中でも、そのアルゴリズムの出力する解の目的関数値と最適解の目的関数値の比（近似度）がある範囲内に収まることが保証されているもののことを特に、精度保証付き近似アルゴリズムと呼ぶ。そのような保証のないアルゴリズムは発見的手法（ヒューリスティクス）と呼ばれる。前者と後者を区別し、前者のみを
「グラフ理論」と「組み合わせ最適化アルゴリズム」の教科書PDF。離散数学の入門用の教科書 - 主に言語とシステム開発に関して
講義ノートの目次へ グラフ理論・組み合わせ最適化の講義ノート。 ネットワーク（経路系）のアルゴリズムも含む。 大学の情報科学では，「離散数学」という分野だ。 以下に，「グラフ理論」と「組み合わせ最適化」の入門段階の要点を並べてみる。 最大フロー問題，最短経路問題，ダイクストラ法 オイラーグラフ，ハミルトングラフ 巡回セールスマン問題，郵便配達人問題 幅優先探索，深さ優先探索 グラフの連結性 有向グラフと無向グラフ，グラフの隣接行列，双対グラフ 辺彩色と面彩色，四色問題 マトロイド，離散マルコフ連鎖 これらの要点を独学で勉強しよう。 グラフがわかれば，グラフ上の最適化もわかる。 資料は，下記の分類にしたがって掲載した。 （１）日本語の教科書 （２）英語の教科書 （３）グラフ理論の応用に関する話題（組み合わせ最適化など離散数学） ※P/NPなどの計算量理論のノートはこちら。 （１）日本語の教科
組合せ最適化を使おう - Qiita
野菜の選び方はナップサック問題、乗り換え駅探索は、最短路問題といいます。典型問題は、よく研究もされているので、多くの場合、効率的な解法があります。あるいは、定式化がされているので、すぐ解くことができます。あとで、やってみましょう。ここで、あげている全ての典型問題の実行例は、典型問題と実行方法をご覧ください。 汎用問題 最近、私がやっているコンテナの仕事のお話しをします。 世界中の人たちが、いろいろなものを安く買えるのはコンテナ輸送のおかげです。中国などで生産したものを日本やアメリカやヨーロッパに、大量に安く運べるからです。でも、空のコンテナが、どんどんたまります。また中国に戻さないといけません。いつ、どこからどこに戻すかを決めるのが、最小費用流問題になります。ところが、最小費用流問題で表せない制約条件もあります。1 つが、カボタージュとよばれるものです。カボタージュというのは、国内のみの輸
メタヒューリスティクス - Wikipedia
この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "メタヒューリスティクス" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2023年8月) メタヒューリスティクスとは、組合せ最適化問題のアルゴリズムにおいて、特定の計算問題に依存しないヒューリスティクスのことである。 近年では、上記の定義から拡張され、特定の問題に依存しない、汎用性の高いヒューリスティクス全般を指すこともある。そのため、組合せ最適化問題のアルゴリズムに限らず、連続最適化問題に対するアルゴリズムも含む解釈も存在する。 通常ある問題に対しての「解法」が存在するとき、その解法が適用できる範囲はその問題に対してのみである。 と
貪欲法 - Wikipedia
この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "貪欲法" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2023年10月) 貪欲法（どんよくほう、英: greedy algorithm）は、アルゴリズムの一種、欲張り法（よくばりほう）、グリーディ算法（グリーディさんぽう）ともいう。 貪欲法は局所探索法と並んで近似アルゴリズムの最も基本的な考え方の一つである。 このアルゴリズムは問題の要素を複数の部分問題に分割し、それぞれを独立に評価を行い、評価値の高い順に取り込んでいくことで解を得るという方法である。動的計画法と異なり保持する状態は常に一つであり、一度選択した要素を再考する事は無い
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完全もまた決定問題に限られるが、定義に
組合せ最適化 - Wikipedia
この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "組合せ最適化" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2018年12月) 組合せ最適化（くみあわせさいてきか、英: combinatorial optimization、組み合わせ最適化、または組み合せ最適化とも表記される）は、応用数学や情報工学での組合せ論の最適化問題である。オペレーションズリサーチ、アルゴリズム理論、計算複雑性理論と関連していて、人工知能、数学、およびソフトウェア工学などの交差する位置にある。組合せ最適化では、厳密解が簡単に求まる場合もあれば、そうでない場合もある。厳密解を求めるのが難しいと思われる問題を解
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Multidimensional Knapsack Problem — Distributed
List of knapsack problems - Wikipedia
Amazon.co.jp: 今日から使える!組合せ最適化 離散問題ガイドブック (KS理工学専門書): 穴井宏和, 斉藤努: 本
Amazon.co.jp: 超高速グラフ列挙アルゴリズム:〈フカシギの数え方〉が拓く,組合せ問題への新アプローチ: ERATO 湊離散構造処理系プロジェクト (著), 湊真一 (編集): 本
https://pun6.com/Home/T/%E3%83%8B%E3%83%A5%E3%83%BC%E3%82%B9/j3558y7qsf2hfu7dpj7uswp4np82501d6ppyoa3a
離散数学 - Wikipedia
Amazon.co.jp: 技術者のための高等数学 6: E. クライツィグ (著), Kreyszig,Erwin (原名), 義保,田村 (翻訳): 本