貪欲なアルゴリズム——アルゴリズムの総括(一)

2609 ワード

欲張りアルゴリズムはいくつかの基本アルゴリズムの中で比較的簡単なアルゴリズムであり、考え方も非常に簡単で、一歩ごとに現在から見れば最も良い選択をしている.すなわち,貪欲アルゴリズムは全体的な最適化から考慮されず,その選択はある意味での局所的な最適化にすぎない.基本的な考え方は問題のある初期解から徐々に与えられた目標に近づき、できるだけ早くより良い解を求めることである.あるアルゴリズムのあるステップに達してこれ以上前進できない場合、アルゴリズムは停止する.
この比較的簡単なアルゴリズムについて、私たちはまず彼の利害を理解しましょう.利益はもちろん簡単で、時間を節約して、使いやすいです.欲張り法に存在するいくつかの問題を見てみましょう.
貪欲法に存在する問題:1.求めた最後の解が最適であることは保証できない. 2. 最大または最小の問題を解くために使用できません. 3. いくつかの制約条件を満たす実行可能な解の範囲しか求められません
上記の問題は他のアルゴリズムで解決できますので、私のブログに引き続き注目してください.しかし、貪欲なアルゴリズムの使用を放棄することはありません.これはまさに敏捷な開発が提唱したもので、永遠に最も良いものはなく、最も適切なものしかない.私たちが欲張りアルゴリズムを選んだのは、彼が現在のニーズを満たすことができ、他のアルゴリズムよりも簡単だからです.

次に例題を見てください.
N個の商品があって、各商品の重量はWIで、価格は:PIで、1つのリュックサックがあって、最大Mの重量を詰めることができます.そのうち(0<=Iコードは次のとおりです.

#include<stdio.h>

//  :n              
//  :  p               
//  :  q               
static void sort(int n,float *p,float *q)
{
 int i;
 int j;
 for(i=0;i<n-1;i++)
 for(j=i+1;j<n;j++)
 if((*(p+i))/(*(q+i))<(*(p+j))/(*(q+j)))
 {
  float f;
  f=*(p+i);
  *(p+i)=*(p+j);
  *(p+j)=f;
  
  f=*(q+i);
  *(q+i)=*(q+j);
  *(q+j)=f;
 }
  
}
 

//  ：  x             
//  ：m         
//  :n               
static void knapsack(int n,float m,float *v,float *w,float *x)
{
 sort(n,v,w);
 int i;
 for(i=0;i<n;i++)
 {
  if(*(w+i)>m) 
   break;
  //        ， 1
  *(x+i)=1;
  //   ,       
  m-=*(w+i);
 }
 //                    ，     
 if(i<n)
  *(x+i)=m/(*(w+i));
 
}
 
int main()
{
 int n=6;//     
 int m=100;//    
 float w1[6]={15,5,60,25,55,80};//       
 float v1[6]={20,30,30,10,55,40};//       
 float x1[6];//           
 float *x;
 float *w;
 float *v;
 w=w1;
 v=v1;
 x=x1;
 
 
 int i;
 
 for(i=0;i<n;i++)
 *(x+i)=0;
 
 knapsack(n,m,v1,w1,x);
 
 printf("
===========          ======================
");
 
 for(i=0;i<n;i++)
 printf("%.1f\t",*(w+i));
 
 printf("
============          =====================
");
 
 for(i=0;i<n;i++)
 printf("%.1f\t",*(v+i));
 
 printf("
============          =====================
");
 for(i=0;i<n;i++)
 printf("%.1f\t",*(x+i));
 
 printf("
============END=====================
");
 
return 0; 
}

簡単な例では、欲張りアルゴリズムがどのように使われているかを説明します.貪欲なアルゴリズムは非常に簡単なアルゴリズムで、生活の中で、もし私たちが他の人に38元を探したいならば、私たちが最初に考えているのはまず1枚の20元を探して、1枚の10元を探して、1枚の5元と3枚の1元を探して、直接38枚の1元を探すことはできません.これは典型的な貪欲なアルゴリズムです.だから、生活の中で至る所アルゴリズムがあって、発見の目が欠けています.

ストラテジー・モードのメリットとデメリットの説明シーンの使用例とコード・プレゼンテーション

闘地主アルゴリズムの設計と実現(一)--プロジェクト紹介&どのように1枚のカードを定義して構築するか