Crosswords问题的智能程序实现

Crosswords问题的智能程序实现（-）课标要求：（三）人工智能语言与问题求解（1） 了解一种人工智能语言的基本数据和程序结构，掌握相关概念，知道人工智能语言的主要特征。（2） 初步学会使用该语言设计程序求解简单问题，并能够上机调试、执行相应的程序。例1用匹配方法解决简单的查询问题。（二）学情分析：学生在完成必修模块的学习后，会逐步对运用信息技术解决实际问题产生浓厚的兴趣，运用信息技术的意识会不断增强。特别是在完成了信息的编程加工与智能化加工的知识后，学生对于如何在计算机编制程序解题会比较关注。华南师大附中在选修课程的开设上，教师根据学生特点，针对高一奥林匹克班学生开设了《算法与程序设计》和《人工智能初步》两门选修课，两门课程的选学人数分别为18人和47人。很明显地看出，学生对人工智能的学习兴趣是比较大的。一方面与这模块的内容比较新颖有关，另一方面也与学生通过各种渠道认识计算机强大的计算能力，从而对计算机智能化认识的不全面有关。第一章的学习后，学生通过充分的体验，认识了人工智能学科的研究内容、主要技术和应用领域。由于大部分学生在选修本模块之前都没有学习程序设计的知识，第二章的教学设计将首先安排学生学习人工智能语言，给予学生更多的动手实践的时间和空间，让学生保持着对这一门技术难度较高的课程的学习兴趣。采用“程序设计”学习与理论知识同步的策略，在学习PROLOG人工智能语言的基础上，渗透教材中“知识”及“知识表示”的内容。PROLOG语言的学习实际上是一个载体，它可以让原本抽象的“知识”及“知识表示”具体化，学生可以在实践中更好地理解和体会这部分内容。学习程序设计语言一直以来都是信息技术教育中讨论的热点问题。在设计PROLOG教学时，要考虑遵循学生的认知规律，循序渐进地引领学生学习程序结构、语法及数据结构。因此，教学时尝试打破一般程序设计教学中“先讲语句语法，再编程序”的思路，直接从实用的角度和解决问题角度入手来认识PROLOG程序。教学过程中简易问题的PROLOG程序最好能够与自然语言的表达相近，推理过程要比较直观，这有助于学生对程序的阅读和理解，消除学生对语言语法学习的恐惧心理。情景案例的选择是本教学设计最重要的一个环节。对于高中生，人工智能初步教学采用的案例要有知识性，也要有趣味性，更要注意问题本身的复杂性。适度的复杂问题会激发学生的探索热情。案例的选择还要注意在程序中的实现，最好能够在PROLOG中用比较简单的算法就可以解决的。一般PROLOG教科书中会采用“家族谱（Family）”等经典例子作为学习PROLOG程序的入门程序。作者认为，这个程序在实用性和趣味性方面非常欠缺，问题的复杂度不够，未能体现计算机解决问题的效率优势。（三）教材分析：本课教学的内容是普通高中信息技术课程选修模块（5）《人工智能初步》中“人工智能语言与问题求解”的内容，对应广东版《人工智能初步》教材的第二章第一节的教学内容。教学中安排学生完成"Crosswords"（纵横字谜）英文单词游戏，学生在比较手工求解和使用程序求解过程中体验智能程序解决问题的效率与特点；掌握Prolog程序的运行方法；初步了解Prolog的程序结构，了解人工智能语言的主要特征。学习内容：典型的人工智能语言主要LISP、PROLOG、Smalltalk等。PROLOG是当代最有影响的人工智能语言之一，主要适合于处理逻辑推理问题。PROLOG语言很适合表达人的思维和推理规则，在自然语言、机器定理证明、专家系统等方面得到了广泛的应用，已经成为人工智能应用领域的强有力的开发语言。PROLOG用事实、规则描述问题，用询问启动系统，使用演绎推理自动求解问题。PROLOG程序由事实、规则、提问三种子句构成。在一个逻辑程序中，所有子句都是独立的，它们之间的关系在推理过程中是确定的。PROLOG的数据结构由一组相应的事实来描述，事实的存放、个数均是任意的，对事实可随机读取、随机更新。数据结构上的操作，则是基于事实库上规则调用。（1）问题的提出“纵横字谜”（CrosswordsPuzzles）是世界上广为流行的单词游戏，但它只有一个很短的历史。第一个英文单词“纵横字谜”游戏出现在19世纪的英格兰。如今，在美国“纵横字谜”已经发展为家喻户晓的休闲游戏。游戏要求玩家根据一定的规则在方格中填入单词，构成单词的字母会存在纵横交错连接的情况。给出若干汉字成语，也可构造此类游戏，如下图1所示。字谜游戏可以通过PROLOG程序实现高效率的求解，求解的结果准确且全面。（2）PROLOG程序设计“纵横字谜”是PROLOG语言编程的“入门级”案例。它主要体现了PROLOG语言接近自然语言，文法简捷，逻辑性强，易写易读，便于学习和使用等特点，也兼顾考虑到PROLOG求解程序的复杂度，程序体不长，仅涉及少量的谓词。用PROLOG解决本问题的要点是构造出表示各个成语和纵横方格解题的谓词，设置标记纵横方格和“交叉点”的变量。各个成语可以用PROLOG中的谓词words（大浪淘沙，大，浪，淘，沙）来表示，可读作“大浪淘沙是一个成语，它由大、浪、淘、沙这四个单字组成”。程序中各成语的谓词，构成本程序的事实库（知识库）。纵横方格共有五处，分别标记为五个变量R1、R2、C1、C2、C3（R表示Row，C表示列Column）。在各字之间的“交叉点”做上标记，表示为变量A、B、C、D等来实现，如图2所示。设游戏解题的谓词为crosswords（R1、R2、C1、C2、C3），推理规则是：crosswords（R1、R2、C1、C2、C3）:-words（R1,A,_,B,_）,words（C3,_,_,D,_）,write（"解题答案为："）.本程序在VisualPROLOG的PIE中运行通过。（3）知识归纳通过学习，学生将了解PROLOG语言的主要特点：PROLOG是一种描述型逻辑程序设计语言。PROLOG程序所描述的是各个被描述对象之间的逻辑关系，而并不是运算过程。用通俗的语言表达，即PROLOG要程序设计者讲清楚“做什么”，而不需要知道“怎么做”。PROLOG语言是在谓词逻辑证明过程的研究中诞生的，以一阶谓词演算为基础，是一种逻辑程序设计语言。PROLOG内部的推理机制是搜索、匹配和回溯，它提供了模式匹配和自动回溯功能。PROLOG是面向符号处理等非数值计算领域。通过游戏体验和程序求解的比较，学生初步学会PROLOG程序设计求解简单的问题。PROLOG程序设计包括简单PROLOG程序的设计、编写、调试和运行等。（一）教学目标：教与学的目标目标要求与内容描述知识与技能概念人工智能语言，Prolog程序，事实，规则，推理，匹配事实了解Prolog人工智能语言的主要特征了解Prolog程序的运行环境和推理机接口引擎（PIE）了解Prolog的程序结构

操作技能能够上机在PIE中运行调试Prolog的程序。初步学会使用Prolog语言设计程序求解简单问题。过程与方法过程从日常生活游戏中发现问题的存在，体验非结构化问题的解决过程。通过观摩人工智能语言程序设计的运行，初步认识人工智能知识与技术，从而获得对非结构化、半结构化问题解决过程的了解，知道人工智能程序=知识+推理。方法理解人工智能语言中运用匹配解决简单的查询问题的设计方法，掌握一般的逻辑推理方法。情感态度与价值观身心健康激发学生对人工智能技术学习的兴趣，消除人工智能专业技术神秘感。信息意识充分体验人类专家的对问题的求解思路和推理风格，培养学生多种思维方式，提高学生的分析、思维和判断能力。增强学生运用信息技术解决实际问题的意识与能力。价值内化培养有效地运用信息意识，迎接信息社会的挑战。（二）教学思路：教学过程将采用讲授与上机操作结合的教学方法。根据学生起点水平情况，教学时间可安排1或2课时。学习重点：1、以PROLOG语言为例，了解人工智能语言的主要特征；2、了解PROLOG程序的运行环境和推理机接口（PIE）的主要功能；3、 知道PROLOG程序“知识（事实）+推理规则”的基本结构；4、 能够上机在PIE中运行调试PROLOG的程序。学习难点：1、 逻辑推理2、 知识（事实）、规则3、 匹配4、 运行和调试PROLOG的程序教学策略：1、形成认识结构的策略设计两个简单的Crosswords游戏。先给出一个简易的中文连字的例子，限时完成，调动学生学习兴趣，形成学习氛围。在完成第一个题目的解题后，给出第二个7x7的英文单词连字的例子。学生这时候会感觉到难度会骤然增加，这是形成认知结构的第一步，学生产生认知冲突。在设计过程中，课堂上会安排学生对“手工”解题与“应用信息技术”解题进行比较，进一步突显出计算机人工智能语言的优势特征。引起学生对运用信息技术高效率解决问题的关注。为了减轻学生对程序设计语言的学习压力，教学情景案例所编制的PROLOG程序尽量贴近自然语言，方便学生对程序的阅读和理解，掌握PROLOG程序的基本结构。案例中的PROLOG程序设计的推理过程也是相对简单的，学生容易理解。这是形成认知结构的第三步。2、促进信息加工的教学策略适当结合游戏课件，使教学过程形象、生动。因为运用多媒体课件教学，可使学生手、脑、眼、耳并用，使学生有新颖感、惊奇感、独特感、直观感，能唤起学生的“情绪”和激发他们的兴趣，从而提高教学效率。教学过程中的游戏环节要求学生在《学习指导手册》中完成Crosswords游戏，有助于增加学生的学习注意力，对理解推理和知识这两个知识难点有帮助作用。《学习指导手册》中还安排PROLOG程序的填空题，可以让部分能力强的学生有拓展的空间。在学生上机操作阶段，教师要准备不少于3个的PROLOG程序案例，让学生在上机调试过程中有充分的运行调试程序