联想存储器中的应用.pdf

1 9 9 5年 7月 第 l 8卷第 4 期 重庆大学学报( 自然科学版) J o u r n a l o f Ch on g q j ng unj ve r g r 【 y( Na t ur a l S c i e n c g Ed i t mn) Vo1 ．1 8． N 4 J u1 ． 1 9 9 5 弓 一 超立方体的 3 一 独立集及其在神经 联想存储器中的应 用 p p u3 - I n d e p e n d e n t S e t s o f Hy p e r c u b e sa n d A c at i o n s i n Ne u r a l As s o c i a t i v e M e mo r i e s 岬 丁 p； 3 3 p p u ⋯ 堑堕坚— 衄 垃 YangXi a ofan He Zho ng s hi ( 重庆大学计 算机研究所 ， 重庆大学 系统 工程及应 用数学 系， 重庆 ， 6 3 0 0 4 4 ) 陈 廷 槐 Ch e n Ti ng h u a i ( 重庆大学计算机研究所 ， 重 庆， 6 3 0 0 4 4 ) 摘要用 ， ( ) 表 示 一 立方体 口 - 的 3 一 独立数。

提 出 了构造 ． 的 3 _ 独 立集 的一个 算 法 ， 证 明 了 2 ' - C ~． 3 ≤， 3 ( 霄 ) ≤[ 2 ． ／( 霄 +1 ) ] ． 这些 结果被应用于 神经联想存储器 曲设 计． 关 键 词 里 笙 苎 鲎- 连 丝 堕 堑； 壁 望 壹 熊 墨， 塑皇 查签； -— i i ~ — l l t 3 _ 中国图书资料分 类法分类号01 5 7 ． 5 1 T P 3 3 3 AB S TRACT L e t I 3 ( 霄 ) d e n o t e t h e 3 - i n d e p e n d e n c e n u mb e r o f~ - ol b e ． ． An a l g o r i t h m i s p r e s e n t e d f o r fi n d ing a 3 - i n d e p e n den t s e t o f - ， a n d 2 ． 一 【 卜 ≤ ， a ( 4 ) ≤ [ 2 ． ／( 翻 +1 ) ]i s s h o w n ． “1 71 ese r e ~ u l = 时e a p p l i e d t o t he d e s i B n o f n e u r a l ass o c ~t i v e me mo r i e s ． K E Y W O RD S g r a 一 廿 l e 0 船廿 c a l a l g o ri t h mI l u r | J n e t w o r k I a s s o c i a ~ v e me m o r y ／ h y pe r c ub ~l 3 - i nd e p e n d e nt s e t l 3- i nd e p e nd e n c e n umb e r 0 引 言 A 3 - i n d e p e n d e nt s e t o f a a p h i s a s e t o f v e r ti c es s u c h r ．h a t the l e n g th of a s h o r t e s t p a 血 b e t we e n a ny t wo of t h e m i s 戤l e as t 3 ．A ma x i mum 3 - i nd e p e nd e n t s e t o f a g r a p h 远a 3 一 ind e pen d e n t s e t suc h r ．h a t e v e r y 3 - ind e p e n d e n t s e t of the g r a p h h a s a t mo s t l l r e ． i c e s ． 凡 ( 口) de ,n ot es th e c a r d i n a l i c y o f a ma x~ u m 3- i n d e p e nd e nt set o f a g r a ph 口· c a l l e d t h e 3 - i n d e pe n de nc e numbe r o f ． n - c u b e ， 口 ． ， i s a g r a p h wh o s e v e r t i c e s c a l l b e l a b e l e d wi th a l l 0 - 1 s e q u e n c es of l e n g t h n s o r ．h a t t wo v e r t i c e s a r e a d j a c e a t i f f t h e i r l a b e l s h a v e a Ha mmi n g d i s t a n c e l( t h e Ha mming d i s t a n c e b e t we e n + 收文 日期1 9 9 4 — 9 4 - 2 3 Th i s wo r k wD @s u pp o r t e d b y t hc Do c t or — St a t i o n F ou nda t i o n of Ch i n e ~Na t i on a l Edu c a t i on a l C∞∞Ⅲt t ∞ ． 重庆大学学报( 白然科学版) 1 9 9 5年 t wo 0 一 l s e q l l e r l c ~ 口a n d声j s t h o n u mb e r 0 f b i t s 0 1 3 wh i c h a d i f f o r s f t o l n ， d e n o t e d b y 如 ( d， ) ) ． F0 r b f e v i t y， t h e v o r t i c e s o f 8 ． r e i d e n t i fie d wi t h t ho i r l a b e l s ． T'a u ~， a 鼹t o f vo r t i e e ~ of 讧 a 3 一 i n d o p e n d o n t s e t i l l a Ⅱ y伸 0 o f t h o rn h a v o a l - l a n u n i n g d i s t a n c e且 t l e a s t 3 ． 1 3 ( )妞 a b b r e vi a t o d a s j 3 ( 霄 ) ． I t i s NP- h a r d t o f i n d ^ ( 口) f o r 蛐a 『 b j 扭 y g r a p h G幢 I ． I n t h i s l ~P e r ， a n d a l g o r i t h m i s p r e ． s ~ n t e df o 1“ f l n d i n g a 3 - i n d e p e n d e n t s e t o f ， a n d 2 I 一 一 ≤ 厶( 霄 ) ≤ [ 2 l ／ ( 日 + 1 ) ]i s s h o w n ( ]d e n o t e st h ol a r g e s t i n t o g o r n O g 旺 t b ． ~ t t z ) ． T h e ．~ r 蝴ms a I e a p p I i e dt ot h o d 曙逗 n o f n e 1 l r a l as s oc i at i re m em 0r i 船 ． 1 B OUNDS ON I 3 ( n) l 就 n ( 0 ) 一 { 0 O O 0 ， 1 U l 】 ， ( ∞ = { 0 O l 1 ， U ∞ ) ， n ( 0 ) = { 0 1 0 1 ， 1 Q l Q ) ， F j ( 0 ) 一 { 0 1 1 0 ， 1 0 0 1 )， n ( 1 ) = f 0 0 0 1 ， 儿 1 0 ) ， ( 1 ) = { 0 0 1 0 ， 1 1 0 1 ) ， n ( 1 ) = { O 1 0 0 ， 1 0 1 1 ) ， ( 1 ) 一 f 0 1 1 1 ， 1 0 0 0 ) ； ( 1 ) 一 { 0 0 0 ， 1 1 1 ) ， ( 2 ) 毫 { 0 0 1 ， 1 l 0 ) ， ( 3 ) 一 f 0 1 0 ， 1 0 1 ) ， ( 4 ) = f 0 1 1 ， 1 0 0 ) ． k mm a 1 ． L e t 0 ≤讧 ≤1 a n d 1 ≤ j ≠l ≤ 4 ． “r h o n t h e f o U o w[ n g a s r t h o l d ． 、 ( 1 )Ⅱ ( ) { 口 ， ) ， t h e n如 ( 口 ， 声 ) d ． 、 ( 2 )I f ( ) = ( 口 ， ) ， t h e n如 ( 口 ， 声 ) =3 ． ( 3 )Ⅱ ∈ ( )。

∈n ( i ) ， t h e n如 ， ) = 2 ， ( 4 )Ⅱ d ∈T( j ) ， ∈ ( )， t h e n如 ， 声 ) ≥ 1 ． L B t [ 口 ] b e( 0 - 1 8 e q u 蛐∞∞n 幽 ； n g o t b i t i t h r o u g h b n J o f a 0 - 1 ~l u e n e e口 ． [ 口 ] is a l ~ b r e v i a t e d a s[ a ] ll L e t d e n o t o t h e s e t 0 f a l l g - 1 s e q u e n c 船 o f l o n g t b且 ． we~t r u c t 4∞t 打( ) o f 0 — 1 s e q u e nc e s o fl o ng t h 4 曩 + 3f r o m a 0 — 1 s e q t l e n e e o fl e n g 血 日b y~ o l l o e t t n g a I l口s u c ht h a t i ( A )[ a 3 H 卜 一 。

t ∈u ( [ 妇， )f o r l ≤讧 ≤ ． J l ( B ) I f [ 口 ] 【 I i - 舢 ∈ ( [ 妇， )( 1 ≤i ≤ ) ， 【 h e n[ f + 1 )一 ( h + 3 ) ∈ ( ( 置 ) Ⅱ 似l 4 +1 ) ． kⅡ u n 8 2 ．L e t y ∈ ． T h e n J 打( ) J ；2 ¨． P r o o f ．』 Ⅱ( ) J =2 x ／ ／J ( [ ] ． ) f ：8 ‘ ×2 =2 斗 1 ． Q ． ． D ， n忙o l 蜘3 ． L e t ∈ ． t h e n打(。