В наступних лекціях ми розглянемо декілька класів розподілених алгоритмів. Один з прикладів використання ідеї розподілених обчислень є задачі задоволення обмежень, коли множина агентів намагається знайти розв’язок певної задачі за наявності глобальних обмежень. В загальному вигляді ці задачі формулюються у термінах змінних та можливих світів. Можливий світ - це один з можливих варіантів існування певного середовища (реального або уявного). Можливі світи формалізуються алгебраїчними змінними. Алгебраїчна змінна позначає певну властивість світу. Кожна змінна \(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.
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
Ідея алгоритму фільтрації полягає у тому, що кожен агент комунікує з сусідами для викидання з домейну зайвих (тих, що не можуть належати успішному призначенню) значень. Кожен агент викликає процедуру \(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} \]
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