Tree Search（樹狀搜尋)

-
一、什麼是 Tree Search（樹狀搜尋）？ 在人工智慧（AI）與演算法中，許多問題都可以表示成一棵樹(圖一)： 起點(A) / | \ B C D /|\ | / \ E F G H I J 每個節點(Node)代表一種狀態(State)。 例如： 迷宮中的位置 棋局的盤面 路徑規劃中的城市 遊戲中的決策 搜尋演算法的目的： 從起點找到目標節點（Goal Node） 二、Breadth First Search (BFS) 核心思想 先搜尋離起點最近的節點。 一層一層往外擴展。 Level 0: A Level 1: B C D Level 2: E F G H I J 搜尋順序： A B C D E F G H I J 圖一結果： A → B → C → D → E → F → G → H → I → J 使用資料結構 Queue（佇列） FIFO： First In First Out 先進先出 例如： Queue: A 取出A 加入B,C,D Queue: B,C,D BFS特性 優點 如果邊權重相同： BFS一定找到最短路徑。 缺點 需要大量記憶體。 假設每個節點有10個子節點： 深度5： 10^5 = 100000 需要保存很多節點。 時間複雜度 O(V + E) V = Vertex（節點數） E = Edge（邊數） 三、Depth First Search (DFS) 核心思想 一路往下走到底。 不能走才回頭。 A | B | E 然後： A | B | F 搜尋順序 圖一結果： A B E F G C H D I J 使用資料結構 Stack（堆疊） LIFO Last In First Out 後進先出 例如： push(B) push(C) push(D) pop() => D DFS特性 優點 記憶體需求小。 只需保存： 目前路徑 即可。 缺點 可能找到很差的解。 例如： A ├── Goal └── 巨大子樹 DFS可能先跑完整個巨大子樹。 時間複雜度 O(V+E)...
張貼留言

Python 迴文數(Palindromic number)

-
根據的維基百科說明：
迴文數或回文數是指一個像14641這樣「對稱」的數，即：將這個數的數字按相反的順序重新排列後，所得到的數和原來的數一樣。這裡，「回文」是指像「媽媽愛我，我愛媽媽」這樣的，正讀反讀都相同的單詞或句子。

方法一，用迴圈拆解數字：


方法二，用字串來解：


Python程式碼：
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
# 方法一
while True:
    try:
        n = int(input())

        # 小於零，或是個位數為零都不會是迴文
        if( n < 0 or (n % 10 == 0 and n != 0)):
            print("不是回文數")
        else:
            # 翻轉後的數字
            rNum = 0
            while(n > rNum):
                rNum = rNum * 10 + n % 10
                n = n // 10

            if(n == rNum or n == rNum // 10):
                print("是回文數")
            else:
                print("不是回文數")

    except EOFError:
        break


# 方法二
while True:
    try:
        n = input()
        length = len(n)
        m = length / 2
        i = 0

        yes = True
        while(i <= m):
            if( n[i] != n[length - i - 1] ):
                yes = False
                break
            i = i + 1

        if yes == True:
            print("是回文數")
        else:
            print("不是回文數")

    except EOFError:
        break

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

If you like this post, please click the ads on the blog or buy me a coffee. Thank you very much.

留言

張貼留言

這個網誌中的熱門文章