Крускала болгон алгоритм - оптималдуу алкагында куруу

алгачкы 19-кылым geometer Берлин Якоб Штайнер, алардын узундугу кыска болгон үчүн үч айылды туташтыруу үчүн кандай милдет койгон эле. Кийинчерээк, ал маселени кыскача: ал учак менен бир ойду табуу үчүн талап кылынат, н башка пунктка чейин алыстыгы төмөн болгон. 20-кылымда бул тема боюнча иштеп жатат. Ал бир нече пунктту алып, алардын ортосундагы аралык кыска эле ушундай жол менен алар өз ара байланыш жөнүндө чечим кабыл алынды. баары изилденип жаткан маселе боюнча атайын иш болуп саналат.

"Ач көз" алгоритми

Крускала болгон алгоритм "ач көз" алгоритм (ошондой эле градиент деп аталат) билдирет. адамдар негизи - ар бир кадамга жогорку утуп. Эмес, ар дайым, "ач көз" алгоритмдер көйгөйдү мыкты чечим менен камсыз кылат. конкреттүү милдеттерди, алардын арыз-жылы алар оптималдуу чечим берип экенин көрсөтүп, бир теория бар. Бул matroids теориясы болуп саналат. Крускала болгон алгоритм ушундай көйгөйлөргө билдирет.

минималдуу Өлүк салмагын табуу

Viewed алгоритм оптималдуу кадр санап курган. Бул маселе төмөнкүчө чагылдырууга болот. Дан параллелдүү бурчтары жана илмектерге эле сатылат деп аташы жана жээктердин коюлган ар бир жагы Белгисиз номер ыйгарат ж салмагы милдетин берилсе, - салмагы кабыргасын - ж (е). кабыргасынан ашырган ар бир затка тиешелүү салмагы, анын четтери салыштырма салмагынын суммасы болуп саналат. кичинекей салмагы сөөгүн табуу үчүн талап кылынат.

баяндоо

Крускала болгон алгоритм иштейт. Биринчиден, баштапкы полёта бардык четтерине салмагынын тартибин көтөрүлүп жайгашкан. Башында, кадр, эч бир кабыргасы, бирок бардык vertices камтыйт камтыбайт. бир камтып, токой өлүгүн, буга чейин курулган бөлүгүнө Алгоритмдин кийинки кадамы кийин, бир жагы кошулат. Бул негизсиз тандап алган эмес. полёта бардык бурчу эмес, рамках таандык, кызыл жана жашыл деп атоого болот. ар бир кызыл кырына жогорку курулуш токой байланышы боюнча бир бөлүгү болуп, ал эми жашыл чокулары - ар кандай. Ошондуктан, кызыл четине кошуп болсо, айлампасы бар, жана эгер жашыл - бул кадам кийин алынган отун байланышкан бөлүктөр бири кем болот. Ошентип, натыйжада курулуш жок кызыл четин кошо жок болот, ал эми жашыл жээк токойду алуу үчүн кошумча болот. Ал эми минималдык салмагы менен жашыл этегине кошумчалайт. The натыйжасы алкактуу минималдуу салмак.

ишке ашыруу

учурдагы токой F. Бул байланышты камсыз кылуу тармагында vertices топтомун бөлүштүрөт билдирет (алардын союз түрлөрүнө F, алар кесилишинде жок). кызыл vertices эки ийни бир бүтүн жатышат. Part (х) - жана милдети экенин ар бир чоку х кайрадан бир бөлүгүн жана аты-жөнү, ал таандык х. Unite (х, у) - бир жол-жобосу, ошол курат бир бөлүгү, турган биригип бөлүктөрү боюнча х жана у жана жана башка бөлүктөрү. н болсун - жээктердин саны. Булардын баары түшүнүктөр Крускала болгон алгоритм киргизилген. ишке ашыруу:

1. N-чи өрттөлүүчү салмактын 1 полёта бардык миздүү уюштуруу. (Ай, би - мен жансыз жээк номери менен).

2. Анткени мен = 1 н болот.

3. х: = Part (ай).

4. Ж: = Part (би).

5. Эгер х эмес, бирдей ж анда Unite (х, у), камтыйт менен жана мизи F мен саны.

туура

T болсун - баштапкы полёта аралыктарын Крускала алгоритмин S менен курулган - анын негизсиз кадр. (T) W (S) жогору эмес ж биз далилдешибиз керек.

Болсун М - кабырчыгы ойнош S, P - T барабар Т. Эгерде S эмес, сүзгүч канаттары менен кызыгат, андан кийин бир кадр кабырга менен T эмес, S. S. Сүр таандык цикл, ал C. C кандайдыр бир жээк инал жок деп аталган кире алат, таандык болот S. Биз кырларынын жана vertices эле, анткени, кайсы бир жаңы алкакты алуу. Анын салмагы жок рулуп W (S), W (ET) тартып, мындан ары БӨЛҮҮ (ES) электр Крускала алгоритмдерди. Бул операция (алмаштыруучу T S кабыргага кабыргасы) көп W (T) деп билдирет Т. ар бир кийинки алган алкагында мурдагы салмагы жогору эмес салмагы, кабыл W (S) жогору эмес кайталанат.

Крускала анын Алгоритмдин бойго matroids боюнча Rado-Эдмондс теоремалары келип чыгат.

Колдонмо мисалдар Крускала алгоритми

vertices менен Диаграмма бир эске алып, B, C, D, Е жана кабырга (а, б), (а, е), (б, с), (б, д), (с, г), (с, е) , (г, д, е). бурчтарынын тараза столдун жана сүрөттө көрүнүп турат. Башында, курулуш токой F полёта бардык vertices камтыйт жана кандайдыр бир кабыргасы жок. Алгоритм Крускала биринчи кошумча бир кыры (а, е), баштап жана салмагы майда, ал эми Кудайдын vertices, ошондой эле электрондук ар түрдүү кошулган компоненттер менен жана токой F (жээк (а, е) сырткары жашыл), андан кийин Кудайдын мизинен (C, D), анткени, жок дегенде ушул кыры Диаграмма кырына салмагы эмес, F таандык, ал эми жашыл болсо, анда ошол эле себептерден улам этегинен топтоо үчүн (а, б). Ал эми мизи (б, д), ал кызыл, анткени калган жээктердин, ал жана минималдуу салмагы да, өтүп турат: биз F үчүн этегинен (б, д) Эгер vertices б е, башкача айтканда, токой байланыш F-жылдын ушул эле бөлүгү таандык, түзүлөт цикл. Андан жашыл этегинен кошо (б, с), кызыл четине өтүп жатат (с, е), андан кийин г, д, е. Ошентип, амалкөйлүк кошуу бурчу (а, е), (с, г), (а, б), (б, с). nihera оптималдуу алкагында жана баштапкы полёта турат. Демек, бул учурда ал алгоритмин иштейт Крускала. Бир мисал көрсөтүп турат.

көрсөткүч эки туташкан бөлүктөн турат, арыздын көрсөтүлгөн. тайманбастык менен сызыктар оптималдуу кадр кабыргасы (жашыл) көрсөтүлөт Крускала алгоритми менен курулган.

Мыкты сүрөт баштапкы арыздын жана түбүн көрсөтүп турат - алгоритми менен ал үчүн курган минималдуу салмагы бир скелет.

кошо кабыргасынан катар (1,6); (0,3), (2,6) же (2,6), (0,3) - маанилүү эмес; (3.4); (0,1), (1,6) же (1,6), (0,1), ошондой эле кам (5,6).

Крускала болгон алгоритм ар бир өлкөдө жаңы турак-жай кыймылсыз жерлерде иш жүзүндө колдонууга, мисалы, документ байланыш, жолдорду оптималдаштыруу таап, ошондой эле башка учурларда.