Bert's brein

geplaatst: 10-2-2014

reageer

Een methode om het pad van de handelsreiziger te optimaliseren, met als gevolg een paradox: de meest complexe problemen zijn verhoudingsgewijs het simpelst op te lossen, de meest triviale problemen juist het moeilijkst.

de handelsreiziger-paradox


  • inleiding
  • Het handelsreizigersprobleem wordt bekend verondersteld:
    gegeven: n knooppunten, gegeven alle afstanden tussen alle knooppunten.
    gevraagd: de kortste route waarbij ieder knooppunt exact 1x wordt bezocht, en waarvoor geldt dat het beginpunt gelijk is aan het eindpunt.
    Aan het probleem zijn niet de beperkingen opgelegd die uit de naamgeving lijken te volgen:
    -niet geldt dat d(a,b) = d(b,a)
    [d staat voor distance, (a,b) is een geordend getallenpaar dat staat voor de lengte van de weg van a naar b]
    -niet geldt de driehoeksongelijkheid, d,w,z dat d(a,b) + d(b,c) niet noodzakelijkerwijs groter dan d(a,c).
    Wel is gegeven dat de afstanden mogen worden opgeteld op de manier die bekend is uit de gewone algebra.
    De enige beperkingen die in het onderliggende stuk gelden (niet noodzakelijk voor het probleem) zijn:
    d(a,a) = 0, d.w.z. dat de afstand van een knoop tot zichelf 0 is
    d(a,b) > 0, d.w.z. dat afstanden tussen knopen altijd positief zijn en groter dan 0.

    Het probleem kan weergegeven worden in een matrix van afstanden tussen de knopen. In de onderstaande tekst zal e.e.a. worden geillustreerd aan de hand van een matrix van slechts 6 knopen. Om te garanderen dat de getallen random zijn, zijn de afstanden afgeleid van het getal pi.
      a b c d e f
    a 0 31 41 59 26 53
    b 58 0 97 93 23 84
    c 62 64 0 33 83 27
    d 95 02 88 0 41 97
    e 16 93 99 37 0 51
    f 05 82 09 74 94 0

    i.e: d(a,b) = 31 en d(b,a) = 58 enz.

    algemene karakteristieken:
    Het aantal mogelijke paden bedraagt (n-1)!. In het voorbeeld (n=6) zijn dat 120 oplossingen. Bij n = 1001 zijn dat 4,02387260077093773543702433923 * 102567 mogelijke paden. De voornaamste eigenschap van dit probleem is dus dat het nogal snel uit de hand loopt.
    Als knoop 1002 wordt toegevoegd wordt het aantal mogelijke paden 1001 keer zo groot. Om deze reden zoekt men doorgaans niet naar "de beste" oplossing van het probleem, maar naar een "zeer goede" oplossing. Daarvoor zijn allerlei technieken ontwikkeld.

    Er is slechts 1 kortste weg, al kunnen er wel verschillende paden zijn die dezelfde kortste weg weergeven. Om te bepalen welke weg de kortste is, moeten (in principe) alle wegen worden uitgerekend.

  • methode voor optimalisatie
  • Mijn interesse is (natuurlijk) de enige echte kortste weg.
    Van een pad is bekend dat het niet het kortste kan zijn, als er (o tautologie) een korter pad is aan te wijzen. Dit geldt ook voor een gedeelte van een pad: als er op dit gedeeltelijke pad al een verbetering is aan te geven, maakt dit gedeeltelijke pad zeker geen deel uit van de uiteindelijke oplossing.
    Als er een gedeeltelijk pad is, met de volgorde a-b-c, en daarnaast maakt (p,q) deel uit van het gedeeltelijke pad, dan is met zekerheid bekend dat de volgorde a-b-c geen deel uitmaakt van de gezochte oplossing als d(a,b) + d(b,c) + d(p,q)  >  d(a,c) + d(p,b) + d(b,q). In dat geval is er een verbetering aan te wijzen: haal knoop b weg tussen a en c, en plaats hem tussen p en q.
    Daaruit volgt dat
    als
    d(a,b) + d(b,c) + d(p,q)>d(a,c) + d(p,b) + d(b,q)
    dan
    p-q maakt geen deel uit van een oplossing waarin a-b-c voorkomt.

    Dit idee laat zich uitwerken tot een strategie om gekozen (willekeurige) paden te optimaliseren, maar kan ook gebruikt worden om "de echte" oplossing te vinden.
    Daartoe wordt voor iedere knoop een tabel gemaakt (de insertie-waarde tabel), met de getalsmatige waarde voor de hoeveelheid pad die een knoop aan de oplossing toevoegt als hij tussen iedere mogelijke combinatie van twee andere knopen wordt geplaatst. Voor knoop a staat in het veld (b,c) de waarde [d(b,a) + d(a,c) - d(b,c)].
    Onderstaand is één insertiewaardentabel; alle tabellen van het voorbeeld zijn te vinden op de rekenvoorbeeld-pagina.
    De tabel voor knoop a:
      a b c d e f
    a x x x x x
    b x x 2 24 61 27
    c x 29 x 88 5 88
    d x 124 48 x 80 51
    e x -46 -42 38 x 18
    f x -46 37 -10 -63 x
    ter illustratie:
    als een gedeelte van de oplossing de volgorde b-a-e zou zijn, dan kan de lijn e-f niet in dezelfde oplossing voorkomen. d(b,a) + d(a,e) = 58 + 26 = 84 en d(e,f) = 51. Van deze oplossing is dus een minimale lengte van 84 + 51 = 135 bekend. Maar exact dezelfde knopen kunnen op een kortere manier worden gerangschikt, nl. als gekozen wordt voor b-e in combinatie met e-a-f: d(b,e) = 23; d(e,a) = 16 en d(a,f) = 53; Het totaal is dan (23 + 16 + 53 =) 102. Er is dus een verbetering te bereiken van (135 - 102 = ) 33, door knoop weg te halen tussen b en e, en hem te plaatsen tussen e en f.
    Als b-a-e voorkomt (met insertiewaarde 61), dan kan geen enkele lijn met een lagere insertiewaarde in dezelfde oplossing voorkomen. De lijnen die hierdoor uitvallen zijn dan: c-b, d-c, d-f, e-c, e-d, e-f, f-b, f-c en f-d. Uiteraard vallen ook alle lijnen die vertrekken vanuit b en de lijnen die gaan naar e uit zodra b-a-e gekozen is.

    Het idee om tot de "enige echte" oplossing te komen, is een brach-and-bound strategie:
    Begin bij een knoop, breidt die uit naar iedere andere mogelijke knoop, en dan nogmaals (branch). Bekijk voor iedere potentiele oplossing welke lijnen er uitvallen op basis van de insertiewaarde van het ingesloten punt. Herhaal deze twee stappen totdat
    -er voor een knoop geen enkele valide vervolgknoop is, of
    -er voor een knoop geen enkele knoop is die er valide aan vooraf kan gaan, of
    -de laatst ingesloten knoop een pad dat al in de voorlopige oplossing voorkomt verbiedt, of
    -er op basis van de-oplossing-tot-zover met zekerheid gesteld kan worden dat die onder iedere omstandigheid groter is dan de kleinste oplossing (dit kan o.a. door d.m.v. hybride technieken een suboptimale oplossing te genereren. De echte oplossing is altijd beter dan de suboptimale oplossing)

    De hoop is natuurlijk, dat na een aantal keren branchen de boom (graaf) niet groter wordt, maar juist kleiner.
    Het handmatig uitwerken van een klein voorbeeld leverde op dat:
    -keuzes die sterk afwijken van het optimale pad onmiddelijk leiden naar het elimineren van zeer veel paden
    -bij "redelijke" keuzes vaak dezelfde paden worden geelimineerd, zodat de winst na enige tijd marginaal is.

    Dit leidt naar de vraag: wanneer werkt deze techniek van branch-and-bound wel, en wanneer niet? Het antwoord daarop kent speculatieve elementen, maar is niettemin het overwegen waard, omdat het uitmondt in een fascinerende paradox.

  • het speculatieve stuk
  • Kijk naar het meest triviale handelsreizigerprobleem dat er is:
      a b c d e f
    a 0 1 1 1 1 1
    b 1 0 1 1 1 1
    c 1 1 0 1 1 1
    d 1 1 1 0 1 1
    e 1 1 1 1 0 1
    f 1 1 1 1 1 0

    Zonder te rekenen is duidelijk dat het kortste pad 6 bedraagt, om de eenvoudige reden dat alle paden exact even lang zijn.
    Ook zal duidelijk zijn, dat de boven beschreven branch-and-bound methode hier geen enkel effect sorteert: geen enkel pad zal uitvallen om de reden dat er "winst" te behalen valt door een punt in de keten te verplaatsen.
    Hieruit blijkt, dat het voor het slagen van branch-and-bound essentieel is, dat de punten onderling verschillen. Dit is ook direct inzichtelijk: op basis van insertiewaarden is (in het platte vlak, waar de driehoeksongelijkheid en de stelling van pythagoras gelden) niet of nauwelijks onderscheid te maken tussen twee knopen die op zeer geringe afstand van elkaar liggen. Deze twee knopen hebben immer vrijwel dezelfde insertiewaarden voor hun hele tabel en bij de ene keuze vallen dus dezelfde paden uit als bij de andere keuze. Pas als het hele traject is voltooid kan worden bepaald welke traject het betere is.
    Om branch-and-bound te laten werken is er een maat vereist die uitdrukt in hoeverre twee punten verschillend zijn.

    Per definitie zijn twee punten ten opzichte van een derde punt gelijk als ze tot dat punt dezelfde afstand hebben. Omdat de symmetrie-conditie niet geldt ((a,b) d(b,a)), moet dit gelden voor zowel de paden naar een knoop toe als voor de punten vaneen knoop af.
    De meest eenvoudige maat is de absolute verschil in afstand. Om te corrigeren voor schalings-effecten (een probleem wordt niet anders als ik alle afstanden verdubbel) zoek ik naar een getal tussen 0 en 1. Dit wordt bereikt door het absolute verschil te delen door de langste lijn.
    De mate waarin de knopen a en b verschillen t.o.v. knoop c is dus |d(a,c) - d(b,c)| / d(b,c) als d(b,c) > d(a,c)
    Ook het verschil t.o.v. de punten a en b wordt op deze manier berekend. Vergelijk ik in het gegeven voorbeeld de knopen a en b:
    Het verschil tussen de punten a en b, t.o.v. alle andere punten in het gegeven voorbeeld; 0 = geen verschil, 1 = maximaal verschil

    knoop   d(a,knoop) d(b,knoop) rel verschil a en b   d(knoop,a) d(knoop,b) rel verschil a en b  
    a   0 58 1   0 31 1  
    b   31 0 1   58 0 1  
    c   41 97 56/97   62 64 2/64  
    d   59 93 34/93   95 2 93/95  
    e   26 23 3/26   16 93 77/93  
    f   53 84 31/84   5 82 77/82  
                       

    Een maat om te bepalen in hoeverre a en b verschillend zij t.o.v. alle punten, is om de relatieve verschillen van bovenstaande tabel te middelen. De uitkomst is 8,204521968/12 = 0,683710164. De knopen a en b zijn dus matig verschillend.
    Bovenstaand is berekend in hoeverre knopen van elkaar verschillen. geschaald naar een getal tussen 0 en 1, waarbij 0 staat voor identiek en 1 staat voor maximaal verschillend.
    Per definitie geldt: 1 - (mate van verschil) = mate van overeenkomst.


    Op deze wijze is weer een geheel nieuwe tabel te maken, met daarin de mate waarin knopen met elkaar overeenkomen. Deze tabel is wel symmetrisch, d.w.z. dat de overeenkomst tussen a en b gelijk is aan de overeenkomst tussen b en a. Op de diagonaal staan 1-en, omdat een knoop (per definitie) maximaal overeenkomt met zichzelf. Als gevolg hiervan zijn bij n = 6 slechts 15 van de 36 cellen informatiedragend, oftewel 1/2n(n-1)

    De berekeningen zijn na te gaan op een aparte pagina.

    overzicht overeenkomsten tussen knopen (3 cijfers achter de komma)
      a b c d e f
    a 1 0,316 0,342 0,281 0,330 0,341
    b 0,316 1 0,310 0,441 0,399 0,233
    c 0,342 0,310 1 0,300 0,299 0,400
    d 0,281 0,441 0,300 1 0,290 0,249
    e 0,330 0,399 0,299 0,290 1 0,275
    f 0,341 0,233 0,400 0,249 0,275 1
    Opmerkelijk is dat deze tabel (behalve de schaal) in 15 getallen in principe exact dezelfde informatie bevat als de tabel die het probleem definieerde in 30 getallen.
    Als dezelfde berekening wordt gemaakt voor het triviale geval waar alle afstanden 1 zijn, is de hele tabel gevuld met 1-en, d.w.z. dat er geen verschil is tussen de knopen.

  • de handelsreizigers-paradox
  • Uit het bovenstaande volgt, dat in het triviale geval alle berekeningen [(n-1)!] gemaakt moet worden om te kunnen beslissen wat het beste pad is. In het minder triviale geval vallen er bij de geschetste branch-and-bound gedurende de berekening steeds meer mogelijke paden uit. Ergo: hoe trivialer het geval, hoe meer er gerekend moet worden en (omgekeerd) hoe minder triviaal, hoe meer er gerekend moet worden.

  • en nu verder...
  • In een volgend stuk zal ik de mogelijkheden verkennen om deze paradox in te zetten bij het vinden van een strategie om het handelsreiziger probleem aan te pakken.
    Overigens is het kortste pad van het gestelde niet-triviale probleem het pad a-f-c-d-b-e-a = 136.

Bert's werk