Homework1

2018013402 方麟 im.fl@icloud.com 2021.04.07

第一題

1. 正確。UCS是在BFS上的擴展，當UCS中所有路徑代價都為1時，UCS退化為BFS。
2. 正確。如果在起始點和目標點間有路徑解存在，則該解的搜索深度一定是有限的，則BFS一定可以在有限時間內(nèi)搜索完該深度之內(nèi)的所有點，找到目標解。
3. 正確。一個有解的問題樹（圖）可能含有無窮分枝，DFS可能誤入無窮分枝。如果誤入無窮分枝（即深度無限），則不可能找到目標節(jié)點。
4. 正確。當算法的啟發(fā)式函數(shù)=0時，算法退化為UCS。

第二題

1. 變量是k匹馬的坐標

   變量的取值：

2. 變量受到的約束為：

3. 使用爬山法：從一個較小的k值開始，將k個馬隨機放在棋盤的k個位置作為初始狀態(tài)。然后檢測該狀態(tài)是否有沖突，如果有沖突，則按照每匹馬的沖突信息來調(diào)整馬的位置，經(jīng)過多次調(diào)整（climbing過程）后，如果沒有沖突，則隨即添加一匹馬。重復以上過程，如果在當前狀態(tài)下無法找到調(diào)整后沒有沖突的狀態(tài)，則返回當前k-1，為最大能放置的馬的數(shù)量。value函數(shù)越大表示沖突越少。

   function K-HOURSE-HILL-CLIMBING(problem) returns a state that is a local maximum
    current_state = problem.initial()
    while true do
        result_state = current_state
        current_state.addHourseRandomly()
        while true do
            if current_state.isSatisfied()
                break
            modified_state = current_state.climbing()
            if value(modified_state) ≤ value(current_state)
                   break
            current_state = modified_state
        if current_state.isUnsatisfied()
            return result_state
   

第三題

約束弧有條，一共有個變量，每個變量的取值域中最多有個值。

按照題目提示，對每條弧，存儲為中與取時相容的所有取值。

算法過程：

首先考察所有約束弧，對于條約束弧，每條約束弧考慮兩個變量的所有取值，最大時間復雜度為，在考量的過程中更新所有的，如果所有大小都不為0，則說明問題存在解。如果出現(xiàn)大小為0，則將從的值域剔除，將入隊。所有操作結(jié)束后，如果存在變量值域為空，則說明該弧相容模型無解。如果所有變量值域都不為空，則考慮所有的入隊變量取值。最多有個變量取值入隊，對，考慮，最多有個集合待考慮，如果集合內(nèi)存在，則將從該集合中刪除。若此時該集合為空，則將入隊，并將從的值域剔除。重復進行此操作，直到隊列中沒有元素。若此時存在變量值域為空，則說明該弧相容模型無解。反之則說明該弧相容模型有解。這個過程的時間復雜度為，因為小于，所以上述過程的時間復雜度為。

第四題

作業(yè)一

搜索算法用時比較表

展開節(jié)點數(shù)比較表

路徑代價比較表

分析：

四種迷宮規(guī)模都較小，搜索算法用時都較短。

BFS和算法因為其寬度優(yōu)先的原理，在該四種規(guī)模的迷宮下可以找到路徑代價低的解。算法是BFS和迪杰斯特拉算法的發(fā)展，由于有啟發(fā)式函數(shù)，展開節(jié)點數(shù)比BFS少一些。

DFS因為其深度優(yōu)先的原理，可能可以迅速找到一個可行解。雖然展開節(jié)點數(shù)較少，但是找的的解的路徑代價都較高，找到的解往往不是最優(yōu)解。

作業(yè)二

說明你的啟發(fā)函數(shù)是良定義的：非負，一致性，并且在目標狀態(tài)下的值為0：

代碼如下：展開了8537個節(jié)點，效果很不錯。

def foodHeuristic(state, problem): 
    position, foodGrid = state
    "*** YOUR CODE HERE ***"

    def x(elem):
        return elem[0]

    def manhattan(elem):
        return abs(elem[0] - position[0]) + abs(elem[1] - position[1])

    food_list = foodGrid.asList()[:]
    if len(food_list) == 0:
        return 0
    food_list.sort(key=x)
    food_list_left = []
    food_list_right = []
    food_list_equal = []
    for food in food_list:
        if food[0] > position[0]:
            food_list_right.append(food)
        elif food[0] < position[0]:
            food_list_left.append(food)
        else:
            food_list_equal.append(food)
    food_list_right.sort(key=manhattan, reverse=True)
    food_list_left.sort(key=manhattan, reverse=True)
    food_list_equal.sort(key=manhattan, reverse=True)
    right = medium = left = 0
    max_x = min_x = position[0]
    if len(food_list_right) > 0:
        right = manhattan(food_list_right[0])
        max_x = food_list_right[0][0]
    if len(food_list_left) > 0:
        left = manhattan(food_list_left[0])
        min_x = food_list_left[0][0]
    if len(food_list_equal) > 0:
        medium = manhattan(food_list_equal[0])
    if (left >= medium and left >= right) or (right >= medium and right >= left):
        count = 0
        hx = left + right
        for food in food_list:
            if food[0] < min_x:
                hx = hx + 1
            else:
                break
        food_list.reverse()
        for food in food_list:
            if food[0] > max_x:
                hx = hx + 1
            else:
                break
        return hx
    elif medium >= right and medium >= left:
        return medium + len(food_list) - len(food_list_equal)

非負：如果未達到目標狀態(tài)，hx初始化為正整數(shù)，對hx做的所有操作是增加一個正整數(shù)，所以最后得到的hx一定是非負的，該啟發(fā)式函數(shù)返回值是非負的。

一致性：對于任意狀態(tài)，運行foodHeuristic函數(shù)。每次action所需要的代價為1，下面說明：

1. 如果離position曼哈頓距離最大的食物與position橫坐標不同，將食物分為兩部分，返回的橫坐標小于position的所有食物的極大曼哈頓距離+橫坐標大于position的所有食物的極大曼哈頓距離+所有橫坐標在這兩個有極大曼哈頓距離的食物的橫坐標范圍之外的食物數(shù)目（橫坐標比左側(cè)極值還要小，或比右側(cè)極值還要大）。這樣構(gòu)造的滿足，因為在左側(cè)極值和右側(cè)極值范圍內(nèi)的所有食物至少需要兩個最大曼哈頓距離之和次action才能夠吃完，在這兩個有極大曼哈頓距離的食物的橫坐標范圍之外的食物至少需要其數(shù)目次action才能夠吃完。所以將三者相加得到的值一定小于或等于吃豆人在該position吃完所有食物所需要的最少action次數(shù)。
2. 如果離position曼哈頓距離最大的食物與position橫坐標相同，則返回的該最大曼哈頓距離+和position橫坐標不同的所有食物數(shù)目。這樣構(gòu)造的滿足，因為和position橫坐標相同的所有食物至少需要該最大曼哈頓距離次action才能吃完，和position橫坐標不同的所有食物至少需要其數(shù)目次action才能夠吃完。所以將二者相加得到的值一定小于或等于吃豆人該position吃完所有食物所需要的最少action次數(shù)。

在目標狀態(tài)下值為0：當?shù)竭_目標狀態(tài)，foodGrid.asList()為空列表，返回值為0。

作業(yè)三

見其他文件。