問(wèn)題背景
        隨著(zhù)科學(xué)技術(shù)的不斷發(fā)展，掃地機逐步走入平常百姓家，并被越來(lái)越多的人所接受，掃地機（也稱(chēng)掃地機器人）將在不久的將來(lái)像白色家電一樣成為每個(gè)家庭必不可少的清潔幫手。產(chǎn)品也會(huì )由現在的初級智能向著(zhù)更高程度的智能化程度發(fā)展，逐步取代人工清潔。
       智能掃地機器人是通過(guò)電動(dòng)機的高速旋轉，在主機內形成真空，利用由此產(chǎn)生的高速氣流，從吸入口吸進(jìn)垃圾。掃地機一般為半徑0.2米圓盤(pán)，、運行速度一般在每秒0.25米左右，只走直線(xiàn)，且碰到墻壁等障礙才可轉彎。與傳統的掃地機不同，智能掃地機可以通過(guò)微處理器進(jìn)行現場(chǎng)環(huán)境分析，自動(dòng)選擇運行路線(xiàn)。遇到障礙發(fā)生碰撞后將重新隨機地選擇路線(xiàn)，逐步進(jìn)行清掃。智能掃地機具有記憶、存儲功能。利用傳感器掃描現場(chǎng)環(huán)境，設計運行路徑并存儲。一般不能100%的清掃指定區域（如墻角部分）。清掃后的垃圾裝進(jìn)機子尾部的集塵盒，再通過(guò)人工清倒垃圾。機器在工作電壓不足時(shí)會(huì )自動(dòng)回到充電站充電。
目標任務(wù)
考慮圖1的工作現場(chǎng)，其中點(diǎn)A（1,5）為掃地機充電站，區域的垃圾指標見(jiàn)附件1.不考慮再充電情況，有以下問(wèn)題：
問(wèn)題一：有些低檔的掃地機因為價(jià)格低廉，智能程度不高。其工作時(shí)的
路徑選擇方案是將現場(chǎng)分成若干區域（例如上下左右4個(gè)區域），并通過(guò)傳感器間隔一段時(shí)間掃描現場(chǎng)一次，選則垃圾最多區域清掃。假設每次掃過(guò)的區域垃圾指標值減少1。針對附件1，估計清掃完給定區域大致需要的時(shí)間（盡量保證每個(gè)點(diǎn)的垃圾指標不超過(guò)1）。
    問(wèn)題二：智能程度高的掃地機每次可以選擇清掃垃圾指標值最大的地方清掃，每次掃過(guò)的區域垃圾指標值減少1。該機器人需多長(cháng)時(shí)間才能保證清掃完該區域（區域內指標值不超過(guò)1）。比較問(wèn)題1與問(wèn)題2，說(shuō)明問(wèn)題1中方案的合理性。
    問(wèn)題三：其他條件同2，如何設計掃地機的路徑，保證掃地機以最短時(shí)間清掃完該區域。