91av视频/亚洲h视频/操亚洲美女/外国一级黄色毛片 - 国产三级三级三级三级

  • 大小: 5.08KB
    文件類型: .zip
    金幣: 1
    下載: 0 次
    發布日期: 2024-05-07
  • 語言: Python
  • 標簽: python??實現??py??搜索??

資源簡介


1. 實驗目的 

1） 掌握搜索算法的基本設計思想與方法，  

2） 掌握A*算法的設計思想與方法，  

3） 熟練使用高級編程語言實現搜索算法，  

4） 利用實驗測試給出的搜索算法的正確性。  


1. 實驗問題 

尋路問題。以圖1為例，輸入一個方格表示的地圖，要求用A*算法找到并輸出從起點（在方格中標示字母S）到終點（在方格中標示字母T）的代價最小的路

徑。有如下條件及要求：  

1） 每一步都落在方格中，而不是橫豎線的交叉點。

2） 灰色格子表示障礙，無法通行。

3） 在每個格子處，若無障礙，下一步可以達到八個相鄰的格子，并且只可以到達無障礙的相鄰格子。其中，向上、下、左、右四個方向移動的代價為1，向四

個斜角方向移動的代價為 √2。

4） 在一些特殊格子上行走要花費額外的地形代價。比如，黃色格子代表沙

漠，經過它的代價為4；藍色格子代表溪流，經過它的代價為2；白色格子為普通地形，經過它的代價為0。

5） 經過一條路徑總的代價為移動代價 地形代價。其中移動代價是路徑上所做的所有移動的代價的總和；地形代價為路徑上除起點外所有格子的地形代價的總和。



資源截圖

代碼片段和文件信息 

import?numpy?as?np
import?matplotlib.pyplot?as?plt
import?numpy?as?np;?np.random.seed（0）
import?seaborn?as?sns;?sns.set（）
import?matplotlib.pyplot?as?plt
from?matplotlib.colors?import?ListedColormap

import?numpy?as?np
import?matplotlib.pyplot?as?plt
import?numpy?as?np;

np.random.seed（0）
import?seaborn?as?sns;

sns.set（）
import?matplotlib.pyplot?as?plt
from?matplotlib.colors?import?ListedColormap

#?%%

#?地形

#?通路
road?=?0
#?沙漠
caravan?=?4
#?路障
barrier?=?1
#?河流
river?=?2

#?起始點，終止點
st_end?=?3
#?path
path1?=?5
path2?=?6

#?直線距離
d?=?1
#?斜線距離
k?=?1.414


def?check_pass（terrain）:
????if?terrain?==?road?or?terrain?==?caravan?or?terrain?==?river:
????????return?True
????else:
????????return?False


class?Node:
????def?__init__（self?x?y）:
????????self.x?=?x
????????self.y?=?y
????????self.F?=?.0
????????self.G?=?.0
????????self.H?=?.0
????????self.parent?=?None


def?least_f（open）:
????res?=?open[0]
????for?node?in?open:
????????if?node.F?????????????res?=?node
????return?res


def?get_surrounds（node?area_map?close）:
????res?=?[]
????for?i?in?range（-1?2）:
????????for?j?in?range（-1?2）:

????????????if?i?==?0?and?j?==?0:
????????????????continue

????????????x?=?node.x?+?i
????????????y?=?node.y?+?j

????????????#?超出邊界
????????????if?x?????????????????????len（area_map）?<=?x?or?len（area_map[0]）?<=?y:
????????????????continue
????????????????#?判斷是否可行
????????????if?not?check_pass（area_map[x][y]）:
????????????????continue
????????????#?未訪問過
????????????node_tmp?=?Node（x?y）
????????????flag?=?is_in_list（node_tmp?close）
????????????if?flag?is?None:
????????????????res.append（node_tmp）

????return?res


#?Calc?G
def?calc_g（start?surround?area_map）:
????extra_g?=?d?if?（（abs（surround.y?-?start.y）?+?abs（surround.x?-?start.x））?==?1）?else?k
????extra_g?+=?area_map[surround.x][surround.y]??#?額外的地形代價
????parent_g?=?0?if?surround.parent?is?None?else?surround.parent.G??#?當前點的父節點的起始點到父節點的代價
????surround.G?=?parent_g?+?extra_g??#?當前步＋之前的步


def?is_in_list（surround1?close）:
????for?c?in?close:
????????if?surround1.x?==?c.x?and?surround1.y?==?c.y:
????????????return?c
????return?None


def?calc_h（surround?close?m_tmp）:??#?計算當前點到終點的距離
#?def?calc_h（surround?end）:??#?計算當前點到終點的距離
????#?h_diagonal?=?min（abs（surround.x?-?end.x）?abs（surround.y?-?end.y））
????#?h_straight?=?abs（surround.x?-?end.x）?+?abs（surround.y?-?end.y）
????#?surround.H?=?k?*?h_diagonal?+?d?*?（h_straight?-?2?*?h_diagonal）
????min_h?=?99999
????surroundPoints?=?get_surrounds（surround?m_tmp?close）
????for?target?in?surroundPoints:
????????if?is_in_list（target?close）?is?not?None:
????????????if?（abs（target.x?-?surround.x）?+?abs（target.y?-?surround.y））?==?1:
????????????????if?（d?+?m_tmp[surround.x][surround.y]）?????????????????????min_h?=?d?+?m_tmp[surround.x][surround.y]
????????????else:
????????????????if?k?+?m_tmp[surround.x][surround.y]

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????文件???????10263??2020-12-02?16:07??a_star_bidirection.py
?????文件????????9389??2020-12-04?09:17??a_star_single.py

評論

共有 條評論