Поиск

Решение задачи поиска

---

Для решения задачи поиска представим на python:

• Состояния системы.
• Results(s, a) находит состояние в которое переходит состояние s под действием a.
• Actions(s) для состояния s возвращает возможные действия.
• GoalTest(s) возвращает true, если состояние s цель, иначе возвращает false.
• PathCost(p) возвращает числовое значение для пути p.

Решение - это последовательность действий, переводящих из начального в целевое состояние. Оптимальное решение имеет минимальную цену пути.
Для решения задачи мы будем строить дерево поиска решений. Узел дерева будет содержать:

• Состояние
• Ссылку на узел родитель
• Действие, которое привело в текущий узел.

Представим узел в виде класса Python.

class Node: 
    def __init__(self, action, state, parent): 
        self.action = action 
        self.state = state 
        self.parent = parent 

    def path(self): 
        if self.parent == None: 
            return [{"action": self.action, "state": self.state}] 
        else: 
            h1 = self.parent.path() 
            h2 = {"action": self.action, "state": self.state} 
            h1.append(h2) 
            return h1

Запишем алгоритм поиска.

def search(initialState, goalTest, actions, results, typeFrontier="stack", printPath=False):
    frontier = Frontier(typeFrontier)
    explored = Explored()
    initialNode = Node(None, initialState, None)
    numTest = 0
    frontier.add(initialNode)

    while True: 
        if frontier.isEmpty():
            raise Exception("No solution")
        parent = frontier.get()
        numTest += 1
        parentS = parent.state 
        if goalTest(parentS): 
            if printPath: 
                print("Soluten:", parent.strPath() ) 
                print("num =", numTest) 
            return parent.path()

        if printPath: 
            print(parent.strPath())
        explored.add(parentS)

        for action in actions(parentS):
            newS = results(parentS, action)
            newN = Node(action, newS, parent) 
            if not explored.hasState(newS):
                frontier.add(newN)

Состязательный поиск

Состязательный алгоритм ищет путь к цели, учитывая, что его соперник стремиться достичь противоположной цели.

Минимакс

Рассмотрим игру крестики-нолики. Введём функцию utility(state). Если X победили, функция возвращает 1. Если O победили, возвращает -1. Возвращает 0, если игра закончилась в ничью. Определим функцию minimax(state), она для состояния возвращает оптимальное действие. Запишем псевдокод действия minimax :

• Дано состояние s.
  • Если ход Х, то он будет выбирать то a действие , среди actions(s), которое будет давать максимальное значение для minValue(reslut(s, a)).
  • Если ход O, то он будет выбирать то a действие среди actions(s), которое даёт минимальное значение maxValue(result(s, a)).
• Функция maxValue(state)
  • v = -\(\infty\)
  • if terminal(state): return utility(state)
  • for action in actions(state): v = max(v, minValue(result(state, action)))
  • return v
• Функция minValue(state)
  • v = \(\infty\)
  • if terminal(state): return utility(state)
  • for action in actions(state): v = min(v, minValue(result(state, action)))
  • return v