私は多くのアルゴリズムを経験しました。私は多くのプログラミングの質問を解決し、おそらくブルートフォースから最高のものまで、単一の問題を解決するためのさまざまなアプローチを見つけました。
ブルートフォースアプローチでは解決できないが、より良いアプローチで解決できる問題があるかどうか疑問に思っていましたか?
3729 次
6 に答える
3
力ずくのアプローチでは解決できないが、もっと良いアプローチでは解決できる問題があるかどうか疑問に思いました。
はい。決定可能性を証明することは重要です。
1）平面性：
グラフが平面かどうかをテストするにはどうすればよいですか？単純に、グラフを描画する方法は無限にあるため、ブルートフォースを使用することはできません。
平面性の巧妙な基準が存在することがわかったら、アルゴリズムは簡単です。
2）プレスバーガー式：
プレスバーガー算術の数式は、数量詞∀、∃、加算+、定数（自然数）、および論理演算子を使用して作成されます。異なるものは許可されていません。数量詞は自然数の範囲です。
例：
∀n∃m（n = m + m）または（n = m + m + 1）
この式は、すべての整数が偶数または奇数であるという事実を表しています。それは本当です。
∃m∀n∃km+k= n
この式は、最大の自然数が存在するという事実を表しています。それは誤りです。
数式が真であるかどうかを判断するアルゴリズムはありますか？単純に、すべての自然数をチェックする必要があるため、ブルートフォースは機能しません。ただし、問題は決定可能です。
于 2012-08-02T22:08:15.493 に答える
3
それはcanの意味によって異なります。
解の数が有限であるほとんどすべての問題には、力ずくで解決する方法があります。十分な計算能力や時間があれば、そのソリューションを使用して解決できます。
一部の問題については、十分な計算能力や時間がないため、ブルート フォース ソリューションを使用することは事実上不可能です。
Euler Projectの特定のケースでは、ブルート フォース ソリューションがあまりにも多くの計算能力および/または時間を必要とするように、多くの問題が設計されています。たとえば、問題は、現在利用可能なコンピューターを考慮して計算に 100 万年かかるように設計されている可能性があり、解決策が有用になるのに十分な時間で問題を解決するには、別のアプローチを使用する必要があります。
于 2012-08-02T21:20:26.280 に答える
0
離散空間で定義された問題を解いていて、空でない解のセットが存在する限り、明らかにそうです。
次の点を考慮してください。
于 2012-08-02T21:39:16.553 に答える
0
あまり。ブルートフォースの概念そのものが、すべてを試すことを意味します。したがって、一致するように何かを作成および再作成できる場合、可能なすべての順列を試すと、別の一致が見つかります。
于 2012-08-02T21:11:39.843 に答える
0
力ずくで解決できない問題はたくさんあります。
たとえば、停止問題を見てください。プログラムと入力を受け取り、その入力で実行したときにプログラムが最終的に停止する場合は「True」を返し、そうでない場合は「False」を返すアルゴリズムを設計する必要があります。
アルゴリズムは最終的に停止し、「False」または「True」を伝える必要があります。
言うまでもありませんが、そのようなアルゴリズムはありません。
編集：
「解く」と言うときは、計算的に解くことを意味していると思います。
はいと思います - 次の問題を見てください。
ループが与えられます：
一方 (x < m)
x--
そして定数mとk。そして、存在する場合はループが終了する < k の最小 x を返す必要があり、そうでない場合は "False" を返す必要があります。ブルート フォース アルゴリズムを使用すると、k = 999 および m = 1000 の場合、x = 999 から開始し (x < k = 999 という要求があるため)、永遠に行き詰まります。
より良いアプローチを使用できます-m <kの場合、mを返します。それ以外の場合は、"False" を返します。
于 2012-08-02T21:48:33.433 に答える