arrays - 0's and 1' 数组的状态数是多少

Question

给定一个只有 0 和 1 的数组。

如果 0 位于 1 的左侧，则它们交换它们的值

计算使数组右侧全为 0 的步数。

示例 1如果数组=[0 1 0 0 1 0 1 0 1]

[1 0 0 1 0 1 0 1 0]

[1 0 1 0 1 0 1 0 0]

[1 1 0 1 0 1 0 0 0]

[1 1 1 0 1 0 0 0 0]

[1 1 1 1 0 0 0 0 0]

the Answer is ```5``` steps.

示例 2如果数组=[0 1 0 1 0]

[1 0 1 0 0]

[1 1 0 0 0]

答案= 2

我编写了代码来执行要求的操作。但是对于大尺寸的数组来说它非常慢:(请帮忙

Answer 1

我认为使用 A* 搜索 和 hamming 之类的 heuristic 函数可以最好地解决这个问题(我们需要证明启发式是 可接受的)。以下是步骤:

1. 对于给定的数组，首先计算我们想要达到的目标数组(简单地排序数组降序)。
2. 将问题表示为(图形)搜索问题，其中源节点是给定数组，相邻节点定义为可通过单个 0 1 交换获得的数组。
3. 将源节点推送到优先级队列，其中优先级定义为与源节点的距离的总和 (f(. )) 和来自目标节点的启发式函数 (h(.)=hamming distance)。队列中优先级最低的节点将首先被弹出，任意断开连接。
4. 迭代地从优先队列中弹出一个节点，直到到达目标节点，并将所有尚未访问的相邻节点插入队列，更新弹出节点与源的距离。<
5. 一旦 goal 节点弹出就停止。