面向Lightpoint状态间低成本修改的高效算法方案问询

需求说明 #

我正在开发一款算法，需要计算将Lightpoint对象列表修改至目标状态的最低成本方案。Lightpoint包含位置、标签及存在状态属性，起始与目标列表的规模完全一致。各操作的成本/收益规则如下：

• 创建Lightpoint成本：200
• 删除Lightpoint收益：-150（即删除可获得150的收益）
• 移动成本：100
• 重标成本：50

当前实现的瓶颈 #

当前的实现思路是：为每个目标状态生成所有可能的转换操作（共n²种，任意起始Lightpoint可转换为任意目标Lightpoint），再生成所有操作排列并过滤无效项。但该方案会产生n^n量级的排列，仅10个Lightpoint时计算就需要约10秒，完全无法支撑50-100个节点的规模。

转换示例 #

// 初始状态：
// A 位于 (1,1)
// B 位于 (2,2)
// C 位于 (3,3)

// 目标状态：
// B 位于 (1,1)
// A 位于 (2,2)
// C 位于 (3,1)

// 可能的转换方案：
// 方案1：
// A 移动到 (2,2)（成本：100）
// B 移动到 (1,1)（成本：100）
// C 移动到 (3,1)（成本：100）
// 总成本：100+100+100=300

// 方案2：
// A 修改标签为 B（成本：50）
// B 修改标签为 A（成本：50）
// C 移动到 (3,1)（成本：100）
// 总成本：50+50+100=200

// 方案3：
// C 移动到 (1,1) 并修改标签为 A（成本：100+50）
// A 移动到 (2,2) 并修改标签为 B（成本：100+50）
// B 移动到 (3,1) 并修改标签为 C（成本：100+50）
// 总成本：100+50+100+50+100+50=450

// ... 其他可行转换方式

寻求帮助 #

现寻求可支持50-100个Lightpoint规模的最优或近似最优算法方案，可参考原型实现代码（OptimalAlignment.zip）。

内容的提问来源于stack exchange，提问作者Robin Dittrich