c - 找到给定输入和目标字符串所需的最少转换次数

Question

鉴于我有一个输入字符串，例如:aab
我得到了一个目标字符串，例如:bababa
然后我得到了一组转换规则。例如:

ab -> bba
b -> ba

在 C 语言中，我如何做一个算法来找到需要在输入字符串中应用以获取目标字符串的最小 转换数。

在这个例子中，例如，数字将是 3。因为我们会这样做:

1 - Apply rule 1 (abba)
2 - Apply rule 1 again (bbaba)
3 - Apply rule 2 (bababa)

可能会发生给定输入和目标但没有解决方案的情况，这也应该引起注意。

我几乎迷失了这样做的策略。我想到了创建一个自动机，但我不确定在这种情况下我将如何应用。我认为这是一个有趣的问题，我一直在网上研究，但我能找到的只是给定规则的转换，而不是如何确保它是最小值。

编辑:正如建议的答案之一，我们可以从初始字符串开始绘制图表，并创建节点，这些节点是对前一个节点应用转换的结果。但是，从我的角度来看，这会带来一些问题:

1. 假设我有一个看起来像这样的转换 a --> ab。我的初始字符串是“a”。我的输出字符串是“c”。所以，我继续像这样进行转换(增长图形):

   a -> abab -> ababb -> abbb...

我怎么知道什么时候需要停止构建图表？

1. 假设我有以下字符串 aaaa，并且我有一个像 aa->b 这样的转换规则。我将如何创建新节点？我的意思是，我如何找到该输入字符串中的子字符串并记住它们？

Answer 1

我认为对此没有有效的解决方案。我认为你必须进行广度优先搜索。这样一来，一旦您拥有一个解决方案，您就会知道它是最短解决方案。

编辑:

图片:先修改字符串宽度

每一层都是通过将所有可能的规则应用于所有可能的子字符串而从前一层构成的。例如，b->ba 规则可以应用于每个 b 的 abba。重要的是只应用一个规则，然后在列表中记住该字符串(例如 ababa 和 abbaa)。在开始下一层(=广度优先)之前，您必须在程序的列表中完全拥有每一层。

编辑 2:

你写你现在有一个输出c。为此，您显然需要一个带有 XX->c 的规则。所以说你有规则 aaa->c。现在在第 2 层中，您将有一个字符串 aaa，它来自一些 a->aa 规则。然后，您将再次应用 a->aa 并获得 aaaa，没关系，因为您应该先广度，然后再应用 aaa->c 规则到 aaa，现在第 3 层由 aaaa、c 和其他组成。您不要继续修改 aaaa，因为那样会转到第 4 层，您已经在第 3 层找到目标 c，因此您可以停止。

编辑 3:

你现在问你是否可以决定一组未指定的规则，你如何决定何时停止分层。一般来说这是不可能的，它被称为Halting problem https://en.wikipedia.org/wiki/Halting_problem .

但是对于特定规则，您可以判断是否可以达到输出。

• 示例 1:如果目标包含任何规则都无法提供的原子(您的“c”示例)。
• 示例 2:如果您的规则都是增加字符串的长度或保持长度不变(没有规则减少字符串的长度)
• 示例 3:如果通过算法发现某些规则是循环的，则可以删除它们
• 还有其他例子