代码分享｜带新下界算法和支配规则的精确式算法解决非限制性集装箱翻箱问题

前言

解决非限制性集装箱翻箱问题的精确式算法的概念和原理在之前中已有过介绍，本文为代码分享，在阅读本文之前请先学习推文论文拾萃|带新下界算法和支配规则的精确式算法解决非限制性集装箱翻箱问题。

项目代码基于C99编写，代码下载链接：https://github.com/jinboszu/ucrp-idbb

原论文：An exact algorithm for the unrestricted container relocation problem with new lower bounds and dominance rules", Bo Jin*, Shunji Tanaka, European Journal of Operational Research, Volume 304, Issue 2, 16 January 2023, Pages 494-514. https://doi.org/10.1016/j.ejor.2022.04.006

参考文献：

• JZW(evaluation heuristic)算法：Jin, B., Zhu, W., & Lim, A. (2015). Solving the container relocation problem by an improved greedy look-ahead heuristic. European Journal of Operational Research, 240(3), 837–847. https://doi.org/10.1016/j.ejor.2014.07.038.
• SM-2算法：Tricoire, F., Scagnetti, J., & Beham, A. (2018). New insights on the block relocation problem. Computers & Operations Research, 89, 127–139. https://doi.org/10.1016/ j.cor.2017.08.010.

问题回顾

该算法主体为迭代加深搜索框架，下面我们结合代码中的方法来回顾一下。

迭代加深搜索框架:

• 首先对输入的 进行多次retrievable操作使其最小化为 。
• 再使用代码中的lowerbound，即选择LB-N,LB-TS,LB-TS中的一个方法计算根下界lb。
• 使用代码中的upperbound（对应Probe函数），即JZW或SM2方法初始化搜索阈值 ，方法返回长度值和一个已知最优解 。
• 如果得到的下界等于阈值，则找到最优解；如果下界小于阈值，使用search函数，在搜索过程中，利用支配规则（dominance rules）去除不符合规则的节点，得到子节点 ，判断是否完成搜索。若未完成，则产生一个动态下界f，比较f与 。
• 若f大于 ，说明真正的阈值大于当前阈值 ，令 ，继续循环。
• 若 ，则使用probe方法得到新解S，并检验解是否为最优
• 若经过以上步骤仍未得到最优，则以一定规则对候选分枝集合中的节点排序并遍历，每次遍历再使用一次search函数。

前一篇推文中未介绍LB-N算法，下面将进行简单介绍

LB-N:

1. 首先初始化高度向量 ，其中 表示堆栈s的当前高度。
2. 进入迭代，在每次迭代中，算法找到block堆最高层具有最高优先级的block，即为目标容器。
3. X是包含所有目标容器的集合，其中目标容器的位置（s，t）满足s在S中，t在1到ηs之间，并且 等于 。
4. X⊥是X的子集，包含了那些没有其他目标容器位于它们上方的目标容器。
5. 对于X⊥中的每个目标容器（s∗，t∗），算法会依次处理以下步骤：
• 记录堆栈s∗的旧高度为 。
• 设置堆栈s∗的高度为t∗ - 1，同时移除容器（s∗，t∗）以及在它上方的所有容器。
• 对于X⊥中的每个目标容器，尝试将堆栈s∗的高度恢复为 。
• 调用Check函数来验证是否可能通过强制重定位操作使所有位于目标容器（s∗，t∗）上方的容器得到良好放置。如果Check函数返回True，算法立即终止并返回B+1，其中B是配置C中的坏放置容器总数。
• 如果Check函数返回False，再次移除容器（s∗，t∗）以及在它上方的所有容器。
6. 如果所有 Check 调用都返回 False，则算法返回 B。

Check函数：

• 先找到非满堆栈中q最大的堆栈，用于后续的比较。

• 创建一个集合 D 包含那些可用于放置阻挡容器的堆栈。D 包含满足以下条件之一的堆栈：

• 堆栈高度小于T；
• 堆栈高度为T，但堆栈顶部为坏放置容器，并且堆栈上方的容器优先级不高于qmax。

• 对于每个堆栈 ，执行以下步骤：

• 如果存在阻挡容器的优先级 ps∗,t 高于 D 中所有堆栈的当前 θs 值，即无论这个block移动到哪里，都会造成额外的relocation，则返回 True，表示无法通过强制重定位操作来使容器（s∗，t∗）得到良好放置。
• 否则，选择 D 中具有最大 θs 值的堆栈 s'，使得 θs' 满足 ps∗,t ≥ θs'。这是一种贪婪选择，表示选择一个可以最容易地重定位容器（s∗，t）的堆栈。更新堆栈 s' 的 θs' 值为 ps∗,t，表示容器（s∗，t∗）被放置在堆栈 s' 上。
• 初始化一个临时质量值 θs，初始值为堆栈 s 的当前质量。
• 从目标容器（s∗，t∗）的位置开始，逐层处理堆栈 s 上方的阻挡容器，从顶部向底部。

代码讲解

问题的解由数组hist存储，如下图的数据结构所示。

list和rank数组：list以优先级值排序，rank存储了不同stack对应list的索引。

//state.c
int compare_stack(int s1, int s2, int *h, int **q, int **b) {
return q[s1][h[s1]] != q[s2][h[s2]] ? q[s1][h[s1]] - q[s2][h[s2]]
: b[s1][h[s1]] - b[s2][h[s2]];
}
/*
compare_stack用于比较两个栈 s1 和 s2 的顶部元素。它首先比较栈 s1 和 s2 顶部元素的质量q，
如果不相等，则返回质量的差值；
如果质量相等，则返回badness的差值。
*/

static void adjust_left(state_t *state, int s){
int i = state->rank[s];
while (i > 0 && compare_stack(s, state->list[i - 1], state->h, state->q,
state->b) < 0) {
state->list[state->rank[state->list[i - 1]] = i] = state->list[i - 1];
i--;
}
state->list[state->rank[s] = i] = s;
}
/*
adjust_left用于将堆s在rank中排名提高，即将堆s的rank值在rank数组中向左移动
*/

static void adjust_right(state_t *state, int s) {//同理
int i = state->rank[s];
while (i < state->n_stacks - 1 &&
compare_stack(s, state->list[i + 1], state->h, state->q, state->b) >
0) {
state->list[state->rank[state->list[i + 1]] = i] = state->list[i + 1];
i++;
}
state->list[state->rank[s] = i] = s;
}


所以在relocate_out,relocate_in函数中，block移动之后会更新堆s的rank值。

下面重点讲解search函数。

//algorithm.c
static bool search(int level, branch_t *children) {
n_nodes++; // 增加节点计数

/*
* 检查时间限制
*/
if (++n_timer == timer_cycle) {
n_timer = 0;
if (get_time() >= end_time) {
return true; // 如果达到时间限制，返回true
}
#if defined(VERBOSE) || !defined(NDEBUG)
debug_info("running"); // 打印调试信息
#endif
}

/*
* 当前状态
*/
int curr_lb = hist[level].lb; // 当前下界
state_t *curr_state = hist[level].state; // 当前状态
memory_t *curr_memory = hist[level].memory; // 当前的memory

//以下为准备参数阶段
/*
* Prepare TC, IB
*/
if (level > 0) {
int min_last_change_time = level + 1;
for (int s = 0; s < n_stacks; s++) {
min_last_change_time_fw[s] = min_last_change_time;
if (curr_state->h[s] < n_tiers &&
min_last_change_time > curr_state->last_change_time[s]) {
min_last_change_time = curr_state->last_change_time[s];
}
}

int max_last_relo_out_time = 0;
for (int s = n_stacks - 1; s >= 0; s--) {
max_last_relo_out_time_bw[s] = max_last_relo_out_time;
if (max_last_relo_out_time < curr_state->last_relo_out_time[s]) {
max_last_relo_out_time = curr_state->last_relo_out_time[s];
}
}
}

/*
* Prepare EA
*/
int leftmost = -1;
for (int s = 0; s < n_stacks; s++) {
if (curr_state->h[s] == 0) {
leftmost = s;
break;
}
}

/*
* Prepare SC, SD
*/
if (level > 0) {
memset(group_src_bw[0], 0, sizeof(int) * (max_prio + 1) * n_stacks);
for (int sk = 0; sk < n_stacks; sk++) {
if (curr_state->last_change_type[sk] == RELOCATE_OUT) {
int k = curr_state->last_change_time[sk];
int pk = path[k - 1].pri;
for (int s = 0; s < sk; s++) {
if (group_src_bw[pk][s] < k) {
group_src_bw[pk][s] = k;
}
}
}
}

memset(group_dst_bw[0], 0, sizeof(int) * (max_prio + 1) * n_stacks);
for (int dk = 0; dk < n_stacks; dk++) {
if (curr_state->last_change_type[dk] == RELOCATE_IN) {
int k = curr_state->last_change_time[dk];
int pk = path[k - 1].pri;
for (int d = 0; d < dk; d++) {
if (group_dst_bw[pk][d] < k) {
group_dst_bw[pk][d] = k;
}
}
}
}
}

/*
* 准备分支
*/
copy_state_body(hist[level + 1].state, curr_state, true);
int size = 0;

//这段嵌套for循环的作用是遍历relocation所有的可能，同时通过规则判断来减少计算量
/*
* Enumerate source stack
*/
for (int sn = 0; sn < n_stacks; sn++) {
/*
* 检查源栈的可行性
*/
if (curr_state->h[sn] == 0) {
continue;
}

int pn = curr_state->p[sn][curr_state->h[sn]];
int q_sn = curr_state->q[sn][curr_state->h[sn]];
int lv = curr_state->l[sn][curr_state->h[sn]];
int lid = curr_memory->lid[sn][curr_state->h[sn]];

/*
* Lower bounding
*/
int temp_lb = curr_lb - (pn > q_sn) - (lid != -1);
if (level + 1 + temp_lb > best_lb) {//粗略检查下界是否优于当前最优下界
continue;
}


/*
* Check TA, TC
*/
if (lv > 0) {
int k = lv;
int sk = path[k - 1].src;
if (curr_state->last_change_time[sk] == k &&
curr_state->last_change_type[sk] == RELOCATE_OUT) {
continue; // TA
}

if (min_last_change_time_fw[sn] < k) {
continue; // TC
}
}

/*
* Check SC
*/
if (level > 0) {
if (curr_state->last_change_time[sn] < group_src_bw[pn][sn]) {
continue;
}
}

/*
* Prepare temporary state and memory
*/
copy_state_head(temp_state, curr_state, true);
reuse_state_body(temp_state, hist[level + 1].state);

relocate_out(temp_state, sn, level + 1, true);

if (lid != -1) {
copy_memory(temp_memory, curr_memory, n_stacks, n_tiers);
temp_memory->n_layers--;
for (int s = 0; s < n_stacks; s++) {
temp_memory->lid[s][temp_memory->tau[lid][s]] = -1;
}
}

/*
* Update path when generating branches
*/
path[level].pri = pn;
path[level].src = sn;

/*
* Enumerate destination stack
*/
for (int dn = 0; dn < n_stacks; dn++) {
/*
* Check feasibility
*/
if (dn == sn || curr_state->h[dn] == n_tiers) {
continue;
}

/*
* Check EA
*/
if (curr_state->h[dn] == 0 && dn != leftmost) {
continue;
}

/*
* Check TB
*/
if (curr_state->last_change_time[dn] < lv) {
continue;
}

/*
* Check IB
*/
if (level > 0) {
int k = max_last_relo_out_time_bw[sn];
if (curr_state->last_change_time[sn] < k &&
curr_state->last_change_time[dn] < k) {
continue;
}
}

/*
* Check SA, SB, SD
*/
if (level > 0) {
if (curr_state->last_change_type[dn] == RELOCATE_OUT) {
int k = curr_state->last_change_time[dn];
int pk = path[k - 1].pri;
int dk = path[k - 1].dst;
if (pk == pn) {
if (curr_state->last_change_time[sn] < k) {
continue; // SA
}
if (curr_state->last_change_time[dk] == k) {
continue; // SB
}
}
}
if (curr_state->last_change_time[dn] < group_dst_bw[pn][dn]) {
continue; // SD
}
}

int q_dn = curr_state->q[dn][curr_state->h[dn]];

/*
* Lower bounding
*/
if (level + 1 + temp_lb + (pn > q_dn) > best_lb) {
continue;
}

state_t *child_state = children[size].child_state;

copy_state_head(child_state, temp_state, true);
reuse_state_body(child_state, hist[level + 1].state);

relocate_in(child_state, dn, pn, level + 1, true);

/*
* Update path when generating branches
*/
path[level].dst = dn;

bool dominated = false;
while (is_retrievable(child_state)) {
int s_min = child_state->list[0];
int p = child_state->p[s_min][child_state->h[s_min]];
int l = child_state->l[s_min][child_state->h[s_min]];

/*
* Check RA
*/
if (l > 0) {
int k = l;
int sk = path[k - 1].src;
if (child_state->last_relo_out_time[sk] == k &&
child_state->last_relo_in_time[sk] < k &&
hist[k - 1].state->q[sk][hist[k - 1].state->h[sk]] == p) {
dominated = true;
break;
}
}

/*
* Check RB
*/
if (l > 0) {
int k = l;
for (int d = 0; d < s_min; d++) {
if (hist[k - 1].state->h[d] < n_tiers &&
child_state->last_relo_out_time[d] < k &&
child_state->last_relo_in_time[d] < k &&
hist[k - 1].state->q[d][hist[k - 1].state->h[d]] >= p) {
dominated = true;
break;
}
}
if (dominated) {
break;
}
}

retrieve(child_state, level + 1, true);
}

if (dominated) {
continue;
}

/*
* Goal test
*/
if (child_state->n_blocks == 0) {
best_ub = level + 1;
memcpy(best_sol, path, sizeof(relocation_t) * best_ub);
time_to_best_ub = get_time();
#if defined(VERBOSE) || !defined(NDEBUG)
debug_info("goal");
#endif
return true;
}

/*
* Child lower bound
*/
memory_t *child_memory = children[size].child_memory;
bool inherited = false;
int inherited_n_layers = curr_memory->n_layers - (lid != -1);
if (inherited_n_layers == 0) {
inherited = has_empty_stack(child_state);
} else {
for (int s = 0; s < n_stacks; s++) {
if (child_state->h[s] == inherited_n_layers) {
inherited = true;
break;
}
}
}
if (inherited) {
copy_memory(child_memory, lid != -1 ? temp_memory : curr_memory,
n_stacks, n_tiers);
child_memory->lid[dn][curr_state->h[dn] + 1] = -1;
}
int child_lb;
switch (lb_type) {
case LB_N:
child_lb = curr_lb - 1 > child_state->n_bad
? curr_lb - 1
: lb_n_impl(child_state, array_s1, array_s2, array_s3,
array_s4);
break;
case LB_TS:
child_lb = inherited ? child_state->n_bad + child_memory->n_layers
: lb_ts_impl(child_state,
best_lb - level - child_state->n_bad,
array_s1, child_memory);
break;
default: // LB_PS:
child_lb =
inherited
? child_state->n_bad + child_memory->n_layers
: lb_ps_impl(child_state, best_lb - level - child_state->n_bad,
pending, active, array_s1, array_s2, child_memory);
break;
}

/*
* Lower bounding
*/
if (level + 1 + child_lb > best_lb) {
continue;
}

/*
* Probing
*/
//probing的解释在下一段
if (level + 1 + child_lb == best_lb - 1) {
n_probe++;
if (ub_type == JZW || ub_type == HYBRID) {
copy_state(probe_state, child_state, false);
int new_len = jzw_impl(probe_state, path, level + 1, best_ub - 1);
if (new_len != -1) {
best_ub = new_len;
memcpy(best_sol, path, sizeof(relocation_t) * best_ub);
time_to_best_ub = get_time();
#if defined(VERBOSE) || !defined(NDEBUG)
debug_info("update");
#endif
if (best_lb == best_ub) {
return true;
}
}
}
if (ub_type == SM2 || ub_type == HYBRID) {
copy_state(probe_state, child_state, false);
int new_len = sm2_impl(probe_state, path, level + 1, best_ub - 1);
if (new_len != -1) {
best_ub = new_len;
memcpy(best_sol, path, sizeof(relocation_t) * best_ub);
time_to_best_ub = get_time();
#if defined(VERBOSE) || !defined(NDEBUG)
debug_info("update");
#endif
if (best_lb == best_ub) {
return true;
}
}
}
}

children[size].pri = pn;
children[size].src = sn;
children[size].dst = dn;
children[size].q_src = q_sn;
children[size].q_dst = q_dn;
children[size].child_lb = child_lb;
size++;
}
}

// 如果有子分支，则对子分支进行排序并递归搜索
if (size > 0) {
qsort(children, size, sizeof(branch_t), compare_branch);

state_t *child_state = hist[level + 1].state;

for (int i = 0; i < size; i++) {
path[level].pri = children[i].pri;
path[level].src = children[i].src;
path[level].dst = children[i].dst;

hist[level + 1].lb = children[i].child_lb;
reuse_state_head(child_state, children[i].child_state);
hist[level + 1].memory = children[i].child_memory;

int dn = path[level].dst;
if (child_state->h[dn] == curr_state->h[dn] + 1) {
set_block(child_state, dn, child_state->h[dn], path[level].pri,
level + 1, true);
}

if (search(level + 1, children + size)) {
return true;
}
}
}

return false;
}


JZW和SM-2都是用来搜索节点并选择具有较少relocation次数的解作为结果

search函数中，调用JZW函数时，尝试在level + 1的层级上，以best_ub - 1为上界，找到更好的解，其中best_ub是当前的最佳上界。jzw_impl函数会返回新的长度（new_len）作为上界；如果new_len不等于-1，表示找到了更好的上界，那么它会更新best_ub为new_len，并复制path中的路径信息到best_sol中，还会记录时间以便跟踪何时达到新的上界。如果此时已经达到最佳下界（best_lb等于best_ub），就返回true表示问题已经被解决。调用SM2时同理。

int jzw_impl(state_t *state, relocation_t *path, int len, int len_limit) {
if (len + state->n_bad > len_limit) {
return -1;
}

int n_stacks = state->n_stacks;
int n_tiers = state->n_tiers;
int *h = state->h;
int *list = state->list;
int *rank = state->rank;
int **p = state->p;
int **q = state->q;
int **b = state->b;

while (state->n_bad > 0) {
while (is_retrievable(state)) {
retrieve(state, len, false);
}

int q_min = q[list[0]][h[list[0]]];//list[0]为q最小的一个stack
int i_next = -1;
for (int i = 0; i < n_stacks; i++) {//寻找被移动的block
int s = list[i];
if (q[s][h[s]] > q_min) {
break;
}

//下列不等式为true，则除s外的stack剩余足够多的空位，可以将坏块移入
if (b[s][h[s]] <= (n_stacks - 1) * n_tiers - (state->n_blocks - h[s])) {
i_next = i;
break;
}
}
if (i_next == -1) {
return -1;//没有空位，不能移动
}

int i_max;
int q_max;
for (int i = n_stacks - 1;; i--) {
int s = list[i];
if (i != i_next && h[s] < n_tiers) {
i_max = i;//找可移入的空位
q_max = q[s][h[s]];//记录此位置的q值
break;
}
}

bool has_multi_q_max = false;
if (q_min < q_max) {//检验是否存在多个具有相同q_max的stack
for (int i = i_max - 1;; i--) {
int s = list[i];
if (q[s][h[s]] < q_max) {
break;
}
if (h[s] < n_tiers) {
has_multi_q_max = true;
break;
}
}
}

int src = list[i_next];
int dst;

//寻找移入和移出的stack
if (p[src][h[src]] <= q_max) {//找dst
for (int i = i_next + 1;; i++) {
int s = list[i];
if (h[s] < n_tiers && p[src][h[src]] <= q[s][h[s]]) {
dst = s;//src的优先级值小于q[s][h[s]，可以移入s
break;
}
}

int x = -1;
if (h[dst] < n_tiers - 1) {//目标stack是否有空位
for (int i = 0; i < rank[dst]; i++) {//查找可能更新的src
int s = list[i];
if (s != src && b[s][h[s]] > 0 && p[src][h[src]] <= p[s][h[s]] &&
p[s][h[s]] <= q[dst][h[dst]] &&
(x == -1 || p[x][h[x]] < p[s][h[s]])) {
x = s;//选择优先级值不小于src，且不大于dst的q值的坏block
}
}
}
if (x != -1) {
src = x;//将src的块变为查找到的x
}
}

else {//p[src][h[src]] > q_max，即src移动到哪都仍然是坏块，则尝试找新的src
if (len + state->n_bad == len_limit) {//是否达到长度限制
return -1;
}

int i_opt = -1;//i_optimal，即最优的i，此处为潜在的目标stack
//从当前 i_max 开始，以 dir 方向递增或递减 i，dir 的初始值是1，表示正向遍历。
for (int dir = 1, i = i_max;; i += dir) {
int s = list[i];
if (i == n_stacks || (i > i_max && q[s][h[s]] > q_max)) {
dir = -1; //i超过最大stack数量/i大于当前imax并且q大于qmax
i = i_max - 1;//这种情况下反转遍历方向，
s = list[i];//获取imax-1对应的栈值
}
if (q[s][h[s]] == q_min) {//找到了与list[0]相同q值的stack，则未找到i-opt
break;
}
if (b[s][h[s]] == 0 && p[src][h[src]] <= q[s][h[s] - 1] &&
(i != i_max || has_multi_q_max)) {
//s上没有坏块，i不为imax或有多个具有qmax的堆，src优先级值不大于s前一层的q值
i_opt = i;
break;
}
}

if (i_opt != -1) {
src = list[i_opt];
for (int dir = -1, i = i_opt - 1;; i += dir) {//反向遍历
int s = list[i];
if (i < i_opt && q[s][h[s]] < p[src][h[src]]) {//放入src后增加s坏块数量
dir = 1;
i = i_opt + 1;
s = list[i];
}
if (h[s] < n_tiers) {//放入src后不增加s坏块数量且s处有空位
dst = s;
break;
}
}

int x = -1;
if (h[dst] < n_tiers - 1) {//dst空位数量大于1
for (int i = 0; i < rank[dst]; i++) {//遍历排在dst前面的stack
int s = list[i];
//s上还有坏堆块，s的优先级值不小于src，不大于dst的q值，或者出现比x更大的优先级值
if (s != src && b[s][h[s]] > 0 && p[src][h[src]] <= p[s][h[s]] &&
p[s][h[s]] <= q[dst][h[dst]] &&
(x == -1 || p[x][h[x]] < p[s][h[s]])) {
x = s;
}
}
}
if (x != -1) {
src = x;
}
} else {
dst = list[i_max];// 如果没有找到i_opt，选择i_max作为dst
if (h[dst] == n_tiers - 1) {//dst只有一个空位
for (int k = 1; k < b[src][h[src]]; k++) {//src坏块多于1
if (p[src][h[src] - k] < p[src][h[src]]) {//若顶层向下第k个优先级较大
for (int i = i_max - 1; i >= 0; i--) {//向左遍历stack
int s = list[i];
if (s != src && h[s] < n_tiers) {//寻找最靠近imax的空余stack
dst = s;
break;
}
}
break;
}
}
}
}
}

if (path != NULL) {
path[len].pri = p[src][h[src]];
path[len].src = src;
path[len].dst = dst;
}//更新路径
relocate(state, src, dst, ++len, false);//执行并记录relocate操作
}

return len;
}


SM-2:

int src = -1;
int dst = -1;
int best_diff = INT_MAX;

if (q_min < q_max) {
for (int i = 0; i < i_max; i++) {
int from = list[i];
if (h[from] == 0) {
// 空stack
break;
}
if (b[from][h[from]] > 0 && p[from][h[from]] <= q_max) {
// from有坏块且优先级不大于qmax
for (int j = i + 1;; j++) {
// i之后的
int to = list[j];
int diff = q[to][h[to]] - p[from][h[from]];
if (diff >= best_diff) {
break;
}
if (h[to] < n_tiers && diff >= 0) {
// diff大于0表示移入后不增加坏块数量
src = from;
dst = to;
best_diff = diff;
break;
}
}
}
}
}

if (best_diff == INT_MAX) {
// 无论移入哪里都会增加坏块数量
if (len + state->n_bad == len_limit) {
return -1;
}

// 再次检查q_min和q_max之间是否有块可以移动
if (q_min < q_max) {
for (int i = 0; i < n_stacks; i++) {
int from = list[i]; // 当前源堆栈
// 如果源堆栈的q值大于q_max，退出循环
if (q[from][h[from]] > q_max) {
break;
}
// 如果源堆栈没有坏块且不是i_max或者存在多个最大q值
if (b[from][h[from]] == 0 && (i != i_max || has_multi_q_max)) {
int s_bad = -1; // 最适合的坏块堆栈
int s_bad_alt = -1; // 备选坏块堆栈

// 再次遍历堆栈列表以查找可能的目标堆栈
for (int j = 0; j < n_stacks; j++) {
int s = list[j]; // 当前堆栈
// 如果s堆栈的q值大于等于from堆栈的第二层的q值，退出循环；小于则继续
if (q[s][h[s]] >= q[from][h[from] - 1]) {
break;
}
int diff = q[from][h[from] - 1] - p[s][h[s]];
// 如果s堆栈有坏块且差异大于等于0且小于最佳差异
if (b[s][h[s]] > 0 && diff >= 0 && diff < best_diff) {
// 更新坏块堆栈和备选坏块堆栈
if (s_bad == -1 || p[s_bad][h[s_bad]] < p[s][h[s]]) {
s_bad_alt = s_bad;
s_bad = s;
} else if (s_bad_alt == -1 || p[s_bad_alt][h[s_bad_alt]] < p[s][h[s]]) {
s_bad_alt = s;
}
}
}

// 如果找到适合的坏块堆栈
if (s_bad != -1) {
int to = -1; // 目标堆栈
// 再次遍历堆栈列表，这次反向遍历以找到可能的目标堆栈
for (int dir = -1, j = i - 1;; j += dir) {
int s = list[j]; // 当前堆栈
// 如果当前方向是向左且s堆栈的q值小于from堆栈的q值，改变方向继续搜索
if (dir == -1 && q[s][h[s]] < p[from][h[from]]) {
dir = 1;
j = i + 1;
s = list[j];
}
int diff = q[from][h[from] - 1] - p[s_bad][h[s_bad]] + q[s][h[s]] - p[from][h[from]]; // 计算差异
// 如果差异大于等于最佳差异，退出循环
if (diff >= best_diff) {
break;
}
// 如果目标堆栈有空位，更新目标堆栈
if (h[s] < n_tiers) {
to = s;
break;
}
}

// 如果找到合适的目标堆栈
if (to != -1) {
// 如果坏块堆栈不是目标堆栈，更新源堆栈和目标堆栈以及最佳差异
if (s_bad != to) {
src = from;
dst = to;
best_diff = q[from][h[from] - 1] - p[s_bad][h[s_bad]] + q[to][h[to]] - p[from][h[from]];
} else {
if (s_bad_alt != -1) {
// 计算从s_bad_alt到to的迁移差异（坏块数量减少，移动到更低的优先级位置）
int diff = q[from][h[from] - 1] - p[s_bad_alt][h[s_bad_alt]] + q[to][h[to]] - p[from][h[from]];

if (diff < best_diff) {
// 如果该迁移差异更小，更新src和dst以及最佳差异值
src = from;
dst = to;
best_diff = diff;
}
}

// 遍历rank[to]之前或之后的堆栈
for (int dir = (rank[to] < i ? -1 : 1), j = rank[to] + dir; j <= i_max; j += dir) {
int s = list[j]; // 当前堆栈
if (dir == -1 && q[s][h[s]] < p[from][h[from]]) {
dir = 1;
j = i + 1;
s = list[j];
}

// 计算从s_bad到s的迁移差异
int diff = q[from][h[from] - 1] - p[s_bad][h[s_bad]] + q[s][h[s]] - p[from][h[from]];

if (diff >= best_diff) {
break; // 如果差异大于等于当前最佳差异，退出循环
}

if (h[s] < n_tiers) {
src = from;
dst = s; // 更新src和dst
best_diff = diff; // 更新最佳差异值
break;
}
}
}
}
}
}
}
}

if (src == -1) {//仍未找到，直接使用inext和imax
src = list[i_next];
dst = list[i_max];
}
}


以上是代码解析的全部内容，希望能对你有所帮助。

转载自久章智能（微信公众号，久章智能于 2023-12-19 转载），内容保持原貌，版权归原作者及原账号所有。阅读原文 ↗