大多数时候，当实现诸如A *的寻路算法时，我们寻求最小化沿路径的旅行成本 . 我们还可以寻找具有最少匝数的最佳路径 . 这可以通过具有位置方向状态网格而不是具有位置状态网格来完成 . 对于旧网格中的任何给定位置，我们将在该点中具有4个状态，表示该位置向左，向右，向上或向下移动 . 也就是说，如果您正在扩展到上面的节点，那么您实际上会将该节点的“up”状态添加到优先级队列，因为我们在启动时找到了到此节点的最快路径 . 无论如何，如果你正朝着这个方向前进，我们就不会增加任何重量 . 但是，如果我们不得不从当前节点转到扩展节点，我们会在权重上添加一个小的epsilon，这样如果它们的匝数不同，距离中的两条最短路径的成本就不相等 . 只要epsilon是“在节点之间移动的成本，它仍然是最短的路径 .
我现在提出了类似的问题，但有轻松的约束 . 我不再希望找到最短的路径，甚至不是最少转弯的路径 . 我唯一的目标是找到一个长度为numTurns <= n的路径 . 为了澄清，该算法的目标是回答这个问题：
“从位置A到B是否存在路径P，使得小于或等于n圈？”
我在问这里是否使用某种贪婪算法会有所帮助，因为我不需要最小距离也不需要转弯 . 问题是，如果我没有找到最小值，算法可能会在板上搜索更多的方块 . 也就是说，通常最短路径算法搜索它所具有的最小数量的平方，这是性能的关键 .
是否有任何技术可以提供一种有效的方法（更好或与A *相同）来找到这样的路径？同样，具有最少转弯的A *为距离和#turns提供了“最佳”解决方案 . 但是对于我的问题，“最佳”是函数可以返回的最快方式，无论在A和B之间是否存在<= n转弯的路径 . 注意路径中可能存在障碍物，但除此之外，从一个方格移动对另一个是相同的成本（除非转动，如上所述） .
我一直在集思广益，但除了转向状态的A *之外我什么也想不到 . 可能不可能比这更好，但我认为可能会巧妙地利用我放松的条件 . 我甚至考虑使用numTurns作为移动电路板的成本，但这可能会浪费大量时间来搜索死路径 . 非常感谢！
编辑：最终澄清 - 路径不必具有最少的转弯数，只需<= n . 路径不一定是最短的路径，如果它只有n个转弯，它可以是一条巨大的路径 . 目标是让这个功能快速执行，我甚至不需要记录路径 . 我只需知道是否存在一个 . 谢谢 ：）