Главная

Эксперимент

Главная
Комми
Алгоритм
Быстрый
Средний
Случайный
Точный
Новый
Эксперимент

Карта

Результаты экспериментов



Результаты экспериментов для каждого набора графов, сгруппированных по числу узлов, представлены в таблице, при этом падение бета-границы есть отношение стартовой длины тура к финальной, а погрешность считается относительно best-known решения. В случае, когда такое решение неизвестно, я нагло беру в качестве best-known лучший тур, найденный моими алгоритмами. Это несколько занижает фактическую погрешность, но, во-первых, когда будет доказана оптимальность тура, эта ошибка снимается, во-вторых, если считать погрешность по альфа-границе, ошибка получается куда более грубой, да и альфа-границу для крупных графов получить не так-то просто! А бета-граница всегда под рукой.

Точный алгоритм: интегральная статистика
РазмерГрафовУзлов
(среднее)
Погрешность, %Падение β, раз
СредняяMAXСредняяMAX
3-976001.281.66
10-992156003.326.65
100-999883980.070.727.4025.65
1000-999914633850.731.8227.28197.96
10000-9999970320552.305.37111.39713.90
100000-999999353523192.678.74593.742351.81
1000000-99999992238422681.3710.141686.2959274.45
10000000-999999995309135793.1615.78573.031998.62
100000000 и более112345678900167.45167.45
Итого3959561011.1315.78370.819274.45


Если длина лучшего нам неизвестна (найдена нами самостоятельно), она и процент погрешности, посчитанной относительно неё, выделяются красным. Имена графов, у которых расстояния считаются по EUC_2D, даны цветом обычного текста, если длина рассчитывается по CEIL_2D, имена выделены цианом, для графов с GEO-координатами - зелёным, данные незавершённых расчетов выделены малиновым.

229,68266913353351015277568619979
ГрафУзловЛучшийСтартТочный%β
r382988298829801
r411346130931134601.15
r511370131171137001.15
r611581155871158101.35
r711976156681197601.31
r812044164701204401.37
r913606225881360601.66
r1213838281791383802.04
burma1433234562332301.37
ulysses1668599665685901.41
ulysses22701312198701301.74
r2319713518981971302.63
wi2927603522842760301.89
r3423188804692318803.47
r45274401041872744003.80
eil51426130842603.07
berlin52754222205754202.94
r56302591268833025904.19
r67335281590133352804.74
st70675341067505.05
eil76538196953803.66
pr7610815915078110815901.39
r78346431851033464305.34
dj89665632266665604.85
r89357702261833577006.32
gr9655209810075520901.47
r98370532465663705306.65
rat9912112124121101.75
kroA100212821913872128208.99
kroB100221411571902214107.10
kroC100207491834662074908.84
kroD100212941709902129408.03
kroE100220681883512206808.54
rd100791050560791006.39
eil101629206262903.28
lin10514379364801437902.54
pr10744303627524430301.42
c111256091790272560906.99
r123413253060834132507.41
pr12459030989415903001.68
bier12711828239398911828203.33
ch130611047797611007.82
xqf131564138356402.45
pr136967722870289677202.97
gr13769853971136985301.39
pr14458537935265853701.60
ch150652852814652808.09
kroA1502652428784426524010.85
kroB1502613027323926130010.46
pr152736821609807368202.18
u15942080433814208001.03
qa194935239561935204.23
rat19523234030232301.73
d19815780224981578001.43
kroA2002936837393829368012.73
kroB2002943732745629437011.12
gr20240160581504016001.45
eil_all219823451382305.48
c222374663393083746609.06
ts22512664327654012664302.18
tsp225391610349391602.64
pr226803691104178036901.37
gr22913460217981913460201.34
r2345705462169857054010.90
xqg23710192946101902.89
gil2622378262982378011.06
pr26449135779774913501.59
a28025792808257901.09
ch_all280880873729880808.37
pr29948191835064819101.73
lin318420291198724202902.85
c3331521571719706152157011.30
pma34313683111136802.27
r3456897390563868973013.13
pka37913322891133202.17
bcl380162110012162106.18
pbl39512815445128104.25
rd4001528121555815281014.11
pbk41113435917134304.41
fl41711861554451186104.67
pbn42313656811136504.99
gr4311714142330641715870.101.36
pbm4361443738914500.495.10
pr43910721727064610721702.52
pcb44250778221440509690.384.34
c4441652032205950165203013.35
r45679604121330279604015.24
d49335002113549350900.253.24
kro_all5004606351419946063011.16
rd_all5001689119496316891011.54
ali53520233933700802027360.2016.62
c5551881872629399188187013.97
r56788128153496088128017.42
u5743690540197369770.201.09
rat57567731293467830.151.91
p654346431077373464303.11
d65748912232159490600.304.73
xql66225131215325310.724.80
c6662102913158641210291015.02
gr6662943584237102954080.361.43
r67895663182926995663019.12
rbx711311518579311505.96
u72441910157485420560.353.74
uy73479114844742792350.1510.66
rbu73733141647433370.694.94
c7771823023347335182302018.36
rat78388067213488230.198.18
r7891041872125788104187020.40
dkg8133199320483199010.02
c8882212294863111221229021.98
zi92995345933844955330.209.78
lim96327891854028080.686.60
lu98011340262361113940.4823.03
pbd98427971593728060.325.68
r9871154492665995115449023.09
c9992209625668296220962025.65
c1k.0100011387430589478106114077900.1851.67
c1k.1100011376735471306789114164410.3541.28
c1k.2100010855033511230199108793820.2246.99
c1k.3100011886457588474536119162610.2549.38
c1k.4100011499958537304618115313350.2746.60
c1k.5100011394911430829153114520840.5037.62
c1k.6100010166701404674956101976950.3039.68
c1k.7100010664660414591854106864540.2038.80
c1k.8100011605723556008650116332450.2447.79
c1k.9100010906997506407477109320160.2346.32
dsj100018659688557633042186858160.1429.84
e1k.0100023360648533805583235265170.7122.69
e1k.1100022985695505954062231594930.76
e1k.2100023023351518385627232160860.8422.33
e1k.3100023143748524387797232539480.4822.55
e1k.4100022698717521108150228247130.5622.83
e1k.5100023192391528202745233929130.8622.33
e1k.6100023349803520922721234607730.4822.20
e1k.7100022879091517579641229366810.2522.57
e1k.8100023025754532394322232276640.8822.92
e1k.9100023356256516236328234154690.2822.25
pr10022590453494032596590.241.35
u10602240942601742253480.561.15
xit1083355819330355805.43
vm108423929753507422397750.2022.32
c11111635183579857163518021.89
pcb117356892123837571620.472.17
r12341292163314111129216025.65
d129150801150852512480.882.94
rl130425294832316942539810.4112.72
rl132327019930881902717650.5811.36
dka137646664225146920.569.00
nrw137956638712343567790.2512.55
dca138950855816351100.4911.38
fl140020127172735202290.518.54
u14321529701830701534210.291.19
dja143652573460253040.896.52
icw148344165154644550.8811.57
fra148842641912643010.874.45
fl15772224951304224050.702.29
rbv158353873782654360.916.96
rby159955333598455790.836.45
fnb161549562927549870.635.87
rw1621260511011974261550.4038.69
rat_all16471200923730412009019.76
d165562128206087627040.933.29
vm1748336556100053423383050.5229.57
djc178561155569861740.969.02
u18175720171460576460.781.24
rl188931653666012803191420.8220.68
dcc191163964714564570.957.30
dkd197364212645864830.974.08
mu1979868911080660871610.3112.40
djb203661977477262410.7111.98
dcb208666006670966600.9110.02
d210380450141310804660.021.76
bva214463044255863640.956.69
u21526425381704647620.791.26
xqc217568305528668940.948.02
bck221767645128268250.907.51
c22221546467080822154646045.79
xpr230872196949272770.809.55
u23192342562814962347650.221.20
ley2323835220292584020.6024.16
r23451750856351933175085036.28
dea2382801719288980820.8123.87
pr239237803237803237803201
rbw248177247774077970.959.97
pds256676437264077060.829.43
mlt2597807110429681701.2312.77
vm_all27354476319933790447631022.19
bch276282348215983331.209.86
irw2802842311607585111.0413.64
lsm285480148624180951.0110.65
dbj292410128114170102471.1711.14
pr_all29654984955853527498495011.74
xva299384928843985871.1210.30
pcb30381376942957931387800.792.13
pia305682586383183611.257.63
dke309710539108254106170.7410.20
lsn311991149899492141.1010.74
lta3140951712423396221.1012.91
c3k.03162191982581622067766193406710.7483.87
c3k.13162190178051584613207191955530.9382.55
c3k.23162195475511829389381196473650.5193.11
c3k.33162191085081666159724191996780.4886.78
c3k.43162188640461612269078190158960.8084.79
e3k.03162406340811652867430409688830.8240.34
e3k.13162403152871673513928405710640.6341.25
e3k.23162403033941652704439406269110.8040.68
e3k.33162405896591685070603409364680.8541.16
e3k.43162407572091642988934410879500.8139.99
fdp325610008142986101261.1814.12
beg3293977214672298470.7714.90
c333335862514121229358625039.38
dhb338611137156446112410.9313.92
r34562111189265882211118043.89
nu3496961323862779971391.0539.77
fjs3649927242882493400.7345.91
fjr3672960141438396610.6242.89
dlb369410959110014111201.479.89
ltb37291182196077119841.388.02
fl379528772169398289110.485.86
xqe389111995133730121181.0311.04
xua393711239153424114171.5813.44
dkc39381250382431126741.376.50
dkf395412538147862127011.3011.64
bgb435512723149640128501.0011.65
bgd439613009351786131801.3126.69
frv44101071196729108591.388.91
c444470282941491458702829059.03
fnl446118256658723021840820.8331.90
bgf447513221274949133761.1720.56
r456724063612177068240636050.60
pcb_all46531765893333785176589018.88
ca466312903194789298813020480.9136.78
xqd49661531671602155181.324.61
fl_all498035658160578635658045.03
c3d499561176224115313611762039.42
fqm50871302950999131991.303.86
c555596457655462586964576057.50
fea555715445313943156201.1320.10
r567826892315024210268923055.87
rl5915565530101450255742121.5417.67
rl593455604598613245656331.7217.43
tz611739471870185343994981.2117.57
c6666692224961647116922240138.92
r678929382117996086293821061.25
xsc688021535272748218601.5112.48
eg714617238730971651742301.0717.78
bnd716821834375208222131.7416.89
pla739723260728194900160234086720.648.33
lap745419535378452197761.2319.14
ym766323831467286432416491.4027.84
c77779563191893614619563190198.01
pm80791165428613224116542073.91
ida819722338547333227421.8124.07
ei824620617180324942090591.4038.42
u_all83545333986826057533398012.80
c888892856989286287928569096.15
ar9152837479582666168485701.3268.66
dga969827724672530282191.7923.83
ja984749192457532844980871.2511.55
r987635515826106765355158073.50
gr988230089928431953045031.209.34
kz997610618825547193110778241.5051.47
c9999124318817959364912431880144.46
c10k.010000330010345198212329334490561.36155.41
c10k.110000331862484829723279335696041.16143.87
c10k.210000331554245013566837336143641.38149.15
e10k.010000718658265207875979731581501.8071.19
e10k.110000720316305203408565733593051.8470.93
e10k.210000718224835236195601731314441.8271.60
xmc1015028387422853289431.9614.61
fi1063952052757163485308031.9710.77
c111119555271788163419555270187.14
rl11849923288866212779380541.6092.34
r1234539785232690992397852082.17
usa13509199828591590833042203753891.9678.08
xvb1358437084575904380012.4715.15
brd14051469385235875944778641.8149.36
mo1418542737759419304354611.8913.65
xrb14233454621469057466562.6331.49
ho14473177105158603701812072.3287.53
d15112157308411231076516028281.8970.07
it1686255731574043395692972.1513.01
xia1692852850648013543142.7711.93
pjh1784548094750115494292.7815.18
d18512645238345096426580761.9952.44
frh19289557981236067573062.7121.57
fnc19402592881785519608542.6429.34
r2072692050138582535671192050138063.28
ido21215635191474658653212.8422.58
fma21553665271279403683992.8118.70
c22222116553330676780211655330263.20
vm2277556928833240895816122.165.72
lsb22777609771439245625472.5723.01
r23456550911617681335509110112.12
xrh24104692941118257713723.0015.67
rl_all247321608597348453791608597021.66
sw2497885559792085208767752.4810.50
bbz25234693381950194713532.9127.33
irx28268726071186328746532.8215.89
fyg28534785652399803808582.9229.68
icx28698780902595413804793.0632.25
boa28924796243257019823973.4839.53
ird29514803592140377828723.1325.83
pbh30440883133132551912943.3834.31
c31k.0316235954539016648546397611643452.72272.19
c31k.1316235929326616814542248612712923.34274.43
e31k.031623127282138165161612881320840243.77125.04
e31k.131623127452384164141455021323733933.86124.00
xib328929676742584911006514.0142.31
fry33203972404428929999132.7544.33
c33333117099541778649311709950356.78
bm3370895930466930389936743.586.74
pla3381066048945229014696678168642.683.38
r34567682427910603276824270133.44
bby346569917228079771033684.2327.16
pba3847810832726081261131444.4523.05
ics3960310682144201571115244.4039.63
rbz4374812519155869881314384.9942.51
c44444140771552242530814077150371.12
r456787839751204107077839750153.59
fht4760812512457947051305034.3044.40
c4d49995436004267619688343600420155.09
fna5205714780245154551549754.8529.14
c55555135258259240342413525820437.98
bna5676915810152690221658394.8931.77
r567898741751495523088741750171.08
dan5929616539768881461732024.7239.77
c666666359576286890082763595760451.12
ch71009456656330009823547537303.9863.20
c777775421107376695675354211070694.87
pla859001423660915008396041465990542.973.42
c888884585140329294002045851400718.18
r98765115285326029761611528530225.79
c999995946155344454739759461550579.29
c100k.0100000104617752514602812091105501285.67465.49
c100k.1100000105390777511796052171113122345.19459.78
e100k.0100000225784127522113490082359935864.52221.24
e100k.1100000225654639522138047022374238465.22219.92
monalisa100000575719199178477858901082.31168.38
sra10481425136137205632642315.1214.08
c1111115607363435571384656073630776.78
usa11547565014022139209226501402032.90
vangogh1200006543610123181960667115472.57183.54
r123456129478532545867812947850251.36
pla_all1271072330542532965653025233054253012.73
venus1400006810665137135944569817262.51196.42
pareja1600007619953167339519378217502.65213.94
courbet1800007888733186834793081344753.12229.68
earring2000008171677218860850584440133.33259.19
c2222227830480654567682178304800835.92
r234567178698161773812117869810345.69
ara23802557883078291736149406.2412.73
tsplib23869826878069712567695905268780697046.76
cities284228147840402755954408147840400186.41
c316k.03162281868708391649652483311996336616.83826.34
e316k.03162284013012061648130413934235798205.55389.10
c3333336799827655726780867998270964.33
r345678218438991013055021843890416.65
c444444978795611608654856978795601186.0
r4567892513912120369278125139120478.81
lra498378216824317591673523072006.4176.25
c5d4999952611360715391456427261136070589.40
c555555882376919262824969882376902183.1
c66666611356620175061922231135662001541.5
lrb744710161142017002419717207546.7898.81
c777777860233119121063825860233102222.8
c88888811403202257182271391140320202255.4
pict_all899159147985922376531478147985920160.59
r9876543794933260261541837949330685.81
c99999912219685293280289731221968502400.1
c1m.0100000036972993152056283648836972993101408.0
e1m.010000007131876885211701791077726553838.34674.52
c111111140029044983792591344002904402457.7
r12345674142229325318613841422290785.37
small_all1611561783818897002714578381880123.76
world19047117512218268404794416459182357483499.63491.51
world_1904711551052345020551009500.0
world__1904711103292954046776894103292950391.78
vlsi_all1966088546405164106465854640510117.32
c2222222494031271795876045544940312703635.1
r234567860592066181965803605920601020.3
c3m.03162278659904246164823239643365990424602497.7
e3m.031622781267318251164806999266113860659339.371189.0
c3333333580361413164758422605803614105453.1
r345678976341389108484470763413801193.1
c4444444683238353697043569536832383505411.1
c6d4999995970675461400036430389706754601437.3
c5555555756755315946682112657567553107858.1
c666666615197610561118465135215197610504021.6
c777777795341076100208690355795341076010510
c888888810294322262032631861510294322206025.9
r9876543147444114260166093071474441140176.45
c9999999944260449422593552909442604409978.8
c10m.010000000371003206705208035352407371003206700140.38
e10m.01000000022530881625213652267289247860681110.012103.5
r123456786632053132519838109663205310490.34
r23456789226519314617799146712265193140272.74
c7d4999999515037569334734673006913150375693303148.6
r98765432230021158826015319105823002115880113.10
r123456789187593316732520587629118759331670173.36
02.10.2022 11:54
 
`