現実の生活の中で多くの問題があり、人造悪い解決策が、コンピュータの速度の使用は、エラーのない特性は、これらの問題を解決するために非常に便利なことができ、次の簡単に言うと、私はプログラミングでは、一般的なアイデアのいくつかの実際の問題を解決するために、マスターを無視することができ、私はまた、何気なく書いて退屈しています。
1.最適解を列挙する場合
一見、厄介に思える問題がいくつもありますが、注意深く分析すれば、いくつかの明白な結論を導き出すことができます。
例えば、次のような問題です：平面上に何千もの点がありますが、半径Rの円がカバーできる点は最大でいくつありますか？
多くのプログラマーが最も激しく思い浮かべるのは列挙であり、もちろん、コンピュータの列挙を使うことは、特にデータが非常に小さい場合には、確かに非常に効果的な方法ですが、上記の質問の場合、どのように列挙するのですか？円の位置を列挙しますか？
確かに円の位置を列挙することは可能で、何も考えなければ、2次元直交系の各点を円の中心として列挙し、その円がいくつの円をカバーするかを決定し、最大の結果を取ることができます。これは確かに方法ですが、どのように中心を列挙するのですか？円の中心の位置は連続的なもので、必ずしも点全体のような離散的なものではありません。 データ量が少なく、精度の要求が高くない場合、円の中心の位置を直接列挙するのは良い方法ではありません。 しかし、少し分析すれば、最適解の円、つまり、最も多くの点をカバーするR半径の円は、円上に2点を持たなければならないと結論づけることができます。
上図のように、最適解が円上に2点を持たないと仮定すると、円は微小な並進操作で平面上の2点に接するようにすることができ、庭の点数は減らず、その結果は円上に2点がない場合よりも悪くなりません。"何点をカバーするか "の最大値を求めるだけなので、任意の2点まで列挙することができ、半径Rのこの円の位置を決定し、何点をカバーできるかを判断します。これはO(n^3)のアルゴリズムで、1秒以内に結果が出るので、もうかなり効率的です。
そのため、どのようなケースが最適解を満たすかを分析し、コンピュータの特性を利用して最適解を列挙し、問題を逆解決することが何度も可能です。
2.ダイナミックな企画アイデア
動的計画法はとても効率的な方法で、これはプログラミングの中ではとてもとても一般的なことです。探索と動的計画法を知らなければ、基本的にプログラミングの方法を知らないことになります。大きな問題を同じ種類のいくつかの小さな問題に分割し、小さな問題は問題が一目でわかるほど小さくなるまで分割することができれば、小さな問題を先に解いて保存し、それから大きな問題を解くことができます。 この例はたくさんあり、再帰的な書き方やメモ化された深さ探索を使えば、このアイデアを実装するのは簡単です。 他にも，最長昇順部分問題，ナップザック問題など，古典的な動的計画問題はたくさんあります．
もしまだダイナミック・プログラミングを理解していない学生がいたら、次のCコードを見てください。
/******************
Author: lxgsbqylbk
Function : Get the factorial of integer n (n>=0) nの階乗を求めよ
n!=
1 n==0
n*(n-1)! n>0
****/
//動的計画法を完成させるための一般的な考え方は2つある。
//1.ディープ・サーチを記憶する
int fac[MAXN];
int F(int n)
{
return n?(fac[n]?fac[n]:fac[n]=n*F(n-1)):1;
}
//2.方向性を練ってから解く
int fac[MAXN];
for(fac[0]=1,i=1;i<=N;i++)
{
fac[i]=fac[i-1]*i;
}
3.アイデアの分類
並べ替えは非常に重要なステップです。前処理で並べ替えを行うことで、より簡単に解くことができる問題はたくさんあります。例えば、額面の異なる紙幣がたくさんあり、m枚の紙幣を選んでその価値を最大にする場合、その一つの方法はもちろん、額面の大きいものから小さいものへと紙幣を並べ替え、m枚の紙幣からお金を取り出すことです。 多くの場合、上記の動的計画法では、変数を操作する前に一定の規則に従って並べ替える必要があり、問題は一般に一定の順序が確立された後の方が解きやすくなります。
並べ替えというと、貪欲アルゴリズムの話になります。 貪欲アルゴリズムとは、大きな問題に対して最適解をとり、大きな問題を構成する小さな問題の中からその都度最適解をとることで、大きな問題が最適な状態になるようにするものですが、もちろんこの戦略が正しいことが証明されないと実現できません。 貪欲な処理の多くは、有名なクルスカル最小スパニングツリーアルゴリズムのように、最初に辺をソートするソート処理が先行するため、ソートは様々な言語のライブラリに含まれるほど重要な処理であり、ユーザが便利に呼び出せるようになっています。
4.2点、3点
数日前、ある学生が、今、8Kは二項対立を書けるプログラマーを採用できないでいる、と言っているのを聞きました。もちろん、この文章は誇張の要素がありますが、^-^ プログラミングでよく使われる二項対立を参照してください。
実際には、これは列挙アルゴリズムに並置することができます、それは、この列挙は非常に効率的であることだけで、SQLデータベースなどの多くの場所は、ルックアップメソッド内のバイセクション、バイセクション列挙、トリセクション列挙は、時間の複雑さは対数であり、プログラミングでは非常に効率的なアルゴリズムです。
二等分する条件：データの単調性。 例えば、小さいものから大きいものへと並べられた数の集合の中から数xを求めます。 これは列挙を二分することになります。毎回、範囲を半分にすることができるので、データがどんなに大きくても、int型を越えていても、すぐに見つけることができます。
例えば、区間[0,100]における関数8*x^4 + 7*x^3 + 2*x^2 + 3*x + 6 == Kの解を求めます。この関数は[0,100]において単調増加するので、2分法が良い選択です。
三分法の条件：データの凸性。
例えば、区間[0,100]における関数 6*x^7 + 8*x^6 + 7*x^3 + 5*x^2 - K*x の最小値を求めます。
この関数は、[0,100]で減少し、その後増加する関数なので、3分の1ずつ解きます。
もちろん、この問題は、関数は、0にその位置の二等分することができる導出される、二等分するために変換することができ、これは高度な数学が含まれ、繰り返すことはできません。
特定のプロセスは、一般的にも操作を並べ替える必要がある2つの点の前に情報に行くことができます。
5.ランダム化アルゴリズム
解決すべき問題にアイデアがなく、列挙されたデータの量が多すぎる場合、多くの場合、ランダム化されたアルゴリズムが使用されます。
一般的な確率的アルゴリズム、アントコロニーアルゴリズム、シミュレーテッドアニーリングなど。
シミュレーテッド・アニーリングについて
例えば、平面上に何千もの点があり、すべての点をカバーする円を平面上で選びたい場合、「最小半径は？
最初にこの問題に取り組んだとき、ひとつのアプローチが頭に浮かびました：
1に基づくと、やはり最適なケースの円はその上に2つの点を持たなければならないと結論づけることができ、そうでなければ、円はその上に2つの点を持つように収縮と平行移動を続けることができ、結果はさらに良くなります。
ということは、任意の2点を列挙すると、円の中心はこの2点のミッドプラムライン上になければなりません。 そして、この円の中心がミッドプラムライン上を移動しており、条件を満たしていればすべての点を囲んでいると仮定します。
そうすると、円は半径が小さくなり、動くにつれて大きくなるのでしょう。 半径関数は超凸なので、上記の3つの部分からなる列挙がここで使えます。
私はこの方法の正しさはさておき、まず、複雑さは少し、2つのポイントを列挙し、次に3つのポイントです。
これがシミュレーテッド・アニーリングの考え方です。 この理論によると、ある位置posがあると仮定して、最適解の中心がposより上にある場合、posより下を探索すると、円の中心はposの位置より大きくなるはずです。
この理論に従えば、平面上に多数のランダムな点を生成し、ある点に到達するまで貪欲にランダムに移動させて停止させることが可能です。このアルゴリズムの時間複雑度はO(n)です。
6.最終号の変換
このようなときは、問題を一般的なモデルに変換し、一般的なモデルと古典的なアルゴリズムを使って問題を解くことを試みます。
最も一般的なのは、現実の問題をフローネットワークや二部グラフに変換するグラフ理論的な問題です。
