贪心算法( 三 ) _生活百科

这样做是完全可行的，它输入的是全部解，但是马遍历当8×8时解是非常之多的，用天文数字形容也不为过，这样一来求解的过程就非常慢，并且出一个解也非常慢。怎幺才能快速地得到部分解呢？【贪心算法】其实马踏棋盘的问题很早就有人提出，且早在1823年，J.C.Warnsdorff就提出了一个有名的算法。在每个结点对其子结点进行选取时，优先选择‘出口’最小的进行搜寻，‘出口’的意思是在这些子结点中它们的可行子结点的个数，也就是‘孙子’结点越少的越优先跳，为什幺要这样选取，这是一种局部调整最优的做法，如果优先选择出口多的子结点，那出口少的子结点就会越来越多，很可能出现‘死’结点（顾名思义就是没有出口又没有跳过的结点），这样对下面的搜寻纯粹是徒劳，这样会浪费很多无用的时间，反过来如果每次都优先选择出口少的结点跳，那出口少的结点就会越来越少，这样跳成功的机会就更大一些。这种算法称为为贪心算法，也叫贪婪算法或启发式算法，它对整个求解过程的局部做最优调整，它只适用于求较优解或者部分解，而不能求最优解。这样的调整方法叫贪心策略，至于什幺问题需要什幺样的贪心策略是不确定的，具体问题具体分析。实验可以证明马遍历问题在运用到了上面的贪心策略之后求解速率有非常明显的提高，如果只要求出一个解甚至不用回溯就可以完成，因为在这个算法提出的时候世界上还没有计算机，这种方法完全可以用手工求出解来，其效率可想而知。均分纸牌#include<cstdio>#include<iostream>#include<cstdlib>int a[1000];using namespace std;int f(int n){ int ave=0; int f=0; for (int i=1;i<=n;i++) { f=f+a[i]; } return f/n;}int main(){ int n; int ans=0; int ave; scanf ("%d",&n); for (int i=1;i<=n;i++) { scanf ("%d",&a[i]); } ave=f(n); for (int i=1;i<=n;i++) { if (a[i]==ave) { continue; } if (a[i]!=ave) { a[i+1]+=a[i]-ave; ans++; } } printf ("%d",ans); return 0;}备注贪心算法当然也有正确的时候。求最小生成树的Prim算法和Kruskal算法都是漂亮的贪心算法。贪心法的套用算法有Dijkstra的单源最短路径和Chvatal的贪心集合覆盖启发式所以需要说明的是，贪心算法可以与随机化算法一起使用，具体的例子就不再多举了。其实很多的智慧型算法（也叫启发式算法），本质上就是贪心算法和随机化算法结合——这样的算法结果虽然也是局部最优解，但是比单纯的贪心算法更靠近了最优解。例如遗传算法，模拟退火算法。套用如把3/7和13/23分别化为三个单位分数的和【贪心算法】设a、b为互质正整数，a<b 分数a/b 可用以下的步骤分解成若干个单位分数之和：步骤一：用b 除以a，得商数q1 及余数r1 。（r1=b - a*q1）步骤二：把a/b 记作：a/b=1/(q1+1）+(a-r1)/b(q1+1）步骤三：重複步骤2，直到分解完毕3/7=1/3+2/21=1/3+1/11+1/23113/23=1/2+3/46=1/2+1/16+1/368以上其实是数学家斐波那契提出的一种求解埃及分数的贪心算法，準确的算法表述应该是这样的：设某个真分数的分子为a，分母为b; 把b除以a的商部分加1后的值作为埃及分数的某一个分母c；将a乘以c再减去b，作为新的a；将b乘以c，得到新的b；如果a大于1且能整除b，则最后一个分母为b/a；算法结束；或者，如果a等于1，则，最后一个分母为b；算法结束；否则重複上面的步骤。备注：事实上，后面判断a是否大于1和a是否等于1的两个判断可以合在一起，及判断b%a是否等于0，最后一个分母为b/a，显然是正确的。PHP代码：class tanxin{ public $weight; public $price; public function __construct($weight=0,$price=0){ $this->weight=$weight; $this->price=$price; }}//生成数据$n=10;for($i=1;$i<=$n;$i++){ $weight=rand(1,20); $price=rand(1,10); $x[$i]=new tanxin($weight,$price);}//输出结果function display($x){ $len=count($x); foreach($x as $val){ echo $val->weight,' ',$val->price; echo '<br>'; }}//按照价格和重量比排序function tsort(&$x){ $len=count($x); for($i=1;$i<=$len;$i++) { for($j=1;$j<=$len-$i;$j++) { $temp=$x[$j]; $res=$x[$j+1]->price/$x[$j+1]->weight; $temres=$temp->price/$temp->weight; if($res>$temres){ $x[$j]=$x[$j+1]; $x[$j+1]=$temp; } } } }//贪心算法function tanxin($x,$totalweight=50){ $len=count($x); $allprice=0; for($i=1;$i<=$len;$i++){ if($x[$i]->weight>$totalweight) break; else{ $allprice+=$x[$i]->price; $totalweight=$totalweight-$x[$i]->weight; } } if($i<$len) $allprice+=$x[$i]->price*($totalweight/$x[$i]->weight); return $allprice;}tsort($x);//按非递增次序排序display($x);//显示echo '0-1背包最优解为:';echo tanxin($x);