Gren og bundet metode. Matematisk model af den rejsende sælger-problemet

Rejsende sælger problemer løses af forskellige metoder, afledt af teoretiske studier. Alle effektive metoder (reducerer udtømmende søgning) er heuristiske metoder. De fleste heuristiske metoder finder ikke den mest effektive rute, men en omtrentlig løsning. Algoritmer, der gradvist forbedrer nogle nuværende omtrentlige løsninger, er ofte efterspurgte. Der er følgende grupper af metoder til at løse rejsende sælgerproblemer, som er klassificeret som de enkleste:

· Fuldfør søgning;

Brute force (eller metode " råstyrke") - en metode til at løse et problem ved at søge gennem alle mulige muligheder. Kompleksiteten af ​​udtømmende søgning afhænger af antallet af alle mulige løsninger på problemet. Hvis løsningsrummet er meget stort, vil en udtømmende søgning muligvis ikke give resultater i flere år eller endda århundreder.

· Tilfældig søgning;

Typisk kan valget af en løsning repræsenteres som en række valg. Hvis du foretager disse valg ved hjælp af en tilfældig mekanisme, så findes løsningen meget hurtigt, så du kan finde løsningen mange gange og huske "rekorden", det vil sige den bedste løsning, du stødte på. Denne naive tilgang er væsentligt forbedret, når det er muligt at tage højde for udsigterne til visse valg i den tilfældige mekanisme, dvs. tilfældig søgning med heuristisk metode og metode lokal søgning. Sådanne metoder bruges for eksempel ved oprettelse af tidsplaner for Aeroflot.

· Grådige algoritmer (nærmeste nabo-metode, nærmeste by-inkluderingsmetode, billigste inklusionsmetode);

Grådig algoritme – algoritme til at finde korteste afstand ved at vælge den korteste kant, der endnu ikke er valgt, forudsat at den ikke danner en cyklus med allerede valgte kanter. Denne algoritme kaldes "greedy", fordi du i de sidste trin skal betale hårdt for grådighed. Når man løser problemet med den rejsende sælger, vil den grådige algoritme blive til en strategi "gå til den nærmeste (endnu ikke indtastede) by." Den grådige algoritme er åbenbart magtesløs i dette problem. Lad os for eksempel overveje et netværk (fig. 2), der repræsenterer en smal rhombus. Den rejsende sælger starter fra by 1. "Gå til den nærmeste by"-algoritmen vil tage ham til by 2, derefter 3, så 4; på sidste skridt du bliver nødt til at betale for din grådighed ved at vende tilbage langs den lange diagonal af diamanten. Resultatet bliver ikke den korteste, men den længste tur.

· Minimum spanning tree metode (træalgoritme);

Algoritmen er baseret på udsagnet: "Hvis trekantsuligheden er sand, så er det for hver kæde sandt, at afstanden fra begyndelsen til slutningen af ​​kæden er mindre end (eller lig med) den samlede længde af alle kanter på kæden." Dette er en generalisering af den almindelige overbevisning om, at en lige linje er kortere end en kurve. Træalgoritmen til at løse problemet med den rejsende sælger vil være som følger: Det korteste spændingstræ er bygget på inputnetværket for det rejsende sælgerproblem, og alle dets kanter fordobles. Som et resultat opnår vi en forbundet graf med toppunkter, der kun har lige grader. Derefter konstrueres en Eulerisk cyklus, startende fra toppunkt 1, er cyklussen specificeret af en liste over toppunkter. Listen over knudepunkter scannes, startende fra 1, og hvert knudepunkt, der gentager en, der allerede er stødt på i sekvensen, er streget over. Tilbage er turen, som er resultatet af algoritmen.

Det er bevist, at træalgoritmen er mindre end dobbelt så forkert, hvorfor sådanne algoritmer kaldes omtrentlige og ikke kun heuristiske.

· Simuleret udglødningsmetode.

Eksotisk navn af denne algoritme forbundet med simuleringsmetoder i statistisk fysik baseret på Monte Carlo teknikken. Studiet af krystalgitteret og atomernes adfærd under den langsomme afkøling af et legeme førte til fremkomsten af ​​probabilistiske algoritmer, der viste sig at være ekstremt effektive i kombinatorisk optimering. Dette blev først bemærket i 1983. I dag er denne algoritme populær både blandt praktikere på grund af dens enkelhed, fleksibilitet og effektivitet, og blandt teoretikere, da det for denne algoritme er muligt analytisk at studere dens egenskaber og bevise asymptotisk konvergens. Den simulerede annealing-algoritme tilhører klassen af ​​tærskel-lokale søgealgoritmer. Ved hvert trin i denne algoritme, for den aktuelle løsning i k i dens naboskab N(ik), vælges en løsning j, og hvis forskellen i objektiv funktion mellem den nye og nuværende løsning ikke overstiger givet tærskel t k , så erstatter den nye løsning j den nuværende. Ellers vælges en ny naboløsning. I praksis bruges forskellige modifikationer mere effektive metoder:

· Gren og bundet metode;

Forgrenings- og bundmetoden blev foreslået i 1963 af en gruppe forfattere J. Little, K. Murthy, D. Sweeney, K. Carroll. Den meget udbredte backtracking-søgning er faktisk kun et specialtilfælde af den begrænsede søgemetode 4 . Begrænsninger i I dette tilfælde er baseret på den antagelse, at der gives en bestemt omkostningsfunktion på sættet af mulige og delløsninger, og at den optimale løsning skal findes, dvs. billigste løsning. For at anvende branch and bound-metoden skal omkostningsfunktionen have den egenskab, at omkostningerne ved enhver delløsning ikke overstiger omkostningerne ved enhver udvidelse af denne delløsning (Bemærk at omkostningsfunktionen i de fleste tilfælde er ikke-negativ og endda opfylder et stærkere krav). En så stor succes med at bruge denne metode forklares af det faktum, at forfatterne var de første til at være opmærksomme på bredden af ​​muligheder ved metoden, bemærkede vigtigheden af ​​at bruge de specifikke forhold ved problemet og selv udnyttede de særlige forhold vedr. det rejsende sælgerproblem.

Forgrenings- og bundmetoden er baseret på ideen om sekventiel opdeling af et sæt tilladte løsninger i delmængder. Ved hvert trin i metoden kontrolleres partitionselementerne for at bestemme, om en given delmængde indeholder den optimale løsning eller ej. Verifikation udføres ved at beregne et lavere estimat for den objektive funktion på en given delmængde. Hvis det lavere estimat ikke er mindre end rekorden - den bedste løsning fundet - så kan delmængden kasseres. Det afkrydsede undersæt kan også kasseres, hvis det er muligt at finde bedste løsning. Hvis værdien af ​​objektivfunktionen på den fundne løsning er mindre end posten, ændres posten. I slutningen af ​​algoritmen er posten resultatet af dens arbejde. Hvis det er muligt at kassere alle elementer i partitionen, så er posten den optimale løsning på problemet. Ellers fra de ikke-kasserede delmængder vælges den mest lovende (f.eks. med den laveste værdi lavere skøn), og den er delt. Nye undersæt kontrolleres igen mv.

· Metode til genetiske algoritmer;

Den "grundlægger" af genetiske algoritmer anses for at være John Holland, hvis bog Adaptation in Natural and Artificial Systems (1975) er et skelsættende værk inden for dette forskningsområde. En genetisk algoritme er en heuristisk søgealgoritme, der bruges til at løse optimerings- og modelleringsproblemer ved tilfældigt at udvælge, kombinere og variere ønskede parametre ved hjælp af mekanismer, der minder om biologisk evolution. Det er en form for evolutionær beregning. Særpræg genetisk algoritme er en vægt på brugen af ​​"krydsnings"-operatoren, som udfører operationen af ​​rekombination af kandidatløsninger, hvis rolle svarer til rollen som krydsning i levende natur. Genetiske algoritmer tjener primært til at finde løsninger i multidimensionelle søgerum.

· myrekolonialgoritme.

Myrealgoritmer, eller myrekolonioptimering (navnet blev opfundet af algoritmens opfinder, Marco Dorigo), er baseret på brugen af ​​flere midler og har de specifikke egenskaber som myrer og bruger dem til at navigere i det fysiske rum. Myrealgoritmer er især interessante, fordi de kan bruges til at løse ikke kun statiske, men også dynamiske problemer, for eksempel i skiftende netværk.

2.4 Gren og bundet metode

For at løse problemet med den rejsende sælger ved hjælp af branch and bound-metoden, skal du udføre følgende rækkefølge af handlinger:

(1) Konstruktion af en matrix med indledende data.

(2) Find minimum ved rækker.

(3) Strengreduktion.

(4) Finde minimum ved kolonner.

(5) Kolonnereduktion.

(6) Beregning af nul cellescore.

(7) Matrixreduktion.

(8) Hvis fuld vej ikke fundet endnu, gå til punkt 2, hvis fundet, gå til punkt 9.

(9) Beregning af den endelige sti-længde og anlæg af ruten.

Detaljeret løsningsmetode

For bedre at forstå problemet, vil vi ikke arbejde med begreberne i en graf, dens hjørner osv., men med enkle begreber og så tæt som muligt på virkeligheden: spidserne på grafen vil blive kaldt "byer", kanter, der forbinder dem, vil blive kaldt "veje".

Så metoden til at løse problemet med den rejsende sælger:

1. Konstruktion af en matrix med indledende data

Først skal du præsentere længderne af veje, der forbinder byer i form af følgende tabel:

tabel 1

I vores eksempel har vi 4 byer, og tabellen viser afstanden fra hver by til 3 andre, afhængigt af kørselsretningen (da nogle jernbanespor kan være ensrettede osv.).

Afstanden fra en by til samme by er angivet med bogstavet M. Der bruges også et uendelighedstegn. Dette gøres, så dette segment af stien betinget accepteres som uendeligt langt. Så nytter det ikke noget at vælge bevægelse fra 1. by til 1., fra 2. til 2. osv. som et rutesegment.

2. Find minimum efter rækker

Vi finder minimumsværdien i hver linje (di) og skriver den i en separat kolonne.

tabel 2

3. Strengreduktion

Vi udfører en rækkereduktion - fra hvert element i rækken trækker vi den tilsvarende værdi af det fundne minimum (di).

Tabel 3

Som et resultat vil hver linje have mindst én nulcelle.

4. Find minimum ved kolonner

Tabel 4

5. kolonnereduktion

Vi trækker den tilsvarende dj fra hvert element i matricen.

Tabel 5

Som et resultat vil hver kolonne have mindst én nulcelle.

6. Beregning af nul cellescore

For hver nulcelle i den resulterende transformerede matrix finder vi en "score". Det vil være summen af ​​minimumselementet i en række og minimumselementet i en kolonne, hvori denne nulcelle er placeret. Det i sig selv er der ikke taget højde for. Tidligere fundet di og dj er ikke taget i betragtning. Vi skriver det resulterende skøn ud for nul, i parentes.

Tabel 6

Og så videre for alle nulceller:

Tabel 7

7. matrixreduktion

Vi vælger den nulcelle med den højeste score. Erstat den med "M". Vi fandt en af ​​sektionerne af stien. Vi skriver det ned (fra hvilken by vi flytter til hvilken, i vores eksempel fra 4. til 2.).

Tabel 8

Vi krydser helt den linje og den kolonne, hvor to "M"'er blev dannet. I det tilsvarende bur langt tilbage Vi sætter et andet bogstav "M" (da vi ikke vil gå tilbage).

Tabel 9

8. hvis den fulde sti endnu ikke er fundet, gå til punkt 2, hvis fundet, gå til punkt 9

Hvis vi endnu ikke har fundet alle segmenterne af stien, vender vi tilbage til 2. punkt og leder igen efter minima i rækker og kolonner, reducerer dem, tæller estimaterne for nulceller osv.

Hvis alle segmenter af stien er blevet fundet (eller ikke alle segmenter er fundet endnu, men resten af ​​stien er indlysende), skal du gå til trin 9.

9. beregning af den endelige sti-længde og rutekonstruktion

Efter at have fundet alle sektioner af stien, er der kun tilbage at forbinde dem sammen og beregne den samlede længde af stien (omkostninger ved rejse langs denne rute, brugt tid osv.). Vi tager længden af ​​veje, der forbinder byer fra den allerførste tabel med de indledende data.

I vores eksempel viste ruten sig at være: 4 → 2 → 3 → 1 → 4.

Samlet vejlængde: L = 30.

Konklusion

I dette arbejde stiftede vi bekendtskab med grafteoriens grundlæggende begreber, gav en ide om problemet med den rejsende sælger og beskrev de vigtigste metoder til at optimere metoden. De gav også et eksempel på at bruge branch and bound-metoden til at løse problemet med rejsende sælger.

Lad os endnu en gang bemærke, at problemet med den rejsende sælger er et af de vigtigste problemer i grafteori. Evnen til at repræsentere forskellige produktionsprocesser i grafteoriens sprog og evnen til at løse det formulerede matematisk problem giver dig mulighed for at finde den optimale landbrugsstrategi, spare ressourcer og fuldføre opgaven på kortere tid.

Liste over brugt litteratur

1. Kirsanov M.N. "Graphs in Maple", M. Fizmatlit, 2007.

2. Zykov A.A. "Fundamentals of Graph Theory", M. "University Book", 2014

3. Wilson R. "Introduction to graph theory", M. "Mir", 2010

4. Berge K. "Graph theory and its application", M., IL, 2008;

5. Gardner M. "Matematisk fritid", M. "Mir", 2009 (kapitel 35);

6. "At hjælpe matematiklæreren", Yoshkar-Ola, 2011 (artikel "Studiering the elements of graph theory");

7. Olehnik S.N., Nesterenko Yu.V., Potapov M.K. "Gamle underholdende problemer", M. "Nauka", 2008;

8. Gardner M. "Matematiske puslespil og underholdning", M. "Mir", 2012;

9. Ore O. "Graphs and their applications", M. "Mir", 2011;

10. Zykov A.A. "Teori om endelige grafer", Novosibirsk, "Nauka", 2009;

11. Renyi A., "Trilogi om matematik", M., "Mir", 2010.

Udgivet på Allbest.ru

©2015-2019 websted
Alle rettigheder tilhører deres forfattere. Dette websted gør ikke krav på forfatterskab, men giver gratis brug.
Sidens oprettelsesdato: 2016-08-08

Hej! Mens jeg implementerede forskellige algoritmer til at finde den billigste Hamilton-cyklus, stødte jeg på en publikation, der tilbyder min egen version. Efter at have prøvet det, fik jeg det forkerte svar:

Yderligere søgninger på internettet gav ikke det forventede resultat: enten en teoretisk beskrivelse, der var svær for ikke-matematikere, eller forståelig, men med fejl.

Under snittet finder du en korrigeret algoritme og en online lommeregner.

Selve metoden, udgivet af Little, Murthy, Sweeney, Carel i 1963, er anvendelig på mange NP-komplette problemer, og er et meget teoretisk materiale, der uden god viden Engelsk og matematik kan ikke umiddelbart anvendes på vores rejsende sælgerproblem.

Kort om metoden - det er en komplet søgning af alle mulige muligheder med eliminering af klart ikke-optimale løsninger.

Korrigeret algoritme til at finde en virkelig minimal rute

Algoritmen består af to trin:

Første etape

Reduktion af omkostningsmatrixen og beregning af det lavere estimat af ruteomkostningen r.

1. Beregn det mindste element i hver række (støbekonstant for rækken)
2. Lad os gå videre til ny matrix omkostninger ved at trække dens reduktionskonstant fra hver række
3. Beregn det mindste element i hver kolonne (tvangskonstant for kolonnen)
4. Vi går videre til en ny omkostningsmatrix, og trækker dens reduktionskonstant fra hver kolonne.
Som et resultat har vi en omkostningsmatrix, hvor hver række og hver kolonne har mindst ét ​​nul-element.
5. Beregn grænsen på på dette tidspunkt som summen af ​​reduktionskonstanter for kolonner og rækker (denne grænse vil være den pris, under hvilken det er umuligt at konstruere den nødvendige rute)

Anden (hoved) fase

1. Beregning af straffen for manglende brug for hvert nulelement i den givne omkostningsmatrix.
Straffen for ikke at bruge et element med indeks (h,k) i matricen betyder, at denne kant ikke er inkluderet i vores rute, hvilket betyder minimumsomkostninger"Ikke-brugen" af denne kant er lig med summen af ​​de minimale elementer i række h og kolonne k.

a) Vi leder efter alle nul-elementer i den givne matrix
b) For hver af dem beregner vi dens straf for manglende brug.
c) Vælg de elementer, der svarer til den maksimale straf

2. Nu opdeler vi vores sæt S i sæt - der indeholder kanten med den maksimale straf (S w i) og ikke indeholder disse kanter (S w i /o).
3. Beregning af omkostningsoverslag for ruter inkluderet i hvert af disse sæt.
a) For sæt S w i /o er alt simpelt: da vi ikke tager den tilsvarende kant med den maksimale straf (hi ,k i), så er omkostningsestimatet for det lig med omkostningsestimatet for sættet S + straf for ikke ved hjælp af kanten (hej, k i)
b) Ved beregning af omkostningerne for sættet S w i tager vi højde for, at da kanten (hi i,ki) indgår i ruten, betyder det, at kanten (ki,hi) ikke kan indgå i ruten, derfor i omkostningsmatrixen skriver vi c(k i,hi) =uendelighed, og da vi "allerede er tilbage" fra punkt hi, og vi "allerede er ankommet" fra punkt ki, så forlader ikke en eneste kant hi, og ikke en eneste kant, der ankommer til ki, kan allerede bruges, så vi krydser ud fra omkostningsmatricen, række h i og kolonne k i. Herefter giver vi matricen, og så er omkostningsestimatet for S w lig med summen af ​​omkostningsestimatet for S og r(hi,ki), hvor r(hi,ki) er summen af ​​reduktionskonstanterne for den ændrede omkostningsmatrix.
4. Af alle uopdelte sæt vælges den med den laveste score.

Vi fortsætter på denne måde, indtil der er en ukrydset række og en ukrydset kolonne tilbage i omkostningsmatrixen.

Lille optimering - tilføjelse af heuristik

Ja, virkelig, hvorfor introducerer vi ikke heuristik? Faktisk bygger vi i gren- og bundalgoritmen et træ, ved hvis knudepunkter vi beslutter os for at tage kanten (hej, k i) eller ej, og hænge to eller flere børn - Sw(hi,ki) og Sw/ o (hej, k i). Men den bedste mulighed til næste iteration udvælger vi kun efter skøn. Så lad os vælge den bedste, ikke kun med hensyn til vurdering, men også med hensyn til dybde i træet, fordi... Jo dybere det valgte element er, jo tættere er det på slutningen af ​​tællingen. På denne måde kan vi endelig vente på svar.

Nu, faktisk, om fejlene i den publikation

Disse fejl har én grund - ignorerer muligheden for udseendet af flere nulelementer med en maksimal straf. I dette tilfælde er det nødvendigt at opdele ikke i to delmængder, men i stor mængde(2n). Du bør også vælge at partitionere sættet med minimumsgrænsen af ​​alle mulige måder, og ikke fra de to børn opnået som følge af den sidste split.

Bevis

Lad os vende tilbage til billedet i begyndelsen af ​​indlægget:

Og her er løsningen med den korrigerede algoritme.

Det er helt åbenlyst, at problemet kan løses ved at søge gennem alle omvejsmulighederne og vælge den optimale. Problemet er, at antallet af mulige ruter stiger meget hurtigt, efterhånden som n vokser (det er lig med n! - antallet af måder at bestille point på). For eksempel, for 100 point vil antallet af muligheder være repræsenteret af et 158-cifret tal - ikke en eneste lommeregner kan klare det! En kraftfuld computer, der er i stand til at sortere gennem en million muligheder i sekundet, vil kæmpe med problemet i cirka 3 ⋅ 10.144 år. En stigning i computerens produktivitet med 1000 gange vil give, om end 1000 gange mindre, men stadig en monstrøs tid til at søge gennem muligheder. Det hjælper ikke engang situationen, at der for hver rutemulighed er 2 ⁢n ækvivalente, der adskiller sig i valget af startpunkt (n muligheder) og retningen af ​​omvejen (2 muligheder). Under hensyntagen til denne observation reduceres søgningen lidt - til n! 2⁢n = n−1! 2 muligheder.

Måske er en algoritme baseret på udtømmende søgning efter muligheder ikke den mest effektive (hastighedsmæssigt) til at løse problemet med den rejsende sælger? Ak, det er blevet bevist, at der ikke er nogen løsningsalgoritme, der har magtlovskompleksitet (det vil sige, der kræver rækkefølge n a operationer for nogle a) - enhver algoritme vil være værre. Alt dette gør det rejsende sælgerproblem håbløst for en computer med sekventiel udførelse af operationer, hvis n i det mindste er noget stor.

I dette tilfælde bør du opgive at forsøge at finde en eksakt løsning på det rejsende sælgerproblem og koncentrere dig om at finde en omtrentlig - omend ikke optimal, men i hvert fald tæt på. I lyset af problemets store praktiske betydning vil omtrentlige løsninger også være nyttige.

Bemærk, at det menneskelige intellekt, ikke bevæbnet med computerteknologi, er i stand til at finde sådanne omtrentlige løsninger på problemer, der kræver en enorm søgning af muligheder i jagten på den optimale. Lad os lige huske skak. En person kan med stor succes konkurrere i dette spil computer enten uden at ty til brute force overhovedet, eller at reducere det til et minimum. En person er styret af intuition og et sæt af heuristisk(finder) - regler, der normalt hjælper med at løse problemer, selvom effektiviteten af ​​sådanne regler ikke har tilstrækkelig begrundelse. Som sådan en universel heuristik kan vi nævne Kants kategoriske imperativ : "Gør mod andre, som du vil have de skal gøre mod dig." Et andet, mere jordnært eksempel er givet af den gyldne regel for en valutaspekulant: "når alle sælger dollars, så køb, og når alle køber, så sælg."

Mange naturlige processer løser valgproblemer optimal mulighed fra et stort (selv måske uendeligt) udvalg af muligheder. For eksempel tager en tung fleksibel homogen kæde ophængt i enderne på to søm, fra alle mulige tilgængelige former, præcis den, der svarer til den minimale potentielle tyngdekraftsenergi (som er proportional med højden af ​​kædens tyngdepunkt ). Desuden er kæden til at finde den nødvendige formular (kaldes den katenoid, eller kæde linje) kræver meget mindre tid end den person, der komponerer og løser differentialligning Euler - Lagrange for at finde netop denne katenoid. En sæbefilm strakt over en trådløkke antager en form, der svarer til filmens minimale indre energi (bestående hovedsageligt af den potentielle energi af overfladespændingskræfter, proportional med filmens areal). En lysstråle i et gennemsigtigt (muligvis inhomogent) medium, der brydes, finder den korteste vej (der kræver den korteste tid at rejse gennem nogen af ​​dens sektioner) under hensyntagen til lysets hastighed på hvert punkt i mediet, som den passerer igennem. Stoffet, der krystalliserer fra smelten, antager gradvist den krystallinske form, hvilket igen minimerer den indre energi, som består af energierne fra den parvise vekselvirkning mellem molekyler. I sidste eksempel molekyler af et stof, der gennemgår kaotisk termisk bevægelse, som bremses, når det afkøles, "famler" gradvist efter den ønskede konfiguration, minimalt i energimæssig forstand, bl.a. kæmpe mængde molekylære arrangementsmuligheder. Biologisk evolution forbedrer arter ved at reducere sandsynligheden for overlevelse (og følgelig overførsel af genetisk information til afkom) af mindre velegnede individer.

Alle disse overvejelser fører os til heuristik: "hvis du tilnærmelsesvis vil løse et problem, skal du modellere (for eksempel ved hjælp af en computer) en naturlig proces, der løser et lignende problem." Her er et par stykker specifikke applikationer denne heuristik: "du har brug for en ellipse - lad lommelygten skinne på gulvet, vip den lidt (lommelygte eller gulv)." Eller "hæld vand i et cylindrisk eller konisk glas og vip det lidt." Eller "tag et brød pølse og skær det diagonalt." "Du skal bruge en sinusbølge - pak pølsen ind i papir og klip den sammen med papiret, og fold derefter papirarket ud." Eller "vær med oscillerende kredsløb til oscilloskopet” - oscillatorkredsløbet løser øjeblikkeligt differentialligningen for oscillationer, og løsningerne til denne ligning er sinus og cosinus. "Vil du regne bestemt integral- klip en buet trapez ud af papir, vej den og divider den med massen af ​​en enkelt papirfirkant."

Observationerne beskrevet ovenfor giver os mulighed for at betragte naturlige processer som computere (sådanne maskiner kaldes analog), ganske velegnet til at løse mange vigtige problemer. Analoge computere kan bruges direkte, eller principperne for deres drift kan bruges som grundlag for meget effektive algoritmer til traditionelle, digital COMPUTER. Det eneste, der kan lide med sådan modellering, er nøjagtigheden af ​​at løse problemet.

Søgeproblemer rettet mod at finde den optimale mulighed kaldes kombinatoriske optimeringsproblemer

Lad os give en formel formulering af optimeringsproblemet. Givet en endelig (normalt meget stor) mængde X og en numerisk funktion U ⁡ x på dette sæt. Denne funktion kaldes mål. Det er nødvendigt at finde sådan x * ∈ X, at U ⁡ x * vil være den mindste, det vil sige U ⁡ x * ⩽ U ⁡ x for alle x ∈ X . En variant af problemformuleringen, når det er påkrævet at finde målfunktionens maksimumpunkter, kan let reduceres til at søge efter funktionens minimumpunkter − U .

Det rejsende sælgerproblem kan formuleres som et optimeringsproblem. Som en mængde X er det tilstrækkeligt at tage S n (sættet af permutationer af en n-elementmængde), og som objektivfunktionen U ⁡ x - længden af ​​en lukket stiplet linje, der går gennem n givet point i rækkefølgen givet af permutationen x ∈ X.

For at løse problemet med at finde minimumspunktet for en funktion er der blevet opfundet mange metoder. For eksempel, for differentiable funktioner U defineret på et numerisk sæt X, som det er kendt, skal minimumspunkter (hvis nogen) søges blandt kritiske punkter U, det vil sige sådan x, at U ′ x = 0. Der er dog ingen grund til at tale om differentiabiliteten af ​​en funktion defineret på en endelig mængde, som ikke nødvendigvis er numerisk, så metoden baseret på kritiske punkter er ikke egnet. Vi afviser også en fuldstændig søgning af alle x af de årsager, der er diskuteret ovenfor.

For sæt X, som den er defineret for intimitetsforhold, andre metoder er også velegnede. Blandt dem - gradient nedstigningsmetode

En nærhedsrelation er en måde at bestemme for to elementer i et sæt, om de er tætte (i en vis forstand). For numeriske sæt, for sæt af punkter på et plan eller i rummet, kan to tal (to punkter) betragtes som tætte, hvor afstanden mellem dem ikke overstiger et lille tal ε. For et sæt S n er det praktisk at betragte to permutationer, der adskiller sig med én, som tætte Omrokering, det vil sige opnået fra hinanden ved at "castle" to elementer i sættet. For eksempel er permutationerne 2 4 1 3 og 2 3 1 4 tæt på i denne forstand, da de adskiller sig i permutationen af ​​elementer nummereret 2 og 4. Det er muligt at definere en mere stringent nærhedsrelation, hvor tætte permutationer adskiller sig med tilstødende gennemførelse , når castling påvirker elementer af sættet med tilstødende numre. Så vil ovenstående permutationer ikke længere være tæt på, men 2 4 1 3 og 2 4 3 1 vil være tæt på.

Essensen af ​​gradient-nedstigningsmetoden afspejles i dens navn og er som følger. En sekvens x 0 x 1 x 2 x 3 … ⊂ X er konstrueret, hvor det initiale element x 0 er valgt vilkårligt (eventuelt tilfældigt), og hver efterfølgende er en af ​​naboerne til den foregående, og netop den nabo for hvor værdien af ​​funktionen U vil være den mindste. Konstruktionen af ​​sekvensen er afsluttet, når rækkefølgen af ​​værdier af objektivfunktionen U ⁡ x 0 U ⁡ x 1 U ⁡ x 2 U ⁡ x 3 … ophører med at være monotont aftagende.

Det sidste element i den konstruerede sekvens kaldes et punkt lokalt minimum. Dette er et punkt, hvor værdien af ​​U er strengt taget mindre end hos alle dens naboer. Ordet "lokal" indeholder den største ulempe ved den beskrevne metode. Funktionen U kan have mange lokale minima, og hver af dem har som regel sin egen lokalt minimale værdi af den objektive funktion. Vi er interesserede i det absolutte minimum af funktionen og elementet i mængden X, hvori den opnås. Hvis det var nemt at finde alle de lokale minimumspoint, ville vi søge blandt dem for at finde det absolutte minimumspunkt. Men metoden med gradientnedstigning giver ikke en søgeopskrift alle sammen punkter af lokalt minimum, det giver dig mulighed for kun at finde nogle .

Der er en probabilistisk version af gradient descent-metoden. Ved hvert trin vælges en tilfældig nabo for et element i sættet X. Hvis værdien af ​​objektivfunktionen ved et tilfældigt nabopunkt er faldet, tilføjes den til sekvensen, og vi går videre til næste trin. Hvis ikke, så vælges en tilfældig nabo igen. Algoritmen stopper, hvis sekvensen ikke genopfyldes i lang nok tid (overgangen til næste trin sker ikke): sandsynligvis førte algoritmen i dette tilfælde til et lokalt minimumspunkt.

En af de omtrentlige metoder til at løse sådanne optimeringsproblemer er simuleret udglødningsmetode. Udglødning- den allerede nævnte proces med gradvis afkøling af et stof, hvor molekyler, på baggrund af en stadig mere langsommere termisk bevægelse, samles i de mest energisk gunstige konfigurationer. Udtrykket "glødning" kommer fra metallurgi. Faktum er, at metal i en mere energisk gunstig tilstand er både hårdere og stærkere: der kræves mere ydre påvirkning, stor mekanisk arbejde over et stykke metal for at forstyrre den gunstige konfiguration af molekyler, "hæve" denne konfiguration over bunden af ​​energihullet.

Den simulerede udglødningsmetode er en modifikation af den probabilistiske gradientnedstigningsmetode. Forskellen ligger i algoritmens opførsel, når U ⁡ x ⩽ U ⁡ x ~, hvor x er det næste element i sekvensen, og x ~ er dens nabo, valgt tilfældigt. Den probabilistiske gradientnedstigningsmetode afviste en sådan nabo ubetinget, og den simulerede udglødningsmetode tillader tilføjelsen af ​​en sådan "dårlig" nabo til sekvensen, dog med en vis sandsynlighed p, afhængigt af hvor meget den dårlige nabo forværrede den objektive funktion. Lad os tage forskellen ∆ ⁡ U = U ⁡ x ~ − U ⁡ x (den er ikke-negativ, hvis naboen er “dårlig”) og sætter p = e − ∆ ⁡ U Θ . Her er e et eller andet tal, der er større end et (hvilket er ikke vigtigt, men normalt tager de e ≈ 2,718281828459045... - basis af naturlige logaritmer), og Θ er et positivt tal kaldet temperatur

I figur 45.1. "Mutationssandsynlighed for den simulerede annealing metode" viser afhængigheden af ​​mutationssandsynligheden af ​​værdien ∆ ⁡ U ved forskellige betydninger temperatur Θ. Høje temperaturer De grafer, hvis farve er tættere på rød, svarer til dem, hvis farve er tættere på blå. Som forventet er sandsynlighedsværdien indeholdt i intervallet 0 1. For negativ ∆ ⁡ U er sandsynligheden 1, hvilket svarer til tilfældet med en "god" mutation.

Fortsættes…

Send dit gode arbejde i videnbasen er enkel. Brug formularen nedenfor

Godt arbejde til webstedet">

Studerende, kandidatstuderende, unge forskere, der bruger videnbasen i deres studier og arbejde, vil være dig meget taknemmelig.

opslået på http://www.allbest.ru/

1 . Beskrivelse af metodengrene og grænser

Forgrenings- og bundmetoden er baseret på ideen om sekventielt at opdele sættet af gennemførlige løsninger i delmængder. Ved hvert trin i metoden kontrolleres partitionselementerne for at bestemme, om en given delmængde indeholder den optimale løsning eller ej. Verifikation udføres ved at beregne et lavere estimat for den objektive funktion på en given delmængde. Hvis det lavere skøn ikke er mindre end optage- den bedste løsning fundet, så kan undersættet kasseres. Den afkrydsede delmængde kan også kasseres, hvis den bedste løsning kan findes i den. Hvis værdien af ​​objektivfunktionen på den fundne løsning er mindre end posten, ændres posten. I slutningen af ​​algoritmen er posten resultatet af dens arbejde.

Hvis det er muligt at kassere alle elementer i partitionen, så er posten den optimale løsning på problemet. Ellers vælges den mest lovende fra de ikke-kasserede delmængder (for eksempel med den laveste nedre grænseværdi), og den opdeles. Nye undersæt kontrolleres igen mv.

Når man anvender forgrening og bundet metode til hvert specifikt problem, først og fremmest, skal dets to vigtigste procedurer bestemmes: 1) forgrening af sættet af mulige løsninger; 2) beregning af nedre og øvre estimater af den objektive funktion.

1 . 1 Forgreningsregler

Afhængigt af opgavens karakteristika bruges en af ​​to metoder normalt til at organisere forgrening:

1. forgrening af sættet af gennemførlige løsninger til det oprindelige problem D;

2. forgrening af mængden D" opnået fra D ved at fjerne heltalsbetingelsen på variablerne.

Den første forgreningsmetode bruges normalt til opgaver heltals programmering og består i at identificere delområder af mulige løsninger ved at fastsætte værdierne individuelle komponenter heltalsoptimeringsvariabler (fig. 1). I fig. 1-a giver en geometrisk fortolkning af området med tilladelige løsninger til heltalsprogrammeringsproblemet, bestemt af to lineære begrænsninger og betingelser for variables ikke-negativitet og underområderne dannet ved forgrening, og i fig. Figur 1-b viser det tilsvarende forgreningsdiagram.

Den anden forgreningsmetode er mere universel end den første. For at forgrene et bestemt område D i " på denne måde på D i " løses et optimeringsproblem med målfunktionen for det oprindelige problem og reelle variable.

Forgrening udføres, hvis værdien af ​​mindst én heltalsvariabel ifølge den oprindelige problemformulering i den optimale løsning ikke er heltal. Blandt disse variable vælges en, for eksempel j - i. Lad os betegne dens værdi i den fundne optimale løsning x 0 [j]. De siger, at forgrening udføres af variablen x[j]. Regionen Di " er opdelt i to underregioner D i1 " og D i2 " som følger:

Hvor ] - hele delen værdier x 0 [j]

I fig. 2 giver konventionelt en geometrisk fortolkning af en sådan forgrening.

opslået på http://www.allbest.ru/

Ris. 2. Geometrisk fortolkning af forgrening

Det kan ses, at i dette tilfælde fjernes delen mellem planerne af de nyligt indførte restriktioner fra området D i ". Da variablen x[j] i henhold til betingelserne for området med tilladte løsninger af det oprindelige problem er heltal, derefter fra underdomænet af tilladte løsninger af det oprindelige problem. D i (D i D i ") med en sådan undtagelse er ingen beslutning udelukket.

1 . 2 Dannelse af nedre og øvre estimater af den objektive funktion

Inden man starter en diskussion af denne problemstilling, skal det siges, at det er almindeligt accepteret at bruge branch and bound-metoden til et problem, hvor optimeringsretningen er reduceret til form af minimering. For at gøre yderligere notation og beregninger mere kompakte, vil vi skrive det diskrete programmeringsproblem, som vi vil bruge gren- og bundmetoden til, i følgende generaliserede form:

hvor x er en vektor af optimeringsvariable, hvoraf nogle er reelle og nogle er heltal; f(x) - i det generelle tilfælde en ikke-lineær objektiv funktion; D er regionen med mulige løsninger på et generelt diskret programmeringsproblem.

Lavere estimater af måldiktionen, afhængigt af den valgte forgreningsmetode, kan bestemmes enten for underområder D i D eller for underområder D i "D" (D i " og D" opnås fra de tilsvarende sæt D i og D ved at fjerne integeritetsbetingelserne på diskrete variable).

Det lavere estimat af objektivfunktionen f(x) på mængden Di (eller D i ") vil være mængden:

Beregning af nedre grænser i hver konkret tilfælde kan udføres under hensyntagen til egenskaberne ved det problem, der skal løses. For at estimater mest effektivt kan opfylde deres funktion, skal de samtidig være så store som muligt, dvs. være så tæt som muligt på de faktiske værdier af min f(x). Dette er først og fremmest nødvendigt, for at de nedre grænser så nøjagtigt som muligt afspejler det faktiske forhold min f(x) på delmængderne dannet under forgrening og gør det muligt mere præcist at bestemme retningen for yderligere søgning optimal løsning original opgave.

I fig. Figur 3 viser et sådant ideelt tilfælde, når de lavere estimater (forbundet med en stiplet stiplet linje) korrekt afspejler forholdet mellem de reelle minimumsværdier f(x) (forbundet med en stiplet linje) for fire delmængder af mulige løsninger D 1, D 2, D 3, D 4.

En af de universelle måder at beregne nedre grænser på er at løse følgende problem:

Oi defineret på denne måde er et lavere estimat af f(x) på Di (eller Di "), da D i D i ".

Hvis det ved løsning af problem (4) konstateres det, så vil vi for almenhedens skyld antage det.

Det er nødvendigt at bemærke en vigtig egenskab ved lavere estimater, som er, at deres værdier for de delmængder, der dannes under forgrening, ikke kan være mindre end det lavere estimat af den objektive funktion på det sæt, der er udsat for forgrening.

Sammen med den nedre grænse bruger branch and bound metoden øvre grænse f(x). Som regel beregnes kun én værdi af den øvre grænse, som defineres som værdien af ​​den objektive funktion for den bedst fundne gennemførlige løsning på det oprindelige problem. Dette øvre skøn kaldes undertiden en rekord. Hvis det for det problem, der skal løses, er muligt ganske enkelt og præcist at opnå øvre grænser f(x) for individuelle mængder dannet under forgrening, så skal de bruges i metoden til at reducere den beregningsmæssige kompleksitet af løsningsprocessen. Når man bruger en enkelt øvre grænse, antages dens begyndelsesværdi sædvanligvis at være lig med uendelig (), medmindre der naturligvis ud fra a priori betragtninger ikke kendes nogen mulig løsning på det oprindelige problem. Når du finder den første mulige løsning:

Derefter, når der bestemmes en bedre gennemførlig løsning, justeres den øvre grænse:

Værdien af ​​det øvre skøn kan således kun falde i processen med at løse problemet.

1 .3 Gren og bundet algoritme

De grundlæggende regler for algoritmen kan formuleres som følger:

1. Først og fremmest er delmængden med det tal, der svarer til den laveste værdi af det nederste estimat af den objektive funktion, genstand for forgrening (I er mængden af ​​tal for alle delmængder, (eller) placeret i enderne af grenene og hvis forgrening endnu ikke er standset). Hvis ovennævnte metode til forgreningssæt implementeres, kan der opstå uklarhed med hensyn til valget af komponent, langs hvilken det næste forgreningstrin skal udføres. Desværre er spørgsmålet om den "bedste" måde for et sådant valg fra et generelt synspunkt endnu ikke blevet løst, og derfor bruges nogle heuristiske regler i specifikke problemer.

2. Hvis betingelsen er opfyldt for en i-te delmængde, skal dens forgrening standses, da de potentielle muligheder for at finde god beslutning i denne delmængde (karakteriserer dem) viser sig at være værre end værdien af ​​den objektive funktion for den reelle fundet af i dette øjeblik tid, en acceptabel løsning på det oprindelige problem (det karakteriserer).

3. Forgrening af delmængden stopper, hvis den optimale løsning fundet i problem (4) findes. Dette begrundes med, at der derfor ikke er nogen bedre gennemførlig løsning end i denne delmængde. I dette tilfælde overvejes muligheden for tilpasning.

4. Hvis, hvor, så er optimalitetsbetingelserne opfyldt for den bedst mulige løsning fundet på nuværende tidspunkt. Begrundelsen er den samme som stk. 2 i disse regler.

5. Efter at have fundet mindst én mulig løsning på det oprindelige problem, kan muligheden for at stoppe algoritmen overvejes med en vurdering af nærheden af ​​den bedste af de resulterende mulige løsninger til den optimale (baseret på værdien af ​​den objektive funktion ):

1 .4 Løsning af problemet ved hjælp af branch and bound-metoden

I første omgang finder vi simpleks metode eller metode kunstigt grundlag optimal plan problemer uden at tage højde for variables heltalskarakter.

Hvis der ikke er nogen brøktal blandt komponenterne i denne plan, er den ønskede løsning på dette problem fundet.

Hvis der er blandt plankomponenterne brøktal, så er det nødvendigt at flytte til nye planer, indtil en løsning på problemet er fundet.

Gren-og-bund-metoden er baseret på den antagelse, at vores optimale ikke-heltalsdesign producerer en funktionsværdi, der er større end ethvert efterfølgende grendesign.

Lad variablen i planen være et brøktal. Så vil dens værdi i den optimale plan være iflg i det mindste enten mindre end eller lig med det nærmeste mindre heltal, eller større end eller lig med det nærmeste større heltal.

Ved at bestemme disse tal finder vi løsningen på to lineære programmeringsproblemer ved hjælp af simpleksmetoden

Der er fire mulige tilfælde, når du løser dette par af problemer:

Et af problemerne er uløseligt, og det andet har en heltalsoptimal plan. Så giver denne plan og værdien af ​​den objektive funktion en løsning på det oprindelige problem.

Et af problemerne er uløseligt, og det andet har en ikke-heltals optimal plan. Derefter overvejer vi det andet problem og vælger i sin optimale plan en af ​​komponenterne, hvis værdi er lig med et brøktal og konstruerer to problemer, der ligner de foregående.

Begge problemer kan løses. Et af problemerne har en optimal heltalsplan, og den anden opgaves optimale plan har brøktal. Derefter beregner vi værdierne af den objektive funktion ud fra planerne og sammenligner dem med hinanden. Hvis værdien af ​​den objektive funktion på en heltalsoptimal plan er større end eller lig med dens værdi på en plan, hvis komponenter inkluderer brøktal, så er denne heltalsplan optimal til det oprindelige problem og giver den ønskede løsning.

Begge problemer er løselige, og de optimale planer for begge problemer omfatter brøktal. Derefter overvejer vi det problem, hvor værdien af ​​den objektive funktion er størst. Og vi konstruerer to opgaver.

Når vi løser problemet, får vi således følgende diagram:

Vi finder en løsning på et lineært programmeringsproblem uden at tage heltal i betragtning.

Opretter yderligere begrænsninger på brøkdelen af ​​planen.

Vi finder løsninger på to problemer med restriktioner på komponenten.

Om nødvendigt konstruerer vi yderligere begrænsninger, i henhold til de mulige fire tilfælde opnår vi en optimal heltalsplan eller fastslår problemets uløselighed.

Lad os finde en løsning på problemet

Løsning. Vi finder en løsning uden at tage højde for problemets heltalsværdi ved hjælp af simpleksmetoden.

Lad os overveje næste par opgaver:

Det første problem har en optimal plan

det andet er uløseligt.

Vi tjekker planen for den første opgave for integritet. Denne betingelse er ikke opfyldt, så vi konstruerer følgende opgaver:

Opgave 1.1

Opgave 1.2

Opgave 1.2 er uløselig, og opgave nr. 1.1 har en optimal plan, hvorpå værdien af ​​det objektive fungerer.

Som et resultat fik vi det oprindelige problem heltalsprogrammering har en optimal plan og.

2. Løsning af det rejsende sælgerproblem ved hjælp af branch and bound metoden

Lad os nu overveje klassen af ​​anvendte optimeringsproblemer. Forgrenings- og bundmetoden bruges i mange af dem. Det foreslås at overveje et af de mest populære problemer - det rejsende sælgerproblem. Her er dens ordlyd. Der er flere byer forbundet på en eller anden måde af veje af en vis længde; det er påkrævet at fastslå, om der er en sti, langs hvilken man kun kan besøge hver by én gang og samtidig vende tilbage til den by, hvorfra stien startede ("rejsende sælgers omvej"), og, hvis en sådan sti findes, for at etablere den korteste af sådanne veje.

2.1 Problemstilling

Lad os formalisere betingelsen i form af grafteori. Byer vil være hjørnerne af grafen, og vejene mellem byer vil være de orienterede (rettede) kanter af grafen, på hver af hvilke en given vægt funktion: Vægten af ​​en kant er længden af ​​den tilsvarende vej. Stien, der skal findes, er en orienteret spændende simpel cyklus med minimumvægt i digrafen (husk: en cyklus kaldes spænder, hvis den passerer gennem alle hjørnerne af grafen; en cyklus kaldes simpel, hvis den passerer gennem hver af dens hjørner kun én gang; en cyklus kaldes orienteret, hvis begyndelsen af ​​hver efterfølgende kant falder sammen med slutningen af ​​den foregående; vægten af ​​en cyklus er summen af ​​vægtene af dens kanter; endelig kaldes en digraf komplet, hvis den indeholder alle mulige kanter); sådanne cykler kaldes også Hamiltonian.

Det er klart, at en komplet digraf indeholder cyklusser af den ovenfor angivne type. Bemærk, at det er nok at overveje spørgsmålet om tilstedeværelsen af ​​en Hamilton-cyklus i en digraf som særlig situation rejsende sælger problemer for komplette digografier. Faktisk, hvis en given digraf ikke er komplet, så kan den suppleres til fuldstændighed med de manglende kanter, og en vægt Ґ kan tildeles hver af de tilføjede kanter, i betragtning af at Ґ er "computer uendelighed", dvs. det maksimale af alle mulige tal i betragtning. Hvis vi nu finder den letteste Hamilton-cyklus i den nyligt konstruerede komplette digraf, så hvis den har kanter med vægt Ґ kan vi sige, at der ikke er nogen "rejsende sælgercyklus" i denne originale graf. Hvis den letteste Hamilton-cyklus i en komplet digraf viser sig at være endelig i vægt, så vil det være den ønskede cyklus i den originale graf.

Det følger heraf, at det er tilstrækkeligt at løse det rejsende sælgerproblem for komplette digrafer med vægtfunktion. Lad os nu formulere dette i sin endelige form:

lad være en komplet rettet graf og være en vægtfunktion; finde en simpel spændingsorienteret cyklus ("rejsende sælgercyklus") med minimumvægt.

Lad den specifikke sammensætning af sættet af toppunkter og være vægtmatricen af ​​en given digraf, dvs. , og for enhver.

Overvejelse af filial og bundet metode til at løse problemet med den rejsende sælger udføres mest bekvemt i baggrunden konkret eksempel. Ved at bruge den her introducerede notation udfører vi denne beskrivelse i næste forelæsning.

Lad os introducere nogle udtryk. Lad der være en numerisk matrix. At reducere en række i denne matrix betyder at vælge minimumselementet i rækken (det kaldes reduktionskonstanten) og trække det fra alle elementer i denne række. Som et resultat heraf vil minimumselementet naturligvis være nul, og alle andre elementer vil være ikke-negative. Ordene "giv en matrixkolonne" har en lignende betydning.

Ordene bringer matrix række for række betyder, at alle rækker i matrixen er givet. Ordene "reducere en matrix med kolonner" har en lignende betydning.

Endelig betyder ordene "reducer matrix", at matrixen først reduceres med rækker og derefter reduceres med kolonner.

Vægten af ​​et matrixelement er summen af ​​matrixreduktionskonstanter, som fås fra en given matrix ved at erstatte det pågældende element med Ґ. Derfor betyder ordene tungeste nul i matricen, at vægten af ​​hvert nul i matricen beregnes, og så er nullet med den maksimale vægt fastsat.

Lad os nu fortsætte med at beskrive gren- og bundmetoden til at løse problemet med den rejsende sælger.

Første skridt. Vi fikser sættet af alle gennemløb af den rejsende sælger (dvs. alle simple orienterede spændingscyklusser). Da grafen er komplet, er dette sæt bestemt ikke tomt. Lad os forbinde med det et tal, der vil spille rollen som en værdi på dette sæt af evalueringsfunktionen: dette tal er lig med summen af ​​reduktionskonstanterne for den givne matrix af vægte af grafkanterne. Hvis sættet af alle runder af en rejsende sælger er angivet med G, så er summen af ​​reduktionskonstanter for vægtmatricen angivet med j(G). Den givne matrix af vægte for denne graf skal huskes; lad os betegne det med M 1; Således resultatet af det første trin:

sættet G af alle runder af den rejsende sælger er forbundet med tallet j(G) og matrixen M 1 .

Andet trin. Lad os vælge det tungeste nulpunkt i matrixen M 1; lad ham stå i et bur; vi fikserer en kant af grafen og deler mængden G i to dele: en del, der består af gennemløb, der går gennem kanten, og en del, der består af gennemløb, der ikke går gennem kanten.

Lad os knytte følgende matrix M 1,1 til mængden: I matrixen M 1 erstatter vi tallet i cellen med Ґ. Så i den resulterende matrix krydser vi rækkenummer i og kolonnenummer j ud og beholder de resterende rækker og kolonner med deres oprindelige tal. Lad os endelig reducere denne sidste matrix og huske summen af ​​reduktionskonstanterne. Den resulterende reducerede matrix vil være matrixen M 1,1; Vi tilføjer summen af ​​reduktionskonstanter lige husket til j(G), og resultatet, yderligere angivet med j(), er sammenligneligt med mængden.

Nu forbinder vi også en bestemt matrix M 1,2 med sættet. For at gøre dette erstatter vi i matrixen M 1 tallet i cellen med Ґ og præsenterer den resulterende matrix. Lad os huske summen af ​​reduktionskonstanterne og betegne den resulterende matrix med M 1,2. Lad os lægge den huskede sum af reduktionskonstanter til tallet j(G), og det resulterende tal, yderligere angivet med j(), er sammenligneligt med mængden.

Lad os nu vælge mellem mængderne den, hvor funktionen j er minimal (dvs. den mængde, der svarer til det mindste af tallene j() og j()).

Lad os nu bemærke, at i ovenstående ræsonnement blev kun ét faktisk objekt brugt som det indledende - den reducerede matrix af vægte af en given digraf. Ved hjælp af den blev en bestemt kant af grafen identificeret, og der blev konstrueret nye matricer, hvorpå selvfølgelig det samme kan anvendes.

Med hver sådan gentagen applikation vil den næste kant af grafen blive registreret. Lad os blive enige om næste handling: før du sletter en række og en kolonne i den næste matrix, er det nødvendigt at erstatte med Ґ tallene i alle de celler, der svarer til kanter, der åbenbart ikke hører til de Hamilton-cyklusser, der passerer gennem de tidligere valgte kanter.

Vi vil gentage det samme for det valgte sæt med matrixen og tallet j tilknyttet, og så videre, så længe dette er muligt.

Det er bevist, at resultatet er et sæt bestående af en enkelt runde af den rejsende sælger, hvis vægt er lig med den næste værdi af funktionen j; således er alle de betingelser, der diskuteres ved beskrivelsen af ​​gren- og bundmetoden, opfyldt.

Herefter forbedres rekorden indtil det endelige svar er opnået.

2.2 Problemets tilstand

Student Ivanov fik til opgave at levere nogle vigtige dokumenter fra den 12. bygning. Men som heldet ville have det, har han meget lidt tid til dette, og han skal stadig tilbage. Vi skal finde den korteste vej. Afstandene mellem objekter er angivet i tabellen

2.3 Matematisk model af problemet

For at løse problemet tildeler vi hvert rutepunkt specifikt nummer: 12. bygning - 1, Hvide Hus - 2, KRK "Premier" - 3, Administration - 4. og 5. bygning - 5. Derfor er det samlede antal point. Dernæst introducerer vi alternative variable, der tager værdien 0, hvis overgangen fra det i-te punkt til det j-te ikke er inkluderet i ruten og 1 ellers. Betingelserne for ankomst til hvert punkt og udgang fra hvert punkt udtrykkes kun én gang ved lighederne (8) og (9).

For at sikre rutekontinuitet, yderligere n variabler og yderligere begrænsninger (10).

Samlet rutelængde F, som skal minimeres, skrives i følgende form:

I vores tilfælde vil disse betingelser blive skrevet i følgende form:

2.4 Løsning af problemet ved hjælp af branch and bound metoden

1) Analyse af sæt D.

Lad os finde et lavere skøn N. For at gøre dette definerer vi en matrix med minimumsafstande for række (1 hvor afstanden er minimal i en række).

På samme måde definerer vi matrixen af ​​minimumsafstande langs søjlerne.

Lad os vælge indledende plan: . Så er den øvre grænse:

Det er klart, hvor betyder overgangen fra det første punkt til det j-te. Lad os overveje disse delmængder i rækkefølge.

2) Analyse af D 12 delmængden.

3) Analyse af delmængde D 13.

4) Analyse af delmængde D 14.

5) Analyse af delmængde D 15.

6) Frasortering af ikke-lovende delmængder.

Undersæt D 13 og D 15 er ikke lovende. Fordi , men så vil vi yderligere overveje delmængden D 14.

7) Analyse af delmængde D 142.

8) Analyse af delmængde D 143.

9) Analyse af D 145 delmængden.

10) Frasortering af ikke-lovende delmængder

Undersæt D 143 er ikke lovende. Fordi , men så vil vi yderligere overveje delmængden D 145.

11) Analyse af D 1452 delmængden.

grengrænsemålalgoritme

12) Analyse af D 1453 delmængden.

Optimal løsning: .

Således elevens rute: 12. bygning - Administration - 5. bygning - Hvide Hus - KRK Premier - 12. bygning.

opslået på http://www.allbest.ru/

Liste over brugtelitteratur

1. Abramov L.A., Kapustin V.F. Matematisk programmering. - L.: Leningrad State University Publishing House, 1981. -328 s.

2. Alekseev O.G. Integreret anvendelse af diskrete optimeringsmetoder. - M.: Nauka, 1987. -294 s.

3. Korbut A.A., Finkelgein Yu.Yu. Diskret programmering. M.: Videnskab. 1969. -240 s

4. Kuznetsov Yu.N. Matematisk programmering: Lærebog. - 2. udg., revideret og suppleret. - M.: Højere skole, 1980. -300 s.

5. Papadimitriou H., Steiglitz K. Kombinatorisk optimering. Algoritmer og kompleksitet. - M.: Mir, 1985. -213 s.

Udgivet på Allbest.ru

...

Lignende dokumenter

Redegørelse og løsning af diskrete problemer optimeringsproblemer den diskrete programmeringsmetode og branch and bound metoden ved hjælp af et eksempel klassisk problem rejsende sælger Stadier af konstruktion af en gren og bundet algoritme og dens effektivitet, konstruktion af et graftræ.

kursusarbejde, tilføjet 11/08/2009


Udtalelse af problemet med den rejsende sælger. At finde den optimale løsning ved brug af branch and bound metoden. Det grundlæggende princip for denne metode, rækkefølgen af ​​dens anvendelse. Brug af den øvre grænse metode i proceduren til at konstruere et træ med mulige muligheder.

kursusarbejde, tilføjet 10/01/2009


Funktioner ved branch and bound-metoden som en af ​​de almindelige løsningsmetoder heltalsproblemer. Dekomponering af et lineært programmeringsproblem i branch-and-bound-algoritmen. Grafisk simpleksmetode til løsning af lineære programmeringsproblemer.

kursusarbejde, tilføjet 03/05/2012


Simulering af myrebevægelse. Gren og bundet metode, nærmeste nabo. Begrænsninger pålagt agenten i standardformuleringen af ​​problemet med den rejsende sælger. Brug af synlighedsgrafen i myrealgoritmen. Ant algoritme datastruktur.

afhandling, tilføjet 02/07/2013


Første og anden ordens gren- og bundmetoder. Optimal og passiv søgning. Ulemper ved Newtons metode. Gyldne snit metode. Eksempler på unimodale funktioner. Dynamisk og lineær programmering. Jordan-Gauss metode. Løsning af rejsende sælgerproblem.

kursusarbejde, tilføjet 20/07/2012


Essensen af ​​grafteori og netværksmodellering. Valg af den optimale vej og omkostninger ved at flytte en rejsende sælger ved hjælp af filial og bundet metode. Udvikling af et program til at vælge den mest rentable rute, der passerer gennem de angivne byer mindst én gang.

kursusarbejde, tilføjet 08/08/2013


Optimering af problemløsningen ved hjælp af annealing-algoritmen. Analyse af optimeringsteori som objektiv funktion. Gradient nedstigningsmetode. Variabler og beskrivelse af annealing-algoritmen. Repræsentation af det rejsende sælgerproblem gennem en graf. Reducere problemet til variabler og løse det.

kursusarbejde, tilføjet 21/05/2015


Udsagn af et lineært heltalsproblem. Skæreplan metode. Fraktionel algoritme til at løse heltal problemer. Effektiviteten af ​​Gomori-skæring. Sammenligning af beregningsevnerne for skæringsplanmetoden og branch and bound-metoden.

kursusarbejde, tilføjet 25.11.2011


Rygselproblemet som et kombinatorisk optimeringsproblem. Problem med lastning, rygsæk, rygsæk. Erklæring og NP-fuldstændighed af problemet. Klassificering af metoder til løsning af rygproblemet. Dynamisk programmering. Gren og bundet metode. Komparativ analyse af metoder.

kursusarbejde, tilføjet 18.01.2011


At finde øvre og nedre grænser for optimal værdi på underdomænet af gennemførlige løsninger. Metoder og problemer til løsning af ikke-lineære programmeringsproblemer. Skrivning og fejlretning af et program. Oprettelse af et program til at løse problemet med den rejsende sælger ved hjælp af en direkte algoritme.

Mange forskere kom med ideen om branch-and-bound-metoden, men Little og hans medforfattere udviklede på baggrund af denne metode en succesfuld algoritme til at løse problemproblemer og bidrog derved til populariseringen af ​​tilgangen. Siden da er branch-and-bound-metoden med succes blevet anvendt på mange problemer, og flere andre modifikationer af metoden er blevet opfundet for at løse problemet, men de fleste lærebøger fokuserer på Littles pionerarbejde.

Den generelle idé er triviel: du skal opdele kæmpe antal sorteret muligheder i klasser og indhent estimater (nedefra - i minimeringsproblemet, fra oven - i maksimeringsproblemet) for disse klasser for at kunne kassere muligheder ikke én efter én, men efter hele klasser. Vanskeligheden er at finde en sådan opdeling i klasser (grene) og sådanne skøn (grænser), at proceduren er effektiv.

tabel 2

Tabel 3

Tabel 4

Lad os præsentere Littles algoritme ved hjælp af eksempel 1 i det foregående afsnit. Lad os omskrive matrixen:

Det vil være mere bekvemt for os at fortolke C ij som rejseomkostningerne fra by i til by j. Lad os antage, at den gode borgmester i by j har udstedt et dekret om at betale hver rejsende sælger, der kommer ind i byen, $5. Det betyder, at enhver tur bliver billigere med $5, da enhver tur kræver indtastning af by j. Men da alle ture ensartet er faldet i pris, vil den tidligere minimumstur nu koste mindst. Borgmesterens gode gerning kan repræsenteres som et fald i alle tal i den j-te kolonne i matrix C med 5. Hvis borgmesteren ønskede at sende rejsende sælgere væk fra den j-te by og sætte en belønning for at tage af sted i beløb på 10 dollars, kan dette udtrykkes ved at trække 10 fra alle elementer jth det linjer. Dette ville igen ændre prisen på hver tur, men minimumsturen forbliver minimum. Så følgende lemma er bevist.

Ved at trække en konstant fra alle elementer i en række eller kolonne i matrix C, forlader vi minimumsturen som et minimum.

For algoritmen vil det være praktisk for os at få flere nuller i matricen C, uden dog at komme dertil negative tal. For at gøre dette trækker vi dets minimumselement fra hver række (dette kaldes rækkereduktion, se tabel 3), og trækker derefter dets minimumselement fra hver kolonne i den rækkevise matrix, hvilket opnår en kolonnevis reduktionsmatrix, se tabel . 4).

Diagonale streger betyder, at du ikke kan gå fra by i til by i. Bemærk, at summen af ​​reduktionskonstanterne i rækker er 27, summen i kolonner er 7, og summen af ​​summer er 34.

Turen kan defineres af et system med seks understregede (fremhævet i en anden farve) elementer i matrix C, for eksempel, som vist i tabel. 2. At understrege et element betyder, at de i runden går fra det i-te element til det j-te. For en seks-by-tur skal der være seks understregede elementer, da der er seks kanter i en seks-by-tur. Hver kolonne skal indeholde nøjagtigt ét understreget element (den rejsende sælger indtastede hver by én gang), hver række skal indeholde nøjagtigt ét understreget element (den rejsende sælger forlod hver by én gang); desuden skal de understregede elementer beskrive en enkelt runde i stedet for flere mindre cyklusser. Summen af ​​tallene for de understregede elementer er prisen for turen. På bordet 2 prisen er 36, dette er den mindste runde opnået ved leksikografisk søgning.

Nu vil vi ræsonnere ud fra den givne matrix i tabellen. 2. Hvis det kan bygges det rigtige system understregede elementer, dvs. system, der opfylder de tre krav beskrevet ovenfor, og disse understregede elementer kun vil være nuller, så er det klart, at for denne matrix vil vi opnå en minimum tur. Men det vil også være minimalt for den originale matrix C, kun for at få de korrekte omkostninger ved turen, skal du tilføje alle reduktionskonstanter tilbage, og prisen på turen vil ændre sig fra 0 til 34. Således, minimumsturen må ikke være mindre end 34. Vi fik en lavere bedømmelse for alle runder.

Lad os nu begynde at forgrene. For at gøre dette vil vi udføre trinnet med at estimere nuller. Betragt nulpunktet i celle (1,2) i den reducerede matrix. Det betyder, at omkostningerne ved at flytte fra by 1 til by 2 er 0. Hvad hvis vi ikke går fra by 1 til by 2? Så skal du stadig indtaste by 2 for de priser, der er angivet i anden kolonne; billigere for kun 1 (fra by 6). Dernæst skal du stadig forlade by 1 til den pris, der er angivet i første linje; den billigste mulighed er at gå til by 3 for 0. Sammenfattende disse to minimumskrav har vi 1+0=1: Hvis du ikke går "nul" fra by 1 til by 2, så skal du betale mindst 1 Dette er estimat af nul. Estimaterne for alle nuller er angivet i tabellen. 5 til højre og over nul (nul score lig med nul blev ikke givet).

Lad os vælge det maksimale af disse estimater (i eksemplet er der flere estimater, lig med én, vælg den første af dem i celle (1,2)).

Så nulkanten (1,2) er valgt. Lad os opdele alle ture i to klasser - dem, der inkluderer kanten (1,2) og dem, der ikke inkluderer kanten (1,2). For anden klasse kan vi sige, at du skal betale 1 mere, så ture i denne klasse koster 35 eller mere.

Hvad angår den første klasse, skal vi overveje matricen i tabellen. 6 med den første linje og anden kolonne overstreget.

Tabel 5

Tabel 7

Derudover er der i den reducerede matrix et forbud i celle (2,1), fordi kant (1,2) er valgt, og det er umuligt at lukke turen før tid med kant (2,1). Den reducerede matrix kan reduceres med 1 i første kolonne, så hver runde svarende til den koster mindst 35. Resultatet af vores forgrening og indhentning af estimater er vist i Fig. 6.

Cirklerne repræsenterer klasser: den øverste cirkel er klassen for alle runder; nederst til venstre - klasse af alle ture inklusive kant (1,2); nederst til højre - klassen af ​​alle ture, der ikke inkluderer kant (1,2). Tallene over cirklerne er skøn nedefra.

Lad os fortsætte med at forgrene os positive side: venstre - ned. For at gøre dette estimerer vi nullerne i den reducerede matrix C i tabellen. 7. Den maksimale score i celle (3,1) er 3. Således er scoren for nederste højre toppunkt i fig. 7 er 35+3=38. For at evaluere det nederste venstre toppunkt i fig. 7, skal du slette en anden række 3 og kolonne 1 fra matrix C, for at opnå matrix C[(1,2), (3,1)] i tabellen. 8. I denne matrix skal du sætte et ban i celle (2,3), da et fragment af turen allerede er blevet konstrueret fra kanter (1,2) og (3,1), dvs. , og for tidlig lukning skal forbydes (2.3). Denne matrix er givet ved kolonne med 1 (tabel 9), og derfor koster hver tur i den tilsvarende klasse (dvs. en tur med kanter (1,2) og (3,1)) 36 eller mere.

Tabel 9

Tabel 11

Nu evaluerer vi nullerne i den givne matrix C[(1,2), (3,1)] nullet med den maksimale score på 3 er i celle (6,5). Den negative mulighed har en score på 38+3=41. For at få en vurdering af den positive mulighed, fjern linje 6 og kolonne 5, indsæt et forbud i celle (5,6), se tabel. 10. Denne matrix er irreducerbar. Som følge heraf stiger scoren for den positive mulighed ikke (fig. 8).

Evaluering af nullerne i matrixen i tabellen. 10, får vi forgrening baseret på valget af kant (2,6), den negative mulighed får en score på 36+3=39, og for at få en score for den positive mulighed krydser vi anden række og sjette kolonne ud, få matricen i tabellen. elleve.

Et ban skal tilføjes til matrixen i celle (5.3), fordi et fragment af turen allerede er blevet konstrueret, og for tidlig tilbagevenden skal være forbudt (5.3). Nu hvor vi har en 2x2 matrix tilbage med diagonale begrænsninger, afslutter vi turen med kanter (4,3) og (5,4). Det var ikke forgæves, at vi forgrenede os til positive muligheder. Nu har vi modtaget en tur: 1>2>6>5>4>3>1 med en pris på 36. Ved at nå bunden af ​​søgetræet blev klassen af ​​ture indsnævret til én tur, og skønnet fra nedenfor omsat til den nøjagtige pris.

Så alle klasser med en score på 36 og derover, bedste tur ikke indeholder. Derfor er de tilsvarende hjørner overstreget. Hjørner, hvis begge efterkommere er slettet, slettes også. Vi har reduceret den samlede søgning enormt. Tilbage står at tjekke, om klassen svarende til matrix C ikke indeholder en bedre tur, dvs. givet matrix C med ban i celle 1,2, reduceret med 1 i kolonne (hvilket gav scoren 34+1=35). Evalueringen af ​​nuller giver 3 for nullet i cellen (1,3), så evalueringen af ​​den negative mulighed 35+3 overstiger værdien af ​​den allerede modtagne runde 36, og den negative mulighed afbrydes.

For at opnå et estimat af den positive mulighed udelukker vi den første række og den tredje kolonne fra matricen, sætter ban (3.1) og får matricen. Denne matrix er givet i fjerde række med 1, klassens score når 36, og cirklen er streget over. Da begge børn af toppunktet "alle" bliver dræbt, bliver det også dræbt. Der er ingen hjørner tilbage, eftersøgningen er slut. Vi modtog den samme minimumstur, som er vist understreget i tabellen. 2.

Der er ingen tilfredsstillende teoretiske skøn over ydeevnen af ​​den lille algoritme og relaterede algoritmer, men praksis viser, at moderne computere de giver dig ofte mulighed for at løse problemproblemer med n = 100. Dette er en kæmpe forbedring sammenlignet med udtømmende søgning. Derudover er algoritmer som branch og bound effektive heuristiske procedurer, hvis de ikke kan gennemføres.