回溯法解决汽车加油次数最少问题

北大青鸟大学城校区logo 北大青鸟大学城校区
招生简章校园环境师资力量就业明星招生问答软件工程师北京大学学历学员项目联系我们 报名通道

免费在线咨询通道>>

免费在线报名通道>>

北大青鸟报名电话
当前位置:北大青鸟 > 软件教程 > .net教程 >

回溯法解决汽车加油次数最少问题

标签:   分类:.net教程


   加油站回溯算法设计(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次方。


若有疑问请拨打北大青鸟咨询热线:010-80146691或点击免费在线咨询!
  • xml地图 网站地图 招生简章 合作企业 学员项目 联系我们
  • 关闭窗口