浅谈问答式交互问题.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,答案只有一个,浅谈问答式交互问题,交互式问题的分类,分类依据：库函数和选手程序的关系,博弈式交互,问答式交互,博弈式交互,问答式交互,问答式交互的逻辑模型,最后的答案,发现之旅,我们的目标,把题目做对，拿到分数。,不管用什么方法，在题目允许的情况下完成此题,把题目做好。,用较好的方法把交互式题目做得简洁、漂亮。,用合适的方法，找出那唯一可能的解。,探讨这一类问题的解决策略。,触类旁通，争取为其它问题提供灵感。,我们的工具,解决问题的两种思路,思路一：“筛”法,一言以蔽之：减少答案的不确定性！,提问的选择范围：,可能降低问题不确定性的所有问题。,如何选择提出的问题：,随机选择；,平均信息量最大的,;,选最坏情况下筛去最多的；,古老的分类学,界：动物界,门：节肢动物门,纲：昆虫纲,目：双翅目,科：蝇科,属：蝇属,种：家蝇,结论：这是一只苍蝇！,思路二：构造法,构造一种提问题的序列，或者一种生成该序列的算法，按照这样的序列提问，找出唯一的符合题目意思的答案。,这是一种“一开始就有计划的提问方式”。,两种方法的比较,筛法,问题规模：不能太大,当前可能为答案的各个元素之间的逻辑关系不明显,思维难度：小,实现难度：大,往往不能准确估计最坏情况下提问次数,构造法,问题规模：任意,当前可能为答案的各个元素之间有明显的逻辑关系,思维难度：往往不小,实现难度：往往不大,往往可以准确估计最坏情况下提问次数,实战：进入问题之旅,要素,题目的模型,交互的方法,评分的标准,地下城市和太空站之谜,模型相似,交互方式相似,推论：解题策略相似？,事实上：解题策略不相似！,评分方式不相似！,地下城市：,M,太空站：,32768,地下城市和太空站之谜的启示,不同的评分标准，将决定不同的解题策略的使用！以不同的标准来评判不同的算法，优劣自然不同！,多数派,一个学校有奇数个学生，分成两个不相交的团体：多数派和少数派请你确定一个一定属于多数派的学生。,交互规则：给出学生编号，得到两个学生是不是同一个团体的信息。,评分：在,m,次提问后得到正确答案，一共有,n,个人。你的得分是,min(n-m,0),的线性函数。,警告：测试库迫使你进入最坏的情况，并且一旦你给出的学生可能属于少数派，我们就生成一个这样的例子作为本轮的测试数据。,多数派问题的解法一,N=11,少,多,解法一的分析,得分：,1,优点：简单，并且找出了每一个学生属于哪个团体。,缺点：过于简单，没有优化。虽然找出了每一个学生属于哪个团体，但是题目并没有要求我们这样做。,灵机一动：不找出每个学生属于哪个集合，仅确定一个属于多数派的学生！,多数派问题解法二,多数派问题解法二,不同组,相同组,调皮的小孩,A,B,B=,星星队,A=,星星队,星星队,月亮队,否,否,月亮队,月亮队,是,是,星星队,星星队,是,是,星星队,裁判,否,是,月亮队,裁判,是,否,小结,灿烂星河,IOI2000,中等硬度,IOI2002 Rods,冬令营,2002,太空站之谜,冬令营,2001,猜单词游戏,NOI 2002,调皮的小孩,CEOI2001,多数派,CEOI2001 Chain,IPSC 2002 Chamber of Secrets,POI Ulam,的游戏,大浪淘沙,千淘万漉虽辛苦，吹尽黄沙始到金！,