最短的操作序列,将文件树转换为另一个文件树

Question

给定两个文件树A和B,是否可以确定最短的操作序列或为了将A转换为B所必需的短序列操作？

操作可以是:

1. 创建一个新的空文件夹
2. 使用任何内容创建新文件
3. 删除文件
4. 删除一个空文件夹
5. 重命名文件
6. 重命名文件夹
7. 将文件移动到另一个现有文件夹中
8. 在另一个现有文件夹中移动文件夹

当A和B在相同的文件夹结构中具有相同内容(或相同大小相同CRC)和相同名称的相同文件时,它们是相同的.

这个问题一直困扰着我.目前我有以下基本想法:

• 计算数据库:
  • 存储文件名及其CRC
  • 然后,查找没有子文件夹的所有文件夹,并从它们包含的文件的CRC计算CRC,并从它们包含的文件的总大小计算大小
  • 升级树以为每个父文件夹创建CRC
• 使用具有数据库A和数据库B的以下循环:
  • 计算A∩B并从两个数据库中删除此交集.
  • 使用内部联接在A和B中查找匹配的CRC,首先按文件夹desc排序
  • 当有结果时,使用第一个结果使文件夹或文件移动(如果需要可能创建新文件夹),从两个数据库中删除结果的源行.如果有移动,则更新db A中新位置的父文件夹的CRC.
  • 然后删除数据库A中引用的所有文件和文件夹,并创建数据库B中引用的那些

但是我认为这实际上是一种不理想的方式.你能给我什么建议？

谢谢!

Answer 1

这个问题是树编辑距离问题的一个特例,为此找到一个最佳解决方案(不幸的是)已知是NP难的.这意味着对于一般情况可能没有任何好的,快速的和准确的算法.

也就是说,我链接的论文确实包含几个关于近似算法和算法的讨论,它们在问题的限制情况下工作.您可能会发现讨论很有趣,因为它阐明了解决此问题时实际出现的许多问题.

希望这可以帮助!并感谢发布一个很棒的问题!