NYU AI作业习题-活动安排问题 BFS+DFS Iterative deepening depth-first search

题目链接 http://cs.nyu.edu/courses/spring12/CSCI-GA.2560-001/prog1.html

题目大意：给定n个任务的时间、价值及先后序关系，求一个可行的任务子集，使得时间之和不大于deadline，价值之和不小于targetVaule，且不可出现逆序。

算法思路：题目已经给出算法，转化为状态空间搜索问题（tree-structured state space search problem），先对结点拓扑排序，存储前序的结点关系，然后先对状态搜索树进行BFS，可行的状态压入队列，到达到限制值后，再以队列中的状态为起点进行迭代深入搜索（Iterative deepening depth-first search）。迭代深入搜索算法就是从状态空间搜索树中某一结点如根结点开始，多次迭代DFS，每次DFS设置最大搜索深度depth，depth不断递增至搜索至树叶，伪代码如下

IDDFS(root, goal)
{
  depth = 0
  repeat
  {
    result = DLS(root, goal, depth)
    if (result is a solution)
      return result
    depth = depth + 1
  }
}

DLS(node, goal, depth) 
{
  if (depth == 0 and node == goal)
    return node
  else if (depth > 0)
    for each child in expand(node)
      DLS(child, goal, depth-1)
  else
    return no-solution
}

迭代深入搜索算法具体参见维基百科http://en.wikipedia.org/wiki/Iterative_deepening_depth-first_search

此题求解源代码如下

//http://cs.nyu.edu/courses/spring12/CSCI-GA.2560-001/
#include <stdio.h>
#include <vector>
#include <map>
#include <queue>
using namespace std;

int taskNum;
int targetValue;
int deadline;
int queueMaxSize;

typedef struct {
	bool * selected;
	int totalValue;
	int totalTime;
	int currentDepth;//当前搜索的状态处于哪一层
} State;

typedef struct{
	int time;
	int value;
} Node;

//记录某点的前序结点（即在执行该任务前必须完成的任务）
map<int,vector<int> *> nodesPre;
int ** edges;
Node * nodes;
int * topologyResult;//拓扑排序的结果数组，记录状态树每一层对应的点的标号
int * nodeToTopNode;
queue<int> q;//用于拓扑排序
queue<State> stateQ;//用于状态空间搜索的队列
State resState;//搜索到的结果状态
bool hasResult;

void initialState(State &state){
	state.selected = new bool[taskNum];
	memset(state.selected, false, sizeof(state.selected));
	state.currentDepth = -1;
	state.totalTime = 0;
	state.totalValue = 0;
}

State copyState(State &state){
	State newState;
	newState.selected = new bool[taskNum];
	for(int i = 0; i < taskNum; i++){
		newState.selected[i] = state.selected[i];
	}
	newState.currentDepth = state.currentDepth;
	newState.totalTime = state.totalTime;
	newState.totalValue = state.totalValue;
	return newState;
}

bool checkPreNode(bool * selected, int nodeID){
	vector<int> * v = nodesPre[nodeID];
	if(v == NULL){
		return true;
	}
	vector<int>::iterator it = v->begin();
	for(;it != v->end(); it++){//遍历该点所有的前序结点，有任何一个结点没有选择都返回false
		//nodeToTopNode映射数组填入原始标号，可以映射成拓扑排序后的新标号
		if(selected[nodeToTopNode[*it]] ==  false) return false;
	}
	return true;
}

bool BFS(){
	State root;//初始状态空间树的搜索起点，即根节点
	initialState(root);
	stateQ.push(root);
	hasResult = false;
	while(!stateQ.empty()){
		if(stateQ.size() == queueMaxSize){
			//当该层结点可以选择时，就会压入两个状态，弹出一个状态，因此状态队列会越来越大
			//达到最大队列限制后跳出BFS，开始进行迭代深度优先搜索IDS
			break;
		}
		State state = stateQ.front();
		stateQ.pop();
		State tempSubState = copyState(state);
		if(tempSubState.currentDepth == taskNum - 1){
			continue;
		}
		tempSubState.currentDepth++;
		int nodeID = topologyResult[tempSubState.currentDepth];
		//下面检查该点之前的结点是否都已经选择，且累计的value和time是否满足要求
		if(checkPreNode(tempSubState.selected, nodeID) == true){
			Node tempNode = nodes[nodeID];
			tempSubState.selected[tempSubState.currentDepth] = true;
			tempSubState.totalTime += tempNode.time;
			tempSubState.totalValue += tempNode.value;
			if(tempSubState.totalTime <= deadline){
				stateQ.push(tempSubState);
				if(tempSubState.totalValue >= targetValue){
					hasResult = true;
					resState = copyState(tempSubState);
					break;
				}
			}
		}
		//如果当前层结点可以选（没有出现未选的前序结点），就一共压入了两个状态入队列（选和不选）；
		//否则就压入一个状态即不选改层结点的状态
		State tempSubState2 = copyState(state);
		tempSubState2.currentDepth++;
		tempSubState2.selected[tempSubState2.currentDepth] = false;
        stateQ.push(tempSubState2);
	}
	return hasResult;
}

bool DFS(int depth, State state){//最大深度为depth，起始结点对应的状态state
	state.currentDepth++;
	int nodeID = topologyResult[state.currentDepth];
	if(checkPreNode(state.selected,nodeID) == true){
		Node node = nodes[nodeID];
		state.selected[state.currentDepth] = true;
		state.totalValue += node.value;
		state.totalTime += node.time;
	
		if(state.totalTime <= deadline ){    
			if(state.totalValue >= targetValue ){
				resState = copyState(state);
				return true;
			}
			if(depth != 1){//这里是选该层结点对应的递归 1
				if(DFS(depth-1,state)){
					return true;				
				}
			}
		}
		//这里是不能选改层结点对应的递归 0 ，要先把该结点拿出来
		state.totalValue -= node.value;
		state.totalTime -= node.time;
	}

	state.selected[state.currentDepth] = false;	
	if(depth != 1){
		if(DFS(depth-1,state)){
			return true;				
		}
	}
	return false;
}
	
bool IDS(){
	while(!stateQ.empty()){
		State tempstate = stateQ.front();
		stateQ.pop();
		for(int i = 1; i <= taskNum - (tempstate.currentDepth + 1); i++){//i为最大的搜索深度
			if(DFS(i,tempstate)) return true;
		}
	}
	return false;
} 


bool findNoInDegreeNode(int i){
	bool hashInDegree = false;
	for(int j = 0; j < taskNum; j++){
		if(edges[j][i]) hashInDegree = true;
	}
	return hashInDegree;
}

void topologySort(){
	for(int i = 0; i < taskNum; i++){
		if(findNoInDegreeNode(i) == false) q.push(i);
	}
	int j,count = 0;
	while(!q.empty()){
		j = q.front();
		q.pop();
		topologyResult[count] = j;
		count++;
		for(int k = 0; k < taskNum; k++){
			if(edges[j][k]) {
				edges[j][k] = 0;
				if(findNoInDegreeNode(k) == false) 
					q.push(k);
			}
		}
	}
	printf("拓扑排序结果为");
	for(int m = 0; m < taskNum; m++){
		nodeToTopNode[topologyResult[m]] = m;//填入原始标号，可以映射成拓扑排序后的新标号
		printf("%d ",topologyResult[m]);
	}
}

void input(){
	scanf("%d%d%d%d",&taskNum,&targetValue,&deadline,&queueMaxSize);
	nodes = new Node[taskNum];
	edges = new int* [taskNum];
	topologyResult = new int[taskNum];
	nodeToTopNode = new int[taskNum];
	for(int j = 0; j < taskNum; j++){
		edges[j] =  new int[taskNum];
		for(int k = 0; k < taskNum; k++){
			edges[j][k] = 0;
		}
	}
	
	int tempNum,preNode,lastNode;
	for(int i = 0; i < taskNum; i++){
		scanf("%d%d%d",&tempNum,&nodes[i].value,&nodes[i].time);
	}
	while(true){
		scanf("%d",&preNode);
		if(preNode == -1) break;
		scanf("%d",&lastNode);
		edges[preNode][lastNode] = 1;
		vector<int> * v = nodesPre[lastNode];//v指向lastNode对应的vector容器
		if(v == NULL){
			v = new vector<int>;
			nodesPre[lastNode] = v;
		}
		v->push_back(preNode);
	}
}

void output(){
	printf("求得的解为：[");
	for(int i=0;i<taskNum;i++){
		if(resState.selected[i] == 1){//注意结果state中第四项没有赋值，也是非零数
			printf(" %d ",topologyResult[i]);
		}
	}
	printf("] %d %d\n",resState.totalValue,resState.totalTime);
}

int main(){
	input();
	topologySort();
	if(!BFS() && !IDS()){
		printf("no solutions");
	}
	else output();
	return 0;
}

测试代码

#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <ctime>
#include <cstdlib>
#include <cmath>
#define MAXN 500
using namespace std;

int main(){
	int n, e = 1000, r[MAXN], v[MAXN], maxLen,p[MAXN];
	int i,j,D,M,minVD,maxVD,k=0;
	int DAG[MAXN][MAXN] = {0};
	cout<<"Please input the number of tasks in each example( less than 500)"<<endl;
	cin>>n;
	srand ( unsigned ( time (NULL) ) );
	for(i = 0; i < n; i++){
		r[i] = rand() % n + 1;
		v[i] = rand() % n + 1;
	}
	minVD = n * n * (1 - 2/sqrt(n))/4; 	
	maxVD = n * n * (1 + 2/sqrt(n))/4;
	D = rand() % (maxVD - minVD) + minVD + 1;
	M = rand() % (maxVD - minVD) + minVD + 1;
	maxLen = rand() % n + 1;//队列最大长度
	//下面随机生成DAG
	vector<int> myvector;
    vector<int>::iterator it;	
	for (i = 0; i < n; ++i) 
		myvector.push_back(i); 
    random_shuffle ( myvector.begin(), myvector.end() );
    cout << "myvector contains:";
    for (it=myvector.begin(); it!=myvector.end(); ++it){
		cout << " " << *it << ",";
		p[k] = *it;
		k++;
	}	
    cout<<endl;
	cout<<"r[]:";
	for(i = 0; i < n; i++){
		cout<<r[i] << ",";
	}
	cout<<endl;
	cout<<"v[]:";
	for(i = 0; i < n; i++){
		cout<<v[i] << ",";
	}
	cout<<endl;
	cout<<"D:"<<D<<endl<<"M:"<<M<<endl;

	for(i = 0; i < n-1; i++)//遍历的其实是数组
		for(j = i+1; j <n; j++){
			DAG[p[i]][p[j]] = rand() % 2;
			if(DAG[p[i]][p[j]]) cout<<p[i]<<" "<<p[j]<<endl;
		}
	for(i = 0; i < n; i++){
		for(j = 0; j < n; j++){
			cout<<DAG[i][j]<<" ";
		}
		cout<<endl;
	}
	cout<<endl;
	cout<<"the input for this example is as follows"<<endl;
	cout<<n<<" "<<M<<" "<<D<<" "<<maxLen<<endl;
	for(i = 0; i < n; i++){
		cout<<i<<" "<<v[i]<<" "<<r[i]<<endl;
	}
	for(i = 0; i < n; i++){
		for(j = 0; j < n; j++){
			if(DAG[i][j]) cout<<i<<" "<<j<<endl;
		}
	}
	cout<<endl;
    return 0;
}