元规划：使用规划器解决数学问题

banq

使用规划器编程（planner programming）解决数学问题的文章。

规划器编程和动态规划 (DP)比较
规划器编程使用搜索来查找一系列操作，而 动态规划（dynamic programming ：DP)） 则将问题分解并重新使用子问题的解决方案。

规划器编程和动态规划 (DP) 是解决复杂问题的相关但不同的技术：

  • 规划器编程涉及将问题建模为一系列动作和状态，并使用广度优先搜索 (BFS) 等规划算法来找到到达目标状态的最短路径。本文演示了如何使用规划器编程来解决涉及达到目标字符数的数学问题。
  • 动态规划是一种解决复杂问题的方法，它将复杂问题分解为更简单的子问题，每个子问题只解决一次，并存储解决方案以避免冗余计算。它对具有最优子结构和重叠子问题很有效。
两者都旨在有效地解决复杂问题。

案例
文章中讨论了一个有趣的问题：
假设开始时有一个空白文档，写入一个字母 "a"，然后只能使用 "全选"、"复制" 和 "粘贴" 这三个功能

  • 目标是找到达到至少100,000个 "a" 的最少步骤数。（"全选"、"复制 "和 "粘贴 "这三个操作中的每一个都算作一个步骤）
  • 如果没有指定目标数，，是否存在一个通用公式来得到确切数量的 "a"？

首先是使用分析方法寻找解决方案，使用C++程序通过广度优先搜索（BFS）来找到解决方案。这保证找到最短路径，但会阻止某些优化，例如融合选择和复制步骤

#include <iostream>
#include <queue>

enum Mode
{
    SELECT,
    COPY,
    PASTE
};

struct Node
{
    int noOfAs;
    int steps;
    int noOfAsCopied;
    Mode mode;
};

int main()
{
    std::queue<Node> q;

    q.push({1, 0, 0, SELECT});

    while (!q.empty())
    {
        Node n = q.front();
        q.pop();

        if (n.noOfAs >= 100000)
        {
            std::cout << n.steps << std::endl;
            break;
        }

        switch (n.mode)
        {
        case SELECT:
            q.push({n.noOfAs, n.steps + 1, n.noOfAsCopied, COPY});
            break;
        case COPY:
            q.push({n.noOfAs, n.steps + 1, n.noOfAs, PASTE});
            break;
        case PASTE:
            q.push({n.noOfAs, n.steps, n.noOfAsCopied, SELECT});
            q.push({n.noOfAs + n.noOfAsCopied, n.steps + 1, n.noOfAsCopied, PASTE});
            break;
        }
    }

    return 0;
}

由于 BFS 的一个有趣特性，这保证能找到最短的解决方案：节点到原点的距离永远不会减小。如果您在节点 X 之后评估节点 Y，则 Y.dist >= X.dist，这意味着第一个有效解决方案将是最短的解决方案。


这也存在一个缺点，就是无法使用洞察力。我们应该能够将选择和复制步骤融合在一起，这意味着我们只需要两个操作（selectcopy、paste），而不是三个操作（select、copy、paste），其中 selectcopy 所需的步骤是粘贴的两倍。

但我们不能这样优化，因为这会破坏单调性。我们现在要把 n+1 步和 n+2 步混合推送到队列中，没有办法保证所有 n+1 步都在 n+2 步之前被搜索到。

我想我应该尝试用规划语言来解决这个问题，这样我们就能同时获得优雅的解决方案和优化。

规划Planning
规划的大致思路是，你提供：

  • 一个初始状态、
  • 一组操作
  • 和一个目标，
然后工具会找出达到目标的最短操作序列。

import planner.
import util.

main =>
  Init = $state(1, 0) % one a, nothing copied
  , best_plan(Init, Plan, Cost)
  , nl
  , printf("Cost=%d%n", Cost)
  , printf("Plan=%s%n", join([P[1]: P in Plan], " "))
  .

我们将系统状态存储为两个整数：打印的字符数和剪贴板上的字符数。由于我们将融合选择和复制，因此我们不需要跟踪所选字符的数量（与 C++ 不同）。

final(state(A, _)) => A >= 100000.

action(state(A, Clipboard), To, Action, Cost) ?=>
  NewA = A + Clipboard
   , To = $state(NewA, Clipboard)
   , Action = {"P", To}
   , Cost = 1
   .

粘贴操作只是将剪贴板添加到字符数中。由于 Picat 是一种研究语言，因此将表达式放在结构中有点奇怪。如果我们这样做，它$state(1 + 1)会将其存储为字面意思 $state(1 + 1)，而不是state(2)。

此外，在函数定义中，定义时必须使用美元符号，但在模式匹配时不能使用美元符号。我不知道为什么。

action(state(A, Clipboard), To, Action, Cost) ?=>
  To = $state(A, A)
   , Action = {"SC", To}
   , Cost = 2
   .

就是这样！这就是整个程序。运行它得到：

Cost=42
Plan=SC P P SC P P SC P P SC P P SC P P SC 
     P P SC P P SC P P SC P P P SC P P P

为了找到是否存在一个恰好等于100,000 的序列，我们只需要做一处更改：

- final(state(A, _)) => A >= 100000.
+ final(state(A, _)) => A = 100000.

作者能够找到最短的操作序列（选择、复制、粘贴），以达到恰好 100,000 个字符，耗时 43 步。

另一方面，即使进行了一些优化，我也无法让它找到一条能精确生成 100 001 个字符的路径。这是因为最短路径的长度超过 9000 步！

  • 找不到一个恰好达到 100,001 个字符的序列，因为最短路径长度超过 9,000 步

元规划（Metaplanning）
规划让我如此着迷的一个原因是，如果一个问题现在很简单，你就可以尝试一下。比如，如果我想添加“删除一个字符”作为动作，这很容易：

action(state(A, Clipboard), To, Action, Cost) ?=>
  A > 0
  , NewA = A - 1
  , To = $state(NewA, Clipboard)
  , Action = {"D", To}
  , Cost = 1
  .

这并不会让超过或达到 100 000 步变得更容易，但会让达到 100 001 步变得只需 47 步，而不是 9000 步。

添加“删除一个字符”操作，将达到 100,001 的步骤从 9,000 步减少到 47 步。

这体现了规划探索不同解决方案和优化的强大力量。

经过一些调整，我还可以问一些问题，比如 "哪些数字的最短路径最简单？哪个数字最多？

规划真的很酷。

总结
规划语言的核心思想是提供一个初始状态、一组动作和目标，然后工具会找到达到目标的最短动作序列。文章中使用Picat语言来实现规划解决方案，并展示了如何定义状态、动作和目标，以及如何运行规划程序来找到成本和计划。