pydcop.algorithms.dsa¶

DSA : Distributed Stochastic Algorithm¶

Distributed Stochastic Algorithm [ZWXW05] is a synchronous, stochastic, local search DCOP algorithm.

This is the classical synchronous version of DSA ; at each cycle each variable waits for the value of all its neighbors before computing the potential gain and making a decision. This means that this implementation is not robust to message loss.

Algorithm Parameters¶

variant: ‘A’, ‘B’ or ‘C’ ; the variant of the algorithm, as defined in [ZWXW05] . Defaults to B
probability: probability of changing a value. Defaults to 0.7
stop_cycle: The number of cycle after which the algorithm stops, defaults to 0 If not defined (of equals to 0), the computation never stops.

Example

pydcop -t 3 solve -algo dsa  \
  --algo_param stop_cycle:30 \
  --algo_param variant:C \
  --algo_param probability:0.5 \
 -d adhoc graph_coloring_csp.yaml

{
  "assignment": {
    "v1": "G",
    "v2": "R",
    "v3": "G"
  },
  "cost": 0,
  "duration": 1.9972785034179688,
  "status": "TIMEOUT"
}