局所探索法 - 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:翻訳のガイドラインに、より詳細な翻訳の手順・指針につい
Optimized QuickSort — C Implementation (Non-Recursive)
Optimized QuickSort — C Implementation (Non-Recursive) August 2005, July 2007 NOTE 2010.02.25: I’ve received a few e-mails over the past few years telling me that my implementation of QuickSort may not be an improvement over the popular, recursive implementation. When I have time, I plan to perform my own comprehensive speed tests. Until then, don’t take the below information as gospel! Perform
)
Heuristic (computer science) - Wikipedia
In mathematical optimization and computer science, heuristic (from Greek εὑρίσκω "I find, discover"[1]) is a technique designed for problem solving more quickly when classic methods are too slow for finding an exact or approximate solution, or when classic methods fail to find any exact solution in a search space. This is achieved by trading optimality, completeness, accuracy, or precision for spe
決定問題 - Wikipedia
英語版記事を日本語へ機械翻訳したバージョン（Google翻訳）。 万が一翻訳の手がかりとして機械翻訳を用いた場合、翻訳者は必ず翻訳元原文を参照して機械翻訳の誤りを訂正し、正確な翻訳にしなければなりません。これが成されていない場合、記事は削除の方針G-3に基づき、削除される可能性があります。 信頼性が低いまたは低品質な文章を翻訳しないでください。もし可能ならば、文章を他言語版記事に示された文献で正しいかどうかを確認してください。 履歴継承を行うため、要約欄に翻訳元となった記事のページ名・版について記述する必要があります。記述方法については、Wikipedia:翻訳のガイドライン#要約欄への記入を参照ください。 翻訳後、{{翻訳告知|en|Decision problem|…}}をノートに追加することもできます。 Wikipedia:翻訳のガイドラインに、より詳細な翻訳の手順・指針についての説
P≠NP予想 - Wikipedia
出典は列挙するだけでなく、脚注などを用いてどの記述の情報源であるかを明記してください。 記事の信頼性向上にご協力をお願いいたします。（2013年2月） P≠NP予想（ピーエヌピー予想、英語: P is not NP）は、計算複雑性理論（計算量理論）における予想 (未解決問題) の1つであり、「クラスPとクラスNPが等しくない」すなわち「クラスNPの元だがクラスPの元でないような決定問題（判定問題）が存在する」というものである。P対NP問題（PたいNPもんだい、英: P versus NP）と呼ばれることもある。 理論計算機科学と現代数学上の未解決問題の中でも最も重要な問題の一つであり、2000年にクレイ数学研究所のミレニアム懸賞問題の一つとして、この問題に対して100万ドルの懸賞金がかけられた。 クラスPとは、決定性チューリングマシンにおいて、多項式時間で判定可能な問題のクラスであり、クラ
ハミルトン閉路問題 - Wikipedia
ハミルトン閉路問題（ハミルトンへいろもんだい）とは、与えられたグラフについて、全ての頂点を一度だけ通る閉路が存在するかどうか調べる問題である。名称はこの問題を最初に研究した数学者ウィリアム・ローワン・ハミルトンの名に因む。 与えられたグラフが有向グラフ（グラフ理論参照）の場合は有向ハミルトン閉路問題、無向グラフ（通常のグラフ）の場合は無向ハミルトン閉路問題と呼ばれる。 この問題はどちらも、NP完全問題であることが知られている。また、無向ハミルトン閉路問題は巡回セールスマン問題の特殊ケースでもある。 始点と終点が一致するという閉路の条件を取り去ると、ハミルトン路問題になる。
全域木を列挙する - Qiita
はじめに 約30年前に大学で習った、全域木の列挙アルゴリズムをPythonで実装してみましたので、ご紹介します。 全域木とは、元のグラフの全ての点を含む木のことです。 アルゴリズム グラフの式表現を求めて、式表現を展開して列挙します。 例えば、三角形のグラフで各辺をそれぞれa,b,cとすると、式表現は組(abc)となり、これを展開するとab/ac/bcとなります。 グラフの式表現は以下のように求められます。 辺の最初の式表現として、アルファベット1文字を持たせます。 グラフは、式表現を維持しながら辺または辺と点を削除できます。 グラフが1点になったときに式表現が求められます。 グラフGの式表現（Expr(G))は、任意の1つの辺Eを選んで以下のように変形できます。(標準ルール) Expr(G) ＝ 和(積(組(Expr(E)), Expr(GからEを削除)), 積(Expr(E), Exp
充足可能性問題のアルゴリズム
充足可能性問題（satisfiability problem）とは？ 充足可能性問題（以下，ＳＡＴ問題と略す）とは， 理論計算機科学で最も基本的で 重要な ＮＰ完全問題 の一つである． グラフ理論における 巡回セールスマン問題，頂点彩色問題，独立頂点集合問題， オペレーションズ・リサーチにおける整数計画問題， ゲーム・パズルにおける数独，テトリスなど， 実社会で遭遇する多くの（決定）問題がＮＰ完全問題である． その中でも， ＳＡＴ問題は，そのＮＰ完全性が示された最初の問題である． 以下の意味で， ＳＡＴ問題は，ＮＰ完全問題の根本である： すべてのＮＰ完全問題のＮＰ完全性は， （いくつかの例外を除いて） ＳＡＴ問題からの有限回の多項式時間還元を経て示された． 例えば， 教科書 [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
マルチキー・クイックソート(multikey-quicksort)で高速に文字列ソート - EchizenBlog-Zwei
一般にソートアルゴリズムの計算量はソート対象となるデータ数NについてO(N^2)とかO(NlogN)等で評価する。数値データのソートであれば特に問題はないのだが、文字列データの場合は一回の比較に対して文字列長Mに比例する計算量O(M)がかかってしまう。例えばクイックソートであればO(NlogN)ではなくO(MNlogN)となる。よってMが非常に大きい場合はソート性能の劣化を招く。 文字列ソートに付いてはBently&Sedgewickのマルチキー・クイックソート(multikey-quicksort)という改良版クイックソートが存在する。このソート法は、ある工夫によって一回の比較を文字列長Mに依存しない形で実現している。 例えば文字列appleとapplicationの比較について考える。 # 先頭の文字を比較 [a]pple = [a]pplication # 2文字目を比較 a[p]p
A Killer Adversary for Quicksort
SOFTWARE—PRACTICE AND EXPERIENCE, VOL. 29(0), 1–4 (0 1999) A Killer Adversary for Quicksort M. D. MCILROY Dartmouth College, Hanover, NH 03755, USA SUMMARY Quicksort can be made to go quadratic by constructing input on the fly in response to the sequence of items compared. The technique is illustrated by a specific adversary for the standard C qsort function. The general method works against any i
Why is quicksort better than other sorting algorithms in practice?
This is a repost of a question on cs.SE by Janoma. Full credits and spoils to him or cs.SE. In a standard algorithms course we are taught that quicksort is O(n log n) on average and O(n²) in the worst case. At the same time, other sorting algorithms are studied which are O(n log n) in the worst case (like mergesort and heapsort), and even linear time in the best case (like bubblesort) but with som
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
http://opensource.apple.com/source/emacs/emacs-41/emacs/lib-src/qsort.c?txt
Amazon.co.jp: 定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS): 近藤嘉雪: 本
Amazon.co.jp: 今日から使える!組合せ最適化 離散問題ガイドブック (KS理工学専門書): 穴井宏和, 斉藤努: 本
Amazon.co.jp: 超高速グラフ列挙アルゴリズム:〈フカシギの数え方〉が拓く,組合せ問題への新アプローチ: ERATO 湊離散構造処理系プロジェクト (著), 湊真一 (編集): 本
enrico-franchi.org