寻找更好的回溯系统
我将尝试用简单的术语解释这一点，因为它可能比我发布代码要短。我制作了递归解决方案的一部分，该解决方案必须通过选择正确的“移动顺序”来完成游戏，如果陷入僵局，则必须回溯。我当前的系统通过在任何未起作用的移动上设置标识符来工作，以便在回溯时不能再次使用它，直到找到新的路径/移动顺序。
然而我遇到了一个问题；游戏可能会达到这样一种状态：只剩下两步棋，而这两步棋都无法解决游戏。我当前的系统基本上会让这两个动作不断地相互交换，因为解决方案尝试下一个动作，发现它不起作用，然后尝试下一个动作。我相信我的问题是我重置了标识符，它告诉解决方案在每次进行移动时不要使用移动，但我不确定如何设置它。
如果您需要任何进一步的信息或有任何见解，请告诉我。谢谢！
I'm going to try to explain this in simple terms, because it's probably shorter than if I were to post code. I made part of a recursive solution which has to complete a game by picking the correct "move order", and if it runs into an impasse, then it must backtrack. My current system works by setting an identifier on any move that hasn't worked so that it cannot be used again while backtracking, until a new path/move order is found.
However I ran into a problem; the game can reach a state where there are only two moves left and neither of them will solve the game. My current system will basically make these two moves continually swap one another because the solution attempts to play a move, sees that it doesn't work, and then tries to next one. I believe my problem is that I reset my identifier which tells the solution not to use a move, every time a move is made, but I'm not sure how else I would set it up.
Let me know if you need any further information or have any insight. Thanks!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
我不确定您所描述的游戏的性质，更多信息可以帮助您确定更好的方法。我在主题中看到您的评论，您说发现新动作后该索引会重置。这听起来不太好。我相信您必须解决这个问题，因为正如您刚刚从示例中看到的那样，在某些情况下它会失败，并且我们不能拥有仅在有条件的情况下工作的算法。
你描述的问题听起来像是一个博弈树？正确的？如果是这样，为什么不将问题的描述更改为博弈树并利用一种经过验证的博弈树搜索算法，例如 Alpha-Beta 修剪 假设游戏是对抗性的？
I am not sure about the nature of the game you are describing and some more information could help in determining a better method for you to follow. I saw your comment in the Topic where you say that this index resets after a new move has been found. This does not sound very good. I believe you would have to fix this because as you just saw from your example there are cases where it will fail and we can't have an algorithm that works only conditionally.
The problem you describe sounds like a game tree? Correct? If so why not change your description of the problem to a game tree and utilize one of the proved game tree search algorithms such as Alpha-Beta Pruning assuming the game is adversarial?