一点背景:作为一种在C++中学习多节点树的方法,我决定生成所有可能的TicTacToe板并将它们存储在一棵树中,这样从一个节点开始的分支都是可以跟随该节点的板,以及节点是一步到位的板.在那之后,我认为使用该树作为决策树编写AI来玩TicTacToe会很有趣.
TTT是一个可以解决的问题,一个完美的玩家永远不会丢失,所以我第一次尝试AI时编码似乎很简单.
现在,当我第一次实现AI时,我回过头来为每个节点添加两个字段:X将赢得的次数和O将在该节点下的所有子节点中获胜的次数.我认为最好的解决方案就是让我的每一步动作都选择AI,然后选择最能赢得次数的子树.然后我发现虽然它在大部分时间都是完美的,但我找到了可以击败它的方法.这对我的代码来说不是问题,只是我用AI选择它的路径的问题.
然后我决定让它选择具有计算机最大胜利或人类最大损失的树,以较多者为准.这使它表现更好,但仍然不完美.我仍然可以击败它.
所以我有两个想法,我希望得到更好的输入:
1)而不是最大化赢或输,而是我可以为胜利分配1,为平局分配0,为亏损分配-1.然后选择具有最高值的树将是最佳移动,因为下一个节点不能是导致丢失的移动.这是电路板生成中的一个简单更改,但它保留了相同的搜索空间和内存使用量.要么...
2)在棋盘生成期间,如果有一个棋盘使X或O在下一步中获胜,则只会产生阻止该胜利的孩子.不会考虑其他子节点,然后生成将在此之后正常进行.它缩小了树的大小,但后来我必须实现一个算法来确定是否有一个移动获胜,我认为这只能在线性时间内完成(我认为让板子生成慢很多？)
哪个更好,还是有更好的解决方案？
问题:我有很多积分.这些点中的每一个都有一个列表,其中包含对已经计算和存储它们之间距离的其他点的引用.我需要确定从原点开始并通过特定数量的点到达任何目的地的最短路线.
例如:我正在度假,我住在一个特定的城市.我正在做一个单程旅行,看到任何四个城市,我想尽可能少地旅行.我不能不止一次访问同一个城市.
当前解决方案:现在我只是手动迭代每个可能性并存储最短路径.这有效,但感觉效率低下.此外,这个问题最终将扩展到包括从多个原点搜索到多个目标点,所以我认为这可能会爆炸搜索空间.
搜索最短路径的更好方法是什么？