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

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

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

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

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

Binary tree

Алгоритм бінарного дерева - найпростіший для генерації лабіринтів. Для кожної клітинки ми шукаємо два напрямки (праву і нижню наприклад) і вибираємо яку стінку “ламати”. Робимо це для кожної клітинки. В кінці виходить лабіринт.

patches-own [
  north south east west
  visited?
  initial?
  neighbors_set
]

to setup
  clear-all
  reset-ticks
  ask patches [
    set north nobody
    set south nobody
    set east nobody
    set west nobody
    set neighbors_set []

  ]

  create-turtles Nx + 1 [
    setxy convert-to-world (who + 1) convert-to-world (1)
    set color 9.9
    set heading 0
    set pen-mode "down"
    set pen-size 5
  ]

  create-turtles Ny + 1 [
    setxy convert-to-world 1 convert-to-world (who - Nx)
    set color 9.9
    set heading 90
    set pen-mode "down"
    set pen-size 5
  ]

   ask patches with [pxcor >= 1 and pxcor <= Nx and pycor >= 1 and pycor <= Ny] [
    set initial? TRUE
    set visited? FALSE
    set pcolor (pxcor * pycor + 10) / (Nx + Ny)

    if (pxcor < Nx) [
      set east patch-at 1 0
      set neighbors_set fput east neighbors_set
    ]
    if (pxcor > 1) [
      set west patch-at -1 0
      set neighbors_set fput west neighbors_set
    ]
    if (pycor < Ny) [
      set north patch-at 0 1
      set neighbors_set fput north neighbors_set
]
    if (pycor > 1) [
      set south patch-at 0 -1
      set neighbors_set fput south neighbors_set
]

  ]
  create-grid
  add-outs
end

to create-grid
  ask turtles with [who < Nx + 1] [
    fd Ny
 ]
 ask turtles with [who >= Nx + 1] [fd Nx]
 clear-turtles
end

to-report convert-to-world[x]
  report x - 0.5
end

to add-outs
  create-turtles 1 [
    setxy X1 Y1
    set color 9.9
    set heading 180
    set pen-mode "erase"
    set pen-size patch-size - 5
    fd 1
    die
  ]

  create-turtles 1 [
    setxy Nx Ny
    set color 9.9
    set heading 90
    set pen-mode "erase"
    set pen-size patch-size - 5
    fd 1
    die
  ]

end

to binary-tree

  while [count patches with [visited? = FALSE] > 1] [
    if (direction = "left-up") [binary-tree-step "north" "west"]
    if (direction = "left-down") [binary-tree-step "south" "east"]
    if (direction = "right-up") [binary-tree-step "north" "east"]
    if (direction = "right-down") [binary-tree-step "south" "east"]

  ]

end

to binary-tree-step [d1 d2]
  let dir []
  create-turtles 1 [
  let p one-of patches with [visited? = FALSE]
    setxy [pxcor] of p [pycor] of p
      set color 9.9
      set hidden? true
      set pen-mode "erase"
      set pen-size patch-size - 6

    if (return-neighbor d1 != nobody) [set dir fput return-neighbor d1 dir]
    if (return-neighbor d2 != nobody) [set dir fput return-neighbor d2 dir]

  ;  if east != nobody [set dir fput east dir]

  ;  if (north != nobody) or (east != nobody) [
    if (return-neighbor d1 != nobody) or (return-neighbor d2 != nobody)[
      ask p [set visited? TRUE]
      face one-of dir
      fd 1
    ]
   die
  ]

end

to-report return-neighbor[d]
  if d = "north" [report north]
  if d = "south" [report south]
  if d = "east" [report east]
  if d = "west" [report west]

end

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 корисний в ситуаціях, коли

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

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

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

end