如何计算将一个排序顺序转换为另一个排序顺序的绝对最小变化量？

Question

目标

如何使用尽可能少的数据对描述如何将静态列表从一个订单重新排序到另一个订单的数据进行编码？

我有一种感觉,有一个算法或计算机科学术语可以帮助我,但现在我太过坚持问题,找出其他方法来看待它.

背景动机

我有一个部署到远程位置的程序,所有通信都是通过间歇性的极其昂贵的卫星连接进行的.这有点夸张,但数据成本接近每千字节一美元,每天只能发生几次.

在一天开始时,向用户提供项目列表,他们在现场外出并做东西,但最终结果或多或少是以不同顺序排序的相同项目列表.还有其他数据,但这对这个问题并不重要.

现在我发回所有发生的动作的记录并按顺序播放它们.当用户对系统感到满意时,移动记录列表开始接近仅发回所有项目的大小,并且通常移动的某些组合导致撤消先前的移动记录.

假设

• 起始列表和结束列表由完全相同的项目组成
• 每个项目都有一个唯一的id(32位整数)
• 每个项目都有一个唯一的排序oder(32位整数)
• 用户将拥有数百至数千或更多项目的列表
• 用户通常会在一天内重新订购约100件商品
• 可以检测到对订单的更改将项目移动到列表中的新位置
• 一些"移动"可能会撤消之前的移动
• 用于计算最佳解决方案的计算资源是便宜/无限的
• 传输时间很昂贵
• 发回更改数据比发回整个列表便宜

最简单的数据结构

出于解决此问题的目的,假设以下数据结构可用.

• 项目清单
  • ITEM_ID
  • 排序
• MoveRecord
  • item_a_id
  • new_a_position

这是一个示例列表.每个列表中的项目是相同的.请注意,即使只有少数项目已更改,但每个项目ID都有一个新的排序顺序,因此您不能只发送新的item_id/sort_order_id对.

**List 1: Original List**    **List 2: Re-ordered List**    
order - id                    order - id
     1. 10                         1. 90
     2. 20                         2. 30
     3. 30                         3. 40
     4. 40                         4. 50
     5. 50                         5. 60
     6. 60                         6. 10
     7. 70                         7. 80
     8. 80                         8. 70
     9. 90                         9. 20

如何使用尽可能少的数据编码将列表1的顺序转换为列表2的顺序所需的更改？

好奇心是否有可能证明解决方案是最优的？

更新

一位同事指出,"交换"可能不是正确的思考方式.您还可以将项目发送到列表的顶部或底部,这更像是一个移动而不是交换.交换然后变成两个动作的组合.

谢谢你的指点.到目前为止,我没有看到有保证的最佳解决方案.此外,问题只是改变了一点.

如果我无法证明任何单个方法产生最佳结果,那么我将使用每种方法找出解决方案并使用指示所用方法的小标头发回该解决方案.继续建议解决方案,我将用我的研究更新这个问题.

感谢大家!

Answer 1

一个快速解决方法可能是使用Zobrist 哈希来发现您返回到先前订单的情况。也就是说，每次交换后，根据您达到的排列计算哈希值。每个散列映射到迄今为止针对该特定排列找到的最短交换序列。

这可以通过一些探索性搜索轻松扩展 - Zobrist 哈希是作为优化博弈树搜索的一种方式而发明的。

当然，很容易对交换数量给出严格的下限 - 不在所需位置的物品数量。然而，这个下限是否真的可以实现，是一个更困难的问题。