怎样在阿里巴巴上做网站重庆房产信息网官网

怎样在阿里巴巴上做网站,重庆房产信息网官网,中国网站建设公司有哪些内容,软件开发专业就业[算法设计与分析-从入门到入土] 回溯法 个人导航 知乎#xff1a;https://www.zhihu.com/people/byzh_rc CSDN#xff1a;https://blog.csdn.net/qq_54636039 注#xff1a;本文仅对所述内容做了框架性引导#xff0c;具体细节可查询其余相关资料or源码 参考文章…[算法设计与分析-从入门到入土] 回溯法个人导航知乎https://www.zhihu.com/people/byzh_rcCSDNhttps://blog.csdn.net/qq_54636039注本文仅对所述内容做了框架性引导具体细节可查询其余相关资料or源码参考文章各方资料文章目录[算法设计与分析-从入门到入土] 回溯法个人导航回溯法Backtracking1.三色着色问题(3-coloring problem)2.八皇后问题(8-queens problem)通用回溯法适用问题解向量步骤回溯法Backtracking本质:有组织的穷举搜索核心目标: 避免搜索所有可能性将搜索空间缩减到更小范围1.三色着色问题(3-coloring problem)给定无向图G ( V , E ) G(V,E)G(V,E)用三种颜色如1、2、3为 V 中每个顶点着色要求任意两个相邻顶点颜色不同总可能方案数n个顶点的图共3 n 3^n3n种合法/非法着色方案搜索树所有可能着色集合可表示为“完全三叉树”部分解不完全着色方案中所有已着色的相邻顶点颜色均不同终止条件找到一种合法解即终止回溯规则若部分解变为“死节点”返回上一个节点若回溯至根节点则修改根节点颜色无需存储整个搜索树仅需存储“根节点到当前活动节点的路径”实际上无物理节点生成整棵树是隐式的只需跟踪颜色分配情况例子:2.八皇后问题(8-queens problem)在8×8棋盘上放置8个皇后使得任意两个皇后无法相互攻击两个皇后处于同一行、同一列或同一对角线上时可相互攻击为简化理解通常以“四皇后问题”为示例展开分析核心逻辑与八皇后完全一致例子:通用回溯法适用问题适用于“解为向量形式”的搜索问题解的通用形式为( x 1 , x 2 , … , x i ) (x_1, x_2, \dots, x_i)(x1​,x2​,…,xi​)其中 i 的取值固定i如3着色问题、8皇后问题可变i部分问题中不同解对应的i可能不同解向量元素取值解向量中每个x i x_ixi​属于有限的线性有序集合X i X_iXi​遍历规则按字典序遍历笛卡尔积X 1 × X 2 × ⋯ × X n X_1 \times X_2 \times \dots \times X_nX1​×X2​×⋯×Xn​中的元素X i X_iXi​是位置i对应的可选元素集合步骤算法以“空向量”为初始状态逐步向向量末尾添加元素过程中通过“有效性判断”决定“推进”或“回溯”:初始启动从空向量开始选择X 1 X_1X1​中的最小元素作为x 1 x_1x1​得到部分向量( x 1 ) (x_1)(x1​)迭代构建假设已得到部分向量( x 1 , x 2 , … , x j ) (x_1, x_2, \dots, x_j)(x1​,x2​,…,xj​)下一步尝试添加X j 1 X_{j1}Xj1​的最小元素得到新向量v ( x 1 , x 2 , … , x j , x j 1 ) v (x_1, x_2, \dots, x_j, x_{j1})v(x1​,x2​,…,xj​,xj1​)有效性判断与分支处理对新向量v vv进行判断分三种情况处理情况1v 是最终解记录该解若问题只需要一个解算法直接终止情况2v 是部分解非最终但可继续扩展继续推进选择X j 2 X_{j2}Xj2​的最小元素重复步骤2情况3v 无效既非最终解也非部分解子情况3.1X j 1 X_{j1}Xj1​仍有未选元素将x j 1 x_{j1}xj1​替换为X j 1 X_{j1}Xj1​的下一个元素重复步骤3子情况3.2X j 1 X_{j1}Xj1​无未选元素执行回溯——将x j x_jxj​替换为X j X_jXj​的下一个元素若X j X_jXj​也无未选元素继续回溯至x j − 1 x_{j-1}xj−1​以此类推直到找到可替换的元素或回溯至空向量无更多解