请教拓扑学
现有如下问题：地图（MAP），
地图是用一个二维数组表示的。数组里的值代表地图上对应的道路、墙壁、或者宝物。
大门位于地图的 (0,0) 点（左上角）。开始的时候位于这个点，结束的时候也必须回到这个点。
可以向上下左右四个方向移动。如果移动的目标是墙壁或者宝库的边界，那么移动不会成功。如果移动的目标点上有宝物，那么宝物会自动被拣起。每移动一次就算是走了1步。
有步数限制，只能走N步，因此劳必须在N步之内（包括N步）回到大门处（坐标0,0点）。如果没能回来，就算任务失败。
我学想出什么好办法，就是贪心，选距当前最近的走，但这样效率不高，在CSDN上有人说用拓扑学中的有关知识解决，但小弟不才，谁能给说说。 问题描述的不是很清楚
猜想你的地图是个离散的（既然你有一步的说法）
不知你是预先可以知道地图结构还是只能根据反馈来了解
如果是前者，则用A*之类的寻路算法
如果是后者，在N较小时，就随便找个方向看运气了
如果N足够大，如果内存足够存储地图（或说地图足够小），应该用深度优先遍历之类的策略
你说的“我学想出什么好办法，就是贪心，选距当前最近的走”是什么概念，不太明白
感觉和拓扑学关系不太大 :) 我也感觉同拓扑学没有关系.
而且这个题目看上去也的确很难能够找到最优解.
也许用A*算法是比较合适的一种方法了 又发一遍啊..........http://bbs.emath.ac.cn/thread-1369-1-1.html
页:
[1]