<span>68 words</span><span class="px-2 text-primary-500">·</span><span title="Reading time">1 min</span><span class="px-2 text-primary-500">·</span><span>
<span id="views_posts/search-algorithm/index.md" title="views">0</span>
<span class="inline-block align-text-bottom">
<span class="relative block icon">
<svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 576 512">
<path fill="currentColor" d="M288 32c-80.8 0-145.5 36.8-192.6 80.6C48.6 156 17.3 208 2.5 243.7c-3.3 7.9-3.3 16.7 0 24.6C17.3 304 48.6 356 95.4 399.4C142.5 443.2 207.2 480 288 480s145.5-36.8 192.6-80.6c46.8-43.5 78.1-95.4 93-131.1c3.3-7.9 3.3-16.7 0-24.6c-14.9-35.7-46.2-87.7-93-131.1C433.5 68.8 368.8 32 288 32zM432 256c0 79.5-64.5 144-144 144s-144-64.5-144-144s64.5-144 144-144s144 64.5 144 144zM288 192c0 35.3-28.7 64-64 64c-11.5 0-22.3-3-31.6-8.4c-.2 2.8-.4 5.5-.4 8.4c0 53 43 96 96 96s96-43 96-96s-43-96-96-96c-2.8 0-5.6 .1-8.4 .4c5.3 9.3 8.4 20.1 8.4 31.6z"/></svg>
</span>
</span>
</span><span class="px-2 text-primary-500">·</span><span>
<span id="likes_posts/search-algorithm/index.md" title="likes">0</span>
<span class="inline-block align-text-bottom">
<span class="relative block icon">
<svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512">
<path fill="currentColor" d="M47.6 300.4L228.3 469.1c7.5 7 17.4 10.9 27.7 10.9s20.2-3.9 27.7-10.9L464.4 300.4c30.4-28.3 47.6-68 47.6-109.5v-5.8c0-69.9-50.5-129.5-119.4-141C347 36.5 300.6 51.4 268 84L256 96 244 84c-32.6-32.6-79-47.5-124.6-39.9C50.5 55.6 0 115.2 0 185.1v5.8c0 41.5 17.2 81.2 47.6 109.5z"/></svg>
</span>
</span>
</span><span class="px-2 text-primary-500">·</span><span>
<button id="likes_button"
class="rounded-md border border-primary-400 px-1 py-[1px] text-xs font-normal text-primary-700 dark:border-primary-600 dark:text-primary-400"
onclick="process_article()">
<span id="likes_button_heart" style="display:none" class="inline-block align-text-bottom">
<span class="relative block icon">
<svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512">
<path fill="currentColor" d="M47.6 300.4L228.3 469.1c7.5 7 17.4 10.9 27.7 10.9s20.2-3.9 27.7-10.9L464.4 300.4c30.4-28.3 47.6-68 47.6-109.5v-5.8c0-69.9-50.5-129.5-119.4-141C347 36.5 300.6 51.4 268 84L256 96 244 84c-32.6-32.6-79-47.5-124.6-39.9C50.5 55.6 0 115.2 0 185.1v5.8c0 41.5 17.2 81.2 47.6 109.5z"/></svg>
</span>
</span>
<span id="likes_button_emtpty_heart" class="inline-block align-text-bottom">
<span class="relative block icon">
<svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512">
<path fill="currentColor" d="M244 84L255.1 96L267.1 84.02C300.6 51.37 347 36.51 392.6 44.1C461.5 55.58 512 115.2 512 185.1V190.9C512 232.4 494.8 272.1 464.4 300.4L283.7 469.1C276.2 476.1 266.3 480 256 480C245.7 480 235.8 476.1 228.3 469.1L47.59 300.4C17.23 272.1 0 232.4 0 190.9V185.1C0 115.2 50.52 55.58 119.4 44.1C164.1 36.51 211.4 51.37 244 84C243.1 84 244 84.01 244 84L244 84zM255.1 163.9L210.1 117.1C188.4 96.28 157.6 86.4 127.3 91.44C81.55 99.07 48 138.7 48 185.1V190.9C48 219.1 59.71 246.1 80.34 265.3L256 429.3L431.7 265.3C452.3 246.1 464 219.1 464 190.9V185.1C464 138.7 430.4 99.07 384.7 91.44C354.4 86.4 323.6 96.28 301.9 117.1L255.1 163.9z"/></svg>
</span>
</span>
<span id="likes_button_text"> Like</span>
</button>
</span><span class="px-2 text-primary-500">·</span>
<span class="mb-[2px]">
<a
href="https://github.com/Anoxiacxy/hugo-blog/tree/main/content/posts/search-algorithm/index.md"
class="text-lg hover:text-primary-500"
rel="noopener noreferrer"
target="_blank"
title="Edit content"
><span class="inline-block align-text-bottom">
<span class="relative block icon">
<svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512"><path fill="currentColor" d="M490.3 40.4C512.2 62.27 512.2 97.73 490.3 119.6L460.3 149.7L362.3 51.72L392.4 21.66C414.3-.2135 449.7-.2135 471.6 21.66L490.3 40.4zM172.4 241.7L339.7 74.34L437.7 172.3L270.3 339.6C264.2 345.8 256.7 350.4 248.4 353.2L159.6 382.8C150.1 385.6 141.5 383.4 135 376.1C128.6 370.5 126.4 361 129.2 352.4L158.8 263.6C161.6 255.3 166.2 247.8 172.4 241.7V241.7zM192 63.1C209.7 63.1 224 78.33 224 95.1C224 113.7 209.7 127.1 192 127.1H96C78.33 127.1 64 142.3 64 159.1V416C64 433.7 78.33 448 96 448H352C369.7 448 384 433.7 384 416V319.1C384 302.3 398.3 287.1 416 287.1C433.7 287.1 448 302.3 448 319.1V416C448 469 405 512 352 512H96C42.98 512 0 469 0 416V159.1C0 106.1 42.98 63.1 96 63.1H192z"/></svg>
</span>
</span></a
>
</span>
搜搜算法的核心
- state，状态，状态对应了搜索过程中的节点（node）
- action，动作
状态可以是一个数，可以是一个数组，可以是任何一系列能够描述事物的参数。比如对于迷宫而言，我们会将迷宫的每个位置有什么作为状态。
动作存在于两个状态之间，比如我有一个动作是交换相邻元素。那么对于状态
[1, 2, 3] -> [1, 3, 2]
以上就是交换后两个元素的动作。
相邻状态，就是能从一个状态，执行一步动作就能到达的状态集合
[1, 2, 3] -> [2, 1, 3] [1, 2, 3] -> [1, 3, 2]状态123，经过一次交换动作，只能到达状态213，132，无法到达状态321，312，231
fringe，边界（状态）集合，边界就是我已经枚举到了这个状态，但还没有从这个状态出发，考虑这个状态能够通过动作扩展出其他状态的状态集合（还没扩展）。
搜索时这样的一个过程：从一个状态开始，枚举所有可能的动作，找到该动作的相邻状态，然后从相邻状态继续出发，枚举所有可能的动作，得到相邻状态的相邻状态，……如此重复，从一个状态可以达到相邻状态的相邻状态的相邻状态的相邻状态……，将所有可能的状态按照这种方式枚举出来的过程，就叫做搜索。
搜索往往时有目标的，当我们枚举到一个满足条件的内容时，就可以停下的，这个目标一般称为 goal。
搜索算法的分类
Lecture3: uninformed search，也就是没有额外信息的搜搜，常见算法 DFS，BFS，DLS，IDS
DFS：Depth first search，深度优先搜索，简称深搜：
深搜就是在边界集合 fringe 中，优先扩展深度最深的节点（深度就是从初始状态 init state 开始，需要多少个 action 才能到达该状态）
BFS：Breath first search，广度优先搜索，简称广搜：
广搜就是在边界集合 fringe 中，优先扩展深度最浅的节点
Lecture4 ：informed search
- A*：BFS和DFS是两个极端，一个最深一个最浅，但都不够智能，而且仅仅使用了深度作为判断的依据。我们将深度称为 g，当前状态到终止状态的估计步数称为 h，定义新的价值为 f=g + h，然后优先扩展 f 最小的节点。f 最小意味着，这一个节点在目前所有见过的节点中，估计能够最快搜索到终点 goal