求解一类组合问题的智能回溯法

本文给山一种求解一类组合问题的智能回溯法及其应用条件。若用智能回溯法求解顶点着色等问题将比经典回溯法快若干倍。     

九位不同数字乘法等式的递归与非递归回溯算法

对"九位不同数字构成乘法等式"的问题进行分析,设计了递归回溯算法和非递归回溯算法,给出NP问题穷举算法设计的一般思路,同时比较两种算法的特点,并进行实验测试.     

《算法设计与分析》课程中“回溯法”教学探讨

《算法设计与分析》是计算机科学与技术专业居于核心地位的专业课程,其中"回溯法"因其较强的实用性经常出现在各级计算机竞赛中,因此,本文从课堂教学及实践教学两个环节分别对"回溯法"的教学方法进行了探讨。     

数独求解的候选数优化算法设计

从数独的候选数集合特性出发,通过分析数独游戏的要求,针对标准数独,提出了四条优化规则。避免了计算机回溯法的完全枚举,得到候选数优化回溯法,减少了搜索次数,提高了求解的速度。并且针对3×3的数独,分别给出显性候选数规则跟隐形候选数规则的两个特例,得到了3×3数独的相应的6条优化准则。用两个数独难题进行验证,可知本算法相对于回溯法,节省了三分之一的时间,证明了所提算法的有效性。     

基于历史线索与考试预期的自动组卷算法研究

在分析目前两种常用自动组卷算法的基础上,结合典型的题库结构提出一种基于历史线索与考试预期进行试题优选的算法,该算法可以对试卷的难度和试题分布进行均衡的控制,避免系统盲目选题和试题聚集现象,从而提高组卷的质量和效率.     

排课系统中混合算法的应用研究

排课系统比较复杂又具有智能特点,其算法主要有模拟手工算法、回溯算法、遗传算法、贪心算法等.在软件开发过程中,发挥每种算法优点以提高排课的科学性、高效性和合理性是个重要课题.结合成功研制排课系统的经验,阐述了不同算法的应用,提出了通过所有算法的混合应用解决排课问题的方法.     

N皇后问题Las Vegas优化算法的实现

介绍了n皇后问题常用的回溯解决策略,分析了概率算法中拉斯维加斯(LasVegas)算法的特点及其在n皇后问题中的应用,并给出了两者结合解决n皇后问题的算法策略和效率分析.     

高校排课系统的设计与实践

文章分析了高校排课问题及造成排课困难的各种因素。提出了一种结合贪心算法和回溯算法的混合型排课算法,从理论上阐述算法的可行性,在实践上,改算法在解决复杂的高校排课问题时有较好的效果。     

迷宫游戏的设计与开发

在Eclipse平台上,选择Java语言完成迷宫游戏的设计与开发。采用随机布点算法生成不规则迷宫地图,采用图的深度优先遍历算法随机生成规则地图。在相同的窗口,运用地图格的大小不同来生成较低、中等、较高三种不同难度的规则或不规则地图。把走迷宫的对象设置成角色方块,使用键盘的方向键控制当前移动点进行游戏。按照遍历规则地图的起点不同,把游戏分简单,中等,高难三种难易程度。运用回溯法从入口一步步进行探索,最后找到迷宫出口,并在界面上显示出该路径。编写画布类函数Canvas()实现游戏设置。游戏的成功开发表明,算法研究至关重要,应用这些算法开发游戏是有效的。     

试验回溯问题的算法模版设计

讨论试验、回溯问题的通用算法 ,即称为算法模版 .利用算法模版 ,可使程序代码自动生成 .对简化此类问题的求解有实际意义     

盒子中蛇问题回溯算法

研究了盒子中的蛇问题,即求ｎ方体Ｑ＾ｎ中最大导出环Ｓｎ问题;已知｜Ｓ２｜＝４,｜Ｓ３｜＝６,｜Ｓ４｜＝８,｜Ｓ５｜＝１４,｜Ｓ６｜＝２６,通过回溯算法证明了｜Ｓ７｜＝４８,｜Ｓ８｜≥９４,并给出猜想｜Ｓｎ｜≤２｜Ｓｎ－１｜－２（ｎ≥３）。该猜想对３≤ｎ≤７已成立。     

在有向图中寻找哈密顿回路的快速回溯法

本文提出了回路段的新概念。并在此基础上给出了寻找有向图中所有哈密顿回路 的快速回溯法ＱＢ．算法ＱＢ通过合并回路段来生成哈密顿回路，它的回溯树上各顶 点的期望分枝数ｃｑ等于各层当前图可用顶点的最小出度的平均值。对于常规的简单 回溯法ＳＢ，回溯树上各顶点的期望分枝数ｃｓ等于各层当前可用顶点的平均出度的 平均值。显然，ｃｑ总是小于ｃｓ．算法ＱＢ的期望时间为Ｏ（ｎ２（ｃｑ）ｎ），而算法ＳＢ期 望时间为Ｏ（ｎ（ｃｓ）ｎ），ｎ为图中顶点数。     

维特比译码的双读出回溯算法及ASIC实现

在分析维特比译码器回溯算法的基础上，归纳出回溯算法的规律，提出了双读出回溯（ＤＲＴＢ）算法。计算表明，ＤＲＴＢ算法在不增加硬件开销的情况下，使回溯运算速度达到原来的４倍。本文还介绍了基于ＤＲＴＢ算法幸存路径存储器单元（ＳＭＵ）的ＡＳＩＣ结构和物理设计。对半导体集成电路的测试表明，本文提出的ＤＲＴＢ算法及电路结构是成功的。     

三个典型问题的回溯算法

介绍了排列问题、组合问题和皇后问题的回溯算法,对《算法设计与分析》课程的学习以及参加“大学生数学建模竞赛”与“中学生奥林匹克信息学（计算机）竞赛”等具有一定指导意义。     

元皇后问题回溯算法改进

回溯算法是解决N元皇后问题最有效的算法之一.在传统回溯算法的基础上,采用动态规划的思想,对算法进行了改进,改进后的算法大大降低了求解的复杂度和比较次数.文章还给出了改进算法的实现并通过理论分析和实验数据证明了算法的可行性.     

车厢调度问题的算法实现

讨论了如何利用回溯法设计车厢调度问题的一个递归算法。     

基于BIT位运算的N皇后问题解法

皇后问题是一经典的回溯算法问题,本文使用B IT位运算对非递归的回溯算法进行优化,取得了较好的效果,对其他类似问题的算法的优化有一定指导意义。     

计算机考试系统抽题算法的哈希函数描述

计算机考试系统广泛地应用于各种考试，其中抽题算法的优劣在某种程度上决定了考试系统的性能．本文运用数据结构中的“哈希函数”为模型表述了回溯抽题算法，分析了试题库的知识点模型和试题的冲突处理，对考试系统的设计有一定的理论指导意义．     

马步遍历问题与骑士巡游问题的回溯算法

马步遍历问题与骑士巡游(knight's tour)问题是指在有8×8方格的国际象棋棋盘上进行奇异的骑士L型(L-shaped)移动的问题。而骑士巡游问题实际是带有约束条件的马步遍历问题,因此在用程序求解的时候可以一并求解。本文给出求解这一问题的回溯算法之C++语言程序。     

基于线性规划的构件优选机制研究

针对特定领域构件组装的特点,重点探索了构件组装过程中的优选机制。将组装中构件选择问题转化为在一组线性约束条件下目标函数优选的数学问题,利用回溯法求得最优解,进而确定用于系统组装的构件。该机制可以避免组装后对系统的反复验证,提高构件复用的准确性和效率。同时,也降低系统组装者对领域知识的要求。