有效的路径寻找算法避免锯齿形
Alp*_*per 22 algorithm path-finding shortest-path
我正在开发一个连接物体和电线的软件.该布线具有这样的规则:这些线不能通过其他物体并且不接受对角线移动.
我所知道的所有最短路径算法(A*,dijkstra等)都找到了这种类型的路径:
我不希望在第二个屏幕截图中出现不必要的曲折.我如何实现这一目标？
注意:任何想要尝试算法的人都可以使用此应用程序.
另一个注意:这是我不想要的确切情况.它找到了之字形路径,而不是"向右移动,直到你到达目标的x位置,向上移动直到你到达目标的y位置",这与Z字形的成本相同.
Dia*_*cus 17
您当前的算法找到最短路径,Pmin但改进的算法应找到最小路径,最小路数(Pmin, Tmin).一般解决方案要求您使用一对数字而不是一个数字.如果新发现Pnew小于当前PminOR,如果它相等但Tnew小于Tmin那么取(Pnew, Tnew)新的最小路径.
如果电路板足够小,您仍然可以使用当前使用的单个数字,但此数字必须是复合数字C = P * N + T,其中N足够大并且常数足够小.它必须大于该板的最大可能T,这几乎是板中的瓦片总数.它必须也足够小,以便在算法碰巧处理板中的最大路径时,没有整数溢出,这也是板中的瓦片总数.所以N必须满足这两个条款(B是电路板中瓷砖的总数):
N > B
B * N < INT_MAX
如果B大于SQRT(INT_MAX)那么这个系统是无法解决的,你应该使用一对值.N应该是SQRT(INT_MAX),2 32是2 16.
现在的主要问题是如何计算所有转弯,但这取决于你拥有的算法.添加该部分应该不会太困难.
直观地说,你可以通过给你的代理人一个"动力"来做到这一点.
具体来说,将状态空间的大小增加四倍; 您可以跟踪代理上次,向右,向左还是向下移动的情况.通过一些大的因素来扩大网络中的成本,并为改变方向的移动分配一个小的惩罚.
- 我喜欢这个想法.然而,加倍的国家空间似乎已经足够了:"通过水平移动来到这里"vs"通过垂直移动来到这里". (3认同)
使用一对值（双精度、整数等）进行距离计算。
第一个是距离，第二个是圈数。
按词法排序，因此第一个比第二个更重要。
这在数学和编程上都比“对转弯使用小的惩罚”更干净。
每个节点都是重复的。节点“垂直进入”和“水平进入”，因为它们对圈数产生影响。
启发式是曼哈顿距离，如果您与目标不完全水平或垂直对齐，则转弯。
不利的一面是，这种技术妨碍了跳转点优化，因为到某个位置的对称路径要少得多（因为某些路径的转弯次数比其他路径多）。