1

我正在开发一个麻将纸牌解算器,到目前为止,我做得很好。但是,它并没有我希望的那么快,所以我要求你们可能知道的任何其他优化技术。

所有的瓦片都是从布局中知道的,但解决方案不是。目前,我几乎没有规则可以保证安全移除某些相同的瓷砖对(这不会成为可能的解决方案的障碍)。

为清楚起见,当可以随时拾取瓷砖并且瓷砖松动时,当它根本不绑定任何其他瓷砖时,它是免费的。

  • 如果有四个免费的免费瓷砖可用,请立即删除它们。
  • 如果可以拾取三块瓷砖,并且其中至少有一个是松散的,则移除非松散的。
  • 如果可以拾取三张牌,而只有一张免费牌(两张松动),则移除免费和一张随机松动的牌。
  • 如果有三个松散的瓷砖可用,请移除其中的两个(无论哪个都无所谓)。
  • 由于有四次完全相同的瓷砖,如果剩下两个,请移除它们,因为它们是唯一剩下的。

我的算法递归地在多个线程中搜索解决方案。一旦一个分支完成(到一个没有更多移动的位置)并且它没有导致一个解决方案,它就会将该位置放在一个包含坏的向量中。现在,每次启动新分支时,它都会遍历错误位置以检查该特定位置是否已被检查。
这个过程一直持续到找到解决方案或检查所有可能的位置。

这适用于包含 36 或 72 个图块的布局。但是当有更多时,由于要搜索的位置很多,因此该算法变得非常无用。

所以,我再次问你,如果你们中的任何人有好的想法,如何实施更多的安全瓷砖移除规则或关于算法的任何其他特定加速。

最好的问候, nhaa123

4

4 回答 4

2

几年前,我写了一个程序,通过偷看解决纸牌麻将牌。我用它检查了 100 万只海龟(在半台计算机上花了一天左右的时间:它有两个核心),似乎有 2.96% 的海龟无法解决。

http://www.math.ru.nl/~debondt/mjsolver.html

好的,这不是您所要求的,但是您可能会查看代码以在其中找到一些迄今为止您还没有想到的修剪启发式方法。该程序不使用超过几兆字节的内存。

于 2010-10-14T23:19:58.590 回答
2

我不完全理解你的求解器是如何工作的。当您可以选择移动时,您如何决定首先探索哪种可能性?

如果您选择任意一个,那还不够好-基本上只是蛮力搜索。您可能需要先探索“更好的分支”。要确定哪些分支“更好”,您需要一个评估位置的启发式函数。然后,您可以使用一种流行的启发式搜索算法。检查这些:

  • A* 搜索
  • 束搜索

(谷歌是你的朋友)

于 2009-05-27T07:57:57.687 回答
0

使用具有恒定查找时间而不是线性查找时间的集合,而不是包含“坏”位置的向量。

于 2009-05-27T08:06:52.533 回答
0

如果有 4 个 Tiles 可见但无法拾取,则必须先移除周围的其他 Tiles。路径应该使用您的规则来移除最少的瓷砖,朝向这些瓷砖,以打开它们。

如果 Tiles 被其他 Tiles 隐藏,则问题没有找到路径的完整信息,需要计算剩余 Tiles 的概率。

非常好的问题!

于 2021-03-14T17:24:29.657 回答