首页 > 其他分享 >非时序回溯与时序回溯代码分析2(2023-9-7)

非时序回溯与时序回溯代码分析2(2023-9-7)

时间:2023-09-08 15:34:59浏览次数:40  
标签:std 回溯 时序 trail nInd 2023 nMaxLevel

采用CB+NCB的方式后传播序列trail各层中的文字层序属性发生了变化,原有层数的递增、同层文字属于单一层序发生了变化。


 

[1] Alexander Nadel, Vadim Ryvchin:Chronological Backtracking. SAT 2018: 111-121 

In particular, the decision level of the variables in the assignment trail is no longer monotonously increasing.

赋值轨迹中变量的决策水平不再单调递增


 

涉及决策水平不在单调递增的相关函数及其代码段如下:

 

//传播函数后半段代码

 1 CRef Solver::propagate()
 2 {
 3    。。。
 4            if (value(first) == l_False){
 5                 confl = cr;
 6 
 7                 //--------------------------------------------------------
 8                 conflTrailIndex = qhead -1;  //记录冲突点索引
 9                 if( conflTrailIndex == trail_lim[trail_lim.size() - 1] )
10                 {
11                     confLitIsDecLit_Tag = 1;
12                 }                                           
13                 //--------------------------------------------------------
14 
15                 qhead = trail.size();
16                 // Copy the remaining watches:
17                 while (i < end)
18                     *j++ = *i++;
19             }else
20             {
21                 if (currLevel == decisionLevel())
22                 {
23                     uncheckedEnqueue(first, currLevel, cr);
24 #ifdef PRINT_OUT                    
25                     std::cout << "i " << first << " l " << currLevel << "\n";
26 #endif                    
27                 }
28                 else
29                 {
30                     int nMaxLevel = currLevel;
31                     int nMaxInd = 1;
32                     // pass over all the literals in the clause and find the one 
with the biggest level 33 for (int nInd = 2; nInd < c.size(); ++nInd) 34 { 35 int nLevel = level(var(c[nInd])); 36 if (nLevel > nMaxLevel) 37 { 38 nMaxLevel = nLevel; 39 nMaxInd = nInd; 40 } 41 } 42 43 if (nMaxInd != 1) 44 { 45 std::swap(c[1], c[nMaxInd]); 46 *j--; // undo last watch 47 watches[~c[1]].push(w); 48 } 49 50 uncheckedEnqueue(first, nMaxLevel, cr); 51 #ifdef PRINT_OUT 52 std::cout << "i " << first << " l " << nMaxLevel << "\n"; 53 #endif 54 } 55 }
。。。

 

 

 

 

   

 

标签:std,回溯,时序,trail,nInd,2023,nMaxLevel
From: https://www.cnblogs.com/yuweng1689/p/17687721.html

相关文章

  • 2023牛客暑期多校训练营4
    A.BoboStringConstruction题意:给定一个01串t,构造一个长度为n的01串s,时的t+s+t中t只在首和尾出现。分析:结论,s取全0或者全1。①假设t全0或者全1,那我s和t取相反的即可。②假设t既包含0又包含1,首先t不可能是s的子串,那我们只需考虑t是否可以由t的后缀加上s再加上t的前缀得......
  • 2023/09/08
    问题:在HYS项目中,主要工作是,从正式库中通过脚本将表结构等创建到备库中,但是在备库中建表的时候,速度特别慢,创建一张表需要七八分钟,不正常。问题排查:(1)首先通过命令iostat和top指令来查看当前服务器中的io写入和cpu使用率。结果发现都正常。接着在isql中手动创建一张表发现速度依然很......
  • 世和基因亮相2023服贸会,中国精准检测技术走向世界
    9月6日,2023中国国际服务贸易交易会在北京圆满收官,本届服贸会围绕“开放引领发展,合作共赢未来”年度主题,吸引了全球领先的创新技术和科研成果亮相盛会,累计入场近28万人。作为国内肿瘤精准医学头部企业,世和基因受邀参展,并以“立足中国,服务全球”为主题,亮相健康卫生服务专题展区。众多......
  • WC / CTS 2023
    没做通信和poly。*loj3928.「CTS2023」琪露诺的符卡交换tag:正则二分图的完美匹配,构造。把卡片看成\(n\timesn\)的矩阵,我们的目标是交换一些方格使得每一行都是一个排列。考虑把所有列都换成排列,然后把矩阵转置。那么假设已经确定了前\(k\)列,要确定第\(k+1\)列,问题相......
  • 2023.9.8——每日总结
    学习所花时间(包括上课):9h代码量(行):0行博客量(篇):1篇今天,上午数学建模比赛,下午数学建模比赛+上课。我了解到的知识点:1.学习使用excel的vlookup函数其具体使用方式为:【公式】->【插入函数】第一行代表需要搜索的值;第二行代表搜索的区域;第三行代表返回匹配值是哪一列;第四行输......
  • 深入理解回溯算法及其应用
    回溯算法是一种经典的问题求解方法,常被用于解决组合优化、搜索和排列问题。它通过不断尝试不同的选择,并在每一步做出回溯(回退)来找到问题的解。在本篇博客中,我们将深入探讨回溯算法的原理、应用场景以及一些实际案例。什么是回溯算法?回溯算法是一种暴力搜索的方法,它通过穷举所有可能......
  • idea2023.2版本配置tomcat
    1,首先确保tomcat已经配置好,运行正常2,打开idea,右键项目,找到addframesupport(添加框架结构),我这里没有,所以我是在help,findaction搜索addframesupport(注意要先点击选中项目)  4,找到选中即可,勾选web.appliction 出现如图所示即可 5,添加java文件存放的地方classes......
  • wzOI 2023.8.24 模拟赛(附树的直径和三分法)
    2023-08-2815:53:53$$A$$典型错误一知半解看样例型:如果该队某个数组的值比最大值大就算入答案。上第一次厕所前我的思路:开局\(30\)分钟。显然,我并不需要有一个数值最大才能赢,我只需要其中一个数值比其中一个数值比其中一个数值最大的那个要大的队要大即有可能获胜......
  • wzOI 2023.8.31 题解
    2023-09-0115:59:41$$前言$$太菜了,第一题都打成那样了没发现是MST,第三题数据范围没有很仔细看,以为是乱搞(组合之类的)题就直接跳了。不得不说这次比赛题目的一些思路还是挺妙的,一些想法确实我这种成分想不太到。$$A$$$$题意$$给出了\(m\)个可以查询的区间\([L_i,R_i]\)......
  • 【2023-09-07】“35”边界
    20:00一个人的力量是很难应付生活中无边的苦难的。所以,自己需要别人帮助,自己也要帮助别人。                                                 ——茨威格今天中午,老板......