扫地机器人，Robot API、实现及总结

太有用了，感谢楼主，已加米

楼主很强, 感谢分享, 已加米;

一个小问题, 为什么DFS用的是PostOrder, 有什么讲究吗?

感谢楼主

vegito2002 发表于 2018-4-23 11:56
楼主很强, 感谢分享, 已加米;

一个小问题, 为什么DFS用的是PostOrder, 有什么讲究吗?

好问题，我现在还在尝试另外两种实现，1) preorder 和 2) BFS，我分享一下到目前的思路

preorder 非常非常容易 stack overflow，原因是搜索过程中的座标都是相对的，完全不知道实际的座标。所以非常可能兜圈子（也就是所谓的路痴⋯⋯233）
比方说四个格子的实际座标是 (0, 0) => (1, 0) => (1, 1) => (0, 1)，一开始会把 (0, 0) 加入 visited，如果方向维护的不对的话，之后从 (0, 1) 找下一格的时候，可能会错误的把 (0, 0) 标记成不同的相对座标，导致兜圈子
可以尝试一下，但进去下一层之前的换方向需要非常小心

第二个 approach 是 BFS，但因为 robot 的移动必须是在连续的格子之间，所以最直觉的那种肯定是行不通的。需要先想好 robot 的移动策略，比如说先往最上最左移动，找到参考点，同时路上搜集一些可以访问的格子，之后再回来访问这些格子，现在有做出来一版，但看起来太蠢了所以没放上去

建议可以动手实现一下，这里面细节太多了

jaychsu 发表于 2018-4-23 15:39
好问题，我现在还在尝试另外两种实现，1) preorder 和 2) BFS，我分享一下到目前的思路

preorder 非常 ...

感谢, 你描述了一下之后, 又对这个题目的难度又了更多的了解

跟楼主讨论一下两个问题：
1.是否需要room class，我看到你在room类中区分了cell的不同状态，但是我感觉没必要这么做。首先是否是obstacle是由sensor决定的，前进时只需要调用sensor的api去判断即可，而对于已经clean过的cell，只需要用visited记录，所以当判断一个cell是否需要去遍历的时候，只需要1. 调用sensor api，2. 检查是否在visited数组中。如果不满足，检查左边和右边，如果满足则移动，都不满足则退回到上一个位置。

2. 如何记录方向，我觉得是否可以用一个stack在robot class中，每次要前进的时候都用peek()看前一个是什么方向。需要后退的时候，则取出一个方向，然后取反方向移动一格即可。例如当前状态是L -> L -> U -> R,返回的时候是L -> D -> R -> R即可。

why1992 发表于 2018-4-26 23:59
跟楼主讨论一下两个问题：
1.是否需要room class，我看到你在room类中区分了cell的不同状态，但是我感觉没 ...

不太懂第一点，你的意思是，不需要用 Room 来保存每个位置的状态，而是用一个新的 Sensor API 去判断能不能访问一个格子，以及在里面维护一个 visited 去看需不需要访问，我理解对吗？
可不可以多讲一些 Sensor 的结构，以及怎么判断是不是 obstacle，是用一个 set 去把所有 obstacle 的位置存起来吗？

第二点肯定可行的啊，赞同这个想法

jaychsu 发表于 2018-4-27 09:28
不太懂第一点，你的意思是，不需要用 Room 来保存每个位置的状态，而是用一个新的 Sensor API 去判断能不 ...

可能是我想当然了，因为我不太了解具体背景是什么。我理解就是一般的这种扫地机器人肯定是有传感器，用于检测是否有障碍，当需要前进的时候直接调用对应方法就好。我觉得如果定义room的话，那相当于对于每一个room，你都需要把room的坐标，以及对应的是否有障碍确定好才能进行遍历，有点不太科学。

不需要知道房间大小，哪怕房间是非规则图形，只要是有一个个小格子组成，robot凭着探索路径的和记录每格状态可以把房间扫干净。就好比一个盲人脑子特好使，摸黑把一个房间打扫干净，我已经有初步算法。本人非科班，算法不专业，莫笑。就用一些do while试试

过几天，回头我用c#写出来，可是怎么测试知道对不对呢