《人工智能》读后感 本文关键词：人工智能，读后感
《人工智能》读后感 本文简介：《人工智能》（李开复）读后感本书内容框架如下：1.关于人工智能的五种定义2.人工智能发展的三个阶段3.人工智能是否会威胁人类4.人类将如何变革5.AI行业的创业概况6.AI时代下的教育和个人发展一、关于人工智能的五种定义首先，请抛开人工智能就是人形机器人的固有偏见。人工智能目前作为一种技术手段，已经
《人工智能》读后感 本文内容：
《人工智能》（李开复）读后感
本书内容框架如下：
1.关于人工智能的五种定义
2.人工智能发展的三个阶段
3.人工智能是否会威胁人类
4.人类将如何变革
5.AI行业的创业概况
6.AI时代下的教育和个人发展
一、关于人工智能的五种定义
首先，请抛开人工智能就是人形机器人的固有偏见。
人工智能目前作为一种技术手段，已经成为了不少应用的核心驱动力。
苹果的SIRI、微软的小冰是常见的人工智能助理。当用户与他们对话时，他们会通过事先积累好的人类对话库和互联网资料库中，查找最有可能匹配的回答。
今日头条、淘宝购物推荐，会根据你的浏览习惯、购物历史，学习你的爱好。所以用的越久，它就会越懂你。
人脸识别是目前应用最广泛的机器视觉技术，是人工智能大家庭中的重要分支。用刷脸的方式替代门禁卡，支付宝正在开发的刷脸支付也是依托于人脸识别技术。广义上的机器视觉还包括图像、视频中各种物体识别、场景识别、地点识别乃至语义理解。比如手机中的照片自动分类就是运用了场景识别的功能，还有清理重复照片的功能，也运用到了这个技术。此外，百度中的图片搜索、淘宝中的商品图片搜索，也运用到了人工智能技术。
我们现在用的美图秀秀中的一键P图软件、三生三世画风的一键美妆，都是运用到了人工智能技术。机器通过从大量经典画作中学习到的上色技法、笔触技法、干湿画法、上妆技巧等，来对原始图片进行处理。
搜索引擎根据问题给出最直接的答案，也与SIRI的运行原理相类似。
在机器翻译这一块儿上，通过对语言、语言学的学习，得出的翻译结果也具备较强的可读性。甚至可以通过中文与英文的翻译数据、英文与阿拉伯文的翻译数据，自动学习如何从中文翻译到阿拉伯文。
还有目前在商业化方面已经取得长足进展的自动驾驶技术。也是通过数百万里的驾驶里程学习，来完成车速调整、控制转向、避免碰撞等操作。当然，目前相对比较成熟的还是半自动驾驶技术。完全的无人驾驶或许还要等到十年之后。
还有我们经常在电影中看见的机器人行业。快递分拣机器人、无人飞机、工业机器人，都极大的提高了商业效率。但目前机器人还无法做到像人一样具备完整的思维。大家所期待的人形机器人，其实投资人也是不看好的。原因很简单，机器越像人，就越容易被拿来和真人比较。由于人工智能技术尚未达到十分成熟的阶段，这个机器人的蠢笨会暴露的非常彻底。使期望与现实之间的差距加大，因此难以获得市场认可。
那讲了这么多现象，到底什么是人工智能？
目前常见的定义有五种：
第一，人工智能是让人感到不可思议的计算机程序。几十年前的人类，如果能见识到现在手机上常见的人机对战的象棋、跳棋游戏，恐怕会被吓一大跳，甚至怀疑是有人在背后操纵。可现在的人都见怪不了。所以，用这种方法定义，会使得人工智能随着技术的成熟，失去一个客观的标准。
第二，AI就是与人类思考方式相似的计算机程序。这种说法在早期非常流行。本质上与仿生学无异。但弊端在于，人类至今也无法说清楚大脑是如何进行学习、记忆、归纳、推理等思维过程的。因此，也很难教会机器去模拟人脑的运作。再一点就是，通过为程序输入大量专业的知识、常见的思考逻辑，使得计算机应用难以扩展到较为复杂的领域当中。比如面对语言中的歧义和丰富的表达方式，得出的翻译结果往往也是漏洞百出。
第三，AI就是与人类行为相似的计算机程序。这一定义与仿生学派的说法是对立的。实用主义者并不在乎人工智能要遵循什么思考框架，也不在乎计算机到底是如何处理采集到的数据。只要模型可以工作，最终的结果是对的就行。
第四，AI是会学习的计算机程序。最近的这波人工智能热潮里，深度学习作为一种技术手段确实是一枝独秀，几乎垄断了所有流行的技术方向。而在此之前的专家系统、统计模型都未能使人工智能获得如此大的进步。所以，把学习等同于AI，虽然过于狭隘，但也是比较符合时代精神的。但要注意的是，机器的学习方法和人类的学习方法还有很大的差距与不同。如果人工智能是一种会学习的机器，那么需要着重提高的就是其抽象理解能力。
第五，AI就是根据对环境的感知，做出合理的行动，并获得最大收益的计算机程序。不同的定义分别适用于不同的人群和语境。如果非要得出一个看上去比较合理的定义，那也只能是比较模糊的概念。那么这一种就是学术界的教科书式定义，全面均衡，偏重实证。
二、人工智能发展的三个阶段
1962年，IBM的阿瑟萨缪尔开发的西洋跳棋程序曾经战胜过一位盲人跳棋高手，1997年IBM深蓝战胜卡斯帕罗夫的那一天，全世界科技爱好者奔走相告，2016年ALPHAGO战胜李世石，就由流传起人工智能将要毁灭人类的言论。
纵观前两次次人工智能潮，每一次都曾让人以为人工智能将会掀起大的变革。但最后回头看，都没有达到人们期望的高度。与其说是人们的心理落差，不如说是人们对机器是否具有智能的判断标准在不断被拔高。
那究竟这一次的人工智能热潮，会超出人们的期望吗？
从高德纳咨询公司的技术成熟曲线来看，每一项技术在早期阶段，都会被公众追捧，被媒体大肆报道，最终走向一个充满泡沫的膨胀期。
随着盲目追捧者的激增，跟风的公司越来越多。但随着技术遇到瓶颈，市场供过于求，大量没有核心竞争力的公司不是被兼并，就是倒闭。
行业跌入低谷后，迎来了第二轮、第三轮投资，技术上的突破使得第二代、第三代产品得到了普罗大众的认可。投资得到了回报。
20世纪50年代到60年代，随着通用电子计算机的诞生，人工智能悄然兴起，比如一些简单的象棋程序设想。但由于当年计算机的运算水平远远达不到要求，很多东西只能停留在纸上谈兵的层面。
20世纪80年代到90年代，基于统计模型的技术悄然兴起，并在语音识别、机器翻译等领域取得了不俗的进展。人工神经网络也在模式识别应用等领域开始有所建树。但还是不足以超过人类的预期。
那么这一次的人工智能复兴的最大特点就是AI在多个领域达到了人们心中“有用”的标准，在商业领域被广泛的应用。
从心理学上说，人们接受一件新事物，就像人们接受外界刺激一样，是有一个阈值的。只有当外界刺激的强度超过了一个人能感知的最小刺激量，人们才会注意到它。而这个人们能感知到的最小刺激量，就是心理学上的绝对阈值。
这一次的AI热潮，正是达到了人们的心理阈值才得到了广泛的关注。就拿人脸识别来说，之前的准确率可能只有20%不到，根本不具备实用价值，只能停留在实验室当中，自然就没有达到人们的心理阈值。但现如今就不一样了。
所以，我们说人工智能来了，其实是说人工智能或深度学习真的可以解决实际问题了。在机器视觉、语音识别、数据挖掘、自动驾驶等方面都获得了长足的进步。
而这一切，都离不开深度学习。
今天的人工智能研究者，几乎无人不谈深度学习。很多人甚至喊出了“人工智能=深度学习”的口号。但毋庸讳言，深度学习绝对不是人工智能领域解决的唯一方案，二者之间不能划上等号。但说深度学习是未来很长一段时间内，推动人工智能进步的核心技术，则一点都不为过。
深度学习依赖海量的大数据和强大的计算能力。对于计算机来说，想让它成功识别猫这个物种。需要其学习一千万段视频才行。
三、人工智能是否会威胁人类
人工智能真的足够聪明以至于会超出人类的控制范围，最终威胁到人类吗？
要回到这个问题，首先要理清不同层级人工智能的定义。
弱人工智能：限制领域人工智能，指的是专注于且智能解决某一特定领域问题的人工智能。目前看到的所有人工智能都属于这个范畴。例如AlphaGo。人们更多的是将其看作一种工具，而不是威胁。当然了，同其他所有工具，如汽车、飞机等一样，都是存在风险的。
强人工智能：指可以胜任人类所有工作的人工智能。就是人可以做什么，人工智能就可以做什么。谈及这个层面，就不得不面对强人工智能是否有必要具备“意识”这个问题。一旦牵涉到“意识”，强人工智能的定义和评判标准就会变得十分复杂。
超人工智能：比人类还有天赋、还要聪明的人工智能。目前更多的是从哲学以及科幻的角度加以解析。没有办法和经验去预测这种智能究竟是否存在。
目前大众忧心的人工智能威胁论，主要指的是强人工智能和超人工智能。那么他们会以远超我们预料的速度降临吗？
目前大多数对于这类威胁的论述都是基于“人类科技发展是越来越快，呈现出不断加速的势头”。但这个假设是否正确，也很难给出明确的答复。
但作者更相信：特定的科技如人工智能，经历一段时间的加速度发展后，会遇到难以攻克的技术瓶颈。
客观的分析看，人类威胁还相当遥远。问题的根源可能在于人类总习惯把人工智能人格化。人工智能的危险，本质上还是和其他工具一样具备无法避免的弊端，这是我们需要防范的，而并非担心智能机器会像人类一样思考。
“智能”二字本身就是缺乏一个客观的、可量化的定义的。单从计算能力看，人工智能确实超出人类很多。如果仅根据这种限定范畴的技术能力去推测，确实很可怕。但如果综合考虑人工智能的跨领域推理能力、常识和感性、理解抽象概念的能力等，其实人工智能还很难给人类造成威胁。
今天的人工智能还不能做什么：
1.
跨领域推理：比如使用比喻句。人类强大的跨领域联想、类比能力是跨领域推理的基础。但显然智能机器是不具备的。在今天，迁移学习的概念正在兴起，指的是将人工智能在某一领域取得的经验，通过某种形式的变换，迁移到另一个陌生的领域。
2.
抽象能力：目前的深度学习技术都需要大量的数据来支撑。不像人类可以通过少量样本就总结出规律。
3.
探索原因：人工智能做出行为的原因很简单，就是依赖于设定的一个程序。而不会去追求为什么要设定这个程序。譬如看到苹果落地，智能机器看一万遍也不会去思考背后的原因。
4.
常识：即无须仔细思考就能直接使用的知识、方法和经验。比如虽然小朋友没学习过牛顿定理，但也知道东西会下落。人工智能只能靠人类设定的规则来完成常识的积累，丰富性还不足。
5.
自我意识：这种能力智能机器很难在短时间内拥有。也很难推测有没有拥有的可能。
6.
审美：审美缺少量化的标准，是非常主观的东西。那种体验到美好事物之后的情感，人工智能也难以领会。
7.
情感：推测判断人类的表情目前是可以实现的。但至于说让人工智能自己具备情感，可能还有很远的路要走。
四、人工智能将如何变革
人工智能不仅是技术层面的一次革命。由于人工智能会对生产效率有大幅的提升，也必然会触及社会、政治、经济、文化层面的变革。
这其中热议最多的就是关于失业的问题。从短期看，必然会造成某些行业、局部地区的失业阵痛。但从长期看，会刺激大量工作转变为新的工作类型，从而为生产力的进一步解放、人类生活的进一步提升打下基础。
这里有一个“5秒钟”准则：如果人可以在5秒钟内对工作中需要思考和决策的问题作出相应的决定，那么就很有可能被取代。反之，如果涉及缜密的推理和复杂的决策，就很难被取代。
例如，照着课本讲课的老师可能会被取代，但可以重塑知识架构体系，创造性的方法为学生授课的老师则不会被取代。
因此，一些简单的重复性工作将被取代，但也会催生更多新型的、需要判断力、创造力、情感交流以及审美和艺术创作的工作类型。如设计师、架构师、艺术家、文学创作者。人的独特性会体现出来：思考、创造、沟通、情感交流；人与人的依恋、归属感和协作精神；好奇、热情、志同道合的驱动力。
五、人工智能的创业方向
第一阶段，AI会率先在哪些在线化程度高的行业开始应用，在数据段、媒体端实现自动化。
第二阶段，随着感知技术、传感器和机器人技术的发展，AI会延伸到实体世界，并率先在专业领域、行业应用、生产力端实现线下业务自动化。工业机器人、仓储机器人等将大范围普及。
第三阶段，AI会延伸到个人场景，全面自动化时代终将到来。
AI创业的五大前提：
第一，
清晰的领域界限，例如仓储、物流、扫地机器人。
第二，
闭环、自动标注的数据。
第三，
千万级的数据量。
第四，
超大规模的计算机能力。目前一些空调马力不足的机房，甚至会购买冰块儿散热。
第五，
AI技术专家。
六、一些感想
人工智能是一种提高生产效率的技术手段，在未来会大范围的使用。未来人的价值会被无限放大，越独特，越有思想的人就越值钱。当然了，没什么思想的也可以活，毕竟生产效率的提高会使得物资价格有大幅的降低。但在娱乐体验方面，可能就需要支付较高的费用。
篇2：人工智能英语演讲稿
人工智能英语演讲稿 本文关键词：人工智能，英语，演讲稿
人工智能英语演讲稿 本文简介：Goodmorning,everyone.MynameXXX.Myspeechthemeisartificialintelligence,theabbreviationisAI.Next,mytopicwillbedividedintofourparts.Thefirstpartisoverview
人工智能英语演讲稿 本文内容：
Good
morning,everyone.My
name
XXX.
My
speech
theme
is
artificial
intelligence,the
abbreviation
is
AI.
Next,my
topic
will
be
divided
into
four
parts.
The
first
part
is
overview.AI,It
is
a
new
technical
science
in
the
research
and
development
of
intelligent
theories,methods,techniques
and
applications
for
the
simulation,extension
and
expansion
of
human
ability.
AI
is
a
branch
of
computer
science,it
attempts
to
understand
the
essence
of
intelligence,and
can
produce
a
new
kind
of
response
in
the
form
of
human
intelligence
similar
intelligent
machines,research
in
this
field
include
robot,speech
recognition,image
recognition,natural
language
processing
and
expert
system,etc.
The
second
part
is
the
history
of
AI.
The
year
before
1956
was
the
incubation
period
for
AI.
Scientists
in
various
fields
have
prepared
the
necessary
thought,theoretical
and
material
technical
conditions
for
the
birth
of
AI.
AI
was
born
in
a
historic
meeting,after
which
AI
experienced
the
early
research,the
setbacks
and
lessons
in
application.
Thanks
to
the
development
of
big
data,since
the
turn
of
the
century,AI
as
the
core,in
natural
intelligence
and
integrated
intelligent
has
been
on
the
rise,and
has
attracted
great
attention.
With
good
development,there
will
be
positive
results,the
third
part
is
the
result
of
the
development
of
AI.There
are
four
typical
example,in
the
man-machine
game
with
IBM
s
deep
blue
over
international
chess
players
and
AlphaGo
over
international
go
players,in
terms
of
pattern
recognition,AI
is
used
for
image
processing,voice
recognition
and
face
recognition,etc.,in
automatic
engineering,the
most
representative
is
pilotless
automobile.These
are
already
or
will
be
applied
in
our
lives.
The
last
part
is
about
the
controversy
over
the
development
of
AI.
founder
mark
zuckerberg
think
humans
create
machines
in
order
to
make
stronger
than
human
in
some
respects,but
this
does
not
mean
that
the
machine
has
the
ability
to
study
other
aspects
beyond
human,and
tesla
CEO
elon
musk
take
the
opposite
point
of
view,he
believes
that
as
long
as
you
think
AI
will
continue
to
grow,AI
will
surpass
humans,so
that
we
become
their
pets.
From
my
personal
understanding,AI
is
nothing
more
than
a
logic
of
0
and
1,which
cannot
create
inspiration,intuition,and
feelings.
Finally,I
want
to
say
is,AI
came
from
step
by
step
exploration
and
got
rapid
development,the
human
need
to
seize
the
opportunity
of
the
technological
revolution,let
the
society
more
intelligent
and
convenient
in
the
future.
That’s
all,Thank
you.
篇3：人工智能课程报告--分别用宽度优先、深度优先、贪婪算法和A_算法求解“罗马利亚度假问题”
人工智能课程报告--分别用宽度优先、深度优先、贪婪算法和A_算法求解“罗马利亚度假问题” 本文关键词：算法，优先，罗马，求解，人工智能
人工智能课程报告--分别用宽度优先、深度优先、贪婪算法和A_算法求解“罗马利亚度假问题” 本文简介：人工智能课程报告课程:人工智能实验报告班级:191121班学号:20121004362学生姓名:李华勇指导教师:赵曼2014年11月目录一、罗马利亚度假问题31.问题描述32.数据结构42.1广度优先算法42.2深度优先算法42.3贪婪算法42.4A*算法43.算法思想53.1广度优先搜索算法53.
人工智能课程报告--分别用宽度优先、深度优先、贪婪算法和A_算法求解“罗马利亚度假问题” 本文内容：
人工智能课程报告
课
程:
人工智能实验报告
班
级:
191121班
学
号:
20121004362
学生姓名:
李
华
勇
指导教师:
赵
曼
2014年11月
目录
一、罗马利亚度假问题3
1.
问题描述3
2.
数据结构4
2.1
广度优先算法4
2.2
深度优先算法4
2.3
贪婪算法4
2.4
A*算法4
3.
算法思想5
3.1
广度优先搜索算法5
3.2
深度优先搜索算法5
3.3
贪婪算法6
3.4
A*算法6
4.
运行结果7
5.
比较讨论8
6.
主要代码8
二、N皇后问题13
1.问题描述13
2.数据结构13
2.1
回溯法（递归）13
2.2
GA算法13
2.3
CSP的最小冲突法13
3.算法思想14
3.1
回溯法（递归）14
3.2
CSP的最小冲突法14
3.3
GA算法15
4.运行结果16
5.比较讨论17
6.主要代码18
一、罗马利亚度假问题
题目：
分别用宽度优先、深度优先、贪婪算法和A*算法求解“罗马利亚度假问题”。
要求：
分别用文件存储地图和启发函数表，用生成节点数比较几种算法在问题求解时的效率，并列表给出结果。
1.
问题描述
从文件中读取图和启发函数，分别用广度优先、深度优先、贪婪算法、A*算法得到从起始点Arad到目标点Bucharest的一条路径，即为罗马尼亚问题的一个解。在求解的过程中记录生成扩展节点的个数（用于比较几种算法的优劣），用堆栈记录DepthFSearch和BroadFSearch的路径。
2.
数据结构
分别使用了图结构，顺序队列，顺序表以及堆栈。对于每一个图中的结点，定义了一个结构体HeuristicG，结构体中包含结点的名称以及对应的启发函数值。
typedef
struct{
char
G[20];
int
value;
}HeuristicG;
typedef
struct
//图结构：
typedef
struct
//链表
{
{
SeqList
Vertices;
string
list[20];
int
edge[20][20];
int
size;
int
numedge;
}SeqList;
}AdjMGraph;
typedef
struct
//队列
typedef
struct
//栈
{int
queue[20];
{
int
rear;
int
stack[20];
int
front;
int
top;
int
count;
}SeqStack;
}SeqCQueue;
2.1
广度优先算法
使用了数据结构中的图、队列和堆栈。
2.2
深度优先算法
使用了数据结构中的图和堆栈。
2.3
贪婪算法
使用了数据结构中的图。
2.4
A*算法
使用了数据结构中的图。
3.
算法思想
3.1
广度优先搜索算法
void
BF_Search(AdjMGraph
G,HeuristicG
data[],int
v0,int
vg,intExpand,int
count,int
visited[],int
BFS_path[])
v0---起始节点
vg---目标节点
Expand---返回扩展结点数
count---返回路径结点数
BFS_path[]---存储路径信息
G、data[]---用来读取图的各种信息
visited[]---用来存储节点是否已经被访问的信息
广度优先搜索是分层搜索的过程，广度优先搜索算法思想是用一个队列来保存访问过的顶点的顺序，以便按顺序访问这些顶点的邻接顶点，并把这些邻接顶点依次入栈。在函数中我还创建了两个栈，SeqStack
SaveQ，LineSave，SaveQ将出队列的节点全部进栈，LineSave用于保存路径。广度优先搜索算法如下：
1）
访问顶点v0并标记v0已被访问，把v0输出到屏幕。
2）
顶点v0入队列。
3）
若队列非空，则继续执行，否则算法结束。
4）
出队列取得队头顶点u，并把u入SaveQ栈。
5）
查找顶点u的第一个邻接顶点w。
6）
如果w
=
vg，即找到目标节点，算法结束。
7）
若顶点u的邻接顶点w不存在，则转到步骤3），否则循环执行：
（a）若顶点w尚未被访问，则访问顶点w并标记w为已访问；
（b）顶点w入队列，Expand++；
（c）查找顶点u的w邻接顶点后的下一个邻接顶点w，转到步骤7）。
广度优先搜索起始节点到目标节点的路径的算法是：
1）
把顶点vg以及vg的父节点u入栈。
2）
把SaveQ栈顶元素出栈到u，当SaveQ非空是执行以下步骤：
（a）把SaveQ栈顶元素出栈到u
。
（b）取LineSave栈顶元素给y。
（c）如果u和y没有相同的父亲，没被访问过，并且之间有边则保存路
径，把u压入LineSave栈。
3.2
深度优先搜索算法
void
DF_Search(AdjMGraph
G,SeqStack
S,HeuristicG
data[],int
Expand,int
v0,int
vg,int
visited[])
v0---起始节点
vg---目标节点
Expand---返回扩展结点数
SeqStack
S---用堆栈存储路径信息
visited[]---存储路径是否被访问的信息
G、data[]---用来读取图的各种信息
深度优先搜索的算法思想是用栈来保存已经访问过的节点，递归找该节点的第一个邻接顶点并把把顶点入栈，直到找不到顶点的邻接顶点为止，然后回溯，找该顶点父顶点的下一个邻接顶点。
使用深度优先搜索算法，每次都在访问完当前顶点后首先访问当前顶点的第一个邻接顶点。深度优先搜索算法如下：
1)
访问顶点v并标记顶点v为以访问，把v0压入栈S，并在屏幕上输出v。
2)
如果v0！=
-1，查找顶点v的第一个邻接顶点w
3)
若顶点v的邻接顶点w存在且为被访问，则继续执行，否则算法结束。
4)
若果w
=
vg，即找到目标节点，算法结束。
5)
弹出S栈顶元素。
6)
查找顶点v的w邻接顶点的下一个邻接顶点w，转到步骤3）。
3.3
贪婪算法
void
Greedy_Search(AdjMGraph
G,HeuristicG
data[],int
v0,int
vg,intExpand,int
visited[])
v0---起始节点
vg---目标节点
Expand---返回扩展结点数
G、data[]---用来读取图的各种信息
贪心算法思想是找到当前顶点的所有邻接顶点中h（x）值最小的邻接顶点，并把该顶点设置为下一个起始节点，递归直到找到目标节点。算法如下：
1）
访问v0，并将v0设为以访问，把v0输出到屏幕。
2）
如果v0
=
vg，即找到目标节点，算法结束。
3）
找到v0的所有邻接顶点，并比较邻接顶点的h（x）值，把h（x）最小
的邻接顶点w，把w设置为起始顶点v0，转到步骤1）。
3.4
A*算法
void
A_Search(AdjMGraph
G,HeuristicG
data[],int
v0,int
vg,int
distance,intExpand,int
visited[])
v0---起始节点
vg---目标节点
distance---用来保存已经过路径值
Expand---返回扩展结点数
G、data[]---用来读取图的各种信息
A*算法思想是找到起始节点v0的所有邻接顶点，比较所有邻接顶点的fx值（fx
=
到v0已经经过路径值+v0到邻接顶点w的边的路径值distance+邻接顶点w的hx值），找到fx最小的邻接顶点w作为下一个起始顶点v0，同时更新距离diatance
=
diatance
+
v0到w边的路径值，直到找到目标节点。算法如下：
1）访问v0，并将v0设为以访问，把v0输出到屏幕。
2）如果v0
=
vg，即找到目标节点，算法结束。
3）找到v0的所有邻接顶点w，并比较所有邻接顶点的fx值，
fx=ditance+v0到w的距离+w的启发函数值，找到fx最小的邻接顶点w
令v0
=
w，更新distance
=
distance
+
edge[v0][w]，转到步骤1）。
4.
运行结果
深度优先搜索
宽度优先搜索
A*算法
贪婪算法
扩展节点数
12
11
5
4
路径节点数
5
4
5
4
5.
比较讨论
从运行结果中可以看出，在搜索的过程中：
DFS算法扩展结点数为12
BFS算法扩展结点数为11
A*算法扩展结点数为5
贪婪算法扩展结点数为4
所以在求解该问题时，贪婪算法的效率最高，其次是A*算法，然后是BFS算法，最后是DFS算法。但是贪婪算法和A*算法生成的节点数依赖于启发函数的值，因此虽然对于本题来说贪婪算法和A*算法的效率很高，但是不能说在所有搜索问题中贪婪算法和A*算法的效率都是最高的。
6.
主要代码
1）深度优先搜索
//
v0---起始节点
vg---目标节点
//
//
Expand---返回扩展结点数
//
//
SeqStack
S---用堆栈存储路径信息
//
//
visited[]---存储路径访问信息
//
//
G、data[]---用来读取图的各种信
//
void
DF_Search(AdjMGraph
G,SeqStack
S,HeuristicG
data[],int
Expand,int
v0,int
vg,int
visited[])
{
int
t,w;
//用于寻找目标节点
static
int
flag
=
0;
static
int
DFS_flag
=
0;
//标志位---找到目标节点后退出递归
StackPush(S,v0);
//首先将起始节点入栈
flag++;
printf(“%s-->
“,data[v0].G);
visited[v0]=1;
if(v0
!=
-1)
w=GetFirstVex(G,v0,visited);
//获取第一个临接点
while(!DFS_flagExpand
=
flag;
break;
}
if(!
visited[w]
if(DFS_flag)
break;
StackPop(S,w
=
GetNextVex(G,v0,w,visited);
}
}
2）宽度优先搜索
//
v0---起始节点
vg---目标节点
//
//
Expand---返回扩展结点数
//
//
count---返回路径结点数
//
//
BFS_path[]---存储路径信息
//
//
G、data[]---用来读取图的各种信息
//
void
BF_Search(AdjMGraph
G,HeuristicG
data[],int
v0,int
vg,intExpand,int
count,int
visited[],int
BFS_path[])
{
int
u,w,y,SumExpand=1,i=0;
SeqCQueue
Q;
SeqStack
SaveQ,LineSave;
//SaveQ将出队列的节点全部进栈,LineSave用于保存路径
StackInitiate(
StackInitiate(
printf(“%s-->
“,data[v0].G);
visited[v0]=1;
QueueInitiate(
QueueAppend(
//首先将起始节点入队列
while(QueenNotEmpty(Q))
{
QueueDelete(
StackPush(
//将每一个出队列的结点进行保存
w
=
GetFirstVex(G,u,visited);
if(w
==
vg)
{
SumExpand++;Expand
=
SumExpand;
break;
}
while(w
!=
-1)
{
if(
!visited[w])
{
printf(“%s-->
“,data[w].G);
visited[w]
=
1;
QueueAppend(
SumExpand++;
}
w
=
GetNextVex(G,u,w,visited);
}
}
StackPush(//此时w为目标节点
StackPush(
//此时u为w的父节点
StackPop(
while(StackNotEmpty(SaveQ))
{
StackPop(
StackTop(LineSave,if
(
Edge(G,u,y)==1
}
while(StackNotEmpty(LineSave))
{
StackPop(
BFS_path[i++]=u;
count
=
i;
}
}
3）A*
搜索
//
v0---起始节点
vg---目标节点
//
//
distance---用来保存已经过路径值
//
//
Expand---返回扩展结点数
//
//
G、data[]---用来读取图的各种信息
//
void
A_Search(AdjMGraph
G,HeuristicG
data[],int
v0,int
vg,int
distance,intExpand,int
visited[])
{
int
i,u,temp=10000;
static
int
path_num
=
0;
static
int
A_Search_flag
=
0;
//标志位---找到目标节点后退出递归
static
int
fx
=
0;
if(v0
==
2)
printf(“%s“,data[v0].G);
else
printf(“%s-->“,data[v0].G);
visited[v0]
=
1;
path_num++;
if(v0
==
vg)
{
A_Search_flag
=
1;Expand
=
path_num;
return;
}
for(i=0;i“,data[v0].G);
visited[v0]
=
1;
path_num++;
if(v0
==
vg)
{
G_Search_flag
=
1;Expand
=
path_num;
return;
}
for(i=0;i30时，回溯法已经很难找到解，运行时超过了20s。
当N>50时，GA算法运行时间开始逐渐变长，当N>90时运行时间已经超过了60s。
当N=200时，CSP的最小冲突法时间才仅为7.699s。
对比可知当N较大时，CSP的最小冲突法的效率最高，GA算法次之，回溯法在求解大的皇后数是效率最低。
对于回溯法的时间复杂度，最好情况是O(n^2)，最坏情况是O(n!)。
对于CSP的最小冲突法的时间复杂度，最好的情况是O(n^3)，最坏的情况是O（m*n^3）。
对于GA算法的时间复杂度，最好情况是O(n^3)，最坏的情况是O（p*n^3）。
6.主要代码
1、回溯法：
void
backtrack(int
column)
//以列作为判断点
{
int
row,i,j;
double
secs,ms;
BK_stop
=clock();
ms
=
(double)(BK_stop
-
BK_start);
if(ms>20000)
//回溯法运行超过20s就退出
{
printf(“BackT_Queen
Calculations
took
more
than
20
seconds
!/n“);
exit(0);
}
if
(
column==BK_Q_num)
{
BK_end
=
clock
()
;
secs
=
(double)(BK_end
-
BK_start)
/
CLOCKS_PER_SEC
;
printf(“Back_Queen
Calculations
took
%.3lf
second%s./n“,secs,(secs
eachFitness[i]
eachFitness[worst])
worst
=
i
;
if(p->eachFitness[worst]
==
GA_Q_num-1)
return;
baby
=p
;
for
(i
=
0
;
i
p->unitFitness
||
(double)rand()
/
RAND_MAX
slice)
{
selection
=
i;
break;
}
}
return
selection;
}
//
杂交
father,mother，
产生的子代保存在
baby中
void
CrossOverFM
(Population
father,Population
mother,Populationbaby)
{
int
flag[MAX_QUEENS]
;
int
pos1,pos2,tmp
;
int
i,j
;
//
随机产生两个基因断点
do
{
pos1
=
rand()
%
GA_Q_num
;
pos2
=
rand()
%
GA_Q_num
;
}
while
(pos1
==
pos2)
;
if
(pos1
>
pos2)
{
tmp
=
pos1
;
pos1
=
pos2
;
pos2
=
tmp;
}
for
(j
=
0
;
j
pos2)
{
while
(flag[mother.queen[j]])
j++
;
//保证每个皇后都不在同一行
baby->queen[i]
=
mother.queen[j]
;
j
++
;
}
else
baby->queen[i]
=
father.queen[i]
;
}
UpdateFitnessScore
(baby)
;
}
//
杂交产生子代
void
CrossOver
()
{
int
i
;
int
father,mother
;
Population
p[30
+
MAX_QUEENS
/
10]
;
int
count
;
//
计算总共的
Fitness，
用于轮盘赌局规则时候的选择
m_totFitness
=
0
;
for
(i
=
0
;
i
<
m_size
;
i++)
m_totFitness
+=
m_population[i].unitFitness
;
for
(count
=
0
;
count
<
m_size
-
2
;
count++)
{
father
=
RouletteWheelSelection
()
;
mother
=
RouletteWheelSelection
()
;
CrossOverFM
(m_population[father],m_population[mother],//
杂交,后代保存
}
//
将结果覆盖回原种群，加上原种群中适应度最高的两个个体组成新的进化后的种群
for
(count
=
0
;
count
<
m_size
-
2
;
count++)
m_population[count+2]
=
p[count]
;
}
31