---
# System prepended metadata

title: '人工智慧 Homework #1 #2'
tags: [AI]

---

---
tags: AI
disqus: HackMD
---

人工智慧 Homework #1 #2
===

    In the circles of A to J, fill in numbers from 1 to 10 randomly 
    such that the values in the triangles are equal to the summations 
    of the values filled in the circles surrounding the triangles, 
    for example A+D+E= 18 and so on.
    Part 1:  Due in 12/Nov./2020 midnight.
        (a) Use Breadth First Search, Uniform Cost Search (deep level as cost), 
        and Depth First Search to find out possible solution(s).
        (b) For these three methods also count the nodes expanded 
        for finding the solution(s).
    Part 2: Due in 19/Nov./2020 midnight
         Using the solution found in Part 1, 
         invent a heuristic function f (e.g. node level + f(n) or others ) 
         to find the route to the solution. Also count the nodes expanded 
         for finding the solution(s).

加載程式所需的函示庫
---
```python=
import collections
import numpy as np
from itertools import permutations
```

![](https://i.imgur.com/rYWzEhj.gif)
將上圖中所用到的數值存入容器
---

```python=
nodeValues = {}
initNodesSum = {
    'ACD': 19, 'ADE': 18,
    'BCF': 11, 'DEG': 16,
    'FHI': 17, 'GHJ': 22
    }
triangleNodes = {
    'ACD': ['BCF', 'ADE', 'DEG'],
    'ADE': ['DEG'],
    'BCF': ['FHI'],
    'DEG': ['GHJ'],
    'FHI': ['GHJ'],
    'GHJ': ['FHI']
    }
NextNodes = {
    'A': ['B', 'C', 'D', 'E'],
    'B': ['C', 'F', 'I'],
    'C': ['B', 'D', 'F'],
    'D': ['C', 'E', 'G'],
    'E': ['D', 'G', 'J'],
    'F': ['H', 'I'],
    'G': ['H', 'J'],
    'H': ['I', 'J'],
    'I': ['J'],
    'J': []
    }
```

將圖中三角形周圍節點 A-J 以 1-10 數字填滿
並滿足三角形周圍三個節點相加等於三角形中的數字
例如:A+C+D=19

以窮舉法計算出三角形周圍節點數字
避免浪費計算時間，遇到相鄰數字相同則跳過
並排除計算三角形周圍節點相加不等於欲求總和的組合
例如:A+C+D=19 非19則跳過不處理

```python=
def get_random_dict():
    for kA in range(1, 11):
        for kB in range(1, 11):
            if kA == kB:
                continue
            for kC in range(1, 11):
                if kC == kA or kC == kB:
                    continue
                for kD in range(1, 11):
                    if kD == kC or kD == kB or kD == kA or kA + kC + kD != initNodesSum.get('ACD'):
                        continue
                    for kE in range(1, 11):
                        if kE == kD or kE == kC or kE == kB or kE == kA or kA + kD + kE != initNodesSum.get('ADE'):
                            continue
                        for kF in range(1, 11):
                            if kF == kE or kF == kD or kF == kC or kF == kB or kF == kA or kB + kC + kF != initNodesSum.get('BCF'):
                                continue
                            for kG in range(1, 11):
                                if kG == kF or kG == kE or kG == kD or kG == kC or kG == kB or kG == kA or kD + kE + kG != initNodesSum.get('DEG'):
                                    continue
                                for kH in range(1, 11):
                                    if kH == kG or kH == kF or kH == kE or kH == kD or kH == kC or kH == kB or kH == kA:
                                        continue
                                    for kI in range(1, 11):
                                        if kI == kH or kI == kG or kI == kF or kI == kE or kI == kD or kI == kC or kI == kB or kI == kA or kF + kH + kI != initNodesSum.get('FHI'):
                                            continue
                                        for kJ in range(1, 11):
                                            if kJ == kI or kJ == kH or kJ == kG or kJ == kF or kJ == kE or kJ == kD or kJ == kC or kJ == kB or kJ == kA or kG + kH + kJ != initNodesSum.get('GHJ'):
                                                continue
                                            if kA + kC + kD == initNodesSum.get('ACD') and \
                                                kA + kD + kE == initNodesSum.get('ADE') and \
                                                kB + kC + kF == initNodesSum.get('BCF') and \
                                                kD + kE + kG == initNodesSum.get('DEG') and \
                                                kF + kH + kI == initNodesSum.get('FHI') and \
                                                kG + kH + kJ == initNodesSum.get('GHJ'):
                                                nodeValues['A'] = kA
                                                nodeValues['B'] = kB
                                                nodeValues['C'] = kC
                                                nodeValues['D'] = kD
                                                nodeValues['E'] = kE
                                                nodeValues['F'] = kF
                                                nodeValues['G'] = kG
                                                nodeValues['H'] = kH
                                                nodeValues['I'] = kI
                                                nodeValues['J'] = kJ
                                                return
```

搭配隊列結構容器執行BFS及DFS演算法
---
```python=
def getflow(root, method):
    visited = set() # 暫存所有訪問過的節點紀錄
    queue = collections.deque([root]) # 將起始節點加入隊列結構容器
    flow = collections.deque() # 紀錄訪問流程

    visited.add(root)
    while queue:
        triangle = queue.popleft() # 從隊列頭部(左端)取出進行後續演算法處理
        flow.append(triangle)
        IsFirst = True # DFS用於紀錄節點處理相鄰之集合
        for next_triangle in triangleNodes[triangle]: # 處理節點所有相鄰之集合
            if next_triangle not in visited: # 訪問過的節點跳過不處理
                if method == 'BFS':
                    queue.append(next_triangle)
                elif method == 'DFS':
                    if IsFirst:
                        queue.appendleft(next_triangle) # 加入到隊列左端，走到盡頭時可往返到上一層
                    else:
                        queue.insert(1, next_triangle) # 加入到處理中的隊列左端下一個節點
                IsFirst = False
                visited.add(next_triangle)
    return flow
```

使用貪婪優先搜尋法找出最短路徑
---
```python=
    visited = set()
    flow = collections.deque()
    flow.append(startNode)
    while True:
        neighborDist = 10
        visited.add(startNode)
        for nodes in NextNodes[startNode]:
            if nodes not in visited:
                if abs(nodeValues['A'] - nodeValues[nodes]) < neighborDist:
                    neighborDist = abs(nodeValues['A'] - nodeValues[nodes])
                    nextNode = nodes
        startNode = nextNode
        flow.append(nextNode)
        if nextNode in endNode:
            break
    return list(flow)
```

主程式開始
---
```python=
if __name__ == '__main__':
    get_random_dict()
    print('Nodes value:', end=' ')
    IsFirst = True
    for val in nodeValues:
        if IsFirst:
            IsFirst = False
            print(val + ': ' + str(nodeValues.get(val)), end='')
        else:
            print(', ' + val + ': ' + str(nodeValues.get(val)), end='')
    print()
    print()
    
    BFSFlow = getflow('ACD', 'BFS')
    print('BFS Path:', end=' ')
    for path in BFSFlow:
        if path == BFSFlow[-1]:
            print(path)
        else:
            print(path, '->', end=' ')
    print()

    DFSFlow = getflow('ACD', 'DFS')
    print('DFS Path:', end=' ')
    for path in DFSFlow:
        if path == DFSFlow[-1]:
            print(path)
        else:
            print(path, '->', end=' ')
    print()

    shortestPath = getShortestPath('A', ['I', 'J'])
    print('Shortest Path: ', end=' ')
    for path in shortestPath:
        if path == shortestPath[-1]:
            print(path)
        else:
            print(path, '->', end=' ')
```

result
---
:::info
Nodes value: A: 9, B: 6, C: 2, D: 8, E: 1, F: 3, G: 7, H: 10, I: 4, J: 5

BFS Path: ACD -> BCF -> ADE -> DEG -> FHI -> GHJ

DFS Path: ACD -> BCF -> FHI -> GHJ -> DEG -> ADE

Shortest Path:  A -> D -> G -> H -> J
:::