Ƙananan rikice-rikice algorithm

A cikin kimiyyar kwamfuta, algorithm na rikice-rikice shine algorithm na bincike ko hanyar heuristic don warware matsalolin gamsuwa.

Ɗaya daga cikin irin wannan algorithm shine hawan dutse na rikice-rikice. Idan aka ba da ƙaddamarwa ta farko na dabi'u ga duk masu canji na matsalar gamsuwa ta ƙuntatawa (tare da ƙuntatawa ɗaya ko fiye da ba a gamsu ba), zaɓi mai canji daga saitin masu canji tare da rikice-rikice da ke keta ɗaya ko fiye daga cikin ƙuntatawa. Bayar da wannan canji darajar da ke rage yawan rikice-rikice (yawanci karya alaƙa ba zato ba tsammani). Maimaita wannan tsari na zaɓin canji mai rikitarwa da ƙimar ƙididdigar ƙididdiga har sai an sami mafita ko kuma an sami matsakaicin adadin maimaitawa. Idan ba a sami mafita ba za a iya sake farawa da algorithm tare da wani aiki na farko daban.

Saboda matsalar gamsuwa ta ƙuntataccen ƙuntata za a iya fassara shi azaman matsalar bincike ta gida lokacin da duk masu canji suna da ƙimar da aka ba su (wanda ake kira cikakkiyar jiha), ana iya ganin algorithm na rikice-rikice na min a matsayin gyaran gyare-gyare  wanda ke zaɓar jiha tare da mafi ƙarancin adadin rikice-rikicen.

 Algorithm 
 algorithm MIN-CONFLICTS shine shigarwa: na'ura mai amfani.csp, Matsalar gamsuwa. max_steps, Yawan matakai da aka ba da izini kafin ya saita. halin yanzu_jiha, Aikin farko na dabi'u ga masu canji a cikin 'csp'. fitarwa: saita ƙididdigar ƙididdiga don canji ko gazawar. 

  don i ← 1 zuwa max_mataki yi idan 'halin yanzu_jiha' saita ce ta csp sannan dawo yanzu_jihar saiti 'v' ← wani canji da aka zaɓa ba zato ba tsammani daga saitin masu canji masu rikitarwa CONFLICTED[csp] saiti ← 'darajar' v don 'var' wanda ke rage CONFLICTS (var,v,current_jihar,csp) saiti var 

  gazawar 'dawowa'Rashin nasara
Kodayake ba a ƙayyade shi a cikin algorithm ba, kyakkyawan aikin farko na iya zama mai mahimmanci don kusantar mafita da sauri. Yi amfani da Algorithm mai haɗama tare da wani matakin bazuwar kuma ba da damar aiki mai canzawa don karya ƙuntatawa lokacin da babu wani aiki da zai isa. Rashin daidaituwa yana taimakawa rikice-rikice na min kauce wa ƙarancin gida wanda aka kirkira ta hanyar aikin farko na algorithm mai haɗama. A zahiri, Matsalolin Satisfaction na Ƙuntatawa waɗanda ke amsawa mafi kyau ga mafita ta ƙarancin rikice-rikice suna da kyau inda algorithm mai haɗama kusan ya warware matsalar. Matsalolin launi na taswira ba su da kyau tare da Greedy Algorithm da Min-Conflicts. Yankunan taswirar suna riƙe launuka masu ɗorewa kuma rikice-rikicen min ba za su iya hawa dutse don fita daga mafi ƙarancin gida ba. Ayyukan CONFLICTS suna ƙidaya adadin ƙuntatawa da wani abu ya keta, saboda an san yanayin sauran aikin.

 Tarihi 
Kodayake Artificial In and Discrete Optimization sun san kuma sun yi tunani game da Matsalar Satisfaction na Constraint na shekaru da yawa, ba har zuwa farkon shekarun 1990 ba ne aka tsara wannan tsari don warware manyan CSPs a cikin tsarin algorithmic. Da farko, Mark Johnston na Cibiyar Kimiyya ta Space Telescope ta nemi hanyar da za a tsara abubuwan lura da taurari a kan Hubble Space Telescope. Tare da haɗin gwiwar Hans-Martin Adorf na Space Telescope European Coordinating Facility, ya kirkiro cibiyar sadarwa mai iya warware matsalar n-sarauniya (don sarauniya 1024).  Steven Minton da Andy Philips sun bincika algorithm na cibiyar sadarwa ta jijiyoyi kuma sun raba shi zuwa matakai biyu: (1) aikin farko ta amfani da algorithm mai haɗama da (2) matakai na rage rikice-rikice (daga baya za a kira su "min-conflicts"). An rubuta takarda kuma an gabatar da shi a AAAI-90; Philip Laird ya ba da nazarin lissafi na algorithm.

 Manazarta