Алгоритам анализа со тестот е - изградба на оптимална рамка

Во почетокот на 19 век геометар Јакоб Штајнер од Берлин постави задача за тоа како да се поврзиш три села, така што нивната должина е најкратката. Подоцна, тој ги сумираше проблем: тоа е потребно да се најде точка во рамнина, на оддалеченост од него да се N други точки беа на најниско ниво. Во 20-от век, тој продолжува да работи на оваа тема. Беше одлучено да се земе неколку точки и да ги поврзете на таков начин што растојанието меѓу нив беше најкратката. Сето ова е посебен случај на проблемот што се испитуваат.

"Алчен" Алгоритам

алгоритам анализа со тестот е се однесува на "алчен" алгоритам (исто така наречени градиент). Суштината на оние - највисока победа на секој чекор. Не секогаш, "алчен" алгоритми обезбеди најдобро решение за проблемот. Постои теорија, покажуваат дека во нивната примена на специфични задачи тие се даде на оптимално решение. Ова е теорија на matroids. алгоритам анализа со тестот е се однесува на ваквите проблеми.

Наоѓање минимална тежина труп

Гледано алгоритам гради оптимален број на рамката. Проблемот на тоа е како што следува. Дан ненасочен графикон без паралелно рабовите и петелки, и сет на рабовите е дадена функција на тежината w, кои му ги доделува број на секое работ e - тежина на ребро - w (д). Тежината на секоја подгрупа на мноштво на ребрата е збир на тежините на неговите рабови. Потребно да се најде на скелет на една мала тежина.

опис

алгоритам анализа со тестот дела. Прво, сите рабови на почетна графикон се подредени во растечки редослед на тегови. Првично, рамката не содржи никакви ребра, но ги вклучува сите темиња. По следниот чекор на алгоритмот на веќе изградениот дел од труп, кој е се протега шума, се додава еден раб. Тоа не е избран произволно. Сите рабови на графика, кои не припаѓаат на рамка, може да се нарече црвена и зелена боја. На врвот на секоја црвени рабови се во иста компонента во изградба шума конекција, и зелени блузи - различни. Затоа, ако го додадете во црвен крај, постои циклус, и ако на зелените - како ќе пристигнат по овој чекор на дрво поврзани компоненти ќе биде помалку од еден. Така, како резултат на изградбата не може да не додаваат црвен крај, но секоја зелена работ може да се додаде за да се добие шума. И додава зелена раб со минимална тежина. Резултатот е рамка на минимална тежина.

имплементација

Означување на тековната шума Ѓ дели собата на темиња во областа на поврзување (нивниот синдикат форми F, и тие се сечат). На двете рабовите на црвено темиња лежат во едно парче. Дел (x) - функција која за секое теме x враќа дел од името, таа им припаѓа x. Обединете (x, y) - постапка која гради нова партиција, која се состои од комбинирање на делови од X и Y и сите други делови. Нека n - број на рабовите. Сите овие концепти се вклучени во алгоритам анализа со тестот е. имплементација:

1. Организираме сите рабови на графиконот од 1 до n-ти растејќи тежини. (Ai, BI - i со врвот број работ).

2. за i = 1 до n се направи.

3. x: = Дел (AI).

4. y: = Дел (BI).

5. Ако X не еднаква y тогаш Обединете (x, y), да се вклучуваат со бројот на работ F i.

коректност

Нека Т - рамка на оригиналот графикон конструирани со користење на алгоритам анализа со тестот и S - неговата произволна рамка. Ние треба да докаже дека w (Т) не е поголема од w (S).

Да М - множество на перки S, P - множество на перки Т. Ако S не е еднаква на T, тогаш постои рамка ребро et T, кои не припаѓаат на S. S. et adjoin на циклусот, тоа се нарекува C. C отстрани од било кој раб ES, кои припаѓаат С. Добиеме нова рамка, бидејќи рабови и темиња е иста. Неговата тежина не е поголема од w (S), бидејќи w (et) веќе не w (es) на моќ анализа со тестот алгоритам. Оваа операција (замена T S ребра на ребра) ќе се повторува се додека добиваат Т. Тежината на секоја наредна доби рамка не е поголема од претходната тежина, што значи дека w (Т) не е поголема од w (S).

Стабилноста на алгоритам е анализа со тестот следува од теорема на Радо-Едмондс на matroids.

Примери на употреба анализа со тестот алгоритам

Дан графикон со јазли a, b, c, d, e и ребра (a, b), (А, Е), (b, c), (b, д), (c, d), (ц, д) , (d, e). Тежините на рабовите се прикажани во табелата, а на сликата. Првично, изградба шума F содржи сите темиња на графиконот и не содржи никакви ребра. Алгоритам анализа со тестот прво додадете ребро (а, е), со оглед на тежината имаше најниска и темињата А и Е се во различни компоненти дрво поврзување F (ребро (а, е) е зелено), а потоа на ребро (в, г), бидејќи дека барем оваа предност тежина на графикон рабови, кои не припаѓаат на F, а тоа е зелена, а потоа од истите причини се таложи раб (a, b). Но, на работ (b, d) е донесен, иако тој и минимална тежина од останатите краеви, бидејќи тоа е црвено: темиња б и д припаѓаат на истата компонента на шумски поврзување F, тоа е, ако се додаде до F работ (б, д), се формира циклус. А потоа додаде зелена раб (b, c), е донесен црвено раб (Ц, Е), а потоа d, e. Така, се додаваат рабовите секвенцијално (а, е), (c, d), (a, b), (b, c). Од nihera оптимална рамка и се состои од оригиналниот графиконот. Значи во овој случај тоа работи алгоритам Анализа со тестот. Еден пример е прикажан.

Бројката покажува графикон, кој се состои од две поврзани компоненти. На задебелените линии индицираат на оптимална рамка ребра (зелена) конструирани со користење на алгоритам анализа со тестот.

На врвот на сликата покажува оригиналната графика, и на дното - скелет на минимална тежина, изградена за него со помош на алгоритам.

Секвенцата на додадена ребра (1.6); (0,3), (2,6) или (2,6), (0,3) - не е важно; (3,4); (0,1), (1,6) или (1,6), (0,1), исто така, нега (5,6).

алгоритам анализа со тестот е наоѓа практична примена, на пример, за да се оптимизира на заптивка комуникации, патишта во новите локалитети станбени објекти во секоја земја, како и во други случаи.