Chapter3

13331130 李有才
人工智能

3.19

可以使用A*算法

function Find-Route(Page page1, Page page2) return a path
    page1 <-- 初始页面
    page2 <-- 目标页面
    //按照评估函数f(n)排序的优先权队列
    pri-queue <-- sorted by WebPage.RelevancyToEndPage
    //记录访问过的节点
    visited
    pri-queue.INSERT(page1)
    loop do
        if EMPTY(pri-queue)
        then
            return failure
        //选择与目标网页相关度最高的节点
        currentPage <-- pri-queue.POP
        add currentPage to visited
        if currentPage is page2
        then
            return path
        else
            for each item in AdjacentPages(currentPage) do
                if item is not in visited
                then
                    currentPage.NEXT <-- item
                    relevance ← CaltulateRelevancyToEndPage(item)
                    pri-queue.INSERT-WITH-PRIORITY(item, relevance)

搜索引擎保存了页面之间的相互关系，可以实现一个前任函数，同样也适用双向搜索

3.23

Format:$f: g + h$
1. $L: 0 + 244 = 244$
2. 扩展$L$:
$M: 70 + 241 = 311$, $T: 111 + 329 = 440$
3. 扩展$M$:
$L: 140 + 244 = 384$, $D: 145 + 242 = 387$, $T: 111 + 329 = 440$
4. 扩展$L$:
$D: 145 + 242 = 387$, $T: 111 + 329 = 440$, $M: 210 + 241 = 451$, $T_1: 251 + 329 = 580$
5. 扩展$D$:
$C: 265 +160 = 425$, $T: 111 + 329 = 440$, $M: 210 + 241 = 451$, $M: 220 + 241 = 461$, $T_1: 251 + 329 = 580$
6. 扩展$C$
$T: 111 + 329 = 440$, $M: 210 + 241 = 451$, $M_1: 220 + 241 = 461$, $P: 403 + 100 = 503$, $T_1: 251 + 329 = 580$, $R: 411 + 193 = 604$, $D: 385 + 242 = 627$
7. 扩展$T$:
$M: 210 + 241 = 451$, $M_1: 220 + 241 = 461$, $L: 222 + 244 = 466$, $P: 403 + 100 = 503$, $T_1: 251 + 329 = 580$, $A: 229 + 366 = 595$, $R: 411 + 193 = 604$, $D: 385 + 242 = 627$
8. 扩展$M$:
$M_1: 220 + 241 = 461$, $L: 222 + 244 = 466$, $P: 403 + 100 = 503$, $L_1: 280 + 244 = 524$, $D: 285 + 242 = 527$, $T_1: 251 + 329 = 580$, $A: 229 + 366 = 595$, $R: 411 + 193 = 604$, $D_1: 385 + 242 = 627$
9. 扩展$M_1$：
$L: 222 + 244 = 466$, $P: 403 + 100 = 503$, $L_1: 280 + 244 = 524$, $D: 285 + 242 = 527$, $L_2: 290 + 244 = 534$, $D2：220 + 75 + 242 = 537$, $T_1: 251 + 329 = 580$, $A: 229 + 366 = 595$, $R: 411 + 193 = 604$, $D_1: 385 + 242 = 627$
10. 扩展$L$:
$P: 403 + 100 = 503$, $L_1: 280 + 244 = 524$, $D: 285 + 242 = 527$, $M：222 + 70 + 241 = 533$, $L_2: 290 + 244 = 534$, $D2：220 + 75 + 242 = 537$, $T_1: 251 + 329 = 580$, $A: 229 + 366 = 595$, $R: 411 + 193 = 604$, $D_1: 385 + 242 = 627$, $T：222 + 111 + 329 = 662$
11. 扩展$P$:
$B: 504 + 0 = 504$, $L_1: 280 + 244 = 524$, $D: 285 + 242 = 527$, $M：222 + 70 + 241 = 533$, $L_2: 290 + 244 = 534$, $D2：220 + 75 + 242 = 537$, $T_1: 251 + 329 = 580$, $A: 229 + 366 = 595$, $R: 411 + 193 = 604$, $D_1: 385 + 242 = 627$, $T：222 + 111 + 329 = 662$, $R: 500 + 193 = 693,$C: 541 + 160 = 701$
12. B在队首，找到路径

3.27

a）状态空间$(n*n)(n*(n-1))....n$
b）$5^n$
c）曼哈顿距离
d）选择$min(h_1, ..., h_2)$

3.30

a）旅行商问题要求从起点开始每个城市访问一次，最终回到起点。最小生成树连接所有点，但不能形成环，所以可以看作从旅行商问题减少了“形成环”这一限制（即通过松弛的TSP问题）得到的。
b）MST启发式考虑了城市之间的连接路径，直线距离在城市数量增多时准确性下降很快

c）

function GenerateTSP(CityNumber N) return a instance
    Instance <-- the final graph to return
    Square <-- domain
    for i = 1 to N
        position <-- getRandomPositionFromSquare(Square)
        Instance.city[N].setPosition(position)

d）

function TSPSolution(Instance instance) return a path
    roads[N][N] <-- roads between sities
    startCity <-- instacne.StartCity
    pri-queue <-- 按以未到达城市为根节点生成的MST的边长之和排序
    visited
    pri-queue.INSERT(startCity)
    loop do
        if pri-queue.EMPTY
        then
            return failure
        currentCity <-- pri-queue.POP
        visited[currentCity] <-- true
        for i in roads[N]
            if i is startCity and AllCityVisited
            then
                return path
            if i is not currentCity and cisited[i] is fasle
            then
                visited[i] = true
                weight <-- GetMSTValue(roads, visited)
                pri-queue.INSETR-WITH_PRIORITY(currnetCity, weight)
                explored[i] <-- false

// 使用Kruskal算法求解最小生成树
function Get-MST-Value(roads, visited) returns a value
    cities ← Get-Unexplored-Cities(visited)
    edge ← Get-Roads-Between-Unexplored-Cities(roads) 
    value ← zero
    viewed ← empty set
    loop do
        if All-Viewed() 
        then
            return value
        edgeNow ← POP-Min-Weight-Edge(edge)
        if edgeNow.start and edgeNow.end are all in viewed 
        then
            continue
        value.ADD(edgeNow.weight)
        viewed.INSERT(edgeNow.start)
        viewed.INSERT(edgeNow.end)

3.32

1. 曼哈顿距离

   function Get-Manhattan-Distance() return a value
       value <-- zero
       currentNodeState <-- the current state of the eight num
       targetNodeState <-- the target state of the eight num
       for node in currentNodeState do
           nowPosition <-- node.getPosition()
           num <-- nowPosition.getNum()
           targetPosition <-- targetNodeState.getNodeAt(num).getPosition()
           colDis <-- abs(nowPosition.col-targetPosition.col)
           rowDis <-- abs(nowPosition.row-targetPosition.row)
           value.ADD((int)sqrt(pow(colDis, 2)+pow(rowDis, 2)))
       return value

2. 错位棋子数

   function Get-Wrong-Node-Count() returns a value
       value <-- zero
       currentNodeState <-- the current state of the eight num
       targetNodeState <-- the target state of the eight num
       for node in currentNodeState do
           nowPosition <-- node.getPosition()
           num ← nowPosition.getNum()
           targetPosition <-- targetNodeState.getNodeAt(num).getPosition()
           if nowPosition is not targetPosition then
               value.ADD(1)
       return value

3. 后续节点不正确的个数

   function Get-Wrong-Node-Count() returns a value
       value <-- zero
       currentNodeState <-- the current state of the eight num
       for node in currentNodeState do
           nowPosition <-- node.getPosition()
           nowNextPosition <-- nowPosition.getNext()
           nextNodePosition <-- node.next().getPosition()
           if nowNextPosition is not nextNodePosition then
               value.ADD(1)
       return value

4. 性能分析：