ДОПОЛНЕНИЕ МЕТОДА ВЕТВЕЙ И ГРАНИЦ ДЛЯ РЕШЕНИЯ ЗАДАЧИ КОММИВОЯЖЕРА НА ПЛОСКОСТИ

  • Published on
    05-Apr-2017

  • View
    217

  • Download
    3

Embed Size (px)

Transcript

  • ISSN 1812-9498. . 2007. 1 (36)

    160

    381.31.00

    . .

    (), 1934 .,

    . , -. , - . NP- . .

    , - , N 1 -

    . . - , , - . - N [1]. - , . . ( ) - , , -, .

    , . , . . , , , , -, . [2].

    ():

    -, . . .

    , ( ). . - , , , - ),( EVGp = , NV = , V , . , ( ), . - , , .

    , .

    N 33 , - 0,75 0,1. - N, . - . 1.

  • 161

    1

    N ,

    ,

    3 2 2

    4 14 14

    5 0,41 0,93 37 31 0,44

    6 0,45 1,39 109 66 0,32

    7 2,81 3,33 296 143 0,84

    8 9,51 5,24 785 244 1,81

    9 57,84 23,18 2 370 526 2,49

    10 228,21 83,39 4 328 898 2,73

    11 1 151,13 295,81 8 827 1 328 3,89

    12 3 691,66 856,26 10 496 1 901 4,31

    13 25 653,01 4 161,39 28 104 2 210 5,75

    14 100 390,54 14 507,22 44 087 4 824 6,92

    , , -

    . , - . . 1 - .

    1 000 N = 310 ( - N < 11) .

    012345678

    3 4 5 6 7 8 9 10 11 12 13 14

    N

    . 1.

    . 1, -

    . (N < 7) - , . . -, .

    . 2. , . . . , . . .

  • ISSN 1812-9498. . 2007. 1 (36)

    162

    0

    10 000

    20 000

    30 000

    40 000

    50 000

    60 000

    70 000

    80 000

    90 000

    100 000

    3 4 5 6 7 8 9 10 11 12 13 14

    N

    t,

    c

    . 2. . 2, -

    , . . t = b0 e(b1 N). b0 b1 -

    . t(N) = 0,0001 e(1,4545 N), -

    : t(N) = 0,0015 e(1,1155 N). -

    N 50 (. 3).

    . 3. N

    , -

    , b0 .

    2

    2

    2

  • 163

    () ,

    , . ,

    , . , .

    (, -) . - .

    1. . . - -. : . . . . . 5. , 1995. . 132133.

    2. . . 2- . .; .: , 2004. 366 .

    1.10.2006

    SUPPLEMENT OF THE METHOD OF BRANCHES AND BORDERS FOR THE DECISION OF A TASK OF A TRAVELLING SALESMAN

    ON A PLANE

    . .

    In the given work the method of the decision of a task of the direct-sales rep-resentative (ZK) on a plane on the basis of supplement of the method of branches and borders with the condition of disjointness is submitted. The heuristic assump-tion is suggested: "The optimum route of ZK on a plane in the complete graph al-ways has a condition of disjointness, that is the route can be lead so, that for the next cities the ribs of graph will not have crossings". To confirm the hypothesis more exactly about 1 000 comparisons by a method of branches and borders and modified algorithm for N = 310 were carried out, that is more than 8 thousand tests, the exact result is received with the modified algorithm. The results have shown, that additional restriction "disjointness" for ZK on a plane of the method of branches and borders essentially reduces time of searching. Thus the given modifi-cation keeps the property of paralleling of algorithm of the method of branches and borders, which is a way of reduction of time of calculations.

Recommended

View more >