Главная

Эксперимент

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

Карта

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



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


Точный алгоритм: интегральная статистика
РазмерГрафовПогрешность, %Падение β, раз
СредняяMAXСредняяMAX
3-97001.281.66
10-9921003.326.65
100-999880.070.727.4025.65
1000-99991460.731.8427.28197.91
10000-99999702.795.95109.90684.60
100000-999999352.678.74593.742351.81
1000000-9999999221.3710.141686.2959274.45
10000000-9999999953.1615.78573.031998.62
Более 100000000100167.45167.45
Итого3951.1315.78370.819274.45

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

ГрафУзловЛучшийСтартТочный%β
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
d65748912232159490640.314.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
pbd98427971593728160.685.66
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.0100023360648533805583235395590.7722.68
e1k.1100022985695505954062232037370.9521.80
e1k.2100023023351518385627232428240.9522.30
e1k.3100023143748524387797232539480.4822.55
e1k.4100022698717521108150228247130.5622.83
e1k.5100023192391528202745233929130.8622.33
e1k.6100023349803520922721234647290.4922.20
e1k.7100022879091517579641229366810.2522.57
e1k.8100023025754532394322232276640.8822.92
e1k.9100023356256516236328234154690.2822.25
pr10022590453494032596590.241.35
u10602240942601742253480.561.15
xit1083355819330355805.43
vm108423929753507422397750.2022.32
c11111635193579857163519021.89
pcb117356892123837571620.472.17
r12341292163314111129216025.65
d129150801150852512480.882.94
rl130425294832316942539810.4112.72
rl132327019930881902717650.5811.36
dka137646664225146930.589.00
nrw137956638712343567790.2512.55
dca138950855816351100.4911.38
fl140020127172735202290.518.54
u14321529701830701534210.291.19
dja143652573460253040.896.52
icw148344165154644550.8811.57
fra148842641912643040.944.44
fl15772224951304224050.702.29
rbv158353873782654380.956.96
rby159955333598455850.946.44
fnb161549562927549870.635.87
rw1621260511011974261550.4038.69
rat_all16471201123730412011019.76
d165562128206087627751.043.28
vm1748336556100053423383050.5229.57
djc178561155569861740.969.02
u18175720171460578221.091.24
rl188931653666012803191420.8220.68
dcc191163964714564661.097.29
dkd197364212645864830.974.08
mu1979868911080660871610.3112.40
djb203661977477262601.0211.94
dcb208666006670966791.209.99
d210380450141310804660.021.76
bva214463044255863781.176.67
u21526425381704649941.151.26
xqc217568305528669061.118.01
bck221767645128268290.967.51
c22221546467080822154646045.79
xpr230872196949272770.809.55
u23192342562814962347650.221.20
ley2323835220292584020.6024.15
r23451750856351933175085036.28
dea2382801719288981041.0923.80
pr239237803237803237803201
rbw248177247774078201.249.94
pds256676437264077060.829.43
mlt2597807110429681701.2312.77
vm_all27354476599933790447659022.19
bch276282348215983351.239.86
irw2802842311607585111.0413.64
lsm285480148624180951.0110.65
dbj292410128114170102471.1711.14
pr_all29654985185853527498518011.74
xva299384928843985871.1210.30
pcb30381376942957931387800.792.13
pia305682586383183611.257.63
dke309710539108254106170.7410.20
lsn311991149899492361.3410.72
lta3140951712423396411.3012.89
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.23162403033941652704439406275950.8040.68
e3k.33162405896591685070603409364680.8541.16
e3k.43162407572091642988934410879500.8139.99
fdp325610008142986101261.1814.12
beg3293977214672298470.7714.90
c333335862514121229358625039.38
dhb338611137156446112410.9313.92
r34562111189265882211118043.89
nu3496961323862779972971.2139.70
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_all46531766123333785176612018.88
ca466312903194789298813020480.9136.78
xqd49661531671602155181.324.61
fl_all498035658160578635658045.03
fqm50871302950999131991.303.86
c555596467255462586964672057.49
fea555715445313943156201.1320.10
r567826893515024210268935055.87
rl5915565530101450255742121.5417.67
rl593455604598613245656331.7217.43
tz611739471870185343995471.2217.57
c6666692250961647116922500138.92
r678929399117996086293991061.21
xsc688021535272748218611.5112.48
eg714617238730971651742681.0917.77
bnd716821834375208222231.7816.88
pla739723260728194900160234124410.658.32
lap745419535378452197851.2819.13
ym766323831467286432416981.4227.84
c77779568121893614619568120197.91
pm80791165498613224116549073.90
ida819722338547333227431.8124.07
ei824620617180324942091461.4438.41
u_all83545334856826057533485012.80
c888892900689286287929006096.11
ar9152837479582666168488831.3668.64
dga969827724672530282351.8423.82
ja984749192457532844984491.3311.54
r987635529026106765355290073.48
gr988230089928431953046241.249.33
kz997610618825547193110783511.5551.44
c9999124371317959364912437130144.40
c10k.010000330010345198212329336310701.91154.57
c10k.110000331862484829723279339951532.44142.07
c10k.210000331554245013566837336340311.44149.06
e10k.010000718658265207875979733109102.0171.04
e10k.110000720316305203408565734178741.9270.87
e10k.210000718224835236195601733382502.1171.40
xmc1015028387422853292302.9714.47
fi1063952052757163485317622.1610.75
c111119565951788163419565950186.93
rl11849923288866212779394341.7592.21
r1234539837832690992398378082.06
usa13509199828591590833042204058042.1277.96
xvb1358437084575904381542.8915.09
brd14051469385235875944789882.0549.24
mo1418542737759419304361492.0513.62
xrb14233454621469057467532.8431.42
ho14473177105158603701814952.4887.39
d15112157308411231076516060352.0969.93
it1686255731574043395708062.4212.97
xia1692852850648013544202.9711.91
pjh1784548094750115495312.9915.14
d18512645238345096426593972.1952.34
frh19289557981236067574032.8821.53
fnc19402592881785519610082.9029.27
r2072692202326582535671192202326063.18
ido21215635191474658656683.3822.46
fma21553665271279403686443.1818.64
c22222116804630676780211680460262.63
vm2277556928833240895843492.655.69
lsb22777609771439245627472.9022.94
r23456552425617681335524250111.81
xrh24104692941118257716273.3715.61
rl_all247321617278348453791617278021.55
sw2497885559792085208809822.9710.45
bbz25234693381950194716103.2827.23
irx28268726071186328748773.1315.84
fyg28534785652399803811803.3329.56
icx28698780902595413818704.8431.70
boa28924796243257019836315.0338.95
ird29514803592140377842104.7925.42
pbh30440883133132551931015.4233.65
c31k.0316235954539016648546397630870295.95263.90
c31k.1316235929326616814542248627391695.81268.01
e31k.031623127282138165161612881341066465.36123.16
e31k.131623127452384164141455021347532095.73121.81
xib328929676742584911017345.1341.86
fry332039724044289291003473.2044.14
c33333117980641778649311798060354.11
bm33708959304669303810066054.936.65
pla3381066048945229014696686504943.943.34
r34567690157910603276901570131.94
bby346569917228079771047855.6626.80
pba3847810832726081261146395.8322.75
ics3960310682144201571131075.8839.08
rbz4374812519155869881325015.8442.17
c44444141986652242530814198660367.94
r456787937141204107077937140151.71
fht4760812512457947051317115.2644.00
fna5205714780245154551565775.9428.84
c55555137190059240342413719000431.81
bna5676915810152690221675115.9531.45
r567898883621495523088883620168.35
dan5929616539768881461751745.9139.32
c666666468784286890082764687840443.50
ch71009456656330009823548067285.2662.43
c777775551193376695675355511930678.59
pla859001423660915008396041478855133.883.39
c888884809954329294002048099540684.60
r98765117165826029761611716580222.16
c999996208228344454739762082280554.84
c100k.0100000104617752514602812091126380197.67456.86
c100k.1100000105390777511796052171131025607.32452.51
e100k.0100000225784127522113490082399793096.29217.57
e100k.1100000225654639522138047022402310416.46217.35
monalisa100000575719199178477859287552.98167.28
sra10481425136137205632694967.2113.81
c1111115636147435571384656361470772.82
usa11547565677382139209226567738032.57
vangogh1200006543610123181960667494273.15182.51
r123456131040632545867813104060248.36
pla_all1271072360192722965653025236019272012.57
venus1400006810665137135944570212713.09195.31
pareja1600007619953167339519378677633.25212.69
courbet1800007888733186834793081551363.38229.10
earring2000008171677218860850584664213.61258.50
c2222228131895654567682181318950804.94
r234567180430361773812118043030342.37
ara23802557883078291736247047.9312.53
tsplib23869827086945512567695905270869455046.40
cities284228148561602755954408148561600185.51
c316k.03162281868708391649652483312031977878.74811.85
e316k.03162284013012061648130413934280912776.68385.00
c3333336940090655726780869400900944.84
r345678218806791013055021880670415.95
c444444988726611608654856988726601174.10
r4567892514086120369278125140860478.78
lra498378216824317591673523378267.8275.25
c555555889067619262824969889067602166.63
c66666611487302175061922231148730201523.96
lrb744710161142017002419717381507.8697.82
c777777865926419121063825865926402208.16
c88888811412677257182271391141267702253.48
pict_all899159147986932376531478147986930160.59
r9876543878025260261541838780250671.12
c99999912470398293280289731247039802351.81
c1m.0100000041807591652056283648841807591601245.14
e1m.0100000071318768852117017910778482468510.04664.06
c111111151183165983792591345118316501922.10
r12345674145885325318613841458850784.68
small_all1611561794220097002714579422000122.14
world19047117512218268404794416459182615547039.97489.97
world_1904711564452345020564409274.45
world__1904711104769164046776894104769160386.26
vlsi_all1966088554259764106465855425970115.66
c2222222495083681795876045544950836803627.42
r23456786197280618196580361972800997.53
c3m.03162278661587283164823239643366158728302491.33
e3m.0316227812673182511648069992661139582573010.141180.71
c3333333597978713164758422605979787105292.43
r345678981139689108484470811396801122.57
c4444444701823723697043569537018237205267.77
c55555558721095735946682112658721095730681.87
c6666666151356847661118465135215135684760403.80
c77777772448978715100208690355724489787150409.19
c8888888272564397262032631861527256439720227.59
r987654341868921926016609307418689219062.14
c9999999285813736094225935529028581373600329.68
c10m.01000000089869992985520803535240789869992985057.95
e10m.01000000022530881625213652267289260862770015.781998.62
r123456786834382932519838109683438290475.83
r23456789241006977617799146712410069770256.34
r9876543234045375742601531910583404537574076.41
r123456789194207430232520587629119420743020167.45
04.11.2019 12:05
 
`