中文摘要：

离散空间上的容错搜索理论与网络通讯和网络编码有着密切的联系，作为多学科交叉领域已成为国际热点研究方向之一。本项目将研究有限离散空间上'具有时滞和遗失的容错搜索'问题，它涵盖已得到广泛研究的'容错搜索'问题。我们将重点研究以下两类模型（I）研究"单目标具有时滞和遗失的q-维e-容错搜索模型"，主要针对自由提问格式、区间型提问格式、双区间型提问格式、大小受限提问格式等且e=1,2的情形，给出其worst-case最优算法；（II）研究"两目标适应的2-维e-容错搜索模型"，主要针对自由提问格式且e=1,2的情形，给出其worst-case最优算法。本项目研究新模型，也将探索新的研究手段，其可行性已经在前期的研究工作中得到充分验证。

结论摘要：

本项目依据研究计划，围绕预期目标，取得的主要成果如下（1）针对‘small set’限制，给出了在搜索目标服从均匀分布的条件下，单目标受限制的q+1维搜索模型的average-case 最优的序列算法，完全确定出最优平均长度的精确表达式。（2）通过精确设计前两次提问方式，使得前两次提问后所到达的可能状态均为‘typical state’，进而针对搜索空间{1,2,...,n}，确定出单目标2容错双区间提问搜索模型找到搜索目标所需的最小提问次数。（3）针对两目标适应的2-维自由提问格式搜索,研究了a-Wythoff、(s,t)-Wythoff以及Wythoff-like三类模型。我们将国外学者A.S. Fraenkel及M. Ozery关于a-Wythoff博弈的结果推广到更一般的(s,t)-Wythoff博弈，同时又将(s,t)-Wythoff博弈的结果推广到Wythoff-like模型，从而深入探讨了博弈规则的改变如何影响博弈双方的取胜策略。（4）研究了仅受一个‘动态指针限制’以及同时受到一个‘动态指针限制’和一个‘modular限制’两类新模型。针对这两类受限新模型，我们获得了在normal约定下任何一方能够取胜的充分必要条件，并给出了相应的取胜策略。（5）研究了“单目标同时具有时滞和容错的2维连续型搜索模型”。我们区分凸区域和非凸区域两种不同类型，分别得到了相应的结果，有些获得了最优搜索策略，有些获得了较优的界。（6）研究了多人博弈模型。针对单目标受‘small set’限制的两个联盟对抗问题，获得了在misere约定下一个联盟能够取胜的充分必要条件，并给出了相应的取胜策略。针对单目标自由提问模式下采用“标准偏好矩阵”时所对应的模型，获得了在misere约定下每个博弈者能够取胜的充分必要条件，并给出了相应的取胜策略。