Задача об оптимальном соединении в пространствах компактов, страница 9

O. Pollak, Steiner Minimal Trees, SIAM Journal onApplied Mathematics, 16, pp 1–29, 1968[6] H. O. Pollak, Some remarks on the Steiner problem, J. Combin, TheorySer. A 24 (1978), pp 278–295[7] D. Z. Du, F. K. Hwang, E. Y. Yao The steiner ratio conjecture is truefor five points, Journal of Combinatorial Theory, Series A, 38 (1985), pp230-240[8] J. H. Rubinstein, D. A. Thomas A variational approach to the Steinernetwork problem, Annals of Operations Research 33 (1991), pp 481-499[9] P.

O. De Wet Geometric Steiner minimal trees, Ph.D. thesis, Univ. ofSouth Africa, Pretoria 2008[10] D. Kirszenblat The Steiner ratio conjecture for eight points, M. Thesis,Uni. Melbourne, 2014[11] Е. И. Степанова Суботношение Штейнера евклидовой плоскости,дипломная работа, МГУ имени М.В. Ломоносова, 201243[12] А. С.

Пахомова Оценки для суботношения Штейнера и отношения Штейнера-Громова, Вестник Московского университета. Сер.1, Математика. Механика. - 2014. - № 1. - С. 17-25[13] A. O. Ivanov, A. A. Tuzhilin The Steiner Ratio Gilbert–PollakConjecture Is Still Open, Algorithmica, 62 (2012), issue 1, pp 630-632[14] А. О. Иванов, А. А. Тужилин Одномерная проблема Громова о минимальном заполнении, Матем. сб., 2012, том 203, номер 5, стр.

65–118[15] П. А. Бородин Пример несуществования точки Штейнера в банаховом пространстве, Матем. заметки, 2010, том 87, выпуск 4, стр.514–518[16] J. Henrikson Completeness and total boundedness of the Hausdorffmetric MIT Undergraduate Journal of Mathematics, 1999[17] Б. Б. Беднов, П. А. Бородин Банаховы пространства, реализующиеминимальные заполнения, Матем. сб., 205 (2014), выпуск 3, стр. 3–20[18] А. Ю.

Еремин Формула веса минимального заполнения конечногометрического пространства, Матем. сб., 204 (2013). выпуск 9, стр.51–72[19] О. В. Рублева Критерий аддитивности конечного метрическогопространства и минимальные заполнения, Вестн. Моск. ун-та. Сер.1. Матем., мех., 2012, 2, стр. 8–11[20] Garey M. R., Graham R. L. and Johnson D. S.

Some -completegeometric problems, Eighth Annual Symp. on Theory of Comput., 1976,pp. 10–22[21] Melzak Z. A. On the problem of Steiner, Canad. Math. Bull., 1960, vol.4, pp. 143–148.[22] Hwang F. K. A linear time algorithm for full Steiner trees, Oper.

Res.Letter, 1986, vol. 5, pp. 235–237[23] Shamos M. I. Computational Geometry, Ph. D. Thesis, Dept. of Comput.Sci., Yale Univ., 1978[24] D. Z. Du, W. D. Smith Disproofs of Generalized Gilbert–PollakConjecture on the Steiner Ratio in Three or More Dimensions, J. ofComb. Th. Series A, 74 (1996), pp. 115–130[25] F. K. Hwang On Steiner minimal trees with rectilinear distance, SIAMJournal of Applied Mathematics, 30 (1976), pp 104–11444AИсходный код программы, реализующейпоиск возможного количества реберныхпокрытий двудольного графа*;importcom . g o o g l e . common . c a c h e .importcom . g o o g l e . common .

c o l l e c t . I m m u t a b l e L i s t ;importcom . g o o g l e . common . c o l l e c t . L i s t s ;importcom . g o o g l e . common . c o l l e c t . S e t s ;importjava . u t i l . ArrayList ;importjava . u t i l . Arrays ;importjava . u t i l . List ;importjava . u t i l . Set ;importjava . u t i l . concurrent .

ExecutionException ;importj a v a . u t i l . c o n c u r r e n t . TimeUnit ;publicclassProofer{//0meansnoedge ,//2meansanedgeprivatestaticintint [ ] [ ]if1meansmaybeanedgenumberOfEdgeCoverings (bipartiteAdjacencyMatrix )( bipartiteAdjacencyMatrix . lengthreturn1;( int [ ]row{==0){}forbooleanfor( intif:bipartiteAdjacencyMatrix )hasEdgeedge( edge=:row )>0)hasEdge={false ;{{true ;break ;}}if( ! hasEdge )return{0;}}for( inti=0;i<bipartiteAdjacencyMatrix [ 0 ] .

length ;booleanforhasEdge( int [ ]ifrow( row [ i ]=:false ;bipartiteAdjacencyMatrix )>hasEdge=0){true ;break ;}}if( ! hasEdge )returni ++){0;}}45{{introw=booleanfor0,column=0;hasVariableEdge( inti=0;i=false ;<bipartiteAdjacencyMatrix . length ;for( intjj<={bipartiteAdjacencyMatrix [ i ] . length ;j ++)ifi ++)0;{( bipartiteAdjacencyMatrix [ i ] [ j ]row===1){i ;column=j ;hasVariableEdge=true ;break ;}}if( hasVariableEdge )break ;}if( ! hasVariableEdge )return{1;}b i p a r t i t e A d j a c e n c y M a t r i x [ row ] [ c o l u m n ]intcoverings=2;=numberOfEdgeCoverings ( b i p a r t i t e A d j a c e n c y M a t r i x ) ;b i p a r t i t e A d j a c e n c y M a t r i x [ row ] [ c o l u m n ]coverings=0;+=numberOfEdgeCoverings ( b i p a r t i t e A d j a c e n c y M a t r i x ) ;b i p a r t i t e A d j a c e n c y M a t r i x [ row ] [ c o l u m n ]return=1;coverings ;}privatestaticint [ ] [ ]getSubset ( int [ ] [ ]Boolean [ ]introws=for( intiif0,=cols0;i=<( i<{0;includeVertex .

length ;( includeVertex [ i ] )ifmatrix ,includeVertex )i ++){{matrix . length ){r o w s ++;}else{c o l s ++;}}}if( ( rows==return0)new^( cols==int [ 1 ] [ 1 ] ;0))//{effectivelysame}int [ ] [ ]introwfor( intresult== newi n t [ rows ] [ c o l s ] ;0;i=intcolfor( intif0;=i<matrix . length ;i ++){0;j=0;j<matrix [ i ] . length ;( includeVertex [ i ]j ++)&&includeVertex [ matrix . length46{+j ]){r e s u l t [ row ] [ c o l ++] =matrix [ i ] [ j ] ;}}if( includeVertex [ i ] ){row++;}}returnresult ;}privatestaticclassAtomicGraphprivatefinalprivateL o a d i n g C a c h e <L i s t <B o o l e a n > ,=int [ ] [ ]{bipartiteAdjacencyMatrix ;Integer>cacheC a c h e B u i l d e r .

n e w B u i l d e r ( ) . maximumSize ( 4 0 ). expireAfterAccess (100 ,T i m e U n i t . MINUTES). build (newC a c h e L o a d e r<L i s t <B o o l e a n > ,I n t e g e r >(){@OverridepublicIntegerl o a d ( L i s t <B o o l e a n >throwsreturnExceptionkey ){numberOfEdgeCoverings (getSubset (bipartiteAdjacencyMatrix ,k e y . t o A r r a y ( newBoolean [ key . s i z e ( ) ] ) ) ) ;}});publicAtomicGraph (int [ ] [ ]bipartiteAdjacencyMatrix )this . bipartiteAdjacencyMatrix{=bipartiteAdjacencyMatrix ;}publicintreturngetNumberOfVertices ( ){bipartiteAdjacencyMatrix . length+bipartiteAdjacencyMatrix [ 0 ] . length ;}publicintgetAlpha ( )Boolean [ ]a= newArrays .

f i l l ( a ,returnthrowsExecutionException{Boolean [ getNumberOfVertices ( ) ] ;true ) ;cache . get ( L i s t s . newArrayList ( a ) ) ;}publicAlphaBetathrowsg l u e ( L i s t <A l p h a B e t a>ExecutionExceptionL i s t <B o o l e a n >newfor( inti=array=A r r a y L i s t <>( g e t N u m b e r O f V e r t i c e s ( ) ) ;0;i<getNumberOfVertices ( ) ;a r r a y . add ( f a l s e ) ;}array . set (0 ,graphs ){false );47i ++){intbeta=r e c u r s i o n ( array ,array .

set (0 ,intalphareturn1);true ) ;=newgraphs ,r e c u r s i o n ( array ,graphs ,AlphaBeta ( alpha ,1);beta ) ;}privateintr e c u r s i o n ( L i s t <B o o l e a n >array ,L i s t <A l p h a B e t a>intthrowsif( indexExecutionException==returngraphs ,index )graphs . s i z e ( )+{1){cache . get ( array ) ;}array . s e t ( index ,intresult=true ) ;r e c u r s i o n ( array ,*( graphs . get ( index+graphs . get ( indexarray . s e t ( index ,returngraphs ,index+− 1 ) . alpha− 1 ) . beta ) ;false );result+r e c u r s i o n ( array ,*graphs . get ( indexgraphs ,−index+1)1 ) . alpha ;}}privatestaticclassAlphaBetapublicfinalintalpha ;publicfinalintbeta ;publicAlphaBeta ( i n tt h i s .

alphat h i s . beta=={alpha ,intbeta ){alpha ;beta ;}@Overridepublicbooleanif( thisif( o ==e q u a l s ( Object== o )nullreturnAlphaBetareturnreturn||o)getClass ()alphaBetaalpha==beta=alphaBeta . alpha==alphaBeta . beta ;@OverridereturnhashCode ( )1001*{alpha+}@OverridepublicStringreturno . getClass ())( AlphaBeta )}int!=false ;&&public{true ;toString ()" AlphaBeta {"{+48beta ;o;1)" a l p h a =" +",alpha+beta+b e t a =" +’} ’;}}privatestaticintL i s t <L i s t <A l p h a B e t a>>maxAlpha ,intnumpoints ,L i s t <L i s t <A l p h a B e t a>>L i s t <A l p h a B e t a>for( AlphaBetaifgetAvailableSets (resultfittingvalue=:=S e t <A l p h a B e t a>set ){L i s t s .

newArrayList ( ) ;L i s t s . newArrayList ( ) ;set ){( v a l u e . a l p h a <= maxAlpha ){f i t t i n g . add ( v a l u e ) ;}}if( numpointsfor==1)( AlphaBeta{value:fitting ){r e s u l t . add ( I m m u t a b l e L i s t . o f ( v a l u e ) ) ;}returnresult ;}for( AlphaBetaintvalue:newMaxAlpha =maxAlphafitting ){value . alpha== 0?:Math .

min ( maxAlphamaxAlphaL i s t <L i s t <A l p h a B e t a>>/v a l u e . alpha ,−value . alpha ) ;other=g e t A v a i l a b l e S e t s ( newMaxAlpha ,−numpointsfor( L i s t <A l p h a B e t a>list1,:set );other ){r e s u l t . add ( I m m u t a b l e L i s t . < A l p h a B e t a>b u i l d e r ( ). add ( v a l u e ) . a d d A l l ( l i s t ) . b u i l d ( ) ) ;}}returnresult ;}privatestaticS e t <A l p h a B e t a>S e t <AtomicGraph>S e t <A l p h a B e t a>int// g l u emaxValue )twoatomicGraphs ,alphaBetas ,throwsnewGraphsforleft( AlphaBetaif( l e f t . betabetaintalpha0){S e t s .

newHashSet ( a l p h a B e t a s ) ;==:alphaBetas )0)l e f t . beta=r i g h t . beta ;( l e f t . alphamaxValue )newGraphs . add ( new49{continue ;*( r i g h t . alpha( a l p h a <={continue ;right=*=alphaBetas )( r i g h t . betaintif:==( AlphaBetaifExecutionExceptiongraphsS e t <A l p h a B e t a>forupdate (++l e f t .

beta )r i g h t . beta )−beta ;{AlphaBeta ( alpha ,beta ) ) ;}}}// g l u eforsomegraphs( AtomicGraphinttoatomicgraph:graphatomicGraphs ){maxAlpha = Math . min (formaxValue/graph . getAlpha ( ) ,maxValue−graph . getAlpha ( ) ) ;( L i s t <A l p h a B e t a>list:getAvailableSets (maxAlpha ,−graph . getNumberOfVertices ( )alphaBetas ) )AlphaBetaif1,{result=graph .

g l u e ( l i s t ) ;( r e s u l t . alpha<maxValue ){newGraphs . add ( r e s u l t ) ;}}}returnnewGraphs ;}privatestaticS e t <I n t e g e r >S e t <AtomicGraph>intmaxSteps )prove (graphs ,throwspossibilitiesfor1;i=i<maxAlpha ,ExecutionExceptionS e t <I n t e g e r >( intint={S e t s . newTreeSet ( ) ;maxAlpha ;i ++){p o s s i b i l i t i e s . add ( i ) ;}S e t <A l p h a B e t a>newint=S e t s . newHashSet (AlphaBeta ( 0 ,S e t <A l p h a B e t a>dosetnewSetsteps=setnewSet ;=1));set ;0;{=newSet=update ( graphs ,set ,maxAlpha ) ;s t e p s ++;}while( ( newSet . s i z e ( )&&for!=( maxSteps <( AlphaBetavalue:set . size ())0||stepsset )<maxSteps ) ) ;{p o s s i b i l i t i e s . remove ( v a l u e .