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)...

英語格言

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

Saying and doing are two things. 
                           -John Forwood

Silence is sometimes the severest criticism. 
                                  -Charles Buxton

Slow and steady wins the race.
                      -Robert Lloyd

Speaking without thinking is shooting without aiming.
-Spanish proberb

The empty vessel makes the greatest sound.
                                     -Shakespeare

What makes life dreary is the want of motive.
                                  -George Eliot

There is no royal road to learning.
-Trollope

Thought is the seed of action.
                      -Emerson

The less one thinks, the more one speaks.
           -French proverb

Only educated mem are self-educated.
                            -J. Bennett

It is the peculiarity of knowledge that those who really thirst for it always get it. 
                                                                          -R. Jefferies

Imagination is more important than knowledge.
                                        -Albert Einstein

Great man are not always wise.
                          -Bible

Doubting and questioning, you have got through half of your studying course.
                                                                      -Chan Fsien. Chang

Better to read litter with thought than much with levity and quickness.
                                                                    -Tupper

Conduct is three - fourths of our life and its largest concern.
                                                        -Mathew Arnold

A fault confessed is half redressed.
                            - F. G Bon

Never give advice in a crowd.
                          -Arab proverb

A good book is the precious life - blood of a master - spirit.
                                                         -Milton

A wise man thinks before he speaks, but a fool speaks and then thinks of what he has been saying.
                                                                                   -French proverb

All men naturally desire to know.
                            -Aristotle

Work has a bitter root but sweet fruit.
                                    -German proverb

「They say so」is half a lie.
                           -Thomas Fuller

Tie is rich enough that wants nothing.
                             -G. Herbert

Time and industry produce every day new knowledge.
                                             -Gobbes

Great man are not always wise.
                          -Bible

A fault confessed is half redressed.
                              -H. G. Bohn

Imagination is more important than knowledge.
                                 -Albert Einstein.

High thoughts must have high language.
                                 -Aristophanes

Our life is frittered away by detail ... Simplify, simplify.
                                                        -Henry Thoreau

Things are always at their best in their beginning.
                                          -Blaise Pascal

Seeing is believing.
               -Old Proverb

Form ever follows function.
                    -Louis Henri Sullivan

Intelligence ... is the faculty of making artificial objects, especially tools to make tools.
                                                                            -Henri-Louis Bergson

"Where shall I begin, please your majesty?" she asked. "Begin at the beginning," the king said, very gravely, "and go on till you come to the end; then stop."
                                                                                                                                                      -Lewis Carroll

It is a capital mistake to theorize before one has data.
                                     -Arthur Conan Doyle


... the wisest prophets make sure of the event first.
                                            -Horace Walpole

An actor entering through the door, you've go nothing. But if he enters through the window, you've got a situation.
                                                                                                        -Billy Wilder

You shall see them on a beautiful quarto page, where a neat rivulet of text shall meander through a meadow or margin.
                                                                                                     -Richard Brinsely Sheridan

Exit, pursued by a bear.
           -William Shakespeare

Use it up, wear it out; Make it do, or do without.
                                       -Anonymous

Eternity is a terrible thought. I mean, when's it going to end?
                                                     -Tom Stoppard

If you don't know where you're going, you will probably end up somewhere else.
                                                      The Peter Principle[1969] Laurence Johnston Peter

Who can control his fate?
               -William Shakespeare, Othello

Man is a tool-making animal.
                 -Benjamin Franklin

Intelligence ... is the faculty of making artificial objects, especially tools to make tools.
                                                                                   -Henri Bergson

You could know your own language only if you compared it with other language.     --Engels

Here are only numbers ratified.   --William Shakespeare

Nature has some sort of arithmetic-geometrical coordinate system, because nature has all kinds of models. What we experience of nature is in models, and all of nature's models are so beautiful.

It struck me that nature's system must be a real beauty, because in chemistry we find that the associations are always in beautiful whole numbersthere are no fractions.   --Richard Buckminster Fuller

留言

這個網誌中的熱門文章