Վիքիպեդիա

Մասնակից:AnnGabrieli/ավազարկղ

< Մասնակից:AnnGabrieli
Սա AnnGabrieli մասնակցի սևագրության էջն է՝ «ավազարկղը», և մասնակցի էջի ենթաէջերից մեկն է։ Այն ծառայում է որպես սևագիր և փորձարկումների վայր։ Սա հանրագիտարանային հոդված չէ։

Ձեր անձնական ավազարկղը ստեղծելու համար սեղմեք այստեղ։

Այլ ավազարկղեր՝ Ընդհանուր ավազարկղ
Visualization of links between pages on a wiki using a force directed layout.

Ուժ-հիմք կամ ուժ-ղեկավարել ալգորիթմներ ենք, որոնք ալգորիթմի այն դասի համար են, որոնք նկերելու գրաֆիկ aesthetically հաճելի ճանապարհով. Their purpose is to position the nodes of a graph in two-dimensional or three-dimensional space so that all the edges are of more or less equal length and there are as few crossing edges as possible. Գաղափարը ծագել է 1980-ականների գարնանը- ներդրվել է Eades և Kamada-Kawai-ի մոդելը; force-directed տերմինը ծագել է Fruchterman & Reingold-ի 1990 Համալսարանում Illinois տեղնիկական հաշվետվությունից(UIUCDCS-R-90-1609).

Ուժով ուղղված ալգորթմները հասել են նրան, որ նշանակվում են ուժերի շրջանում փաթեթի եզրերին և փաթեթի հանգույցներին ;առավել պարզ եղանակ է ուժերը հատկացնելը , քանի որ եթե եզրերի աղբյուրներ է (տեսHooke- օրենքը) և հանգույցները էլեկտրական լիցքավերման մասնիկներով (տեսCoulomb-ի օրենքը).Ամբողջ ծրագիրը կեղծվել է, քանի որ եղել է ֆիզիկական համակրգ. Այն ուժերը, որոնք կիրառվում են հանգույցներում, մոտենում են միմյանց կամ հետագայում հրում իրար. Սա անընդհատ կրկնվում է, մինչև համակարգը գալիս հավասարակշռության վիճակի; այսինքն ., դրանց համեմատական դիրքրորշումները չեն փովելմի կրկնությունից հաջորդը. Այդ պահին գրաֆիկը ձևավորվում է. Հավասարակշռության վիճակի ֆիզիկական մեկնաբանությունները բերում են նրան, որ բոլոր ուժերը մեխանիկական հավասարակշռության են.

Այլընտրանքնաին մոդելը համարում է առաձգական ուժ յուրաքնչյուր զույգ հանույցների համար ,որտեղ իդեալական երկրությունը յուրաքնչյուր առաձգականությանը համամասնական է տեսաբանական հեռավորությունից մինչև հանգույցները i և j. Այս մոդելում,առանձին բանող ուժի անհրաժեշտություն չկա. Նշենք, որ նվազագույնի հասցնելով տարբերությունը (սովորաբար քառակուսու տարբերությունը) միչևeuclidean և հանգույցների միջև իդեալական հեռավորությունը համարժեք ե մի մետրի multidimensional scaling խնդրի. Stress majorization տալիս է շատ լավ վարք (այսինքն, monotonically համեմատ) և mathematically էլեգանտ ճանապարհն է նվազեցնելու այս տարբերությունները և, հետևաբար, գտնել լավ դասավորություն գրաֆիկի համար. 

force-directed գրաֆիկը կարող է ներգրավել  ուժեր, որոնք մեխանիկական և էլեկտրական աղբյուրների արդյունք են; օրինակները ներառում են logarithmic-ի աղբյուրներ  (ի տարբերություն գծային աղբյուրների),ինչպես gravitational ուժերի (որը համախառն կապված բաղադրիչներ,  որոնք մենակ կապված գրաֆիկներ չեն), մագնիսական ոլորտները (այսպես, ստանալու համար լավ դասավորություն ուղղված գրաֆիկների համար), և  էլեկտրական լիցքավորված զսպանակներ (խուսափելու համար  համընկնումը  կամ մոտ համընկնումը վերջնական խաղարկությանը). Այդ դեպքում,աղբյուր և  լիցքավորված մասնիկների գրաֆիկները, եզրեր են հակված են միատեսակ երկարության (քանի որ առաձգական ուժեր են), և հանգույցները, որոնք կապված չեն  եզրից հակված են հետագայում տարվելու (էլեկտրական արդյունքի պատճառով).

Մինչ գրաֆիկը նկարելը բարդ խնդիր է, force-directed ալգորթմները, լինելով ֆիզիկական սիմուլացիա, սովորաբար պահանջվում է հատուկ գիտելիքներ ոչ միայն գրաֆիկի տեսության , ինչպիսին է planarity.

Նաև հնարավոր է կիրառել մեխանիզմներ , որոնք որոնման համար ուղղակիորեն ավելի էներգետիկ minima, կամ փոխարենը համատեղ ֆիզիկական մոդելավորում. Նման մեխանիզմները, որոնք օրինակ, ընդհանուր գլոբալ օպտիմալացման մեթոդները, ներառում է կռվելու սիմուլյացիա և գենետիկ ալգորիթմը.

Առավելությունները խմբագրել

Հետևյալ են force-directed ալգորիթմների կարևորագույն առավելություններից:

  • Լավ որակի արդյունքներ: Գրաֆիկների միջին մեծության նվազագույնը (մինչև 50-100 vertices), իսկ ստացված արդյունքները սովորաբար շատ լավ արդյունքներ են հիմնված հետևյալ պայմանների վրա: միասնական եզրի երկարությունը, միասնական vertex բաշխումը և ցուցադրման համաչափությունը. Այս վերջին չափանիշը մեկն է առավել կարևորներից և դժվար է հասնել ցանկացած այլ տեսակի ալգորիթմի.
  • Ճկունություն: Force-directed ալգորիթմները կարող են հեշտությամբ հարմարվել և տարածված է կատարելու լրացուցիչ գեղագիտական չափանիշներ. Սա ստիպում է նրանց առավել բազմակողմանի գրաֆիկ նկարելու ալգորթմների դաս. Գոյության ընդարձակման օրինակները ներառում է նոր գրաֆիկներ, 3D գրաֆիկ նկարել[1], կլաստերի գրաֆիկինկարելը, լարված գրաֆիկի նկարելը, և դինամիկ գրաֆիկի նկարելը.
  • Ինտուիտիվ: Քանի որ դրանք հիմնված են ընդհանուր օբյեկտների ֆիզիկական անալոգների վրա, ինչպիսիք են աղբյուրները, ալգորիթմների պահվածքը համեմատաբար հեշտ է կանխատեսել և հասկանալ. Սա այն դեպքն չէ, այլ տեսակի գրաֆիկի ալգորիթմների հետ.
  • Պարզություն: Տիպիկ force-directed ալգորիթմները պարզ են և կարող է իրականացնել մի քանի տող կոդը. Այլ դասընթացների գրաֆիկ-նկարելու ալգորիթմները, ինչպես orthogonal դասավորություն, սովորաբար շատ ավելի զբաղված են.
  • Interactivity: Այս դասի ալգորիթմի մի այլ առավելությունը ինտերակտիվ առումով է. Կազմելով միջանկյալ փուլերի գրաֆիկը, օգտվողը կարող է հետևել, թե ինչպես է զարգանում գրաֆիկը , տեսնել այն tangled քաոսի մի գեղեցիկ կազմաձևումը. Որոշ ինտերակտիվ գրաֆիկի գործիքներից, օգտվողը կարող մեկ կամ մի քանի հանգույցներ դուրս քաշել իրենց հավասարակշռության վիճակից և հետևելու նրանց հետ վերաբնակելու դիրքորոշումը. Սա ստիպում է նրանց նախընտրելի դինամիկ ընտրությունը և online գրաֆիկի համակարգերը.
  • Ուժեղ տեսական հիմքերի քանակը: Մինչ պարզ ad-hoc force-directed ալգորիթմները (օրինակ, կեղծ սույն հոդվածով) հաճախ հայտնվում են գրականությում և գործնականում (քանի որ դրանք համեմատաբար հեշտ է հասկանալ), և առավել հիմնավորված մոտեցումներ են սկսում ձեռք բերել. Վիճակագիրները լուծել են նմանատիպ խնդիրներ multidimensional scaling (MDS) սկսած 1930-ից, և ֆիզիկոսներ նույնպես ունեն նմանատիպ խնդիրների հետ աշխատելու երկար պատմություն n-body -Ֆորումում խնդիրները շատ հասուն մոտեցումներ կան. Որպես օրինակ, stress majorization մոտեցումը MDS կարող է կիրառվել գրաֆիկի խաղարկությանը ինչպես նկարագրված է վերը. Սա ապացուցվել է զուգամիտելով monotonically.[2] Monotonic կոնվերգենցիան, գույքը, որը ալգորիթմ կլինի յուրաքանչյուր բազմակրկնություն նվազեցնելով կամ արժեքն դիրքով, կարևոր է, քանի որ այն երաշխավորում է, որ այն դիրքով, ի վերջո հասնելու տեղական minimum-ի և դադարի. Խլացում ծրագրերը, ինչպիսիք են մեկ օգտագործվող pseudo-code գրանշանները `առաջացնում է ալգորիթմի դադարեցշում, բայց չի կարող երաշխավորել իսկական տեղական նվազագույնին հասելը.

Թերությունները խմբագրել

force-directed ալգորիթմների գլխավոր թերություններըներառում են հետևյալը:

  • High անընդմեջ ժամանակը: force-directed ալգորիթմներին բնորոշ է համարել ընդհանուր անընդմեջ ժամանակին համարժեք հաղորդագրություններ O(n3), , որտեղ հանգույցների n թիվն մուտքագրման գրաֆիկն է. Սա պայմանավորված է թիվի կրկնությամբ ` գնահատվում է O(n),և բոլոր զույգ հանգույցների ամեն կրկնություն, պետք է այցելել և նրանց փոխադարձ բանող ուժերը հաշվարկվում են. Սա կապված է ֆիզիկայի N-մարմնի խնդիրի հետ. Սակայն, քանի որ զզվելի ուժերը տեղական բնույթի են, գրաֆիկը կարող է բաժանվել այնպես, որ միայն հարևան vertices hama8vwum. Ընդհանուր տեխնիկան օգտագործվում է ալգորիթմների դասավորությունը որոշելու համար, մեծ գրաֆիկներն ներառում են բարձր ծավալային ներկառուցում,[3] գծագրական տրոհված շերտի և այլ մեթոդների հետ կապված N- մարմին մոդելավորում. Օրինակ, Barnes–Hut simulation-հիմնված է FADE մեթոդի վրա Քաղվածելու սխալ՝ Invalid parameter in <ref> tag կարող է բարելավել անընդմեջ ժամանակի n*log(n) յուրաքանչյուր բազմակրկնություն. Որպես ուղեցույց, մի քանի վայրկյանում կարելի է ակնկալել առավելագույնը 1,000 հանգույցների ստանդարտ n հետ2 տեխնիկայի բազմակրկնություն, և 100,000 n*log(n) բազմակրկնություն տեխնիկայով.Քաղվածելու սխալ՝ Invalid parameter in <ref> tag
  • Վատ տեղական minima: Շատ հեշտ է տեսնել, որ force-directed ալգորիթմները արտադրել են գրաֆիկ նվազագույն էներգետիկայով, մասնավորապես մեկում, որի ընդհանուր էներգիան միայն տեղական նվազագույնն է. Տեղական նվազագույն կարող է լինել, շատ դեպքերում, ավելի վատ, քան համաշխարհային նվազագույնը, որը թարգմանվել է ավելի ցածր որակի վիճակահանությամբ. Շատ ալգորիթմներ, հատկապես այն պայմանագրերը , որոնք թույլ են տալիս միայն down-hill vertices-ի շարժում, վերջնական արդյունքը կարող է մեծապես ազդել է մեկնարկային դիրքով, որ շատ դեպքերում պատահականորեն գեներացվել է. Վատ տեղական minima-յի խնդիրը դառնում է ավելի կարևոր, քան vertices գրաֆիկը մեծանում է. Տարբեր ալգորիթմների համակցված կիրառումը օգտակար է լուծել այս խնդիրը. Օրինակ, օգտագործելով Kamada-Kawai ալգորիթ ը[4] արագ առաջացնում է ողջամիտ նախնական դասավորություն, ապա Fruchterman-Reingold ալգորիթմը [5] բարելավելու տեղաբաշխում հարևան հանգույցների.

Կեղծ կոդը խմբագրել

Յուրաքանչյուր առանցք ունի x,y պաշտոնը և dx,dy արագություն և m զանգվածը. Սովորաբար կա անընդհատ առաձգականություն, և խլացում: 0 < damping < 1. Ուժը դեպի ու հեռու հանգույցների հաշվարկվում է ըստ Hooke-ի օրենքի և Coulomb-ի օրենքը կամ նման քննարկումը վերևից. Օրինակ կարող է ընդլայնվել trivially ներառելով a z պաշտոնը 3D ներկայացուցչության համար. 

 set up initial node velocities to (0,0)
 set up initial node positions randomly // make sure no 2 nodes are in exactly the same position
 loop
     total_kinetic_energy := 0 // running sum of total kinetic energy over all particles
     for each node
         net-force := (0, 0) // running sum of total force on this particular node
         
         for each other node
             net-force := net-force + Coulomb_repulsion( this_node, other_node )
         next node
         
         for each spring connected to this node
             net-force := net-force + Hooke_attraction( this_node, spring )
         next spring
         
         // without damping, it moves forever
         this_node.velocity := (this_node.velocity + timestep * net-force) * damping
         this_node.position := this_node.position + timestep * this_node.velocity
         total_kinetic_energy := total_kinetic_energy + this_node.mass * (this_node.velocity)^2
     next node
 until total_kinetic_energy is less than some small number  // the simulation has stopped moving

Տես նաև խմբագրել

  • Թուլիփ, ծրագիր, որը իրականցնում է force directed կառուցվածքի մասին (GEM, LGL, GRIP, FM³)
  • Cytoscape, ծրագրային ապահովման համար visualizing կենսաբանական ցանցեր. Բազային փաթեթը ներառում է force-directed դասավորություն որպես ներկառուցված մեթոդներ.
  • Gephi, որը ինտերակտիվ visualization է և հետախուզական հարթակ բոլոր տեսակի ցանցերի և բարդ համակարգերի, դինամիկ և հիերարխիկ գրաֆիկներ.


References խմբագրել

  1. ↑ http://aphrodite.bio.utk.edu/phytree/. {{cite web}}: Missing or empty |title= (օգնություն); Unknown parameter |առաջին= ignored (օգնություն); Unknown parameter |մուևքի անուն= ignored (օգնություն); Unknown parameter |վերնագիր= ignored (օգնություն); Unknown parameter |վերջին= ignored (օգնություն)
  2. ↑ de Leeuw, J. (1988)
  3. ↑ Harel, D., Koren Y. (2002)
  4. ↑ Kamada, T., Kawai, S. (1989)
  5. ↑ Fruchterman, T. M. J., & Reingold, E. M. (1991)

Հետագա ընթերցում խմբագրել

Արտաքին հղումներ խմբագրել


Category:Graph algorithms Category:Graph drawing Category:Articles with example pseudocode

Ստացված է «https://hy.wikipedia.org/w/index.php?title=Մասնակից:AnnGabrieli/ավազարկղ&oldid=5108906» էջից