最新心理学第七章 情绪、情感课件PPT.ppt 87页

'心理学第七章情绪、情感 第一节情绪、情感的概述一．什么是情绪和情感：㈠情绪、情感的定义：情绪和情感是人对客观事物的态度体验及相应的行为反应。㈡情绪情感的成分主观体验（subjectiveexperience）生理唤醒（physicalarousal）外部表现（motionalexpression） 心理学家研究了英语使用者的交往现象后发现，在日常生活中，55％的信息是靠非言语表情传递的，38％的信息是靠言语表情传递的，只有7％的信息是靠言语传递的。 表情：面部表情体态表情言语表情 （二）感染功能个人由于知觉到另一个人正在体验某种情绪，自己也产生相应的情绪性体验，即人们之间的情绪情感可以相互影响，西方心理学把这种现象称为情感移入，类似于我们日常生活中所说的情感共鸣。一个人的情感会影响他人的情感，而他人的情感反过来又会影响这个人原先的情感，使人与人之间的情绪情感相互影响。这是情绪情感感染功能所导致的必然结果。 （三）调节功能情绪和情感可以调节和影响认知过程。适当的情绪情感对认知过程具有积极的组织效能，而不适当的情绪情感则对认知过程具有消极的瓦解作用。 （四）对健康的促进和损害功能（适应作用）古代阿拉伯学者阿维森纳，曾把一胎所生的两只羊羔置于不同的外界环境中生活：一只小羊羔随羊群在水草地快乐地生活；而在另一只羊羔旁拴了一只狼，它总是看到自己面前那只野兽的威胁，在极度惊恐的状态下，根本吃不下东西，不久就因恐慌而死去。 医学心理学家还用狗作嫉妒情绪实验：把一只饥饿的狗关在一个铁笼子里，让笼子外面另一只狗当着它的面吃肉骨头，笼内的狗在急躁、气愤和嫉妒的负性情绪状态下，产生了神经症性的病态反应。实验告诉我们：恐惧、焦虑、抑郁、嫉妒、敌意、冲动等负性情绪，是一种破坏性的情感，长期被这些心理问题困扰就会导致身心疾病的发生。一个人在生活中对自己的认识与评价和本人的实际情况越符合，他的社会适应能力就越强，越能把压力变成动力。 四、情绪的理论㈠詹姆斯－兰格的情绪外周说：刺激情境生理反应情绪㈡沙赫特的情绪三因素说：情绪的产生是环境因素、生理因素和认知因素整合的结果，其中认知是最重要的因素。㈢坎农的情绪丘脑说：情绪的中心在中枢神经系统的丘脑。 第二节情绪、情感的种类和状态一、情绪的种类：㈠原始情绪：1、快乐：因为需要、目标得到满足而产生的一种情绪体验。其程度取决于愿望的强度。2、悲哀：因为所热爱事物的失去或愿望幻灭而产生的一种情绪体验。 3、愤怒：行为、愿望受到干扰或者累积压力和紧张而产生的一种情绪体验。4、恐惧：由于缺乏准备、不能处理或半拖危险情景而产生的一种情绪体验。常伴有回避或反击行为。 (二)情绪的状态：1、心境(mood)：（1）比较平静而持久的情绪状态。（2）心境产生的原因：2、激情(intenseemotion)：（1）一种强烈的、爆发性的短暂的情绪状态。（2）激情的外部表现： 3、热情热情是一种强有力的、稳定而深厚的情绪状态。4、应激(stress)：（1）对某种意外的环境刺激做出的适应性反应。（2）应激的两种表现：当机立断惊慌失措 二、高级的社会性情感：1、道德感(moralfeeling)：道德感是根据一定道德标准评价别人或自己言行时所产生的情感。2、理智感(rationalfeeling)：理智感是指在智力活动中，在认识和评价事物时所产生的情感。3、美感(aestheticfeeling)：根据一定的审美标准评价事物时所产生的情感。 第三节情绪、情感的品质与调控一、情绪、情感的品质㈠情绪、情感的倾向性；㈡情绪、情感的深刻性；㈢情绪、情感的稳定性；㈣情绪、情感的效能。 二、情绪、情感的调控㈠帮助学生形成正确的人生观和价值观；㈡培养和发展学生的正当需要；㈢深化学生的认识；㈣通过实践活动培育情感；㈤不良情绪、情感的调适与消除。 情绪控制八大技术制怒术：做情绪的主人，当喜则喜，当悲则悲。在遇到发怒的事情时，一思发怒有无道理，二思发怒后有何后果，三思有其他方式替代吗?这样就可以变得冷静而情绪稳定。愉悦术：努力增加积极情绪。具体方法有三：一是多交友，在群体交往中取乐；二是多立小目标，小目标易实现，每一个实现都能带来愉悦的满足感；三是学会辩证思维，可使人从容地对待挫折和失败。幽默术：常笑多幽默。心理学家认为，人不是因为高兴才笑，而是因为笑才高兴，不是因为悲伤才哭，而是因为哭才悲伤。生活中要多笑勿愁。 助人术：学雷锋做善事，既可以给他人带来快乐，也可使自己心安理得，心境坦然，具有较好的安全感。宣泄术：遇到不如意、不愉快的事情，可以通过运动、读小说、听音乐、看电影、找朋友谈心诉说来宣泄自己不愉快的情绪，也可以大哭一场。代偿转移术：当需求受阻或者遭到挫折时，可以用满足另一种需要来代偿。这一门课没考好，可争取在另一门课上取得好的成绩，也可以通过分散注意力，改变环境来转移情绪的指向。 升华术：即把受挫折的不良情绪引向崇高的境界。如著名文豪歌德在失恋后，把失恋的情绪能量升华到文学写作中，写出了名篇《少年维特之烦恼》。放松术：心情不佳时，可以通过循序渐进、自上而下放松全身，或者是通过自我催眠、自我按摩等方法使自己进入放松入静状态，然后面带微笑，想像曾经经历过的愉快情境，从而消除不良情绪。 酸葡萄心理与甜柠檬心理读过伊索寓言的人都知道狐狸吃萄葡的故事。狐狸想吃萄葡，但够不着，狐狸为减轻自己达不到目的而产生的焦虑感，自我安慰说“葡萄是酸的”，既然是酸的，那没有什么好吃的，狐狸平静地走了。借用这个故事，心理学把个体所追求的目标受到阻碍而无法实现时，以贬低原有目标来冲淡内心欲望，减轻焦虑情绪的行为称之为“酸萄葡心理”。生活中常常可以见到这类行为。如求爱不成，虽内心深感失望，但却安慰自己，说对方并不那么值得爱；考研失败，说本来就没想上。 当个体所追求的目标受到阻碍而无法实现时，为了保护自己的价值不受外界威胁，维护心理的平衡，当事人会强调自己既得的利益，淡化原来目标的结果，以减轻失望和痛苦。这种心理反应被称为“甜柠檬心理”。就像狐狸找不到可口的食物，却找到一只酸柠檬，于是自我安慰道，“这柠檬正合我的口味，我就喜欢吃酸的”。例如，联欢会上被人邀请跳舞，其实很喜欢但不会跳，又不愿承认，就说自己喜欢安静，喜欢欣赏舞曲音乐；对自我则安慰道：跳舞没什么好，出一身大汗，还要回去洗澡。再如，研究生考试失利，就说早工作早挣钱，真上研究生经济上亏大了。 酸萄葡心理和甜柠檬心理都是个体为减轻痛苦和紧张，保护自尊而采取的心理防御作用，为自己找理由辩护，自圆其说。从心理健康的角度看有一定意义，在某种程度上可以起到缓解消极情绪的作用。 三、情绪调节的基本过程1、生理调节情绪生理性调节可以改变和降低处于高唤醒水平的苦恼。如有研究发现，抑制厌恶可以降低躯体活动和心率，抑制悲伤可以降低躯体活动，但不能降低心率等。2、情绪体验调节个体体验过于强烈时，会自动进行调节。如研究发现忽视可以有效地降低厌恶感，抑制快乐表情会降低快乐感等。 3、行为调节：通过控制和改变自己的表情和行为来实现，如抑制掩盖不适当情绪表达——有时虽然心情不好，还是要掩盖，以免影响他人情绪。4、认知调节Dodge提出调节步骤：唤醒需要调节情绪——解释导致的原因，发现改变情绪方式——做出改变决定，设定改变目标——进行调节反应——对反应进行评价等过程。5、人际调节属于环境调节或社会调节。如他人的良好情绪，可以改善自己情绪，美丽的环境可让人感到赏心悦目等。 四、情绪调节与身心健康伍子胥是我国春秋时代吴国的大夫。他被任命为吴国大夫之前曾受到楚平王的追捕。伍子胥只好白天躲藏，晚上逃跑。一天。他终于来到了吴楚两国交界的昭关。关上的官吏盘查得很紧，城门上还挂着楚平王悬赏捉拿伍子胥的告示和伍予胥的画像。如果逃出关，伍子胥就会摆脱追捕，否则就危在旦夕。伍子胥十分焦急、忧愁，一连几夜也睡不着觉，传说他愁得连头发都变白了。真是：愁一愁，白了头!情绪对人的健康竟有这样大的作用。 情绪调节对身心健康有密切的关系：良好的情绪调节，可以促进身心健康。如减轻焦虑等负性情绪体验，有助于健康。不良情绪调节，有害于身心健康。如长期压抑悲伤容易引起呼吸系统疾病，情绪不表达出来会加速癌症恶化，愤怒压抑与心血管、高血压发病率有密切关系等。 思考题：概念：情绪与情感、心境、激情、应激、应对1、情绪与情感的区别与联系。2、情绪与情感的功能。3、情绪的状态有哪些？4、如何调节情绪？ 测谎仪的工作原理 面部表情 表情的判断：恐惧、厌恶、高兴、惊奇、轻蔑、生气、悲伤 布什总统的表情 体态表情 手势 ZUNG自我评定焦虑量表（SAS）下面有20条文字，请你仔细阅读每一条，然后根据你最近一星期的实际情况，在右侧相对应的适当数字上画“√”。1.我感到比往常更加神经过敏1234和焦虑2.我无缘无故感到担心12343.我容易心烦意乱或感到恐慌12344.我感到我的身体好象被分成几块，支离破碎12345.我感到事事都很顺利，不会有倒霉的事情发生4321很少有时大部分绝大部分有有时间有时间有 6.我的四肢抖动和震颤12347.我因头痛、颈痛和背痛而烦恼12348.我感到无力且容易疲劳12349.我感到很平静，能安静坐下来432110.我感到我的心跳较快123411.我因阵阵的眩晕而不舒服123412.我有阵阵要晕倒的感觉123413.我呼吸时进气和出气都不费力432114.我的手指和脚趾感到麻木和刺痛123415.我因胃痛和消化不良所苦恼1234很少有时大部分绝大部分有有时间有时间有 16.我必须时常排尿123417.我的手总是温暖而干燥432118.我觉得脸发烧发红　　　　　１　２　　３　４19.我容易入睡、晚上休息很好432120.我做噩梦1234焦虑自评量表（SAS）结果分析SAS的主要统计指标是“总分”。受试者填完后，将20题的各个得分相加得到粗分（X），将粗分乘以1.25即为标准分（Y）。即Y=1.25X。正常人Y分为40分以下，焦虑症患者可达50~60分以上。 抑郁症的基本症状表现：⒈烦躁不安（感觉不适）或者冷漠的情绪。⒉回避刺激。⒊长期没有体验快乐的能力或者缺乏快感。⒋停止与别人接触。⒌反复思考自杀或者死亡。⒍睡眠不安特别是早醒。⒎精神运动不安或者迟钝。⒏食欲减少或遭到破坏。⒐自责；无价值感；没有理由的内疚感。⒑缺乏决定能力；思想迟钝；缺乏专注力。⒒饮酒或用药增多。⒓没来由的哭叫。 Beck抑郁问卷[指导语]请你细看每组项目，然后在每组内选择最适合你的情况（最近一周，包括今天）的一项描述，并将那个数字圈出；如果一组内有不止一条适合你，请你将适合你的所有条目都圈出来。请先读完一组内的各项叙述，然后选择。A0.我不感到忧愁1.我感到忧愁2.我整天感到忧愁，且不能改变这一情绪B0.对于将来我不感到悲观1.我对将来感到悲观2.我感到将来无望，事事都不能变好 C0.我不象一个失败者1.我觉得我比一般人失败多一些2.当我回首过去时我看到的是许多失败3.我感到我是一个彻底的失败者D0.我对事物像往常一样满意1.我对事物不像往常一样满意2.我不再对任何事情感到真正的满意3.我对每件事情都感到不满意或讨厌E0.我没有感到特别内疚1.在相当一部分时间内感到内疚2.在部分时间内内疚3.我时常感到内疚 F0.我没感到正在受惩罚1.我感到可能受惩罚2.我预感到将要受惩罚3.我感到正在受惩罚G0.我感到我并不使人失望1.我对自己失望2.我讨厌自己3.我痛恨自己H0.我感到我并不比别人差1.我对自己的缺点和错误常反省2.我经常责备自己的过失3.我每次发生糟糕的事都责备自己 I0.我没有任何自杀的想法1.我有自杀的念头但不会真自杀2.我很想自杀3.如果有机会我会自杀J0.我并不比以往爱哭1.我现在比以往爱哭2.现在我经常哭3.我以前能哭，但现在即使想哭也哭不出来K0.我并不比以往容易激惹1.我比以往容易激惹或生气2.我现在经常容易发火3.以往能激惹我的那些事情现在则完全不能激惹我了 L0.我对他人的兴趣没减少1.我对他人的兴趣比以往减少了2.我对他人丧失大部分的兴趣3.我对他人现在毫无兴趣M0.我与以往一样能做决定1.我现在做决定没有以前果断2.我现在做决定比以前困难得多3.我现在完全不能作决定N0.我觉得自己看上去和以前差不多1.我担心我看上去老了或没有以前好看了2.我觉得我的外貌变得不好看了，而且是永久性的改变3.我认为我看上去很丑了 O0.我能像以往一样工作1.我要经过一番努力才能开始做事2.我做任何事情都必须作很大努力，强迫自己去做3.我完全不能工作P0.我睡眠像以往一样好1.我睡眠没有以往那样好2.我比往常早醒1－2小时，在入睡时有困难3.我比往常早醒几个小时，且不能再入睡Q0.我现在并不比以前感到疲劳1.我现在比以往容易疲劳2.我做任何事情都感到疲劳3.我太疲劳了以至不能做任何事情 R0.我的事与以前一样好1.我现在食欲没有以往那样好2.我的事比以前差多了3.我完全没有食欲了S0.我最近没有明显的体重减轻1.我体重下降超过5公斤2.我体重下降超过10公斤3.我体重下降超过15公斤，我在控制饮食来减轻体重T0.与以往相比并不过分担心身体健康1.我担心我身体的毛病如疼痛、反胃及便秘2.我很着急身体的毛病而妨碍我思考其他问题3.我非常着急身体的毛病，以至不能思考任何其他事情 [结果判断]判断抑郁程度的临界值因研究目的而异。一般情况下的参考标准为：低于4分无抑郁或极轻微；5－13分轻度；14－20分中度；21分以上为重度。 我是A型性格的人吗？1.在谈话中你是否过分强调一些词，却对句子中最后的几个词一带而过？2.你行动、吃饭、走路的速度是不是总是很快？3.当事情的进展速度不能如你所愿时，你是不是会变得生气和不耐烦？4.你是否经常在同一时间干几件事？5.你是否经常把话题转到你所感兴趣的问题上来？6.当你休息时，你是否有点负罪感？7.你是否经常不注意环境中的新事物？8.你是否更关心结果而不是过程？9.你是否经常在很短的时间内安排很多的事情？10.你是否发现你和喜欢赶时间的人在暗地里竞争？ 11.在交谈时，你是否喜欢用一些有感染力的手势，比如为了强调某一个问题而紧握拳头或敲桌子？12.你是否认为行动迅速是成功的关键？13.在日常生活中，你是否经常用数字给你的成就打分，比如卖出货物的数量等等。测试结果：如果对一半问题的回答是“是”，那你就可以划入“A型行为”者的行列了。如果你是一位“A型行为”人，不知是应该恭喜你还是应该为你担心。由于你对自己有比别人更高的要求，所以你在成就任务上就得付出更多的努力。虽然你会在工作和学业上比别人取得更好的成绩，但是，“A型行为”对于你的成功来说可能既是一种资产也是一项债务。 SeeYouNextTime!TheEnd 学习要点理解回溯法的深度优先搜索策略。掌握用回溯法解题的算法框架（1）递归回溯（2）迭代回溯（3）子集树算法框架（4）排列树算法框架53 通过应用范例学习回溯法的设计策略。（1）装载问题；（2）批处理作业调度；（3）符号三角形问题（4）n后问题；（5）0-1背包问题；（6）最大团问题；（7）图的m着色问题（8）旅行售货员问题（9）圆排列问题（10）电路板排列问题（11）连续邮资问题54 有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往要使用回溯法。回溯法回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。55 问题的解空间问题的解向量：回溯法希望一个问题的解能够表示成一个n元式(x1,x2,…,xn)的形式。注意：同一个问题可以有多种表示，有些表示方法更简单，所需表示的状态空间更小（存储量少，搜索方法简单）。n=3时的0-1背包问题用完全二叉树表示的解空间,其解空间为{(0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,1),(1,1,0),(1,1,1)}定义了问题的解空间后,还应将解空间很好地组织起来,使得能用回溯法方便地搜索整个解空间,通常将解空间组织成树或图的形式56 生成问题状态的基本方法扩展结点:一个正在产生儿子的结点称为扩展结点活结点:一个自身已生成但其儿子还没有全部生成的节点称做活结点死结点:一个所有儿子已经产生的结点称做死结点深度优先的问题状态生成法：如果对一个扩展结点R，一旦产生了它的一个儿子C，就把C当做新的扩展结点。在完成对子树C（以C为根的子树）的穷尽搜索之后，将R重新变成扩展结点，继续生成R的下一个儿子（如果存在）回溯法在搜索解空间树时,通常采用两种策略避免无效搜索:其一是用约束函数在扩展结点处剪去不满足约束的子树;其二是用限界函数剪去得不到最优解的子树.这两类函数统称为剪枝函数.57 回溯法的基本思想回溯法的解题步骤:(1)针对所给问题，定义问题的解空间；(2)确定易于搜索的解空间结构；(3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。58 递归回溯回溯法对解空间作深度优先搜索，因此，在一般情况下用递归方法实现回溯法。voidbacktrack(intt){if(t>n)output(x);elsefor(inti=f(n,t);i<=g(n,t);i++){x[t]=h(i);if(constraint(t)&&bound(t))backtrack(t+1);}}59 迭代回溯采用树的非递归深度优先遍历算法，可将回溯法表示为一个非递归迭代过程。voiditerativeBacktrack(){intt=1;while(t>0){if(f(n,t)<=g(n,t))for(inti=f(n,t);i<=g(n,t);i++){x[t]=h(i);if(constraint(t)&&bound(t)){if(solution(t))output(x);elset++;}}elset--;}}60 迭代回溯用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为O(h(n))。而显式地存储整个解空间则需要O(2h(n))或O(h(n)!)内存空间。61 子集树与排列树遍历子集树需O(2n)计算时间遍历排列树需要O(n!)计算时间voidbacktrack(intt){if(t>n)output(x);elsefor(inti=0;i<=1;i++){x[t]=i;if(legal(t))backtrack(t+1);}}voidbacktrack(intt){if(t>n)output(x);elsefor(inti=t;i<=n;i++){swap(x[t],x[i]);if(legal(t))backtrack(t+1);swap(x[t],x[i]);}}62 装载问题有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi，且装载问题要求确定是否有一个合理的装载方案可将这n个集装箱装上这2艘轮船。如果有，找出一种装载方案。例如,当n=3,c1=c2=50,且w=[10,40,40]或者w=[20,40,40]63 装载问题容易证明，如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案。(1)首先将第一艘轮船尽可能装满；(2)将剩余的集装箱装上第二艘轮船。将第一艘轮船尽可能装满等价于选取全体集装箱的一个子集，使该子集中集装箱重量之和最接近。由此可知，装载问题等价于以下特殊的0-1背包问题。用回溯法设计解装载问题的O(2n)计算时间算法。在某些情况下该算法优于动态规划算法。64 装载问题算法设计:解空间：子集树可行性约束函数(选择当前元素)：voidbacktrack(inti){//搜索第i层结点if(i>n){//到达叶结点if(cw>bestw)bestw=cw;return;}if(cw+w[i]<=c){//搜索左子树x[i]=1;cw+=w[i];backtrack(i+1);cw-=w[i];}backtrack(i+1);//x[i]=0;}65 装载问题改进算法:上界函数(不选择当前元素)：当前载重量cw+剩余集装箱的重量r当前最优载重量bestwvoidbacktrack(inti){//搜索第i层结点if(i>n){bestw=cw;return;}r-=w[i];if(cw+w[i]<=c){//搜索左子树x[i]=1;cw+=w[i];backtrack(i+1);cw-=w[i];}if(cw+r>bestw){//x[i]=0;搜索右子树backtrack(i+1);}r+=w[i];}66 装载问题构造最优解:通过在类Loading中增加两个私有数据成员x和bestx。x用于记录从根至当前节点的路径；bestx记录当前最优解。67 装载问题迭代回溯:数组x记录了解空间树中从根到当前扩展结点的路径,这些信息已包含了回溯法在回溯时所需的信息。因此利用数组x所含的信息，可讲上述回溯法表示成非递归的形式。由此可进一步省去0(n)递归栈空间。68 批处理作业调度给定n个作业的集合{J1,J2,…,Jn}。每个作业必须先由机器1处理，然后由机器2处理。作业Ji需要机器j的处理时间为tji。对于一个确定的作业调度，设Fji是作业i在机器j上完成处理的时间。所有作业在机器2上完成处理的时间和称为该作业调度的完成时间和。批处理作业调度问题要求对于给定的n个作业，制定最佳作业调度方案，使其完成时间和达到最小。tji机器1机器2作业121作业231作业323这3个作业的6种可能的调度方案是1,2,3；1,3,2；2,1,3；2,3,1；3,1,2；3,2,1；它们所相应的完成时间和分别是19，18，20，21，19，19。易见，最佳调度方案是1,3,2，其完成时间和为18。69 批处理作业调度解空间：排列树voidFlowshop::Backtrack(inti){if(i>n){for(intj=1;j<=n;j++)bestx[j]=x[j];bestf=f;}elsefor(intj=i;j<=n;j++){f1+=M[x[j]][1];f2[i]=((f2[i-1]>f1)?f2[i-1]:f1)+M[x[j]][2];f+=f2[i];if(fn)sum++;elsefor(inti=1;i<=n;i++){x[t]=i;if(Place(t))Backtrack(t+1);}}72 0-1背包问题解空间：子集树可行性约束函数：上界函数：templateTypepKnap::Bound(inti){//计算上界Typewcleft=c-cw;//剩余容量Typepb=cp;//以物品单位重量价值递减序装入物品while(i<=n&&w[i]<=cleft){cleft-=w[i];b+=p[i];i++;}//装满背包if(i<=n)b+=p[i]/w[i]*cleft;returnb;}73 最大团问题给定无向图G=(V，E)。如果UV，且对任意u，vU有(u，v)E，则称U是G的完全子图。G的完全子图U是G的团当且仅当U不包含在G的更大的完全子图中。G的最大团是指G中所含顶点数最多的团。U是G的最大团当且仅当U是G的最大独立集。1245312453如果UV且对任意u，vU有(u，v)E，则称U是G的空子图。G的空子图U是G的独立集当且仅当U不包含在G的更大的空子图中。G的最大独立集是G中所含顶点数最多的独立集。对于任一无向图G=(V，E)其补图G=(V1，E1)定义为：V1=V，且(u，v)E1当且仅当(u，v)E。74 最大团问题解空间：子集树可行性约束函数：顶点i到已选入的顶点集中每一个顶点都有边相连。上界函数：有足够多的可选择顶点使得算法有可能在右子树中找到更大的团。voidClique::Backtrack(inti){//计算最大团if(i>n){//到达叶结点for(intj=1;j<=n;j++)bestx[j]=x[j];bestn=cn;return;}//检查顶点i与当前团的连接intOK=1;for(intj=1;jbestn){//进入右子树x[i]=0;Backtrack(i+1);}}复杂度分析最大团问题的回溯算法backtrack所需的计算时间显然为O(n2n)。1245375 图的m着色问题给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G中每条边的2个顶点着不同颜色。这个问题是图的m可着色判定问题。若一个图最少需要m种颜色才能使图中每条边连接的2个顶点着不同颜色，则称这个数m为该图的色数。求一个图的色数m的问题称为图的m可着色优化问题。76 解向量：(x1,x2,…,xn)表示顶点i所着颜色x[i]可行性约束函数：顶点i与已着色的相邻顶点颜色不重复。图的m着色问题voidColor::Backtrack(intt){if(t>n){sum++;for(inti=1;i<=n;i++)cout<voidTraveling::Backtrack(inti){if(i==n){if(a[x[n-1]][x[n]]!=NoEdge&&a[x[n]][1]!=NoEdge&&(cc+a[x[n-1]][x[n]]+a[x[n]][1]temp)temp=valuex;}returntemp;}voidCircle::Compute(void){//计算当前圆排列的长度floatlow=0,high=0;for(inti=1;i<=n;i++){if(x[i]-r[i]high)high=x[i]+r[i];}if(high-lown)Compute();elsefor(intj=t;j<=n;j++){Swap(r[t],r[j]);floatcenterx=Center(t);if(centerx+r[t]+r[1]