圖與網(wǎng)絡(luò)1-資料下載頁
2024-10-04 17:10本頁面
【正文】 2 v5 v6 9 25 3 28 17 4 1 23 v1 v7 v4 v3 v2 v5 v6 9 3 28 17 4 1 23 v1 v7 v4 v3 v2 v5 v6 9 3 28 17 4 1 23 v1 v7 v4 v3 v2 v5 v6 9 3 17 4 1 23 總造價=1+4+9+3+17+23=57 v1 v7 v4 v3 v2 v5 v6 20 15 9 16 25 3 28 17 4 1 23 36 避圈法 v1 v7 v4 v3 v2 v5 v6 20 15 9 16 25 3 28 17 4 1 23 36 總造價 =1+4+9+3+17+23=57 其他樹 —— 搜索樹 一、 ??方法（是人工智能中常用方法） 例 98： 有 n根火柴，甲乙兩個依次可以從中任意取走 1根或 2根，但不能不取，取走最后一根火柴者為勝方，試討論取勝策略。為了便于理解，不妨假設(shè) n=7。 7 5 4 4 3 3 1 2 2 2 1 1 2 6 5 1 2 2 2 3 4 1 2 3 3 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 1 +1 +1 +1 1 1 1 1 1 1 1 1 1 在樹形圖中，圓圈中數(shù)字 7表示輪到甲方取時還有 7根，方框中數(shù)字 6表示表示輪到乙方取時還有 6根，依次類推。顯然，一旦最后出現(xiàn)方框（ 1或 2）狀態(tài)時乙方勝。反之，若最后出現(xiàn)圓圈（ 1或 2）狀態(tài)時甲方勝。 若甲方勝時得分 +1，乙方勝時甲方得分 1，無凝輪到甲方取時一定選擇能使他進入得分 +1狀態(tài)。同理輪到乙方取時一定選擇能使甲方進入得分 1狀態(tài)。 這樣從樹葉開始逐層向上，就可以算術(shù)出甲方勝負情況。 不難看出， n=1或 n=2時，先取者為勝， n=3時，先取者為敗。 如果 n=3k（ k正整數(shù)），假定先取者拿走 a根（ a=1或 2），則后者只要取走b 根，（滿足 a+b=3），使余下火柴為3（ k1）根，那么先取者必敗。如果 n不等于 3k，則先取者取 a根，使 na=3k，那么先取者必勝。 二、 DFS和 BFS法 DFS（ Depth First Search） 深度優(yōu)先法或深探法。 BFS（ Breadth First Search） 廣度優(yōu)先法或廣探法。 例 99： 一個人帶領(lǐng)一條狗、一只羊和一筐菜過河，河中有一條小船，只能乘一個人和一樣東西，而如果人不在場時，狗要咬羊，羊要吃菜，設(shè)想一種過河方案。 解： 用 m、 a、 b、 c表示人、狗、羊和菜。用廣探法確定（奇數(shù)次）過河方案。（二種過河方案） m a b c a c m a c ? m b b a m a b m b c c c m b c m a b a b m b ? m a c a c m a b c
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號-1