求助
扫地机器人的路径优化
随着科学技术的不断发展，扫地机逐步走入平常百姓家，并被越来越多的人所接受，扫地机（也称扫地机器人）将在不久的将来像白色家电一样成为每个家庭必不可少的清洁帮手。产品也会由现在的初级智能向着更高程度的智能化程度发展，逐步取代人工清洁。
扫地机是通过电动机的高速旋转，在主机内形成真空，利用由此产生的高速气流，从吸入口吸进垃圾。扫地机一般为半径0.2米圆盘，、运行速度一般在每秒0.25米左右，只走直线，且碰到墙壁等障碍才可转弯。与传统的扫地机不同，智能扫地机可以通过微处理器进行现场环境分析，自动选择运行路线。遇到障碍发生碰撞后将重新随机地选择路线，逐步进行清扫。智能扫地机具有记忆、存储功能。利用传感器扫描现场环境，设计运行路径并存储。一般不能100%的清扫指定区域（如墙角部分）。清扫后的垃圾装进机子尾部的集尘盒，再通过人工清倒垃圾。机器在工作电压不足时会自动回到充电站充电。
考虑图1的工作现场，其中点A（1,5）为扫地机充电站，区域的垃圾指标见附件1.不考虑再充电情况，请你们解决如下问题：
（1） 有些低档的扫地机因为价格低廉，智能程度不高。其工作时的
路径选择方案是将现场分成若干区域（例如上下左右4个区域），并通过传感器间隔一段时间扫描现场一次，选则垃圾最多区域清扫。假设每次扫过的区域垃圾指标值减少1。针对附件1，估计清扫完给定区域大致需要的时间（尽量保证每个点的垃圾指标不超过1）。
（2） 智能程度高的扫地机每次可
以选择清扫垃圾指标值最大的地方清扫，每次扫过的区域垃圾指标值减少1。该机器人需多长时间才能保证清扫完该区域（区域内指标值不超过1）。比较问题1与问题2，说明问题1中方案的合理性。
（3） 其他条件同2，如何设计扫地机的路径，保证扫地机以最短时
间清扫完该区域。
扫地机器人的路径优化
随着科学技术的不断发展，扫地机逐步走入平常百姓家，并被越来越多的人所接受，扫地机（也称扫地机器人）将在不久的将来像白色家电一样成为每个家庭必不可少的清洁帮手。产品也会由现在的初级智能向着更高程度的智能化程度发展，逐步取代人工清洁。
扫地机是通过电动机的高速旋转，在主机内形成真空，利用由此产生的高速气流，从吸入口吸进垃圾。扫地机一般为半径0.2米圆盘，、运行速度一般在每秒0.25米左右，只走直线，且碰到墙壁等障碍才可转弯。与传统的扫地机不同，智能扫地机可以通过微处理器进行现场环境分析，自动选择运行路线。遇到障碍发生碰撞后将重新随机地选择路线，逐步进行清扫。智能扫地机具有记忆、存储功能。利用传感器扫描现场环境，设计运行路径并存储。一般不能100%的清扫指定区域（如墙角部分）。清扫后的垃圾装进机子尾部的集尘盒，再通过人工清倒垃圾。机器在工作电压不足时会自动回到充电站充电。
考虑图1的工作现场，其中点A（1,5）为扫地机充电站，区域的垃圾指标见附件1.不考虑再充电情况，请你们解决如下问题：
（1） 有些低档的扫地机因为价格低廉，智能程度不高。其工作时的
路径选择方案是将现场分成若干区域（例如上下左右4个区域），并通过传感器间隔一段时间扫描现场一次，选则垃圾最多区域清扫。假设每次扫过的区域垃圾指标值减少1。针对附件1，估计清扫完给定区域大致需要的时间（尽量保证每个点的垃圾指标不超过1）。
（2） 智能程度高的扫地机每次可
以选择清扫垃圾指标值最大的地方清扫，每次扫过的区域垃圾指标值减少1。该机器人需多长时间才能保证清扫完该区域（区域内指标值不超过1）。比较问题1与问题2，说明问题1中方案的合理性。
（3） 其他条件同2，如何设计扫地机的路径，保证扫地机以最短时
间清扫完该区域。
