Bert's brein

geplaatst: 10-2-2014

reageer

begeleidende rekenvoorbeelden bij de handelsreiziger-paradox

terug naar handelsreiziger-paradox

  • het voorbeeldprobleem
  •   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


  • berekeningen van verschil tussen punten
  • verschil a,b
    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  
    verschil a-b = 0,683710164
    overeenkomst = 1 - verschil = 0,316289836


    verschil a,c
    knoop   d(a,knoop) d(c,knoop) rel verschil a en c   d(knoop,a) d(knoop,c) rel verschil a en c  
    a   0 62 1   0 41 1  
    b   31 64 33/64   58 97 39/97  
    c   41 0 1   62 0 1  
    d   59 33 26/59   95 88 7/95  
    e   26 83 57/83   16 99 83/99  
    f   53 27 26/53   5 9 4/9  
    verschil a-c = 0,657682528
    overeenkomst = 1 - verschil = 0,342317471


    verschil a,d
    knoop   d(a,knoop) d(d,knoop) rel verschil a en d   d(knoop,a) d(knoop,d) rel verschil a en d  
    a   0 95 1   0 59 1  
    b   31 2 29/31   58 93 35/93  
    c   41 88 47/88   62 33 29/62  
    d   59 0 1   95 0 1  
    e   26 41 15/41   16 37 21/37  
    f   53 97 44/97   5 74 69/74  
    verschil a-d = 0,719426892
    overeenkomst = 1 - verschil = 0,280573107


    verschil a,e
    knoop   d(a,knoop) d(e,knoop) rel verschil a en e   d(knoop,a) d(knoop,e) rel verschil a en e  
    a   0 16 1   0 26 1  
    b   31 93 62/93   58 23 35/58  
    c   41 99 58/99   62 83 21/83  
    d   59 37 22/59   95 41 54/95  
    e 26 0 1 16 0 1
    f   53 51 2/53   5 94 89/94  
    verschil a-e = 0,669569362
    overeenkomst = 1 - verschil = 0,330430637


    verschil a,f
    knoop   d(a,knoop) d(f,knoop) rel verschil a en f   d(knoop,a) d(knoop,f) rel verschil a en f  
    a   0 5 1   0 53 1  
    b   31 82 51/82   58 84 26/84  
    c   41 9 32/41   62 27 35/62  
    d   59 74 15/74   95 97 2/97  
    e 26 94 68/94 16 51 35/51
    f   53 0 1   5 0 1  
    verschil a-f = 0,659123249
    overeenkomst = 1 - verschil = 0,340876751


    verschil b,c
    knoop   d(b,knoop) d(c,knoop) rel verschil b en c   d(knoop,b) d(knoop,c) rel verschil b en c  
    a   58 62 4/62   31 41 10/41  
    b   0 64 1   0 97 1  
    c 97 0 1 64 0 1
    d   93 33 60/93   02 88 86/88  
    e 23 83 60/83 93 99 6/99
    f   84 27 57/84   82 09 73/82  
    verschil b-c = 0,690263795
    overeenkomst = 1 - verschil = 0,309736204


    verschil b,d
    knoop   d(b,knoop) d(d,knoop) rel verschil b en d   d(knoop,b) d(knoop,d) rel verschil b en d  
    a   58 95 37/95   31 59 28/59  
    b   0 2 1   0 93 1  
    c 97 88 9/97 64 33 31/64
    d   93 0 1   02 0 1  
    e 23 41 18/41 93 37 56/93
    f   84 97 13/97   82 74 8/82  
    verschil b-d = 0,559497081
    overeenkomst = 1 - verschil = 0,440502918


    verschil b,e
    knoop   d(b,knoop) d(e,knoop) rel verschil b en e   d(knoop,b) d(knoop,e) rel verschil b en e  
    a   58 16 42/58   31 26 5/31  
    b   0 93 1   0 23 1  
    c 97 99 2/99 64 83 19/83
    d   93 37 56/93   02 41 39/41  
    e 23 0 1 93 0 1
    f   84 51 33/84   82 94 12/94  
    verschil b-e = 0,600702725
    overeenkomst = 1 - verschil = 0,399297274


    verschil b,f
    knoop   d(b,knoop) d(f,knoop) rel verschil b en f   d(knoop,b) d(knoop,f) rel verschil b en f  
    a   58 5 53/58   31 53 22/53  
    b   0 82 1   0 84 1  
    c 97 9 88/97 64 27 37/64
    d   93 74 19/93   02 97 95/97  
    e 23 94 71/94 93 51 42/93
    f   84 0 1   82 0 1  
    verschil b-f = 0,767070292
    overeenkomst = 1 - verschil = 0,232929707


    verschil c,d
    knoop   d(c,knoop) d(d,knoop) rel verschil c en d   d(knoop,c) d(knoop,d) rel verschil c en d  
    a   62 95 33/95   41 59 18/59  
    b   64 2 62/64   97 93 4/97  
    c 0 88 1 0 33 1
    d   33 0 1   88 0 1  
    e 83 41 42/83 99 37 62/99
    f 27 97 70/97 09 74 65/74
    verschil c-d = 0,699562905
    overeenkomst = 1 - verschil = 0,300437094


    verschil c,e
    knoop   d(c,knoop) d(e,knoop) rel verschil c en e   d(knoop,c) d(knoop,e) rel verschil c en e  
    a   62 16 46/62   41 26 15/26  
    b   64 93 29/93   97 23 74/97  
    c 0 99 1 0 83 1
    d   33 37 4/37   88 41 47/88  
    e 83 0 1 99 0 1
    f 27 51 24/51 09 94 85/94
    verschil c-e = 0,70088464
    overeenkomst = 1 - verschil = 0,299115369


    verschil c,f
    knoop   d(c,knoop) d(f,knoop) rel verschil c en f   d(knoop,c) d(knoop,f) rel verschil c en f  
    a   62 5 57/62   41 53 12/53  
    b   64 82 18/82   97 84 13/97  
    c 0 9 1 0 27 1
    d   33 74 41/74   88 97 9/97  
    e 83 94 11/94 99 51 48/51
    f 27 0 1 09 0 1
    verschil c-f = 0,600361504
    overeenkomst = 1 - verschil = 0,399638495


    verschil d,e
    knoop   d(d,knoop) d(e,knoop) rel verschil d en e   d(knoop,d) d(knoop,e) rel verschil c en f  
    a   95 16 79/95   59 26 33/59  
    b   2 93 91/93   93 23 70/93  
    c 88 99 11/99 33 83 50/83
    d   0 37 1   0 41 1  
    e 41 0 1 37 0 1
    f 97 51 46/97 74 94 20/94
    verschil d-e = 0,71021644
    overeenkomst = 1 - verschil = 0,289783559


    verschil d,f
    knoop   d(d,knoop) d(f,knoop) rel verschil d en f   d(knoop,d) d(knoop,f) rel verschil c en f  
    a   95 5 90/95   59 53 6/59  
    b   2 82 80/82   93 84 9/93  
    c 88 9 79/88 33 27 6/33
    d   0 74 1   0 97 1  
    e 41 94 53/94 37 51 14/51
    f 97 0 1 74 0 1
    verschil d-f = 0,751245174
    overeenkomst = 1 - verschil = 0,248754826


    verschil e,f
    knoop   d(e,knoop) d(f,knoop) rel verschil d en f   d(knoop,e) d(knoop,f) rel verschil c en f  
    a   16 5 11/16   26 53 27/53  
    b   93 82 11/93   23 84 61/84  
    c 99 9 90/99 83 27 56/83
    d   37 74 37/74   41 97 56/97  
    e 0 94 1 0 51 1
    f 51 0 1 94 0 1
    verschil e-f = 0,725209441
    overeenkomst = 1 - verschil = 0,274790558



  • 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   1 0,310 0,441 0,399 0,233
    c   1 0,300 0,299 0,400
    d       1 0,290 0,249
    e       1 0,275
    f       1



  • insertiewaarden tabellen

  • insertiewaarde 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
    insertiewaarde knoop b:
      a b c d e f
    a x x 87 65 28 62
    b x x x x x x
    c 60 x x 124 4 121
    d -35 x 11 x -16 -11
    e 135 x 91 149 x 126
    f 135 x 170 101 72 x
    insertiewaarde knoop c:
      a b c d e f
    a x 74 x 15 98 15
    b 101 x x 37 157 40
    c x x x x x x
    d 55 150 x x 130 18
    e 145 70 x 95 x 75
    f 66 72 x -32 -2 x
    insertiewaarde knoop d:
      a b c d e f
    a x 30 106 x 74 103
    b 130 x 84 x 111 106
    c 66 -29 x x -9 103
    d x x x x x x
    e 116 -54 26 x x 83
    f 164 -6 153 x 21 x
    insertiewaarde knoop e:
      a b c d e f
    a x 88 84 4 x -2
    b -19 x 25 -33 x -10
    c 37 112 x 87 x 107
    d -38 132 52 x x -5
    e x x x x x x
    f 105 105 184 57 x x
    insertiewaarde knoop f:
      a b c d e f
    a x 104 21 68 121 x
    b 31 x -4 65 155 x
    c -30 45 x 68 38 x
    d 7 177 18 x 150 x
    e 40 40 -39 88 x x
    f x x x x x x


  • branch-and-bound
  • Begin met 2 x branchen; als begin-knoop neem ik a.
    Dat houdt in dat ik 5 x 4 matrices moet onderzoeken
    De + is een pad dat gekozen is
    De - is een pad dat uitvalt t.g.v. deze keuze
    De ! geeft een tegenspraak aan: de insertiewaarde van het laatst toegevoegde punt is hoger dan mogelijk gegeven een bestaand pad. In rood is aangegeven welke paden uitvallen op basis van de insertietabel (i.e. de laatst ingesloten knoop)

    1) a-b-c
      a b c d e f
    a - + - - - -
    b - - + - - -
    c -- - -   --  
    d -- - -- - -- --
    e   -     -  
    f   -     -- -
    insertiewaarde b = 87
    a-b-c valt uit, omdat geen enkele knoop meer met e kan verbinden.
    a-b-c valt uit, omdat d met geen enkele knoop meer kan verbinden

    2) a-b-d
      a b c d e f
    a - + - - - -
    b - - - + - -
    c -- - - - --  
    d -- - -- - -- --
    e   -   - -  
    f   -   -   -
    insertiewaarde b = 65
    a-b-d valt uit, omdat d met geen enkele knoop meer kan verbinden

    3) a-b-e
      a b c d e f
    a - + - - - -
    b - - - - + -
    c   - -   -  
    d -- - -- - - --
    e   -     -  
    f   -     - -
    insertiewaarde b = 28
    a-b-e valt uit, omdat d met geen enkele knoop meer kan verbinden

    4)a-b-f
    insertiewaarde b = 62
    a-b-f valt uit omdat d met geen enkele knoop meer kan verbinden

    5) a-c-b
      a b c d e f
    a - - + - - -
    b   - - --   --
    c - + - - - -
    d -- - - -   --
    e -- - -   -  
    f -- - - -- -- -
    insertiewaarde c = 74
    a-c-b valt uit, omdat f met geen enkele knoop meer kan verbinden

    6) a-c-d
      a b c d e f
    a - - + - - -
    b   - - -    
    c - - - + - -
    d     - -    
    e     - - -  
    f     - - -- -
    insertiewaarde c = 15
    a-c-d mag door naar de volgende ronde

    7) a-c-e insertiewaarde c = 98 a-c-e valt uit omdat f met geen enkele knoop meer kan verbinden

    8) a-c-f insertiewaarde c = 15 a-c-f mag door naar de volgende ronde

    9) a-d-b
      a b c d e f
    a - - - + - -
    b   -   -    
    c   - - - --  
    d - + - - - -
    e   - -- - -  
    f   -   - -- -
    insertiewaarde d = 30
    a-d-b mag door naar de volgende ronde, de lijn b-e is verplicht

    10) a-d-c
      a b c d e f
    a - - - + - -
    b   - - -    
    c -- -- - - -- --
    d - - + - - -
    e   - - - - -
    f   - - - - -
    insertiewaarde d = 106
    a-d-c valt uit omdat knoop c nergens meer mee verbonden kan worden

    11) a-d-e
      a b c d e f
    a - - - + - -
    b   -   - -  
    c -- -- - - -  
    d       - +  
    e   -- -- - -  
    f   --   - - -
    insertiewaarde d = 74
    a-d-e mag door naar de volgende ronde, c-f is verplicht, e-f is verplicht (strijdig)

    12) a-d-f
      a b c d e f
    a - - - + - -
    b   - -- -   -
    c -- -- - - -- -
    d - - - - - +
    e   -- -- - - -
    f   --   - -- -
    insertiewaarde d = 103
    a-d-f valt uit omdat knoop c nergens meer mee kan verbinden
    a-d-f valt uit omdat knoop b nergens meer mee verbonden kan worden

    13) a-e-b
      a b c d e f
    a - - - - + -
    b -- - -- -- - --
    c --   - -- -  
    d --   -- - - --
    e - + - - - -
    f       -- - -
    insertiewaarde e = 88
    a-e-b valt uit omdat knoop b nergens meer mee kan verbinden
    a-e-b valt uit omdat knoop d nergens meer mee verbonden kan worden


    14) a-e-c insertiewaarde e = 84
    a-e-c valt uit omdat knoop b nergens meer mee kan verbinden

    15) a-e-d
      a b c d e f
    a - - - - + -
    b -- -   -- - --
    c     - - -  
    d --     - - --
    e - - - + - -
    f       - - -
    insertiewaarde e = 4
    a-e-d mag door naar de volgende ronde, c-f is verplicht, b-c is verplicht


    16) a-e-f
      a b c d e f
    a - - - - + -
    b -- -   -- - -
    c     -   - -
    d --     - - -
    e - - - - - +
    f         - -
    insertiewaarde e = -2
    a-e-f mag door naar de volgende ronde, b-c is verplicht


    17) a-f-b
      a b c d e f
    a - - - - - +
    b -- - -- --   -
    c -- - - -- -- -
    d -- - -- -   -
    e -- - -- -- - -
    f - + - - - -
    insertiewaarde f = 104
    a-f-b valt uit


    18) a-f-c
      a b c d e f
    a - - - - - +
    b   - -     -
    c --   -     -
    d --   - -   -
    e     -   - -
    f - - + - - -
    insertiewaarde f = 21
    a-f-c mag door naar de volgende ronde


    19) a-f-d
      a b c d e f
    a - - - - - +
    b -- - -- -   -
    c -- -- - - -- -
    d --   -- -   -
    e -- -- -- - - -
    f - - - + - -
    insertiewaarde f = 68
    a-f-d valt uit


    20) a-f-e
      a b c d e f
    a - - - - - +
    b -- - -- -- - -
    c -- -- - -- - -
    d --   -- - - -
    e -- -- -- -- - -
    f - - - - + -
    insertiewaarde f = 121
    a-f-e valt uit


    blijft over na 1ste ronde branch-and-bound:
    a-c-d (no 6)
    a-c-f (no 8)
    a-d-b (no 9)
    a-d-e (no 11)
    a-e-d (no 15)
    a-e-f (no 16)
    a-f-c (no 18)
    i.e. 7 van de 20 gaan door voor de volgende ronde b&b, 13 zijn er uitgevallen. De resterende 7 hebben serieuze beperkingen bij het verder branchen.

    2de ronde

    6,1) a-c-d-b
      a b c d e f
    a - - + - - -
    b   - - -    
    c - - - + - -
    d - + - - - -
    e   - - - -  
    f   - - - -- -
    insertiewaarde d = -29
    mag door

    6,2) a-c-d-e
      a b c d e f
    a - - + - - -
    b   - - - -  
    c - -- - + - -
    d - - - - + -
    e   -- - - -  
    f     - - -- -
    insertiewaarde d = -9
    mag door, f-b verplicht, e-f is verplicht (want e-a sluit kort)
    oplossing: a-c-d-e-f-b-a, 41+33+41+51+82+58=306

    6,3) a-c-d-f
      a b c d e f
    a - - + - - -
    b   - - -   -
    c -- -- - + -- -
    d - - - - - +
    e   -- - - - --
    f   -- - - -- -
    insertiewaarde d = 103
    valt uit, geen pad naar b



    8,1) a-c-f-b
      a b c d e f
    a - - +! - - -
    b -- - -     -
    c - - - - - +
    d -- - - -   -
    e   - -   - -
    f - + - -- -- -
    insertiewaarde f = 45
    strijdig: verbetering mogelijk door f te plaatsen tussen a en c

    9,1) a-d-b-e
      a b c d e f
    a - - - + - -
    b - - - - + -
    c   - - - --  
    d - + - - - -
    e   - -- - -  
    f   -   - -- -
    insertiewaarde b = -16
    mag door, f-c is verplicht

    11,1) a-d-e-f
      a b c d e f
    a - - - + - -
    b -- -   - - -
    c -- -- - - - -
    d --     - + -
    e - -- -- - - +
    f   --   - - -
    insertiewaarde e = -5
    a-d-e-f  valt uit

    15,1) a-e-d-b
      a b c d e f
    a - - - - + -
    b -- -   -- - --
    c   - - - -  
    d -- + - - - --
    e - - - + - -
    f   -   - - -
    insertiewaarde d = -54
    a-e-d-b mag door naar de volgende ronde, c-f is verplicht, b-c is verplicht
    weg is compleet: a-e-d-b-c-f-a; totale lengte: 26+37+2+97+27+5 = 194

    15,2) a-e-d-c
      a b c d e f
    a - - - - + -
    b -- - - -- - --
    c     - - -  
    d -- - + - - --
    e - - - + - -
    f     - - - -
    insertiewaarde d = 26
    a-e-d-c valt uit, omdat geen enkel pad naar knoop b leidt


    16,1) a-e-f-b
      a b c d e f
    a - - - - + -
    b -- - -- -- - -
    c -- - -   - -
    d -- -   - - -
    e - - - - - +
    f - + - - - -
    insertiewaarde f = 40
    a-e-f-b valt uit, geen pad vanaf b, geen pad naar a


    16,2) a-e-f-c
      a b c d e f
    a - - - - + -
    b -- - - -- - -
    c     -   - -
    d --   - - - -
    e - - - - - +
    f - - + - - -
    insertiewaarde f = -39
    a-e-f-c valt uit, geen pad vanaf b


    16,3) a-e-f-d
      a b c d e f
    a - - - - + -
    b -- - -- -- - -
    c -- -- - - - -
    d --   -- - - -
    e - - - - - +
    f - - - + - -
    insertiewaarde f = 88
    a-e-f-d valt uit,  geen pad vanaf b, geen pad naar a, geen pad naar c


    18,1) a-f-c-b
      a b c d e f
    a - - - - - +!
    b   - - --   -
    c -- + - - - -
    d -- - - -   -
    e   - -   - -
    f - - + - - -
    insertiewaarde c = 72
    a-f-c-b valt uit want strijdig


    18,2) a-f-c-d
      a b c d e f
    a - - - - - +
    b   - - -   -
    c -- - - + - -
    d --   - -   -
    e     - - - -
    f - - + - - -
    insertiewaarde c = -32
    a-f-c-d mag door naar de volgende ronde


    18,3) a-f-c-e
      a b c d e f
    a - - - - - +
    b   - -   - -
    c -- - - - + -
    d --   - - - -
    e     -   - -
    f - - + - - -
    insertiewaarde c = -2
    a-f-c-e mag door naar de volgende ronde, d-b verplicht


    Na 2 keer branchen heb ik twee keer een mogelijke oplossing (6,2 en 15,1 resp 306, 194)
    Om verder te branchen heb ik nog
    a-c-d-b (6,1)
    a-d-b-e (9,1)
    a-f-c-d (18,2)
    a-f-c-e (18,3)
    Nog 4 stuks, is minder dan de 7 waarmee ik de vorige ronde in ging. Mijn boom wordt dus smaller. Bovendien zijn er aan het vervolg weer meer beperkingen gesteld, in de vorm van paden die verboden zijn. Nb: met alleen branchen had ik nu 5x4x3=60 mogelijke oplossingen moeten branchen.

    3de ronde

    6,1,1) a-c-d-b-e
      a b c d e f
    a - - + - - -
    b - - - - + -
    c - - - + -  
    d - + - - - -
    e   - - - -  
    f   - - - -- -
    insertiewaarde b = -16
    e-f is verplicht oplossing: a-c-d-b-e-f-a, 41+33+2+23+51+5=155

    6,1,2) a-c-d-b-f
      a b c d e f
    a - - + - - -
    b - - - - - +
    c - - - + - -
    d - + - - - -
    e - - - - - -
    f - - - - -- -
    insertiewaarde b = 97
    valt uit

    9,1,1) a-d-b-e-f
      a b c d e f
    a - - - + - -
    b - - - - + -
    c   - - - -- -
    d - + - - - -
    e - - -- - - +
    f   -   - -- -
    insertiewaarde e = -10
    f-c is verplicht
    oplossing: a-d-b-e-f-c-a, 59+2+23+51+9+62=206

    9,1,2) a-d-b-e-a
    valt uit want sluit kort

    18,2,1) a-f-c-d-b
      a b c d e f
    a - - - - - +
    b   - - -   -
    c -- - - + - -
    d -- + - - - -
    e   - - - - -
    f - - + - - -
    insertiewaarde d = -29
    a-f-c-d-b mag door naar de volgende ronde
    b-a sluit kort, dus verboden
    oplossing: a-f-c-d-b-e-a; 53+9+33+2+23+16=136

    18,2,2) a-f-c-d-e
      a b c d e f
    a - - - - - +
    b -- - - - - -
    c -- - - + - -
    d -- - - - + -
    e --   - - - -
    f - - + - - -
    insertiewaarde d = 83
    valt uit, geen pad naar a


    18,3,1) a-f-c-e-d
      a b c d e f
    a - - - - - +
    b -- - - - - -
    c -- - - - + -
    d --   - - - -
    e - - - + - -
    f - - + - - -
    insertiewaarde c = 87
    valt uit, geen pad naar a


    18,3,2) a-f-c-e-d
    valt uit, want b-d verplicht


    ergo:
    De oplossingen die naar voren komen zijn:
    a-c-d-e-f-b-a, 306
    a-e-d-b-c-f-a; 194
    a-c-d-b-e-f-a, 155
    a-d-b-e-f-c-a, 206
    a-f-c-d-b-e-a; 136
    De laatste is met zekerheid het kortste pad.

Bert's werk