Astar&CSP
Astar and CSP Question
实验1.1
实验目的
使用A-star算法，解决$N\times N$二进制迷锁问题。
实验内容
启发式函数
在本实验中，选用启发式函数$h(x)=\frac13\sum$(1的个数)。在实际搜索中，可以根据当前状态计算下一步的1的个数，无需重新遍历数组进行计算
- admissible：每次操作时，对3个位置进行翻转，因此可能存在的最优解为$\sum (d_{ij}==1)/3$向上取整，$h(x)\leq h*(x)$
- consistent：该启发函数是consistent的，因为两个相邻节点之间$c(m,n)\geq${m中1的个数和n中1的个数的差}/3，$h(n)-h(m)=h(n-m)$，因此$h(n)\leq c(n,m)+h(m)$
思路
借助数组
data[][]存储当前的图的情况，step存储当前的步数，solution存储当前的解法，其中solution每一行分别存储每一步的x，y坐标和以该点为中心的四种转法；使用存储受限的启发式搜索，并限制深度，每次递归搜索，使用
priority queue存储每次搜索时探索的节点，其中优先队列的排序根据是每个节点探索后剩余的1的个数，从小到大排序，即为优先探索可以最小化1的个数的情况。auto cmp = [](const int* a, const int* b) { return a[0] > b[0]; }; priority_queue<int*, vector<int*>, decltype(cmp)> pq(cmp); while(!pq.empty()) { auto cur=pq.top(); pq.pop(); change_data(cur[1],cur[2],cur[3]); solution[step-1][0]=cur[1]; solution[step-1][1]=cur[2]; solution[step-1][2]=cur[3]; cur_1_num=cur[0]; visit_state[cur[1]][cur[2]][cur[3]]=1; if(RBFS()==2) return 2; visit_state[cur[1]][cur[2]][cur[3]]=0; change_data(cur[1],cur[2],cur[3]); cur_1_num=temp_1_num; }每次搜索，计算下一步1的个数
int each_step(int cases,int x,int y) { int after_num=cur_1_num; after_num+=1-2*data[x][y]; switch (cases) { case 1: after_num+=1-2*data[x][y+1]; after_num+=1-2*data[x-1][y]; break; //...case 2 3 4 default: break; } return after_num; }每次进入递归或退出递归时，都要及时更新：
step,cur_1_num,datavoid change_data(int x,int y,int cases){ data[x][y]=1-data[x][y]; switch (cases) { case 1: data[x][y+1]=1-data[x][y+1]; data[x-1][y]=1-data[x-1][y]; break; //case 2 3 4: default: break; } }
剪枝操作
由于最优解中，一定不存在同一个位置的同一种转法，可以维护数组限制仅拓展未被探索的节点
解法的顺序不影响解的结果，因此可以限制每次拓展的节点，具体方法为：遍历
data数组，直到遇到第一个1，要把这个1翻转成0，则必须存在一步包含该1，这样的操作最多存在12种，因此只需拓展相关的12个节点即可。for(int i=0;i<size;i++){ for(int j=0;j<size;j++) { if(data[i][j]==1) { if(i!=0&&j!=0) { next_step=find_next(i,j,2); if(visit_state[i][j][2]==0) pq.push(next_step); next_step=find_next(i-1,j,3); if(visit_state[i-1][j][3]==0) pq.push(next_step); next_step=find_next(i,j-1,1); if(visit_state[i][j-1][1]==0) pq.push(next_step); } //...other nine states t_flag=1; break; } }}深度受限搜索中，理论上对于每个单独存在的1，可以用3步将其变为0且不改变其他的状态，因此可以根据每次搜索到解时当前的解的步数更新深度限制
depth-limit，以及更新当前最优解if(cur_1_num==0) { if(step<best_step) { best_step=step; for(int i=0;i<step;i++) for(int j=0;j<3;j++) best_solution[i][j]=solution[i][j]; } if(depth_limit>step) depth_limit=step; step--; return 1; }
对比Dijkstra
Dijkstra搜索和启发式搜索的区别在于Dijkstra不需要借助启发函数确定下一步需拓展的节点，即将原函数的启发函数一直认为是0即可，在其他条件不变的情况下，和启发式搜索的区别：
- 如果需要搜索最优解，由于启发式搜索对深度限制和剪枝的存在，可以大大降低运行的时间和运行的内存占用，Dijkstra并不适合求解最优解
- 如果要搜索可行解，启发式搜索的搜索结果步数低于Dijkstra算法
实验1.2
实验目的
使用CSP算法，为学校宿管阿姨安排值班表，以满足约束条件，尽可能地满足阿姨们的轮班请求，斌并使用MRV、Forward Checking、Constraint Propagation等优化技术，以便快速解决任务并最大化满足请求数。
实验内容
实验的问题模型可以抽象为一个CSP问题：要找到最大化满足约束$Request\subset \{0,1\}^{N\times D\times S}$的取值为staff_num的days_num*shifts_num个变量。下面是CSP算法设计的具体内容：
最小剩余值：使用MRV求解问题，可以提高求解速度，mrv函数的工作就是根据当前的未被分配的变量中，剩余值最少的变量并返回其 index，如果不存在未被分配的变量，即前n步已经完成了排版，返回-1
int mrv() { int min_index=0; int flag=0; for(int i=1;i<shifts_num*days_num;i++) { if(remaining_value[i]<remaining_value[min_index]) min_index=i; if(remaining_value[i]>0) flag=1; } if(flag==0||remaining_value[min_index]==1000000) return -1; return min_index; }处于公平起见，应该让所有的staff被排班的次数均接近平均值，为了达到这一效果，每次对某一时间段进行排版时，根据满足条件的staff已经排班的次数从小到大进行排序，优先安排排版次数较少者；另外，为了保证优先最大化请求数量，如果该时间段存在可以满足约束的请求，优先在可以满足请求的staff中选择，不考虑无法满足的部分，否则再考虑无法满足请求的情况。
vector<int> staff_order(int index) { vector<int> order; for(int i=0;i<staff_num;i++) { if(data[i][index]==1) order.push_back(i); } if(order.size()==0) { for(int i=0;i<staff_num;i++) { if(data[i][index]==0) order.push_back(i); } } sort(order.begin(), order.end(), [](int a, int b){return staff_times[a] < staff_times[b];}); return order; }CSP算法的主干部分，递归求解，下面是为全部的时间段找到解的处理，其中对返回值的解释如下：其中not_fot_num记录了未满足的约束的数目
- 1：找到了满足所有请求的解，此时要更新相关参数并退出递归
- 2：找到了解，没有满足所有请求，但比之前求解的解更好，此时要更新相关参数
- -1：找到了不满足所有约束的解，并且不如之前的解，不做处理
if(num==days_num*shifts_num&¬_fit_num==0) { best_fit_num=not_fit_num; for(int i=0;i<days_num*shifts_num;i++) { best_plan[i]=final_plan[i]; } return 1;} else if (not_fit_num>best_fit_num) return -1; else if(num==days_num*shifts_num&¬_fit_num<best_fit_num) { best_fit_num=not_fit_num; for(int i=0;i<days_num*shifts_num;i++) { best_plan[i]=final_plan[i]; } return 2; }对于一般的情况，要根据MRV的原则找到最小剩余值，并根据已排班数量staff_num来确定赋值顺序。每次进入或退出递归时，都要更新或恢复相关的变量：
- 修改data中该staff相邻时间的状态
- 修改相邻时间中remain_value
- 更改无法满足的情况时not_fit_num
- 修改staff已经被排班的次数
int index=mrv(); int state=0; auto order=staff_order(index); int t; for(int j=0;j<order.size();j++) { int i=order[j]; int old_data_i_index=data[i][index]; if(old_data_i_index==0) not_fit_num+=1; data[i][index]=0; state=0; if(index!=0&&data[i][index-1]==1) { remaining_value[index-1]-=1; state=1; } if(index!=0) data[i][index-1]=-1; if(index!=days_num*shifts_num-1&&data[i][index+1]==1) { remaining_value[index+1]-=1; state+=2; } if(index!=days_num*shifts_num-1) data[i][index+1]=-1; final_plan[index]=i; int temp=remaining_value[index]; remaining_value[index]=1000000; staff_times[i]++; t=csp(num+1); staff_times[i]--; remaining_value[index]=temp; if(t==1) { return 1; } if(index!=0) data[i][index-1]=0; if(index!=days_num*shifts_num-1) data[i][index+1]=0; if(state%2==1) { data[i][index-1]=1; remaining_value[index-1]+=1; } if(state>=2) { data[i][index+1]=1; remaining_value[index+1]+=1; } data[i][index]=old_data_i_index; if(old_data_i_index==0) not_fit_num--; } return 2;
最后处理输入数据，输出数据模块，即可完成CSP排班的全部内容。
void get_input(char * filename) { ifstream file(filename); char c; file>>staff_num>>c>>days_num>>c>>shifts_num; each_time=days_num*shifts_num/staff_num; best_fit_num=100000; not_fit_num=0; for(int i=0;i<staff_num;i++) { for(int j=0;j<days_num;j++) { for(int k=0;k<shifts_num;k++) { if(k) file>>c; file>>data[i][j*shifts_num+k]; remaining_value[j*shifts_num+k]+=data[i][j*shifts_num+k]; }} }} void get_output(char * filename) { fstream file(filename); for(int i=0;i<days_num;i++) { for(int j=0;j<shifts_num;j++) { if(j!=shifts_num-1) file<<best_plan[i*shifts_num+j]<<','; else file<<best_plan[i*shifts_num+j]<<endl; } } file<<days_num*shifts_num-best_fit_num<<endl; }
