search

xyz600 / max-cut-solver

MIT License
0 stars 0 forks source link

dijkstra-like な近傍の貪欲法を実装する #1

Closed xyz600 closed 3 years ago

xyz600 commented 3 years ago
xyz600 commented 3 years ago
don't look bit + greedy result ||timeout[ms]|score| |----|----|----| |G1|10000|11369| |G22|10000|12789| |G43|10000|6359| |G55|10000|9375| |G60|10000|12836| |G6|10000|1869| |G27|10000|2716| |G56|10000|3046| |G61|10000|4520| |G14|10000|2898| |G35|10000|7252| |G51|10000|3644| |G58|10000|18359| |G63|10000|25719| |G18|10000|825| |G39|10000|1961| |G59|10000|4915| |G64|10000|7091| |G11|10000|410| |G12|10000|396| |G13|10000|434| |G32|10000|1018| |G33|10000|970| |G34|10000|1012| |G57|10000|2478| |G65|10000|3970| |G66|10000|4546| |G67|10000|4866| |G72|10000|5038| |G77|10000|7100| |G81|10000|10126|
xyz600 commented 3 years ago

参考:
https://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/1941-09.pdf

xyz600 commented 3 years ago
timeout[ms] score known best
G1 10000 11577 11624
G22 10000 13168 13359
G43 10000 6564 6660
G55 10000 9917 10299
G60 10000 13619 14186
G6 10000 2102 2178
G27 10000 3239 3341
G56 10000 3671 4016
G61 10000 5248 5789
G14 10000 3038 3064
G35 10000 7538 7686
G51 10000 3796 3848
G58 10000 18802 19263
G63 10000 26218 26997
G18 10000 952 992
G39 10000 2270 2408
G59 10000 5483 6078
G64 10000 7892 8735
G11 10000 560 564
G12 10000 556 556
G13 10000 576 582
G32 10000 1386 1410
G33 10000 1348 1382
G34 10000 1358 1384
G57 10000 3282 3492
G62 10000 4490 4868
G65 10000 5058 5558
G66 10000 5830 6360
G67 10000 6150 6940
G72 10000 6328 6998
G77 10000 8470 9926
G81 10000 11170 14030
xyz600 commented 3 years ago

着目する連結成分に関して、枝刈りをちょっとだけやった。

timeout[ms] score known best
G1 10000 11520 11624
G22 10000 13193 13359
G43 10000 6582 6660
G55 10000 10107 10299
G60 10000 13892 14186
G6 10000 2096 2178
G27 10000 3190 3341
G56 10000 3846 4016
G61 10000 5523 5789
G14 10000 3025 3064
G35 10000 7566 7686
G51 10000 3809 3848
G58 10000 19041 19263
G63 10000 26658 26997
G18 10000 958 992
G39 10000 2303 2408
G59 10000 5688 6078
G64 10000 8276 8735
G11 10000 550 564
G12 10000 550 556
G13 10000 574 582
G32 10000 1378 1410
G33 10000 1360 1382
G34 10000 1358 1384
G57 10000 3426 3492
G62 10000 4760 4868
G65 10000 5442 5558
G66 10000 6212 6360
G67 10000 6770 6940
G72 10000 6814 6998
G77 10000 9572 9926
G81 10000 13498 14030