Лекція 6. Алгоритми пошуку. Створення лабіринтів з гарантованим виходом за допомогою DFS

Well-defined problems та їх розв’язок

Проблему можна форально визначити, описавши 5 компонентів:

Почтковий стан агента;
Опис можливих дій агента;
Результат виконання кожної дії для кожного стану (в якій вона може бути виконана) - перехідна функція. Трійка початковий стан, множина дій і перехідна функція визначають простір станів для проблеми. Простір станів можна представити у вигляді орієнтованого графу, де вершини відповідають станам а ребра - діям. Шлях від вершини до вершини - це послідовність дій, яку необхідно виконати для перехода з одного стану в інший;
Функція досягнення мети, яка визначає для кожного стану відповідь на питання: чи досягли ми розв’язку?
Функція вартості, яка визначає числову вартість кожного шляху. При розв’язанні проблеми агент враховує вартість у якості міри ефективності алгоритму розв’язання.

Описані вище елементи визначають структуру даних, яка є вхідним об’єктом алгоритму пошуку рішення. Розв’язком є шлях (послідовність дій) з початкової вершини до вершини, на якій досягається мета. Якість вимірюється вартістю вздовж шляху. Оптимальний розв’язок це той, що має найнижчу вартість.

В цій лекції ми розглянемо алгоритми неінформованого пошуку у дереві варіантів. Велика кількість задач ШІ може бути сформульована як задача пошуку на орієнтованих графах.

Розв’язання - це шлях (послідовність дій) з початкової вершини. Можливі шляхи, що починаються з початкового стану формують дерево пошуку. Всі алгоритми починаються однаково - ми виконуємо всі можливі дії для початкового стану та отримуємо множину вершин. Далі виконується вибір однієї з вершин (тут алгоритми починають відрізнятись). Якщо наша ціль виконана для вибраної вершини то алгоритм закінчує роботу. Якщо ж ні, то перевірена вершина помічається як пройдена. В кожен момент роботи алгоритму є три множини вершин графу: перевірені, границя і неперевірені. На кожному кроці алгоритм пошуку вибирає вершини з границі, перевіряє їх та додає до перевірених і потім відбирає нові неперевірені вершини до границі.

Depth First Search (DFS)

DFS алгоритм це рекурсивний алгоритм, що використовує ідею повернення. Він пропонує обшукувати всі вузли “в глибину”, якщо це можливо, в іншому разі повертатися до першої “розвилки”. Повернення тут означає, що при русі вперед ми отримуємо декілька вузлів, при цьому один вибирається для подальшого дослідження а інші зберігаються в стек. Важливо при цьому помічати вузли, які ми вже дослідили, щоб уникнути подвійних обходів. Границя в DFS працює за принципом LIFO (last-in, first-out). Розглянемо реалізацію в NetLogo

DFS Netlogo implementation

breed [dwarfs dwarf]

dwarfs-own [
  current-patch
  n-stack
]
patches-own[
  visited
  neighbors-black
]

to setup
  clear-all
  reset-ticks
  draw-lines
  ask patches [
  set visited 0]
  black-patches-around
   create-dwarfs num [
     set n-stack []
     let p one-of patches with [pcolor = black]
     set xcor [pxcor] of p
     set ycor [pycor] of p
     ask p [set visited 1]
  ]
end

to go
  tick
  draw-maze
  black-patches-around
end

to draw-lines

  ask patches [
    if (remainder pxcor 2 != 0) or (remainder pycor 2 != 0) [
    set pcolor grey]
  ]
  let number-outs outs
  ask patches with [(abs pxcor = max-pxcor or abs pycor = max-pycor)][
    if (remainder pxcor 2 = 0) or (remainder pycor 2 = 0) [
      if (number-outs > 0 ) [
        set pcolor white
        set number-outs number-outs - 1
      ]
    ]]
end

to black-patches-around
  ask patches [
    let p-set other patches with [
      (distance myself < 2.1)
      and (pcolor = black)
    and (visited = 0)]
    set neighbors-black p-set
  ]
end

to draw-maze

  ask turtles [
    let target-patch 0
    ask patch-here [
      set pcolor white
      set target-patch one-of neighbors-black
    ]

    ifelse (target-patch = nobody)[
      if (empty? n-stack) [die]
      let p pop-n
      ifelse (p = nobody) [stop]
      [
        set xcor [pxcor] of p
        set ycor [pycor] of p]
    ][
      push-n patch-here
      ask target-patch [set visited 1]
      set heading towards target-patch
      run "fd 1"

      ask patch-here [
      set visited 1
      set pcolor white]
    run "fd 1"
    ]
    ]
end


; stack implementation

;; Save the patches state
to push-n [p];; patch procedure
  set n-stack fput p n-stack
end

;; restore the patches state
to-report pop-n ;; patch procedure
  ; need to go through update-n to keep total statistic correct
  let r first n-stack
  set n-stack but-first n-stack
  report r
end

Створення лабіринтів за допомогою BFS

В алгоритмі BFS границя створюється за принципом FIFO (first-in, first-out) черги. Таким чином, вибирається останній доданий елемент у границю.

BFS корисний в ситуаціях, коли

проблема достатно проста і розмір простору станів не важливий.
ви хочете рішення з найменшою кількістю ребер.

breed [dwarfs dwarf]

dwarfs-own [
  current-patch
  n-stack
]
patches-own[
  visited
  neighbors-black
]

to setup
  clear-all
  reset-ticks
  draw-lines
  ask patches [
  set visited 0]
  black-patches-around
   create-dwarfs num [
     set n-stack []
     let p one-of patches with [pcolor = black]
     set xcor [pxcor] of p
     set ycor [pycor] of p
     ask p [set visited 1]
  ]
end

to go
  tick
  draw-maze
  black-patches-around
end

to draw-lines

  ask patches [
    if (remainder pxcor 2 != 0) or (remainder pycor 2 != 0) [
    set pcolor grey]
  ]
  let number-outs outs
  ask patches with [(abs pxcor = max-pxcor or abs pycor = max-pycor)][
    if (remainder pxcor 2 = 0) or (remainder pycor 2 = 0) [
      if (number-outs > 0 ) [
        set pcolor white
        set number-outs number-outs - 1
      ]
    ]]
end

to black-patches-around
  ask patches [
    let p-set other patches with [
      (distance myself < 2.1)
      and (pcolor = black)
    and (visited = 0)]
    set neighbors-black p-set
  ]
end

to draw-maze

  ask turtles [
    let target-patch 0
    ask patch-here [
      set pcolor white
      set target-patch one-of neighbors-black
    ]

    ifelse (target-patch = nobody)[
      if (empty? n-stack) [die]
      let p pop-n
      ifelse (p = nobody) [stop]
      [
        set xcor [pxcor] of p
        set ycor [pycor] of p]
    ][
      push-n patch-here
      ask target-patch [set visited 1]
      set heading towards target-patch
      run "fd 1"

      ask patch-here [
      set visited 1
      set pcolor white]
    run "fd 1"
    ]
    ]
end


; queue implementation

;; Save the patches state
to push-n [p];; patch procedure
  set n-stack fput p n-stack
end

;; restore the patches state
to-report pop-n ;; patch procedure
  ; need to go through update-n to keep total statistic correct
  let r last n-stack
  set n-stack but-last n-stack
  report r
end

Створення лабіринтів за допомогою балансованого пошуку

Ідея: сортувати чергу за кількістю “сусідів” - можливих шляхів руху.

to sort-stack
  set n-stack sort-by [[a1 a2] -> [neighbors-black-number] of a1 < [neighbors-black-number] of a2] n-stack

end

Лекція 6