Вступ

В наступних лекціях ми розглянемо декілька класів розподілених алгоритмів. Один з прикладів використання ідеї розподілених обчислень є задачі задоволення обмежень, коли множина агентів намагається знайти розв’язок певної задачі за наявності глобальних обмежень. В загальному вигляді ці задачі формулюються у термінах змінних та можливих світів. Можливий світ - це один з можливих варіантів існування певного середовища (реального або уявного). Можливі світи формалізуються алгебраїчними змінними. Алгебраїчна змінна позначає певну властивість світу. Кожна змінна \(x_{i}\) має свою область (домейн) - \(dom(x_{i})\) тобто множину можливих значень. Розглядають змінні наступних типів:

Для заданої множини змінних призначенням називається це відображення, яке співставляє набору змінних набір значень. \[\{x_{1},x_{2},...,x_{k}\} \rightarrow \{v_{1},v_{2},...,v_{k}\}\], де \(v_{i} \in dom(x_{i})\). В призначенні кожна змінна може приймати тільки одне значення. Повне призначення визначає всі змінні, але ми будемо розглядати і часткові призначення.

Обмеження

Для багатьох домейнів не всі значення змінних є допустимими. Такі ситуації називаються обмеженнями. Крім цього визначаються також відношення, які описують чи є дане призначення допустимим. Можливий світ, для якого виконуються всі обмеження називається моделлю.

Задача задоволення обмежень (ЗЗО)

Задача задоволення обмежень склададається з:

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

Ми будемо розглядати найбільш просту задачу - знайти якесь рішення ЗЗО або довести, що рішення не існує.

Задача розфарбовування графа.

Розглянемо задачу розфарбовування графа. Це класична ЗЗО, кожному \(x_{i}\) відповідає вершина графа, можливі кольори - це доменйни кожної змінної і ребра графа визначають обмеження: сусідні вершини не можуть мати однаковий колір.

Розв’яжемо задачу розфарбовування графа різними алгоритмами. Почнемо з найпростішого методу - DFS.

Приклад 1. DFS i розфарбовування графа

breed [nodes node]

globals [colors]

to setup
  clear-all
  ask patches [set pcolor white]
  set colors [red blue green]
  
  create-nodes num-nodes [
    set shape "circle"
    setxy random-pxcor random-pycor
    set color black ;one-of colors
  ]
  
  repeat num-edges [
    ask one-of nodes [
      create-link-with one-of other nodes
    ]
  ]


end


to layout
  layout-spring nodes links 0.2 5 1
end


to depth-first-search
  ifelse (dfs (turtle 0)) [
    show "See the colors"
  ][
    show "no coloring possible"
  ]
end

to-report dfs [n]
  let i [who] of n
  foreach colors [
    [a] ->
    ask n [set color a]
    if (not constraint-violations?)[
      if (max [who] of nodes = i)[
      report true
      ]
      if (dfs (turtle (i + 1)))[
      report true
      ]
    ]
  ]
  ask n [set color black]
  report false
end

to-report constraint-violations?
  
  let violated-links links with [
    [color] of end1 != black and 
    [color] of end2 != black and 
    [color] of end1 = [color] of end2
]
report any? violated-links
 
end 

Розв’язання CSP алгоритмами фільтрації

Ідея алгоритму фільтрації полягає у тому, що кожен агент комунікує з сусідами для викидання з домейну зайвих (тих, що не можуть належати успішному призначенню) значень. Кожен агент викликає процедуру \(Revise(x_{i},x_{j})\) для кожного зі своїх сусідів.

Алгоритм фільтрації

\[ \begin{align} & FILTERING\\ & 1.\; \textbf{for} \;j ∈ \{neighbors \;of \;i\}\\ & 2.\quad \textbf{do}\; revise(x_{i}, x_{j})\\ \end{align} \]

\[ \begin{align} & HANDLE-NEW-DOMAIN(j, D')\\ & 1. \; D_{j} ← D'\\ & 2.\quad \textbf{revise}(x_{i},x{j}) \\ \end{align} \]

\[ \begin{align} & REVISE(x_{i}, x_{j})\\ & 1.\; old-domain ← D_{i}\\ & 2. \textbf{for}\; v_{i} \in D_{i}\\ & 3. \quad \textbf{do}\; if \; there\; is\; no\; v_{j}\in D_{j} \;consistent\; with\;v_{j}\\ & 4. \quad then \; D_{i} ← D_{i} − v_{i} \\ & 5. \quad \quad if\; old-domain = D_{i}\\ & 6. \quad \quad then\; ∀ k∈\{neighbors \;of\; i;\}k.handle-new-domain(i, D _{i})\\ \end{align} \]

Приклад 2. Filtering algorithm

breed [nodes node]
undirected-link-breed [edges edge]

breed [mininodes mininode]
undirected-link-breed [minilinks minilink]

nodes-own [domain]
globals [colors]

to-report new-domain
  report n-values num-nodes [
    n-of (1 + random length colors) colors]
end

to setup
  clear-all
  ask patches [set pcolor white]
  set colors [red blue green]
  let the-domain new-domain
  create-nodes num-nodes [
    set shape "circle"
    setxy random-pxcor random-pycor
    set color black ;one-of colors
    set domain the-domain
  ]

  repeat num-edges [
    ask one-of nodes [
      create-edge-with one-of other nodes
    ]
  ]
  ask nodes [
  spawn-mininodes
  ]

end

to go
  ask nodes [
    filtering
  ]
  ask mininodes [die]
  ask minilinks [die]
  ask nodes [
    let my-domain item who domain
    if (length my-domain = 1)[
    set color first my-domain]
    spawn-mininodes]
  
end

to layout
  
  layout-spring nodes edges 0.2 5 2
  layout-spring mininodes minilinks 0.1 1 1
end

;; node methods

to spawn-mininodes
  let my-domain item who domain
  foreach my-domain [
    [a] ->
    let mini 0
    hatch-mininodes 1 [
      set color a
      set shape "square"
      set mini self

    ]
    create-minilink-with mini
  ]
end

to filtering 
  foreach (sort edge-neighbors)[
    [a] -> revise a
  ]
end

to revise [other-node]
  let my-domain item who domain
  let his-domain item ([who] of other-node) domain
  if (length my-domain = 0) [stop]
  if (length his-domain = 0) [stop]
  if (length his-domain > 1) [stop]
  let his-color first his-domain
  if ( member? his-color my-domain) [
    let my-new-domain remove his-color my-domain
    set domain replace-item who domain my-new-domain
    ask edge-neighbors [
      set domain replace-item ([who] of myself) domain my-new-domain
    ]  
  ]
  
end