dfs的剪枝思维和例题分析

ROADS（POJ 1724）

 解题思路：

从城市1开始深度优先遍历整个图，找到所有能过到N的走法，选一个最优的

代码（1）：

#include 
#include 
#include 
using namaspace std;
int K, N, R;
struct Road {
    int d, l, t;
};

vector< vector < Road > > G(110);
//这个其实就是一个二维数组，但是不会一开始就把数组的大小限制掉
//这样每次输入一个道路信息，就直接可以把道路信息压入容器就好了 
int minLen;
int totalLen;
int totalCost;
int visited[110];
//记录是不是每一条路都走过 
void dfs(int s){
    if(s == N){
        //可以用max和min来更新minLen这个也不是第一次知道了 
        minLen = min(totalLen,minLen);
        return;
    }
    for(int i = 0;i){
        //这个G[s]中储存的全部都是与s也就是起点有相连的结点
        Road r = G[s][i];
        //用一个路来储存边信息
        //首先判断价格会不会超过
        if(totalCost+r.t>K){
            continue;
        } 
        if(!visited[r.d]){
            //如果没有走过的话
            totalLen+=r.L;
            totalCost+=r.t;
            visited[r.d] = 1;
            dfs(r.d);
            //现在这条路走完了，在返回的时候要取消之前的标记
            //否则上面会有路变得不通
            visited[r.d] = 0;
            totalLen-=r.L;
            totalCost+=r.t;
        }
    } 
    
    
    
}
int main(){
    cin>> K >> N >>R;
    for(int i = 0;i){
        //后面是输入过程 
        int s;
        //s是起点 
        Road r;
        cin>>s >>r.d>>r.l>>r.t;
        //接下来要把边放到容器里
        if(s != r.d){
            //这个r不是起点 
            G[s].push_back(r);容器里面 
            //把这个道路的信息放到 
        } 
    }
    memset(visited,0,sizeof(visited));
    totalLen = 0;
    minLen = 1<<30;
    //这个就是把1右移了30位，这样就是一个很大的数
    totalCost = 0;
    visited[1] = 1;
    //如果是1的话
    dfs(1);
    //可能找不到最小值,如果找到了最小值
    if(minLen < ( 1 << 30 )) {
        cout<endl;
    }else{
        cout<<"-1"<<endl;
        
    }
     
    return 0;
} 

上面这段代码是没有用到剪枝的（其实这个是有剪枝的，比如因为价钱的超出而continue掉来节省时间），所以如果数值大的话就会超时。那么我可以这样优化：当在深度优先搜索某一条路的时候，只要这条路的totalLen的值大于minLen，这条路没有必要走下去了，直接continue跳过就好了，这样可以大大的节省时间。

代码2：

#include 
#include 
#include 
using namaspace std;
int K, N, R;
struct Road {
    int d, l, t;
};

vector< vector < Road > > G(110);
//这个其实就是一个二维数组，但是不会一开始就把数组的大小限制掉
//这样每次输入一个道路信息，就直接可以把道路信息压入容器就好了 
int minLen;
int totalLen;
int totalCost;
int visited[110];
//记录是不是每一条路都走过 
void dfs(int s){
    if(s == N){
        //可以用max和min来更新minLen这个也不是第一次知道了 
        minLen = min(totalLen,minLen);
        return;
    }
    for(int i = 0;i){
        //这个G[s]中储存的全部都是与s也就是起点有相连的结点
        Road r = G[s][i];
        //用一个路来储存边信息
        //首先判断价格会不会超过
        if(totalCost+r.t>K){
            continue;
        } 
        if(!visited[r.d]){
            if(totalCost+r.L >= minLen){
                continue;
            }
            //如果没有走过的话
            totalLen+=r.L;
            totalCost+=r.t;
            visited[r.d] = 1;
            dfs(r.d);
            //现在这条路走完了，在返回的时候要取消之前的标记
            //否则上面会有路变得不通
            visited[r.d] = 0;
            totalLen-=r.L;
            totalCost+=r.t;
        }
    } 
    
    
    
}
int main(){
    cin>> K >> N >>R;
    for(int i = 0;i){
        //后面是输入过程 
        int s;
        //s是起点 
        Road r;
        cin>>s >>r.d>>r.l>>r.t;
        //接下来要把边放到容器里
        if(s != r.d){
            //这个r不是起点 
            G[s].push_back(r);容器里面 
            //把这个道路的信息放到 
        } 
    }
    memset(visited,0,sizeof(visited));
    totalLen = 0;
    minLen = 1<<30;
    //这个就是把1右移了30位，这样就是一个很大的数
    totalCost = 0;
    visited[1] = 1;
    //如果是1的话
    dfs(1);
    //可能找不到最小值,如果找到了最小值
    if(minLen < ( 1 << 30 )) {
        cout<endl;
    }else{
        cout<<"-1"<<endl;
        
    }
     
    return 0;
} 

和上面的比就优化了一个小小的地方，只要totalLen加上这条路的长度超过minLen就剪枝。但是这样发现如果数据再大一点的话还是过不了，还是超时，说明这个剪枝不够强，还要更多的剪枝。

 代码3（保存中间计算结果）：

#include 
#include 
#include 
using namaspace std;
int K, N, R;
struct Road {
    int d, l, t;
};

vector< vector < Road > > G(110);
//这个其实就是一个二维数组，但是不会一开始就把数组的大小限制掉
//这样每次输入一个道路信息，就直接可以把道路信息压入容器就好了 
int minLen;
int midL[110][10010] ;
int totalLen;
int totalCost;
int visited[110];
//记录是不是每一条路都走过 
void dfs(int s){
    if(s == N){
        //可以用max和min来更新minLen这个也不是第一次知道了 
        minLen = min(totalLen,minLen);
        return;
    }
    for(int i = 0;i){
        //这个G[s]中储存的全部都是与s也就是起点有相连的结点
        Road r = G[s][i];
        //用一个路来储存边信息
        //首先判断价格会不会超过
        if(totalCost+r.t>K){
            continue;
        } 
        if(!visited[r.d]){
            if(totalCost+r.L >= minLen){
                continue;
            }
            if(totalLen + r.L >= midL[r.d][totalCost+r.t]){
                continue;
            }
            minL[r.d][totalCost+r.t] = totalLen+r.L;
            //如果没有走过的话
            totalLen+=r.L;
            totalCost+=r.t;
            visited[r.d] = 1;
            dfs(r.d);
            //现在这条路走完了，在返回的时候要取消之前的标记
            //否则上面会有路变得不通
            visited[r.d] = 0;
            totalLen-=r.L;
            totalCost+=r.t;
        }
    } 
    
    
    
}
int main(){
    cin>> K >> N >>R;
    for(int i = 0;i){
        //后面是输入过程 
        int s;
        //s是起点 
        Road r;
        cin>>s >>r.d>>r.l>>r.t;
        //接下来要把边放到容器里
        if(s != r.d){
            //这个r不是起点 
            G[s].push_back(r);容器里面 
            //把这个道路的信息放到 
        } 
    }
    memset(visited,0,sizeof(visited));
    
    totalLen = 0;
    minLen = 1<<30;
    //这个就是把1右移了30位，这样就是一个很大的数
    totalCost = 0;
    visited[1] = 1;
    //如果是1的话
    for(int i = 0;i<110;i++){
        for(int j = 0;j<10010;j++){
            min[i][j] = 1<<30;
        }
    }
    dfs(1);
    //可能找不到最小值,如果找到了最小值
    if(minLen < ( 1 << 30 )) {
        cout<endl;
    }else{
        cout<<"-1"<<endl;
        
    }
     
    return 0;
}