Главная

Эксперимент

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

Карта

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



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


Точный алгоритм: интегральная статистика
РазмерГрафовПогрешность, %Падение β, раз
СредняяMAXСредняяMAX
3-97001.281.66
10-9921003.326.65
100-999880.131.127.3925.59
1000-99991461,524.2526.87192.60
Больше пока ничего не написано.
10000-99999?????
100000-999999?????
1000000-9999999?????
10000000-99999999?????
Более 100000000?????
Итого?????

Если длина лучшего нам неизвестна (найдена нами самостоятельно), она и процент погрешности, посчитанной относительно неё, выделяются красным. Имена графов, у которых расстояния считаются по 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
gr2291346021798191346160.011.34
r2345705462169857054010.90
xqg23710192946101902.89
gil2622378262982378011.06
pr26449135779774913501.59
a28025792808257901.09
ch_all280880873729880808.37
pr29948191835064819101.73
lin31842029119872420830.132.85
c3331521571719706152157011.30
pma34313683111136802.27
r3456897390563868973013.13
pka3791332289113330.082.17
bcl38016211001216270.376.15
pbl3951281544512820.084.25
rd40015281215558152850.0314.10
pbk41113435917134304.41
fl41711861554451186104.67
pbn4231365681113700.374.97
gr4311714142330641720210.351.35
pbm4361443738914500.495.10
pr43910721727064610721702.52
pcb44250778221440510690.574.34
c4441655062205950165506013.33
r45679604121330279604015.24
d49335002113549351230.353.23
kro_all5004606351419946063011.16
rd_all5001691119496316911011.53
ali53520233933700802027360.2016.62
c5551886052629399188605013.94
r56788128153496088128017.42
u5743690540197370540.401.08
rat57567731293468060.491.90
p65434643107737346510.023.11
d65748912232159491780.544.72
xql66225131215325360.924.79
c6662103273158641210327015.02
gr6662943584237102971870.961.43
r67895722182926995722019.11
rbx711311518579311505.96
u72441910157485420410.313.75
uy73479114844742792780.2110.66
rbu73733141647433440.914.93
c7771824803347335182480018.34
rat78388067213488420.418.16
r7891049252125788104925020.26
dkg8133199320483199010.02
c8882223534863111222353021.87
zi92995345933844955360.209.77
lim96327891854028120.826.59
lu98011340262361113940.4823.03
pbd98427971593728281.115.64
r9871158462665995115846023.01
c9992213715668296221371025.61
c1k.0100011387430589478106114125260.2251.65
c1k.1100011376735471306789114312230.4841.23
c1k.2100010855033511230199108961000.3846.92
c1k.3100011886457588474536119449850.4949.27
c1k.4100011499958537304618115313350.2746.60
c1k.5100011394911430829153114730860.6937.55
c1k.6100010166701404674956102152010.4839.61
c1k.7100010664660414591854106867400.2138.79
c1k.8100011605723556008650116337770.2447.79
c1k.9100010906997506407477109416130.3246.28
dsj100018659688557633042187097060.2729.80
e1k.0100023360648533805583235506970.8122.67
e1k.1100022985695505954062232634231.2121.75
e1k.2100023023351518385627232575451.0222.29
e1k.3100023143748524387797232672990.5322.54
e1k.4100022698717521108150228791000.7922.78
e1k.5100023192391528202745234681001.1922.51
e1k.6100023349803520922721234852540.5822.18
e1k.7100022879091517579641230304200.6622.47
e1k.8100023025754532394322232487160.9722.90
e1k.9100023356256516236328234585230.4422.01
pr10022590453494032597780.281.35
u10602240942601742255610.651.15
xit1083355819330355805.43
vm108423929753507422399380.2722.30
c11111643763579857164376021.78
pcb117356892123837572990.722.16
r12341293383314111129338025.62
d129150801150852511410.672.95
rl130425294832316942545500.6312.70
rl132327019930881902753971.9211.21
dka137646664225147551.918.89
nrw137956638712343570650.7512.48
dca138950855816351230.7511.35
fl140020127172735202290.518.54
u14321529701830701538170.551.19
dja143652573460253451.676.47
icw148344165154644901.6811.48
fra148842641912643231.384.42
fl15772224951304226381.752.27
rbv158353873782654721.586.91
rby159955333598456221.616.40
fnb161549562927550291.475.82
rw1621260511011974261550.4038.69
rat_all16471204623730412046019.70
d165562128206087631461.643.26
vm1748336556100053423387840.6629.53
djc178561155569861961.328.99
u18175720171460580571.501.23
rl188931653666012803191620.8320.68
dcc191163964714564881.447.27
dkd197364212645865061.324.07
mu1979868911080660873610.5412.37
djb203661977477262791.3211.91
dcb208666006670967111.689.94
d210380450141310819221.831.72
bva214463044255864081.656.64
u21526425381704655762.061.25
xqc217568305528669601.907.94
bck221767645128268841.777.45
c22221550127080822155012045.68
xpr230872196949273081.239.51
u23192342562814962347650.221.20
ley2323835220292584391.0424.05
r23451756806351933175680036.16
dea2382801719288981321.4323.72
pr239237803237803237803201
rbw248177247774078912.169.85
pds256676437264077671.629.35
mlt2597807110429682221.8712.68
vm_all27354500129933790450012022.07
bch276282348215983641.589.82
irw2802842311607585831.9013.52
lsm285480148624181681.9210.56
dbj292410128114170102711.4111.12
pr_all29654994825853527499482011.72
xva299384928843986421.7710.23
pcb30381376942957931394531.282.12
pia305682586383184302.087.57
dke309710539108254107652.1410.06
lsn311991149899492891.9210.65
lta3140951712423397212.1412.78
c3k.03162191982581622067766196272132.2382.64
c3k.13162190178051584613207194612382.3381.42
c3k.23162195475511829389381197667991.1292.55
c3k.33162191085081666159724194259361.6685.77
c3k.43162188640461612269078192610462.1083.71
e3k.03162406340811652867430411645181.3140.15
e3k.13162403152871673513928409207671.5040.90
e3k.23162403033941652704439407618851.1440.55
e3k.33162405896591685070603410805961.2141.02
e3k.43162407572091642988934413704611.5039.71
fdp325610008142986102442.3613.96
beg3293977214672299661.9914.72
c333336317914121229363179038.88
dhb338611137156446113421.8413.79
r34562122099265882212209043.66
nu3496961323862779983132.2739.29
fjs3649927242882494041.4245.60
fjr3672960141438397271.3142.60
dlb369410959110014111812.039.84
ltb37291182196077121142.487.93
fl379528772169398290020.805.84
xqe389111995133730122061.7610.96
xua393711239153424114912.2413.35
dkc39381250382431127702.146.46
dkf395412538147862127691.8411.58
bgb435512723149640129992.1711.51
bgd439613009351786133062.2826.44
frv44101071196729109472.208.84
c444470824141491458708241058.58
fnl446118256658723021848611.2631.77
bgf447513221274949134821.9720.39
r456724222912177068242229050.27
pcb_all46531773533333785177353018.80
ca466312903194789298813099591.5236.56
xqd49661531671602156512.194.57
fl_all498036173160578636173044.39
fqm50871302950999132811.933.84
c555598593155462586985931056.25
fea555715445313943158242.4519.84
r567827116915024210271169055.41
rl5915565530101450255823682.9817.42
rl593455604598613245759433.5817.12
tz611739471870185344038832.3217.38
c6666699617961647116996170137.45
r678929613617996086296136060.78
xsc688021535272748220992.6212.34
eg714617238730971651750651.5517.69
bnd716821834375208224032.6116.75
pla739723260728194900160236469031.668.24
lap745419535378452199722.2418.95
ym766323831467286432435852.2127.62
c77779631991893614619631990196.60
pm80791173478613224117347073.40
ida819722338547333229482.7323.85
ei824620617180324942104722.0938.16
u_all83545364006826057536400012.73
c888893153989286287931539095.85
ar9152837479582666168547232.0668.17
dga969827724672530287463.6923.40
ja984749192457532845026372.1811.45
r987635972026106765359720072.58
gr988230089928431953097202.939.18
kz997610618825547193110922102.8650.79
c9999126046417959364912604640142.48
c10k.010000330010345198212329343084423.96151.51
c10k.110000331862484829723279344187683.71140.32
c10k.210000331554245013566837345718474.27145.02
e10k.010000718658265207875979742682623.3470.12
e10k.110000720316305203408565745089423.4469.84
e10k.210000718224835236195601742597833.3970.51
xmc1015028387422853294573.7714.35
fi1063952052757163485371973.2010.64
c111119646301788163419646300185.37
rl11849923288866212779546793.4090.73
r1234540354532690992403545081.01
usa13509199828591590833042205768232.9777.31
xvb1358437084575904383343.3715.02
brd14051469385235875944826202.8248.87
mo1418542737759419304408793.1613.48
xrb14233454621469057470003.3831.26
ho14473177105158603701832123.4586.57
d15112157308411231076516145252.6369.56
it1686255731574043395765033.4412.84
xia1692852850648013549543.9811.79
pjh1784548094750115498893.7315.04
d18512645238345096426641552.9351.96
frh19289557981236067580594.0521.29
fnc19402592881785519616163.9328.98
r2072694733460582535671194733460061.49
ido21215635191474658661394.1222.30
fma21553665271279403696104.6318.38
c22222118647130676780211864710258.55
vm2277556928833240895940734.355.60
lsb22777609771439245632323.7022.76
r23456564740617681335647400109.37
xrh24104692941118257726914.9015.38
rl_all247321653283348453791653283021.08
sw2497885559792085208924724.3110.32
bbz25234693381950194727994.9926.79
irx28268726071186328768935.9015.43
fyg28534785652399803832695.9928.82
icx28698780902595413826715.8731.39
boa28924796243257019843515.9438.61
ird29514803592140377850965.8925.15
pbh30440883133132551932835.6333.58
c31k.0316235954539016648546397631151065.99263.78
c31k.1316235929326616814542248630321946.31266.76
e31k.031623127282138165161612881342872775.50122.99
e31k.131623127452384164141455021350641905.97121.53
xib328929676742584911026366.0741.49
fry332039724044289291036226.5642.74
c33333118311141778649311831110353.13
bm33708959304669303810066054.936.65
pla3381066048945229014696686504943.943.34
r34567692674910603276926740131.46
bby346569917228079771054186.3026.64
pba3847810832726081261151016.2522.66
ics3960310682144201571135276.2838.93
rbz4374812519155869881330926.3141.98
c44444142122052242530814212200367.59
r456787954291204107077954290151.38
fht4760812512457947051324425.8543.75
fna5205714780245154551573866.4828.69
c55555137313359240342413731330431.42
bna5676915810152690221684016.5131.29
r567898896761495523088896760168.10
dan5929616539768881461761906.5339.09
c666666468784286890082764687840443.50
ch71009456656330009823548285325.7462.15
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
lrb744710161142017002419717381737.8797.82
c777777865926419121063825865926402208.16
c8888882865419225718227139286541920897.54
pict_all899159147986932376531478147986930160.59
r9876543878025260261541838780250671.12
c99999912470398293280289731247039802351.81
c1m.0100000044399262452056283648844399262401172.46
e1m.010000007131876885211701791077844445339.99664.38
c111111151183165983792591345118316501922.10
r12345674145885325318613841458850784.68
small_all1611561861195297002714586119520112.64
world19047117512218268404794416459182630383589.99489.89
world_1904711564452345020564409274.45
world__1904711109003074046776894109003070371.25
vlsi_all1966088554259764106465855425970115.66
c222222214907556817958760455414907556801204.67
r23456786255634618196580362556340988.22
c3m.031622783115955257164823239643331159552570528.97
e3m.031622781267318251164806999266113938768049.991182,36
c33333334192933333164758422604192933330754.78
r345678982417869108484470824178601105.16
c44444447451966793697043569537451966790496.12
c55555558721095735946682112658721095730681.87
c6666666151356847661118465135215135684760403.80
c77777772448978715100208690355724489787150409.19
c8888888272564397262032631861527256439720227.59
r987654341868921926016609307418689219062.14
c9999999285813736094225935529028581373600329.68
c10m.01000000089869992985520803535240789869992985057.95
e10m.01000000022530881625213652267289337514033249.801544.72
r123456786834382932519838109683438290475.83
r23456789241006977617799146712410069770256.34
r9876543234906414382601531910583490641438074.53
r123456789194207430232520587629119420743020167.45
14.05.2019 07:51
 
`