オンラインで検索した限り、計算に時間がかかるために実際には解決できないアルゴリズムの例を見つけることができません。
アルファ ケンタウリへの旅でロケット船の近くを通過する各星の数、サイズ、位置を数えることなどの例を考えようとしていました。これは良い例でしょうか？つまり、星系は 26 兆マイル近く離れています。
編集: 私は Big-O と Little-O 表記法に関する短いプレゼンテーションを行っており、問題の解決策が実際には解決可能である理由について、通常とは異なることを考えたかったのですが、原理的には解決できない可能性があります。計算に非常に長い時間がかかるため、Big-O を使用して見積もりを作成する理由です。星を選びたかったのは、他の科目よりも面白そうだからです。
ありがとう！
巡回セールスマン問題のような NP 困難な問題を調べる必要があります。これらは、さまざまな戦略で「解決」できるため、優れた教育の例であり、私たちはまだそれらに取り組んでいます.
あなたが説明したように、正しい答えを保証するアルゴリズムは、多くの場合、リソースを大量に消費して実際に実装することはできません。Big O のおかげで、適切なサイズの入力に対して O((n^2)*(2^n)) をマシンで実行するのは現実的ではないことがわかりました。
パフォーマンスが向上するアルゴリズムで妥協することを余儀なくされていますが、最良または正しい結果が得られない場合があります。これらのアルゴリズムの妥協は、多くの関連性のある実際の例で見ることができます.1 つの巧妙なケースは、50 の USA ランドマークのツアーを生成しています.
2009 年の最先端のアルゴリズムでは、RSA-768 を因数分解するのに 2 年かかりました。この RSA-768の 10 進数字は「わずか」232 です。これは、多数のコンピューターを並行して使用することによって行われました。
617 桁のRSA 2048を因数分解するのにかかる時間を推測できます。
あなたが本当に探すべきことは、アルゴリズムの複雑さではなく、根底にある問題の複雑さです。たとえば、可能なすべてのO(n!)順序を反復するなど、ソートに非常に非効率的なアルゴリズムを使用できますが、実際にはソートに時間がかかるという意味ではありません。 .
最も基本的な文字列の問題の 1 つを考えてみましょう長さ の 2 つの文字列の最長共通部分n列。
O(n^2)この問題は、動的計画法を使用することで解決できることが知られています。一方、問題の一般的な例では、どのアルゴリズムでも操作が必要であることも証明されています (いくつΩ(n^2)かの特殊なケースでは、より高速なアルゴリズムが可能です)。
したがって、数百万文字の文字列 (現代のコンピューティングではそれほど大きな問題ではありません) のこの問題の一般的なインスタンスを解決したい場合、実際には、どのアルゴリズムでも10^12操作に比例して時間がかかります。実際、計算生物学では、DNA シーケンスの最も長い共通部分シーケンスを見つける問題が非常に重要であり、これらのシーケンスが非常に長い場合、それはあなたが求めた現実世界の問題の良い例です。
ドイツのハッカーが NSA のサーバーにログオンして、核ミサイル発射コードを見つけようとしています。彼は、すべての NSA パスワードが少なくとも 16 文字でなければならないこと、管理者パスワードが毎日深夜にランダムに生成されること、およびすべての ASCII を含めることができることを知っています。第三次世界大戦が始まるまであと26日。
彼は世界を救おうとするべきですか？または休暇に行きます。大きなO表記だけが教えてくれます。
この例が「興味深い」ものであったことを願っています。
線形の複雑さ (O(n) 時間) のように見えるため、問題は驚くべきものではありません。旅行の長さを2倍にした場合、プログラムの実行にかかる時間は2倍だけになります。それでも、巡回セールスマン問題のような指数関数的な解の問題を探しているだけで、都市の数が増えるとすぐに事実上解けなくなります。詳細については、 Time Complexityを参照してください。
見てみることができるもう 1 つの興味深い点は、停止問題です。