搜索问题的代数描述及其算法

文中给出了搜索问题的一种代数描述方法，在这种描述方法的基础上，给出了一个算法模式．以货郎担问题的动态规划－分支限界算法为例，讨论了如何用所给出的算法模式来设计包含多种算法设计技术的算法，称这种算法为混合（ｈｙｂｒｉｄ）算法．还讨论了如何用面向对象的方法进行程序设计．这种求解问题的方法不仅为算法的自动生成提供了一种有力的工具，如果用面向对象的方法进行程序设计，还能提高代码的利用率．

基于Clifford半群上共轭搜索问题的密钥建立协议

本文采用更广泛的半群作为平台,推广了Iris Anshel等提出的代数密钥建立协议模型。在定义了Clifford半群上的多重同时共轭搜索问题(MSCSP)后,给出了基于此问题的密钥建立协议。在理论上证明了若Clifford半群上的多重同时共轭搜索问题(MSCSP)是困难的,那么可以利用MSCSP来构造密钥建立协议,从而说明利用半群作为平台构建密钥建立协议是可能的。本文也提供了一种新的利用辫群的思路,即考虑利用辫群上的强半格(许多辫群按照一定规则形成的无交并)构成的Clifford半群来构建密码协议,以弥补单个辫群可能存在的安全缺陷。

辫群上的扭结共轭搜索问题和密码体制研究

通过分析辫群的相关性质及群上的判定问题,结合扭结共轭问题、子群成员判断问题及根搜索问题,提出一种辫群上的公钥加密协议和签名协议,对两者的安全性进行分析,证明敌手无法从公钥中恢复密钥,因此协议可以抵抗长度攻击、惟密钥攻击、一般选择消息攻击、定向选择消息攻击和适应性选择消息攻击。

基于扭共轭搜索问题的有偏比特承诺

提出了基于扭共轭搜索问题的有偏比特承诺方案.(双)扭共轭搜索问题是指:已知G上的一对自同态(?),ψ及G中两元素w,t,找出s∈G,使得:t=ψ(s^(-1))w(?)(s).(假设至少存在一个这样的s.)给出了方案的正确性,安全性的证明,并且在一个具体的平台上讨论了密钥空间,参数设置,并且给出了安全性分析.

图搜索问题算法推导及形式化证明

用非形式化方法解决图搜索问题规模受限,对于一些复杂问题难以保证其正确性.传统的形式化方法推导图搜索问题难以理解且不易于形式化证明,现有形式化方法对这类问题的解决方案较少,在保证可靠性和正确性方面有欠缺.该文通过对图搜索问题的深入研究,开发出一种针对解决图搜索算法的新方法.首先刻画问题的规约,利用循环不变式的递归定义技术给出了开发图搜索问题循环不变式的新策略,在此基础上得到Apla抽象算法程序,并对该算法程序进行了形式化证明,再将已验证的Apla算法程序自动生成C++可执行程序,实现了从抽象的形式规约推演出具体的面向计算机的程序代码的程序精化完整过程.以拓扑排序和广度优先遍历为例对所提方法进行实验,实验结果验证了所提方法的有效性,不仅可以推导和证明已知算法,而且对未知算法的推导也有指导性作用.

基于扭共轭搜索问题的比特承诺

该文提出了一个新的基于扭共轭搜索问题的比特承诺方案,并且给出了方案的正确性、安全性的证明。扭共轭搜索问题比共轭搜索问题的优势是可以使基于长度的攻击变得无效,并且可以抵抗线性攻击。平台的选取是基于扭共轭问题的密码算法的安全性最关键的一点。最后在一个具体的平台上讨论了密钥空间、参数设置和安全性。

目标可移动的直线搜索问题的在线算法研究

直线搜索问题也被叫做迷失的奶牛问题,解决这个问题的算法叫做线性螺旋搜索。该算法被证明是解决这个问题的最佳在线算法,它的竞争比是9。如果这个问题中的目标可以移动,那么这个问题就被强化了。本文将提出被强化后的问题的最佳在线算法及其竞争比。Minimax定理在这个算法中扮演着重要角色。

WWW搜索问题——2003年第8期题解

WWW搜索问题的本质是在给定的字符串中找到包含关键字符集合中所有关键字符串的最短子串，对本题所涉及的部分概念理解如下。

有序序列搜索问题最快算法为二分法的一个理论证明

为了证明有序序列搜索问题最快算法为二分法,先由一个具体例子引入,得到问题描述与三条初步结论。再结合二分法定义由计算均值方法得到评价算法平均收敛速度的标准。最后由数学归纳法证明有序序列搜索问题每次迭代中迭代数的性质,进而证明解决有序序列搜索问题的所有算法中,二分法算法可以达到平均最快的收敛速度。

关于平面上的在线搜索问题(英文)

在计算机科学的各个领域中,用一个机器人在线搜索一个目标是一个热点问题.在这篇文章中,我们就在线搜索问题的研究结果做了简要的综述.首先,我们概述了在线搜索领域中的一些基本问题,其次,简要地介绍了国外学者在平面上在线搜索一个点和一条直线方面所取得的研究成果.

搜索问题答案也有技巧

现在有了问题，别忙着问别人，其实网上提供了相应的搜索，比如QQ的搜搜问问和百度知道。在浏览器中访问http：//wenwen．soso．com，登录之后即可进入问问首页搜索答案或提出问题。

车辆路径问题的禁忌搜索算法研究

简要回顾了车辆路径问题的禁忌搜索算法的发展现状,提出了一种改进的禁忌搜索算法。该算法将路径问题按不同的车辆-顾客分配结构分解成若干子问题,然后用禁忌搜索算法求解每个子问题,最后从所有子问题的最优解中选出全局最优解。理论分析和实验结果表明该算法比以往的算法有以下优点:拓展了搜索空间,提高了最优解的效果;是一种将问题进行空间分解的并行算法,可采用多台计算机同时运算以减少整体运行时间。

EIS 中问题解搜索的一般过程

讨论了用粒度的概念描述问题解搜索的基本理论，分析了ＥＩＳ数据源和信息组织的特点并提出搜索的一般过程．以ＳＸＷＧ－ＥＩＳ中外部信息模块为例，具体探讨了ＥＩＳ中问题解搜索的过程和形式化描述．

大规模层次分类中的候选类别搜索

大规模层次分类问题研究如何将互联网上的网页文档准确地分到类别层次中的各个类别.因为类别层次规模巨大,通常可以达到数千甚至数万个类别,严重影响了分类性能.对此,已有研究通过搜索待分类文档在类别层次中的候选类别对文档进行分类,但结果表明候选类别搜索成为了其中瓶颈.文中首先对候选搜索问题的计算复杂性进行了分析,证明了该问题是NP难的,接下来提出了一个基于贪心策略的启发式候选搜索算法,并且证明了该贪心策略在求解过程中是一个局部最优选择.作者采用DMOZ目录中的简体中文网页数据进行了实验论证,实验结果显示,相比已有算法,文中提出的候选类别搜索算法在候选类别搜索的准确率上提高了大约7.5%.

基于Clifford半群上幂等元问题的密钥建立协议的研究

密钥建立协议是为了以后的密码学应用而使一个秘密密钥对两方或更多方都可用的过程。目前大多数密钥建立协议都是基于有限域上的算术。本文采用半群作为平台,推广了Iris Anshel等提出的代数密钥建立协议模型。在定义了可计算的Clifford半群上的多重同时幂等元搜索问题(MSISP)后,提出基于此问题的密钥建立协议。证明了若Clifford半群上的多重同时幂等元搜索问题(MSISP)是困难的,那么可以利用MSISP来构造密钥建立协议。

数学建模中地面搜救问题浅探

本文对任务进行分析有三种想法:采用哈密尔顿路线进行搜索;转化为一个单旅行商问题;采用"搜索、行进"循环的方式进行。

认知心理学中的“问题解决”的研究成果及其对数学教学的启示（Ⅰ）

本文介绍了现代认知心理学中“问题解决”的一些研究成果，并探讨其对数学教学的启示．

R台装置搜索两个坏硬币的一个最优过程

通过对测试集的巧妙选取，给出了用ｒ台装置搜索两个坏硬币的本性理想模型Ｂｒｅ的一个最优测试过程．

一种基于哈希方法的相似性搜索

在解决高维数据的相似性搜索问题中,最具代表性的算法是局部敏感哈希算法,它将高维空间向量映射至低维汉明空间,并保持原空间向量相似性,使得新空间向量的汉明距离反映原空间向量相似度.本文介绍了局部敏感哈希算法的基本思路以及实现过程,分析了其还存在的不足——需要的大量的存储空间来保证查询效率.为此,尝试采用混合索引结构,在数据的搜索和处理过程对数据按出现次数进行分类,过滤无效数据,提高相似搜索的时间和空间效率.

问题解决

为了满足广大读者较系统地了解国外心理学的新兴学科的愿望,本刊决定陆续开辟认知心理学、管理心理学、工程心理学、教学心理学等讲座专栏。从这期开始,首先刊登认知心理学讲座。认知心理学,这是从五十年代末,六十年代初开始兴起,在七十年代取得重大进展的西方心理学研究的新方向。本刊一九八三年第四期刊登的张厚粲同志的"当前西方心理学的主要思潮——认知心理学"一文已对认知心理学的产生、对象、方法作了概要的介绍。该文可作为我们这个讲座的引论。从本期超,将分专题陆续介绍认知心理学的有关理论和研究成果。