问题求解与程序设计搜索.PPT

问题求解与程序设计第七讲 搜索李文新2004.2 2004.6 内容提要 搜索 讨论 1011 stick 讨论 1054 the troublesome frog 参考王知昆的冬令营报告 作业搜索的一般概念 在 解空间中尝试所有可能，找出满足条件的取值 回顾填数游戏： 1-9填在 3*3的表格中，使得行、列、对角线的和均为 15。 方程组 搜索 逐一尝试 +剪枝题目讨论 1011 stick题目讨论 The Troublesome Frog IOI 2002 day 1 task 1问题 稻田问题 青蛙从外面跳入稻田，踩过一些禾苗，后，跳出稻田。问题 蛙路：一个方向，等间距，大于等于 3个点 不同蛙路：可以方向不同，间距不同问题 许多青蛙跳过稻田，形成多条蛙路，不同蛙路可以踩过同一作物。问题 青蛙每天早上踩坏稻田，早上人们发现稻田有若干株作物被踩坏，但不知多少青蛙来过。也有不在蛙路上的被踩坏的作物。