建议使用以下浏览器,以获得最佳体验。 IE 9.0+以上版本 Chrome 31+ 谷歌浏览器 Firefox 30+ 火狐浏览器
请选择 进入手机版 | 继续访问电脑版
设置昵称

在此一键设置昵称,即可参与社区互动!

确定
我再想想
选择版块
092713ie8gnff9tx2p8m72.jpg 云声6月建议活动来袭,领华为无线耳机就这么简单! 云上开发精选优惠

davidyang

发帖: 1粉丝: 0

级别 : 新手上路

发消息 + 关注

发表于2020-5-11 12:09:18 573 1
直达本楼层的链接
楼主
显示全部楼层
[大赛专区] 口罩大作战(赛道一)陪跑经历和算法思路代码(C++)分享

  因为一直在电脑旁上网课并且一直拿柜子当椅子坐导致腰肌劳损,所以直到现在才来发分享帖,下面开始正题。

  本来早就在学校官方网站上就看到了该比赛,因为课程大作业的原因所以一直推到4月28日才正式开始报名编写代码~

  一开始看到题目我首先想到的是TSP(旅行商)问题,就是多次全局搜索取次优解,想到之前编写过用蚁群算法编写过TSP代码(想着这下可以直接搬过来用了),但看到测试用例说要1000幅地图在5分钟内跑完,我开始犹豫了,想起之前跑蚁群的时候一幅地图就要搜索几千次才能得出一个次优解,想着这1000幅地图有点够呛,但自始至终都没注意一幅地图的大小限定(12*12),我脑内一直想的是有在任意大小的地图内N个口罩需求区,1个随机仓库,N个随机口罩捐赠区的配送问题(这也是我一直的毛病看到一个问题就想实现一个通用性比较强的解法,结果最后是试用在用例上效果并不好~~~~)于是我放弃了蚁群搜索算法和Dijkstra这些耗时的搜索算法,使用构造函数的方法(然后陷入了大坑无法自拔~~)

第一天(4月28日)——完成了算法思路构建和数据结构编写(代码第一版)

1、首先是既然是构造函数法肯定是要有权重值,题目中说基于距离最短,所以将距离因素权重设为0.8,而口罩数量的因素权重设为0.2,然后是每个建筑的位置和口罩数,而且在配送的过程中要时刻删除相关的坐标,所以使用链表数据结构来存储位置信息和口罩数信息,然后是建筑物信息,题目的建筑物可以分为两类,一类是仓库类(捐献小区也可看作是仓库)这类结构体链表中的口罩数是正数;一类是待配送类,这类结构体链表中的口罩数是负数,定义最大口罩数为10000;

#define MAX 10000
struct coordinate {
	int x;         //坐标位置      
	int y;
	int cost;
	struct coordinate *next = NULL;
};
class building {
public:
	int sum;                    //目前建筑数量
	struct coordinate *last;
	struct coordinate *first;
	building() {
		sum = 0;
		first =  NULL;
		last =  NULL;
	}
};

2、接着是开始main函数编写

while循环监控是否有命令输入,若命令是S则是仓库命令,调用add函数向warehouse建筑类内添加仓库;若命令是R则是小区命令,若num>0则是捐赠小区,向warehouse建筑类内添加,若num<0则是需求小区,向resident建筑类内添加,并且记录总共的需求数need_sum;如果命令为G,则是移动命令,开始执行action函数,若需求小区数sum为0,结束;

int main() {
	char op;
	int x, y;
	int num;
	//int count1 = 0;
	int Delivery_x, Delivery_y, Delivery = 100;
	int need_sum = 0;
	//int total = 0;
	struct coordinate *pre =  NULL;
	building warehouse = building();
	building resident = building();
	while (cin >> op) {
		if (op == 'S') {
			cin >> x >> y;
			add(&warehouse, x, y);
			if (warehouse.first->next == warehouse.last) {
				Delivery_x = warehouse.last->x;
				Delivery_y = warehouse.last->y;
			}
		}
		else if (op == 'R') {
			cin >> x >> y >> num;
			if (num > 0) {
				pre = add(&warehouse, x, y, num);
				if (x == Delivery_x && y == Delivery_y) {
					change(&warehouse, &resident, &Delivery_x, &Delivery_y, &Delivery, &need_sum, 2, warehouse.last, pre);
				}
			}
			else {
				need_sum += abs(num);
				add(&resident, x, y, num);
			}
		}
		if (op == 'G') {
			action(&warehouse, &resident, &Delivery_x, &Delivery_y, &Delivery, &need_sum);
			if (resident.sum == 0) {
				break;
			}
		}
	}
}

3、main函数涉及相关函数

(1)添加建筑函数add

这个就没什么多说的了,建立新的位置信息类结构体,在连到链表上面;(不要在意其中的cout,这是运行测试模块能不能正常运行用的)

struct coordinate * establish(int x, int y, int cost = MAX) {
	struct coordinate *p = new struct coordinate;
	p->x = x;
	p->y = y;
	p->cost = cost;
	return p;
}
void action(class building *wa, class building *re, int *d_x, int *d_y, int *sum, int *need, int flat, struct coordinate *n, struct coordinate *n_pre);
struct coordinate* add(class building *build, int x, int y, int num = MAX) {
	struct coordinate* pre =  NULL;
	if (build->first ==  NULL) {
		build->first = new struct coordinate;
		build->last = establish(x, y, num);
		(*build).first->next = build->last;
		//cout<<(*build).first->next->x<<(*build).first->next->y<<(*build).first->next->cost<<endl;
		//cout<<(*build).last->x<<(*build).last->y<<(*build).last->cost<<endl;
	}
	else {
		pre = build->last;
		(*build).last->next = establish(x, y, num);
		build->last = (*build).last->next;
		//cout<<(*build).first->next->x<<(*build).first->next->y<<(*build).first->next->cost<<endl;
		//cout<<(*build).last->x<<(*build).last->y<<(*build).last->cost<<endl;
	}
	build->sum++;
	return pre;
}

(2)移动函数action

1、如果当前配送员口罩数大于等于需要口罩数的平均数的一半(为什么是大于等于需要口罩数的平均数的一半,因为假设极端情况所有的需求小区都是200,那么派送员最大是100,要满足配送需求就是大于等于此时需要口罩数的平均数的一半即100),为什么还有(*sum)!=0,这是后期发现的bug之后再说,我们现在按时间顺序来说,满足条件后说明可以配送

      当此时发现配送员发现持有口罩数大于等于需求区口罩数时(*sum >= abs(p->cost)),计算该需求区的权重意愿值

权重函数构造思路------前半部分:float(abs(*d_x - p->x) + abs(*d_y - p->y))*beta距离越短越好

后半部分:float(abs(*d_x - p->x) + abs(*d_y - p->y)) / abs(p->cost)*alpha  单位距离配送越多越好

     当此时发现配送员发现持有口罩数小于需求区口罩数时(*sum < abs(p->cost))时,使用另一个构造函数计算该需求区的权重意愿值

权重函数构造思路------前半部分:同上  后半部分:a = float(abs(*d_x - p->x) + abs(*d_y - p->y))*beta + float(abs(*d_x - p->x) + abs(*d_y - p->y)) /b*alpha  因为此时所持口罩数大于均值,优先配送需求大的小区,减小需求大的小区从仓库到该区域的来回步数;

2、如果当前配送员口罩数大于所有的需求,若有则判断权重意愿值

3、否则如果有当前配送员口罩数大于需求小区的,则使用权重函数判断

此时权重float(abs(*d_x - p->x) + abs(*d_y - p->y)) / abs(p->cost);  单位距离配送越多越好

4、若有配送目标则a!=-1,则移动到该点,移动玩之后判断是否移动到了其他需求小区的位置或捐献小区的位置,若有进入change函数改变对应的口罩数;

5、否则跳出前往获取口罩Supplementary(wa, re, d_x, d_y, sum, need);

void action(class building *wa, class building *re, int *d_x, int *d_y, int *sum, int *need) {
	float alpha = 0.2, beta = 0.8, a = -1;
	int best_dis = MAX;
	int b;
	struct coordinate *p = re->first->next;
	struct coordinate *p1 = re->first->next;
	struct coordinate *pre = re->first;
	struct coordinate *best= NULL;
	struct coordinate *best_pre = NULL;
	while (p !=  NULL) {
		if (*sum >= (*need) / (re->sum * 2)&&(*sum)!=0) {
                if (*sum >= abs(p->cost)) {
				a = float(abs(*d_x - p->x) + abs(*d_y - p->y))*beta + float(abs(*d_x - p->x) + abs(*d_y - p->y)) / abs(p->cost)*alpha;
				//cout<<"a="<<a<<"SUM="<<*sum<<"AVG"<<*need<<"RE"<<(re->sum*2)<<endl;
				if (a < best_dis) {
					best_dis = a;
					best_pre = pre;
					best = p;
				}
			}
			else {
				b=abs(p->cost) - (*sum);
                b=(b==0)?1:b;
				a = float(abs(*d_x - p->x) + abs(*d_y - p->y))*beta + float(abs(*d_x - p->x) + abs(*d_y - p->y)) /b*alpha;
				//cout<<"a="<<a<<"SUM="<<*sum<<"AVG"<<*need<<"RE"<<(re->sum*2)<<endl;
				if (a < best_dis) {
					best_dis = a;
					best_pre = pre;
					best = p;
				}

			}
			}
		else if(*sum >= (*need)){
			a = float(abs(*d_x - p->x) + abs(*d_y - p->y))*beta + float(abs(*d_x - p->x) + abs(*d_y - p->y)) / abs(p->cost)*alpha;
				//cout<<"a="<<a<<"SUM="<<*sum<<"AVG"<<*need<<"RE"<<(re->sum*2)<<endl;
				if (a < best_dis) {
					best_dis = a;
					best_pre = pre;
					best = p;
				}
		}
		else if (*sum >= abs(p->cost)) {
				a = float(abs(*d_x - p->x) + abs(*d_y - p->y)) / abs(p->cost);
				//cout<<"a="<<a<<"SUM="<<*sum<<"AVG"<<*need<<"RE"<<(re->sum*2)<<endl;
				if (a < best_dis) {
					best_dis = a;
					best_pre = pre;
					best = p;
				}
			}
		else{
            break;
		}
		pre = p;
		p = p->next;
	}
	//cout<<"目前位置"<<*d_x<<','<<*d_y<<"要去的位置:"<<best->x<<','<<best->y<<endl;
	if (a != -1) {
		if (*d_x > best->x) {
			cout << 'N' << endl;
			(*d_x)--;
		}
		else if (*d_x < best->x) {
			cout << 'S' << endl;
			(*d_x)++;
		}
		else if (*d_y < best->y) {
			cout << 'E' << endl;
			(*d_y)++;
		}
		else if (*d_y > best->y) {
			cout << 'W' << endl;
			(*d_y)--;
		}
		if (*d_x == best->x&&*d_y == best->y)
			change(wa, re, d_x, d_y, sum, need, 1, best, best_pre);
		else {
			int flat = 0;
			struct coordinate *w = (*wa).first->next;
			struct coordinate *w_pre = (*wa).first;
			while (w !=  NULL) {
				if (abs(*d_x - w->x) == 0 && abs(*d_y - w->y) == 0) {
					flat = 2;
					break;
				}
				w_pre = w;
				w = w->next;
			}
			struct coordinate *r = (*re).first->next;
			struct coordinate *r_pre = (*re).first;
			while (r !=  NULL) {
				if (abs(*d_x - r->x) == 0 && abs(*d_y - r->y) == 0) {
					flat = 1;
					break;
				}
				r_pre = r;
				r = r->next;
			}
			if (flat == 2)
				change(wa, re, d_x, d_y, sum, need, flat, w, w_pre);
			else
				change(wa, re, d_x, d_y, sum, need, flat, r, r_pre);
		}
	}
	else {
		Supplementary(wa, re, d_x, d_y, sum, need);
	}
}

(3)获取口罩Supplementary函数

1、判断若此时口罩数+捐献小区数大于均值则判断该小区权重意愿值

构造函数思路:float(abs(*d_x - p->x) + abs(*d_y - p->y))*beta + float(abs(*d_x - p->x) + abs(*d_y - p->y)) /b*alpha     距离至上,后半部分表示获取口罩的损失率越小越好

2、得到位置之后移动,同移动函数action后半部分,先移动后判断是否移动到其他区域;

void Supplementary(class building *wa, class building *re, int *d_x, int *d_y, int *sum, int *need) {
	float a = -1;
	int best_dis = MAX;
	int b;
	struct coordinate *p = (*wa).first->next;
	struct coordinate *pre = wa->first;
	struct coordinate *best= (*wa).first->next;
	struct coordinate *best_pre =wa->first;
	while (p !=  NULL) {
		if ((*sum + p->cost) > (*need) / (re->sum * 2)) {
			b = ((100 - (*sum)) > p->cost) ? (p->cost-(*sum)) : (100-(*sum));
			b =(b==0)?1:b;
			a = float(abs(*d_x - p->x) + abs(*d_y - p->y))*beta + float(abs(*d_x - p->x) + abs(*d_y - p->y)) /b*alpha;
			//cout<<"获取口罩a="<<a<<"SUM="<<*sum<<"AVG"<<*need<<"RE"<<(wa->sum*2)<<endl;
			if (a < best_dis) {
				best_dis = a;
				best = p;
				best_pre = pre;
			}
		}
		pre = p;
		p = p->next;
	}
}

(4)口罩数变动函数change

这个没什么多说的,flat是区分送口罩还是取口罩,送口罩:足够就送完删除该小区,不够就持有清0  取口罩:足够就取满,不够就取完删除该捐献小区;

void change(class building *re, int *d_x, int *d_y, int *sum, int *need, int flat, struct coordinate *best, struct coordinate *best_pre) {
	if (flat == 1) {
		if (*d_x == best->x&&*d_y == best->y) {
			if ((-best->cost) > *sum) {
				best->cost = best->cost + *sum;
				(*need) -= *sum;
				*sum = 0;
			}
			else {
				(*sum) = best->cost + (*sum);
				(*need) += best->cost;
				best->cost = 0;
				//cout<<best->cost<<"剩余"<<(*sum)<<endl;
				best_pre->next = best->next;
				re->sum--;
				if (re->last == best)
					re->last = best_pre;
				delete best;
				if (re->sum == 0)
					return;
			}
		}
	}
	if (flat == 2) {
		if (*d_x == best->x&&*d_y == best->y) {
			if ((best->cost + (*sum) > 100)) {
				best->cost = best->cost - (100 - *sum);
				*sum = 100;
			}
			else {
				(*sum) = best->cost + (*sum);
				best->cost = 0;
				best_pre->next = best->next;
				//cout<<"这里"<<best->next->x<<best->next->y<<best->next->cost<<endl;
				warehouse.sum--;
				if (warehouse.last == best)
					warehouse.last = best_pre;
				delete best;
			}
		}
	}
}

然后后面几天就是debug的时间了

第二天(4月29日)——debug半天才知道测试不支持C++11 用null替换nullptr,删除了万能开头头文件;

第三天(4月30日)

1、通过测试一堆数据发现有的时候G命令没有及时移动命令,发现action函数中*sum >= (*need) / (re->sum * 2)这个判断条件若need==1,re->sum==1,sum==0时会卡住,所以加上sum!=0的条件

2、添加了捐献小区落脸上的条件判断,第一次提交成功也是最成功的一次,之后不管如何修改都平均步数会更低;

第四天(5月1日)——通过分析几天的每日PK例子发现代码在一个区域配送时,有时会跑到其他区域配送增加重复的步数,猜想分区域配送可能会好一点,分为右上配送,左上配送,左下配送,右下配送,但捐赠小区不分区照常获取最优口罩,让最远的待配送区域留到最后配送,进行逆时针配送,防止出现重复步数;

例如:

image.png

分区后的main函数,代码中涉及到的移动判断位置都要加入分区域判断(篇幅情况不过多赘述原代码)

building resident_onright = building();
building resident_belowright=building();
building resident_onleft=building();
building resident_belowleft=building();
building warehouse = building();
int need_sum_onright = 0,need_sum_onleft=0,need_sum_belowleft=0,need_sum_belowright=0;
if (op == 'R') {
			cin >> x >> y >> num;
			if (num > 0) {
				pre = add(&warehouse, x, y, num);

				if (x == Delivery_x && y == Delivery_y) {

                    if(x<=wa_x&&y>wa_y)
					change(&resident_onright, &Delivery_x, &Delivery_y, &Delivery, &need_sum_onright, 2, warehouse.last, pre);
                else if(x<wa_x&&y<=wa_y)
                    change(&resident_onleft, &Delivery_x, &Delivery_y, &Delivery, &need_sum_onleft, 2, warehouse.last, pre);
                else if(x>=wa_x&&y<wa_y)
                    change(&resident_belowleft, &Delivery_x, &Delivery_y, &Delivery, &need_sum_belowleft, 2, warehouse.last, pre);
                else if(x>wa_x&&y>=wa_y)
                    change(&resident_belowright, &Delivery_x, &Delivery_y, &Delivery, &need_sum_belowright, 2, warehouse.last, pre);

				}
			}
			else {

				if(x<=wa_x&&y>wa_y){
                need_sum_onright += abs(num);
                if(abs(x-wa_x)+abs(y-wa_y)>further_dis){
                further_dis=abs(x-wa_x)+abs(y-wa_y);
                position=1;
                }
				add(&resident_onright, x, y, num);
				}else if(x<wa_x&&y<=wa_y){
				    need_sum_onleft += abs(num);
				    if(abs(x-wa_x)+abs(y-wa_y)>further_dis){
                further_dis=abs(x-wa_x)+abs(y-wa_y);
                position=2;
                }
				add(&resident_onleft, x, y, num);
				}else if(x>=wa_x&&y<wa_y){
				    need_sum_belowleft += abs(num);
				    if(abs(x-wa_x)+abs(y-wa_y)>further_dis){
                further_dis=abs(x-wa_x)+abs(y-wa_y);
                position=3;
                }
				add(&resident_belowleft, x, y, num);
				}else if(x>wa_x&&y>=wa_y){
				    need_sum_belowright += abs(num);
				    if(abs(x-wa_x)+abs(y-wa_y)>further_dis){
                further_dis=abs(x-wa_x)+abs(y-wa_y);
                position=4;
                }
				add(&resident_belowright, x, y, num);
				}
			}
	}

最后debug提交发现并没有什么用~~~直接崩溃

第五天(5月2日)没办法生病了,划水度过~~~~~~~~~眼睁睁的看着排名一直下跌从20到37~~~~~~~~~~~~~~~

image.png

最后附上垃圾代码,以上!


Delivery.rar 10.59 KB,下载次数:2

举报
分享

分享文章到朋友圈

分享文章到微博

ecstatic

发帖: 18粉丝: 10

级别 : 高级会员

发消息 + 关注

发表于2020-5-12 07:29:06
直达本楼层的链接
沙发
显示全部楼层

感谢分享~

点赞 评论 引用 举报

游客

富文本
Markdown
您需要登录后才可以回帖 登录 | 立即注册