Mo ki gbogbo yin.
Ninu akọsilẹ yii, Mo pinnu lati ṣe atokọ awọn ẹya data akọkọ ti a lo lati tọju awọn aworan ni imọ-ẹrọ kọnputa, ati pe Emi yoo tun sọrọ nipa tọkọtaya diẹ sii iru awọn ẹya ti bakan “crystallized” fun mi.
Nitorinaa, jẹ ki a bẹrẹ. Ṣugbọn kii ṣe lati ibẹrẹ akọkọ - Mo ro pe gbogbo wa ti mọ kini iwọn kan ati kini wọn jẹ (itọsọna, aiṣe-itọnisọna, iwuwo, ti ko ni iwuwo, pẹlu tabi laisi awọn egbegbe pupọ ati awọn losiwajulosehin).
Nitorina, jẹ ki a lọ. Awọn aṣayan wo fun awọn ẹya data fun “ipamọ awọn aworan” ni a ni?
1. Matrix data ẹya
1.1 Matrix adjacency. Matrix adjacency jẹ matrix nibiti awọn ori ila ati awọn akọle iwe ṣe deede si awọn nọmba ti awọn inaro ti ayaworan naa, ati pe iye awọn eroja kọọkan a (i,j) jẹ ipinnu nipasẹ wiwa tabi isansa ti awọn egbegbe laarin awọn inaro. i ati j (o han gbangba pe fun ayaworan ti a ko daa, iru matrix kan yoo jẹ alamọdaju, tabi a le gba pe a tọju gbogbo awọn iye nikan loke diagonal akọkọ). Fun awọn aworan ti ko ni iwuwo, a(i,j) le ṣeto nipasẹ nọmba awọn egbegbe lati i si j (ti ko ba si iru eti bẹ, lẹhinna a(i,j)= 0), ati fun awọn aworan iwuwo, paapaa nipasẹ iwuwo (lapapọ iwuwo) ti awọn egbegbe ti a mẹnuba.
1.2 Matrix iṣẹlẹ. Ni idi eyi, awọn aworan wa tun wa ni ipamọ ninu tabili eyiti, gẹgẹbi ofin, awọn nọmba ila ni ibamu si awọn nọmba ti awọn aaye rẹ, ati awọn nọmba ọwọn ni ibamu si awọn egbegbe ti a ti ṣaju. Ti fatesi ati eti ba ṣẹlẹ si ara wọn, lẹhinna iye ti kii ṣe odo ni a kọ sinu sẹẹli ti o baamu (fun awọn aworan ti a ko daa, 1 ti kọ ti o ba jẹ pe fatesi ati eti ba ṣẹlẹ, fun awọn aworan ti o ni ilarun - “1” ti o ba jẹ eti. "jade" lati awọn fatesi ati "-1" ti o ba "pẹlu" ninu rẹ (o rọrun to lati ranti, nitori awọn "iyokuro" ami tun dabi lati wa ni "pẹlu" ni nọmba "-1")). Fun awọn aworan ti o ni iwọn, lẹẹkansi, dipo 1 ati -1, o le pato iwuwo lapapọ ti eti.
2. Enumeration data ẹya
2.1 Akojọ adjacency. O dara, ohun gbogbo dabi pe o rọrun nibi. Kọọkan fatesi ti awonya le, ni apapọ, ni nkan ṣe pẹlu eyikeyi enumeration be (akojọ, fekito, orun, ...), eyi ti yoo fi awọn nọmba ti gbogbo vertices nitosi si awọn ti fi fun. Fun awọn aworan ti a darí, a yoo ṣafikun si iru atokọ bẹ nikan awọn inaro wọnyẹn eyiti o wa ni eti “itọsọna” lati fatesi ẹya kan. Fun awọn aworan iwuwo imuse yoo jẹ eka sii.
2.2 Akojọ ti awọn ribs. Oyimbo kan gbajumo data be. Atokọ ti awọn egbegbe, gẹgẹ bi Captain Obviousness ti sọ fun wa, jẹ kosi atokọ ti awọn egbegbe ti ayaworan, ọkọọkan eyiti o jẹ pato nipasẹ fatesi ibẹrẹ, vertex ipari (fun awọn aworan ti a ko ni itọsọna aṣẹ ko ṣe pataki nibi, botilẹjẹpe fun iṣọkan o le lo orisirisi awọn ofin, fun apẹẹrẹ, pato awọn vertices ni ibere npo si) ati iwuwo (fun awọn iwọn awọn aworan nikan).
O le wo awọn atokọ matrix ti a ṣe akojọ loke ni awọn alaye diẹ sii (ati pẹlu awọn apejuwe), fun apẹẹrẹ, .
2.3 orun adjacency. Kii ṣe ilana ti o wọpọ julọ. Ni ipilẹ rẹ, o jẹ fọọmu ti awọn atokọ isọdọmọ “ikojọpọ” sinu eto ikawe kan (orun, fekito). Ni igba akọkọ ti n (gẹgẹ bi awọn nọmba ti vertices ti awọn awonya) eroja ti iru ohun orun ni awọn itọka ibẹrẹ ti awọn kanna orun, ti o bere lati eyi ti gbogbo vertices nitosi si awọn fi fun ọkan ti wa ni kikọ ni ọna kan.
Nibi Mo rii alaye ti o ni oye julọ (fun ara mi):
3. Adjacency Vector ati Associative Adjacency orun
O wa ni jade wipe onkowe ti awọn wọnyi ila, ko ni ogbon a ọjọgbọn pirogirama, ṣugbọn ti o lorekore jiya pẹlu awọn aworan, julọ igba jiya pẹlu awọn akojọ ti awọn egbegbe. Lootọ, o rọrun ti ayaworan naa ba ni awọn iyipo pupọ ati awọn egbegbe. Ati nitorinaa, ni idagbasoke awọn atokọ Ayebaye ti awọn egbegbe, Mo daba lati san ifojusi si “idagbasoke / ẹka / iyipada / iyipada” wọn, eyun: vector adjacency ati akojọpọ isunmọ associative.
3.1 adjacency fekito
Ọran (a1): aworan ti ko ni iwuwo
A yoo pe fekito adjacency fun aworan ti ko ni iwuwo ni eto ti a paṣẹ ti nọmba ani awọn odidi (a[2i], a[2i+1],..., nibiti mo ti ni nọmba c 0), ninu eyiti awọn nọmba meji kọọkan. jẹ a[2i], a[2i+1] pato kan eti iwọn laarin awọn inaro a[2i] ati a[2i+1], lẹsẹsẹ.
Ọna kika gbigbasilẹ yii ko ni alaye ninu boya aworan naa ni itọsọna (awọn aṣayan mejeeji ṣee ṣe). Nigbati o ba nlo ọna kika digraph, eti ni a gba pe o jẹ itọsọna lati a[2i] si a[2i+1]. Nibi ati ni isalẹ: fun awọn aworan ti a ko ni itọsọna, ti o ba jẹ dandan, awọn ibeere fun aṣẹ ti awọn inaro gbigbasilẹ le ṣee lo (fun apẹẹrẹ, pe fatesi pẹlu iye kekere ti nọmba ti a yàn si rẹ wa ni akọkọ).
Ni C ++, o ni imọran lati ṣalaye fekito adjacency nipa lilo std :: vector, nitorinaa orukọ eto data yii.
Ọran (a2): aworan ti ko ni iwuwo, awọn iwuwo eti jẹ odidi
Ní ìfiwéra pẹ̀lú ọ̀rọ̀ (a1), a ń pè ékítà ọ̀gbẹ́ńkẹ́ta fún àwòrán oníwọ̀n kan pẹ̀lú ìwọ̀n òṣùwọ̀n ẹ̀gbẹ́ odidi ẹ̀rọ tí a ṣètò (àkópọ̀ ìmúdàgba) ti àwọn nọ́mbà (a[3i], a[3i+1], a[3i+2], ..., nibiti mo ti ni nọmba c 0), nibiti “meta” ti awọn nọmba kọọkan a[3i], a[3i+1], a[3i+2] ṣe afihan eti ti awọnya laarin awọn inaro ti a ni nọmba a[3i] ati a[3i+1], lẹsẹsẹ, ati iye a [3i+2] ni awọn àdánù ti yi eti. Iru a awonya le tun ti wa ni boya directed tabi ko.
Ọran (b): aworan ti ko ni iwuwo, awọn iwuwo eti ti kii ṣe nomba
Niwọn igba ti ko ṣee ṣe lati tọju awọn eroja oriṣiriṣi sinu titobi kan (fekito), fun apẹẹrẹ, imuse atẹle jẹ ṣeeṣe. Aworan naa ti wa ni ipamọ sinu bata meji, ninu eyiti fekito akọkọ jẹ fekito isunmọ ayaworan lai ṣe alaye awọn iwuwo, ati pector keji ni awọn iwuwo ti o baamu (imuse ti o ṣeeṣe fun C ++: std :: bata ). Nitorinaa, fun eti ti a ṣalaye nipasẹ bata meji labẹ awọn atọka 2i, 2i+1 ti fekito akọkọ, iwuwo yoo dọgba si ano labẹ atọka i ti fekito keji.
O dara, kilode ti eyi ṣe pataki?
O dara, onkọwe ti awọn ila wọnyi rii pe o wulo pupọ fun ipinnu awọn iṣoro nọmba kan. O dara, lati oju oju-ọna deede, awọn anfani wọnyi yoo wa:
- Fekito adjacency, bii eyikeyi eto “akojọ” miiran, jẹ iwapọ pupọ, o gba iranti kere ju matrix isọdi (fun awọn aworan fọnka), ati pe o rọrun lati ṣe.
- Awọn inaro ti iwọn, ni ipilẹ, tun le samisi pẹlu awọn nọmba odi. Tó bá jẹ́ pé irú “ìwà ìkà” bẹ́ẹ̀ ńkọ́?
- Awọn aworan le ni awọn egbegbe pupọ ati ọpọlọpọ awọn losiwajulosehin, pẹlu awọn iwuwo oriṣiriṣi (rere, odi, paapaa odo). Ko si awọn ihamọ nibi.
- O tun le fi awọn ohun-ini oriṣiriṣi si awọn egbegbe - ṣugbọn fun diẹ sii lori iyẹn, wo apakan 4.
Sibẹsibẹ, o gbọdọ jẹwọ pe “akojọ” yii ko tumọ si wiwọle yara yara si eti. Ati nibi Associative Adjacency Array wa si igbala, eyiti a jiroro ni isalẹ.
3.2 Associative adjacency orun
Nitorinaa, ti iraye si eti kan pato, iwuwo rẹ ati awọn ohun-ini miiran jẹ pataki fun wa, ati awọn ibeere iranti ko gba wa laaye lati lo matrix adjacency, lẹhinna jẹ ki a ronu nipa bii a ṣe le yi vector adjacency pada lati yanju iṣoro yii. Nitorinaa, bọtini naa jẹ eti ti awọnyaya, eyiti o le sọ pato bi bata awọn nọmba ti o paṣẹ. Kini eleyi dabi? Ṣe kii ṣe bọtini kan ninu akojọpọ alajọṣepọ kan? Ati pe, ti o ba jẹ bẹ, kilode ti a ko ṣe imuse rẹ? Jẹ ki a ni akojọpọ akojọpọ nibiti bọtini kọọkan - bata odidi ti a paṣẹ - yoo ni nkan ṣe pẹlu iye kan - odidi kan tabi nọmba gidi kan ti o ṣalaye iwuwo eti. Ni C ++, o ni imọran lati ṣe ilana yii ti o da lori std :: apoti maapu (std :: maapu , int> tabi std :: maapu , ė>), tabi std :: multimap ti ọpọlọpọ awọn egbegbe ba nireti. O dara, a ni eto fun titoju awọn aworan ti o gba iranti ti o kere ju awọn ẹya “matrix” lọ, le ṣalaye awọn aworan pẹlu ọpọlọpọ awọn losiwajulosehin ati awọn egbegbe, ati pe ko paapaa ni awọn ibeere ti o muna fun aisi aibikita ti awọn nọmba inaro (Emi ko mọ ti o nilo yi, sugbon si tun).
4. Awọn ẹya data ti kun, ṣugbọn nkan ti nsọnu
Ati pe o jẹ otitọ: nigba ti o ba yanju nọmba awọn iṣoro, a le nilo lati fi awọn abuda kan si awọn egbegbe ti awọn aworan ati, gẹgẹbi, tọju wọn. Ti o ba ṣee ṣe lati dinku awọn ẹya wọnyi lainidi si awọn odidi, lẹhinna o ṣee ṣe lati fipamọ iru “awọn aworan pẹlu awọn ẹya afikun” ni lilo awọn ẹya ti o gbooro sii ti vector adjacency ati akojọpọ isọdi associative.
Nitorinaa, jẹ ki a ni iwọn ti ko ni iwuwo, fun eti kọọkan ti eyiti o jẹ dandan lati fipamọ, fun apẹẹrẹ, awọn ẹya afikun 2 ti a ṣalaye nipasẹ awọn odidi. Ni idi eyi, o ṣee ṣe lati ṣalaye fekito isunmọ bi eto ti a paṣẹ kii ṣe ti “awọn orisii”, ṣugbọn ti “quartets” ti awọn nọmba (a[2i], a[2i+1], a[2i+2], a [2i+3]…) , nibiti a[2i+2] ati [2i+3] yoo pinnu awọn abuda ti eti ti o baamu. Fun aworan kan pẹlu awọn iwọn odidi ti awọn egbegbe, aṣẹ naa jọra ni gbogbogbo (iyatọ kan ṣoṣo yoo jẹ pe awọn abuda yoo tẹle iwuwo eti ati pe yoo jẹ pato nipasẹ awọn eroja a[2i + 3] ati [2i + 4] , ati awọn eti ara yoo wa ni pato ko 4, ṣugbọn 5 paṣẹ awọn nọmba). Ati fun aworan kan pẹlu awọn iwuwo eti ti kii ṣe nomba, awọn ẹya le kọ sinu paati ti ko ni iwuwo.
Nigbati o ba nlo eto isọdi associative fun awọn aworan pẹlu awọn iwuwo eti odidi, o ṣee ṣe lati pato bi iye kii ṣe nọmba kan, ṣugbọn orun (fekito) ti awọn nọmba ti o pato, ni afikun si iwuwo eti, gbogbo awọn miiran pataki awọn ẹya ara ẹrọ. Ni akoko kanna, ohun airọrun fun ọran ti awọn iwuwo ti kii ṣe odidi yoo jẹ iwulo lati pato ami kan pẹlu nọmba aaye lilefoofo (bẹẹni, eyi jẹ airọrun, ṣugbọn ti ko ba si iru awọn ami bẹ bẹ, ati pe ti o ba ṣe bẹ. 't ṣeto wọn ju "ẹtan" ni ilopo, lẹhinna o le jẹ ohunkohun) . Eyi tumọ si pe ni C ++ ti o gbooro sii awọn akojọpọ adjacency associative le jẹ asọye bi atẹle: std :: maapu. , std :: fekito> tabi std :: maapu , std :: fekito, ninu eyiti iye akọkọ ninu "bọtini-iye-vector" yoo jẹ iwuwo ti eti, ati lẹhinna awọn apejuwe nọmba ti awọn abuda rẹ wa.
Litireso:
Nipa awọn aworan ati awọn algoridimu ni gbogbogbo:
1. Cormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Awọn alugoridimu: ikole ati onínọmbà, 2nd àtúnse: Trans. lati English – M.: Williams Publishing House, 2011.
2. Harari Frank. Ilana aworan. M.: Ọdun 1973.
Ijabọ onkọwe naa nipa awọn fekito kanna ati akojọpọ awọn isọdọmọ:
3. Chernoukhov S.A. Adjacency fekito ati associative adjacency orun bi awọn ọna lati soju ati fipamọ awọn aworan / SA Chernouhov. Iṣeduro adjacency ati maapu adjacency gẹgẹbi awọn ẹya data lati ṣe aṣoju iwọn kan // Gbigba awọn nkan ti Apejọ Imọ-jinlẹ ati Iṣeṣe Kariaye “Awọn iṣoro ti imuse awọn abajade ti awọn idagbasoke imotuntun ati awọn ọna lati yanju wọn” (Saratov, Oṣu Kẹsan Ọjọ 14.09.2019, Ọdun 2019). – Sterlitamak: AMI, 65, p. 69-XNUMX
Awọn orisun ori ayelujara ti o wulo lori koko:
4.
5.
orisun: www.habr.com