計算佔位柵格中的最大覆蓋路徑

我正在實現一個基本機器人，它使用SLAM算法生成其環境的佔用柵格。這是非常簡單的沒有概率的方面，只是一個枚舉來表示空，佔用，未找到，無法到達等。計算佔位柵格中的最大覆蓋路徑

我想知道是否有一個衆所周知的算法來找到訪問所有網格單元所需的最短路徑一次（這是一個吸塵器！）。這是旅行推銷員的問題嗎？

我已經研究了一些基於圖的解決方案，例如查找哈密爾頓週期，但我想知道是否有任何有效的工作在網格上直接。

該網格將大約250x250個單元格。

謝謝！

2012-03-27 Joe S

不太會旅行的推銷員。你介意兩次訪問同一個網格單元嗎？你需要在開始時完成同一點嗎？ – Helen 2012-03-27 14:04:48

https://parasol.tamu.edu/~amato/Courses/620/openProblems/csce620-openProblem-P54_TSPinSolidGridGraphs_OzgurGonen.pdf可能有幫助嗎？ – Helen 2012-03-27 14:14:41

我不介意兩次訪問同一個單元格，只要這個效果最小化，覆蓋率就高效了！我也會看看這個鏈接，謝謝。 – 2012-03-27 14:42:47

只是想到了id我的解決方案添加到這個未答覆的問題 - 我試過的大多數算法只是計算複雜。我使用反向波前算法相當有效地計算了最大覆蓋路徑的近似值。

使用這種算法，我能夠在大約5秒內構建一個250x250的網格單元陣列的最大覆蓋路徑，這在我的場景中當然是可以接受的。

來源

2012-05-07 18:48:53

計算佔位柵格中的最大覆蓋路徑

回答

相關問題