图搜索算法
图搜索技术时人工智能中的核心技术之一,并且在其他场合也有着非常广泛的应用。这里的图称为状态图,指由节点和有向(带权)边所做成的网络,每个节点即状态。按照搜索的方式不同,图搜索一般分为树式搜索和线式搜索。两者最大的区别就在于搜索过程中所记录的轨迹不同,顾名思义,树式搜索记录的是一颗搜索树,而线式搜索是一条折线。我们一般用一个Closed表的数据结构来记录搜索节点,对于树式搜索来说,Closed表存储的正是一颗不断成长的搜索树,而线式搜索存储的则是一条不断伸长的折线,如果能找到目标节点的话,它本身就是搜索的路径。而树式搜索需要通过目标节点进行回溯,直至初始节点,从而找到路径。