C#示例：加油站回溯算法设计

加油站回溯算法设计(C#)：

　　using System;
　　Namespace jiayouzhan
　　{
　　/**////
　　/// Class1 的摘要说明。
　　///
　　Class Class1
　　{
　　/**////
　　/// 应用程序的主入口点。
　　///
　　static double sum=7;//加油站总数
　　static double csum=0;//当前加油总数
　　static double bestsum=6;//最优解
　　static double s=100;//总路程
　　static double cs=0;//当前走过的路程
　　static double n=30;//满油能走的路程
　　static double cn=30;//当前能走的路程
　　static double[ ] a={0,20,10,10,10,20,10,20};//加油站分布static double[ ] b={0,0,0,0,0,0,0,0};
　　static double p=0;//记录临时CN
　　Private static void jiayou (int i)
　　{
　　if (i>sum
　　{
　　if(bestsum>csum)
　　{
　　bestsum=csum;
　　Console.WriteLine("{0}",bestsum);
　　for(int j=1;j=a[i+1]))
　　{
　　p=cn;
　　cn=n;
　　cs+=a[i];
　　csum+=1; b[i]=1;
　　jiayou(i++);
　　cn=p-a[i+1];
　　csum-=1; b[i]=0;
　　jiayou(i++);
　　}
　　}
　　static void Main(string[] args)
　　{
　　jiayou(1);
　　Console.Read();
　　}
　　}

　　回溯算法的正确性证明

　　回溯法具有"通用的解题法"之称它的解空间包括了所有的可行解与不可行解我们通过剪枝比较最终得到的最优解，所以使用回溯算法一定是可以得到最优解，即回溯算法解该题具有正确性。

　　回溯算法时间复杂度分析

　　由于回溯算法得到所有的解，最坏的情况在每个加油站都加油即n次，其次加油次数为n-1次，n-2次，n-3次……1次，0次。又由于加油地点不同根据不同的组合，我们分析得出时间复杂度为2的n次方。