如何训练机器人解决 Katona 风格的问题？

人工智能 搜索 图论 广度优先搜索
2021-10-31 12:37:23

自 1940 年代开始研究认知心理学。这个想法是为了理解人类解决问题的方法以及启发式方法在其中的重要性。George Katona（早期心理学家）在 1940 年代发表了一篇关于人类学习和教学的论文。他提到了所谓的 Katona-Problem，这是一个几何任务。

正方形

Katona 风格的问题是您在给定的吸管配置中移除吸管以最终创建 n 个单位正方形的问题。最后，每一根稻草都是一个单位正方形的边。一些变体包括允许使用 2x2 或 3x3 大小的正方形，只要没有两个正方形重叠，即较大的 2x2 正方形不能包含较小的 1x1 正方形。有些问题使用火柴作为变体，有些使用吸管，有些使用线条。一些变体允许较大的正方形包含较小的正方形，只要它们不共享边即。https://puzzling.stackexchange.com/questions/59316/matchstick-squares

  • 有没有办法我们可以将其视为一个图形，并删除吸管/火柴棒作为删除图形中节点之间的边？

  • 如果是这样，我是否可以训练一个机器人，在其中插入一些随机但有效的游戏条件和目标状态以获得所需的解决方案？

编辑＃1：以下问题只是一个示例，以显示我的目标。我的游戏的要求要大得多。此外，我选择了不知情的搜索来使事情变得更简单，而无需担心复杂的启发式和优化技术。请随时与我一起探索想法。

场景#1：

考虑这种情况。在下图中，每条虚线或管线代表一根稻草。数字和字母表示稻草相遇的路口。比方说，我的机器人可以探索每个路口，移除零、一、二、三或四根稻草，使得结果状态具有

  • 没有因为没有连接到正方形而悬垂的稻草。
  • 较小的 mxm 方块不包含在较大的 nxn 方块中（m<n）
  • 吸管一旦取出，就无法再放回去。

此处显示初始配置。我总是需要从左上角节点 P 和优化开始......目标是在达到目标状态时使用最少的移动次数从节点到节点的最小跳数中移除稻草。

       P------Q------R------S------T
       |      |      |      |      |
       |      |      |      |      |
       E------A------B------F------G
       |      |      |      |      |
       |      |      |      |      |
       J------C------D------H------I
       |      |      |      |      |
       |      |      |      |      |
       K------L------M------N------O
       |      |      |      |      |
       |      |      |      |      |
       U------V------W------X------Y

目标 1：我希望创建一个 2x2 的大正方形。

在某个时候，比如说 BFS 搜索（尽管它可能是对部分可观察宇宙的任何不知情的搜索，即一次查看一个节点），我可以在技术上到达 A，吹掉 A 上的所有边缘以创建以下内容。

       P------Q------R------S------T
       |             |      |      |
       |             |      |      |
       E      A      B------F------G
       |             |      |      |
       |             |      |      |
       J------C------D------H------I
       |      |      |      |      |
       |      |      |      |      |
       K------L------M------N------O
       |      |      |      |      |
       |      |      |      |      |
       U------V------W------X------Y

那是一招。

目标 2：我想创建一个 3x3 正方形。

我不能一口气做到这一点。我需要探索连续节点的记录，然后如果状态未能产生预期的结果，也可能回溯到给定点。每个中间状态可能会产生不允许的矩形（另外，如何知道还有多少以及要移除哪些吸管才能到达正方形）或者悬挂一根吸管或更糟糕的是卡在无限循环中，因为我可以选择不移除任何稻草。我该如何解决这个问题？

#编辑2：

为了验证，下面给出了图 3、4 和 5。

       P------Q------R------S------T
       |             |      |      |
       |             |      |      |
       E      A      B------F      G
       |             |      |      |
       |             |      |      |
       J------C------D------H      I
       |      |      |      |      |
       |      |      |      |      |
       K------L------M------N      O
       |      |      |      |      |
       |      |      |      |      |
       U------V------W------X      Y

上图（3）是无效的，因为我们不能有悬垂的棒 TG、GI 等。

       P------Q------R------S------T
       |      |                    |
       |      |                    |
       E------A                    G
       |                           |
       |                           |
       J                           I
       |                           |
       |                           |
       K                           O
       |                           |
       |                           |
       U------V------W------X------Y

上图（4）是无效的，因为我们不能有重叠的正方形

       P------Q------R      S      T
       |             |             
       |             |            
       E      A      B------F------G
       |             |      |      |
       |             |      |      |
       J------C------D------H------I
       |      |      |      |      |
       |      |      |      |      |
       K------L------M------N------O
       |      |      |      |      |
       |      |      |      |      |
       U------V------W------X------Y

图 (5) 是有效配置。

1个回答

您的直觉是正确的：这从根本上是组合搜索的问题。

您也是对的，问题是由于并非每一步在状态下都有效这一事实造成的。要解决这个问题，除了检查它是否是您的目标状态的常用函数之外，您还需要添加一个可以确定给定状态是否有效的函数。在将每个节点添加到搜索算法的队列之前，请检查它是否是有效状态。如果不是，请不要添加它。

您提出的第二个问题是您的搜索可能会进入无限循环。由于可以从状态中删除零边缘，因此这是一个严重的问题。有两种方法可以解决这个问题。首先，您可以尝试将您已经访问过的所有状态存储在一个快速的数据结构中，例如Hash Table。在将节点添加到队列之前，请检查它是否已被处理。如果有，请不要添加。这可能有效，但内存需求随着解决方案所需的移动次数呈指数增长。有时它是值得的，但我认为你可能会因为这个问题跳过它。

如果您担心速度，一个更好的方法是将您的算法切换到迭代加深之类的东西，它具有 BFS 的良好特性，但内存要求要低得多；或者如果您可以为您的域提出一个可接受的启发式方法，则进行A* 搜索（一个很好的起点：计算您需要从其中移除棍棒的交叉点的数量，如果机器人可以传送，将是可以接受的）。

希望这可以帮助！

编辑：这是一些用于过滤无效动作的伪代码：

function valid_state(State s){
    for stick in s.remaining_sticks:
        if stick is vertical:
           1. let side = walk up from the middle of stick until it becomes possible to turn right.
           2. let side += walk down from the middle of stick until it becomes possible to turn right.
           3. From the first junction above stick where we can turn right, try to walk *side* steps to the right.
           4. Then try to walk side steps down.
           5. Then try to walk side steps left.
           6. Repeat previous 5 steps but for the nearest junctions where we can turn left instead of right.
        else:
           Do exactly what's in the if above, but substitute "left" for "up" and "right" for "down".      
    if we could walk in a square successfully for every stick, this is a valid state, so return true. Otherwise, return false.     
}
其它你可能感兴趣的问题
上一篇如何在正数据模式快速变化的情况下设计分类器？ 下一篇优化未知标签的图像识别结果