2

假设我有一个输入字符串，例如： 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 -> ab ab -> abb abb -> abbb ...

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

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

1 回答 1

3

我认为没有有效的解决方案。我认为您必须进行广度优先搜索。通过这样做，您将知道，只要您有一个解决方案，它就是一个最短的解决方案。

编辑：

图片：先修改字符串宽度

首先搜索字符串宽度

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

编辑 2：

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

编辑 3：

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

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

  • 示例 1：如果目标包含任何规则都无法提供的原子（您的“c”示例）。
  • 示例 2：如果您的规则都是增加字符串的长度或保持长度不变（没有减少字符串长度的规则）
  • 示例 3：如果您通过算法发现某些规则是循环的，则可以删除某些规则
  • 存在其他示例
于 2013-02-22T21:59:15.353 回答