Ett distribuerat tillfredställelseproblem (DisCSP) är ett problem med begränsad tillfredsställelse där variabler och begränsningar fördelas mellan flera agenter. Olika algoritmer för att lösa DisCSPs har utvecklats, som är avsedda för allmänna ändamål, dvs. de kan tillämpas på alla nätverksstrukturer. Men om ett nätverk har någon särskild struktur, t.ex., nätverksstrukturen är skalfri, kan vi förvänta oss att vissa specialiserade algoritmer eller heuristiker, som är stämda för nätverksstrukturen, kan överträffa allmänna algoritmer/heuristik. I detta dokument, som ett första steg mot att utveckla specialiserade algoritmer för särskilda nätverksstrukturer, undersöker vi variable-order heuristics i skalfria nätverk. Vi använder den klassiska asynkrona backtracking algoritmen som en basal algoritm och undersöka effekten av variabel ordning heuristik. För det första visar vi att valet av variable-order heuristics är mer inflytelserikt i skalfria nätverk än i slumpmässiga nätverk. Dessutom utvecklar vi en ny variabla heuristisk heuristisk som är specialiserad på skalfria nätverk. Experimentella resultat visar att vår nya variabla heuristisk är mer effektiv än en standardgradbaserad variabel-order heuristisk. Vår föreslagna heurism minskar de nödvändiga cyklerna med 30 procent vid den kritiska punkten.
Okimoto m.fl. REF har också studerat effekten av olika variabla heuristik för ABT i skalfria grafer.
Effect of DisCSP variable-ordering heuristics in scale-free networks
{'venue': 'Multiagent and Grid Systems', 'journal': 'Multiagent and Grid Systems', 'mag_field_of_study': ['Computer Science']}