実装が単純すぎる正当なユーティリティのアルゴリズムは何ですか？実行するにはあまりにも複雑な強力なアルゴリズム
私は明らかにしています：私は現在の漸近最適行列乗算アルゴリズムのようなアルゴリズムを探しているわけではありません。これは実装するのに合理的ですが、実際には役に立たない定数です。私は実際には価値があるかもしれないアルゴリズムを探していますが、はコード化するのが難しいです。は実装されておらず、非常に人工的な設定でしか実装されていないか、非常に特殊用途向けにしか実装されていません。
また、懐疑的だが実際のパフォーマンスは低い可能性のある実装不可能なアルゴリズムです。
私はあなたが求めていることは分かっていませんが、標準のNP不完全な計算は私が知る限り難しく、多くの点で実世界価値を持っています伝送回路、または回路基板を切断すること、または電源を電力網に配線することなどが考えられます。
は決してコードされているアルゴリズムはありませんが、コーディングするのは難しいです。
漸近的に最適ですが、コード化が非常に難しいアルゴリズムの例は、Chazelle's O(n) polygon triangulation algorithmです。 Skienna（The Algorithm Design Manualの著者）によると、「アルゴリズムは実装するのが全く望めない」
一般に、三角形分割や他の計算ジオメトリアルゴリズム（3D凸包やボロノイ図など）は、実装するのが簡単ではありません。トリッキーさの多くは、浮動小数点の不正確さを処理することになります。
私たちは「難しい」と「退屈」と同一視することができた場合は、その後、いくつかの証明には、ヘイルの証拠やケプラーの推測のような特殊な例非常に多く持つことができます。 Fejesによって提案されたアプローチに続きhttp://en.wikipedia.org/wiki/Kepler_conjecture
をToth（1953）、Thomas Hales、then 、University of Michigan、 最大密度が であり、全ての配置が の変数を最小化することによって150 の変数になることが判明した。 1992年には、彼の 大学院生サミュエル・ファーガソンによって助け、彼 は体系 5,000以上のセットのそれぞれに対して、この機能 の値にバインドされ 下を見つけるために、線形 プログラミング方法を適用 に研究プログラムに着手しました球の異なる構成。ケプラー予想が証明されるだろう 下限（関数の 値）の場合は、その後、 の一人一人 立方最密充填配置のための関数の値よりも大きかった これらの構成のために見つけることができます。 すべての場合の下限を見つけるには は約10万回の線形問題を解決することに関与します。 プログラミングの問題。
1996年に彼の プロジェクトの進捗状況を提示
は、ヘイルズは 終わりが見えていたと言ったが、それが完了するまでに、「 1年か2年」かかる場合があります。8月に 1998 Halesは、 という証明が完了したことを発表しました。その段階では、 は250ページのノートと3 ギガバイトのコンピュータプログラム、データ と結果で構成されています。障害物のある環境を介してロボットを移動させる
The Piano Mover's Problemは、数学的に定義され、既知の漸近的な複雑さを持つアルゴリズムを用いて解くことができます。
It is amazing that such algorithms exist;しかし、実装するのが非常に難しく、ほとんどのアプリケーションでは十分に効率的でないことも残念です。
ロボット動作計画上のすべての新しい論文がキャニーのロードマップアルゴリズムに言及していますが、それは今までに実装されている場合、それは疑問である：
no general implementation of Canny's algorithmは現時点で存在するように見えます。
+1 Chazelleを参照していますが、アルゴリズムにも不条理に大きな定数があることを覚えているようです。 – jprete
@jprete：うん、それはそうだと思います。実際にはより基本的なO（ng n）アルゴリズムよりも優れているとは思えません。 –