算法目的

找到从起点到终点间的最短（最优）路径。

关键问题是如何利用知识，尽可能有效地找到问题的解或最优解。

回溯

概述

精髓在于尝试和递归回溯。

八皇后问题

八皇后问题就是说在棋盘上摆8个皇后让她们互相不处于对方的控制域内。本例中为了演示方便把搜索空间减小为一个的棋盘，变成四皇后问题。。

基本概念

不确定性推理是建立在非经典逻辑基础上的一种推理，它是对不确定性知识的运用与处理。

严格地说，所谓不确定性推理就是从不确定性的初始证据出发，通过运用不确定性的知识，最终推出具有一定程度的不确定性但却是合理或者近乎合理的结论的思维过程。

基本概念

推理方式

从推出结论的途径划分：演绎、归纳、默认

演绎

从全称判断推导出单称判断的过程，由一般知识推理细化出适合某一情况的结论。从一般到个别。

一阶谓词逻辑

命题

非真即假，陈述句，唯一的真值。

如果满足上述条件而暂时无法确定真值也算，明天是晴天、存在外星人都是命题。

Overview

Given the equivalence relation on A set , we can divide into several equivalence classes by . These equivalence classes form a partition of a set.

Conversely, given a partition of a set, we can define an equivalence relation: if two elements belong to the same subset, then they are equivalent. This gives us an equivalence relation.

Theorem

Let be a group, any subgroup of , then the number of left (right) cosets of in is called the index of in , denoted as .

Lagrange's Theorem：

is a finite group, any subgroup of , then .

Proof: Let , then there are distinct left cosets of , denote , then is a partition of (Partition is not covering, cosets in are not overlapped), at this time we have

Definition

Let be a subgroup of (i.e., ). If for all , , then is called a normal subgroup of (or an invariant subgroup), denoted as .

In this case, the left and right cosets are simply called cosets.

The two trivial subgroups of , and itself, are normal subgroups.

Overview

Review the definition of symmetry group:

Let be an arbitrary set. . The group formed by the composition of such permutations is called the symmetric group on . -

Why is it called a symmetric group? This is because such groups describe the symmetry of objects. - In nature and real life, many objects have symmetry, such as isosceles triangles, squares, and regular polyhedra in geometric shapes. The symmetry of these shapes can be described as a transformation in the plane or space where the image of the shape coincides with itself.

Overview

The left and right cosets of a normal subgroup are the same, and the set of all cosets forms a partition of the group. Using the same equivalence relation to form the quotient group, it is denoted by . A group can be defined on , called the quotient group.

is a normal subgroup of . Let the set which is the set formed by all cosets of in .