Диссертация (1137405), страница 15
Текст из файла (страница 15)
ðÕÓÔØ | ÉÎÄÅËÓ ×ÌÉÑÎÉÑ, ÏÐÒÅÄÅÌÅÎÎÙÊ ÎÁ ÍÎÏÖÅÓÔ×Å ÐÒÏÓÔÙÈ ÉÇÒ, ÕÄÏ×ÌÅÔ×ÏÒÑÀÝÉÈ ÕÓÌÏ×ÉÀ ÏÄÎÏÚÎÁÞÎÏÓÔÉ ÇÏÌÏÓÏ×ÁÎÉÑ. ôÏÇÄÁ ÕÄÏ×ÌÅÔ×ÏÒÑÅÔ ÁËÓÉÏÍÁÍ NP, An É Tn É E, ÅÓÌÉ É ÔÏÌØËÏ ÅÓÌÉ (v) = Bz (v).5. ïÂÚÏÒ É ÓÒÁ×ÎÅÎÉÅ ÁËÓÉÏÍðÒÏÂÌÅÍÅ ÁËÓÉÏÍÁÔÉÞÅÓËÏÇÏ ÚÁÄÁÎÉÑ ÒÅÛÅÎÉÊ ËÏÏÐÅÒÁÔÉ×ÎÙÈ ÉÇÒ ÐÏÓ×ÑÝÅÎÏ ÍÎÏÖÅÓÔ×Ï ÒÁÂÏÔ É ÍÎÏÇÉÅ ÉÚ ÎÉÈ ÍÏÇÕÔ ÂÙÔØ ÁÄÁÐÔÉÒÏ×ÁÎÙ ÄÌÑ ÉÎÄÅËÓÏ××ÌÉÑÎÉÑ (ÎÁÐÒÉÍÅÒ, ÐÅÒ×ÙÊ ÉÚ×ÅÓÔÎÙÊ Á×ÔÏÒÕ ÁÎÁÌÏÇ ÔÅÏÒÅÍÙ ËÌÁÓÓÉÆÉËÁÃÉÉÓÏÄÅÒÖÉÔÓÑ × [93]). îÏ ÔÁËÏÊ ÏÂÚÏÒ ×ÙÈÏÄÉÔ ÚÁ ÒÁÍËÉ ÜÔÏÊ ÄÉÓÓÅÒÔÁÃÉÉ, ÐÏÜÔÏÍÕ ÏÇÒÁÎÉÞÉÍÓÑ ÔÏÌØËÏ ÉÎÄÅËÓÁÍÉ ×ÌÉÑÎÉÑ.÷ÙÛÅ ÕÐÏÍÉÎÁÌÉÓØ É ÉÓÐÏÌØÚÏ×ÁÌÉÓØ ÁËÓÉÏÍÁÔÉËÉ [48] (ÐÅÒ×ÁÑ ÁËÓÉÏÍÁÔÉËÁÄÌÑ ÉÎÄÅËÓÁ ûÅÐÌÉ|ûÕÂÉËÁ) É [50] (ÐÅÒ×ÁÑ ÁËÓÉÏÍÁÔÉËÁ ÄÌÑ ÉÎÄÅËÓÁ ðÅÎÒÏÕÚÁ|âÁÎÃÁÆÁ).ðÏÖÁÌÕÊ, ÓÁÍÁÑ ÎÅÅÓÔÅÓÔ×ÅÎÎÁÑ ÉÚ ÜÔÉÈ ÁËÓÉÏÍ | ÁËÓÉÏÍÁ ÏÂÝÅÊ ÓÕÍÍÙ ÄÌÑ104ÉÎÄÅËÓÁ ðÅÎÒÏÕÚÁ. ìÅÈÒÅÒ ([70]) ÐÏËÁÚÁÌ, ÞÔÏ ÅÅ ÍÏÖÎÏ ÚÁÍÅÎÉÔØ ÎÁ ÓÌÅÄÕÀÝÅÅÕÔ×ÅÒÖÄÅÎÉÅ.ðÕÓÔØ v | ÐÒÏÓÔÁÑ ÉÇÒÁ, R ⊆ N .
ïÂÏÚÎÁÞÉÍ vR ÉÇÒÕ, ÐÏÌÕÞÅÎÎÕÀ ÏÂßÅÄÉÎÅÎÉÅÍ ×ÓÅÈ ÉÇÒÏËÏ× ÉÚ R × ÏÄÎÏÇÏ, Ô.Å. vR (S ) = v(S ), ÅÓÌÉ S ∩ R = ∅ ÉvR (S ∪ {R}) = v(S ∪ R).áËÓÉÏÍÁ 2-ÜÆÆÅËÔÉ×ÎÏÓÔÉ / 2-Eciency axiom ÕÔ×ÅÒÖÄÁÅÔ, ÞÔÏ ÏÂßÅÄÉÎÑÔØÓÑ × ËÏÁÌÉÃÉÉ ×ÙÇÏÄÎÏ ÌÀÂÙÍ Ä×ÕÍ ÉÇÒÏËÁÍ: ∀i; j ∈ Ni(v) + j (v) ≤ {i;j }(v{i;j }):äÒÕÇÁÑ ×ÙÚÙ×ÁÀÝÁÑ ËÒÉÔÉËÕ ÁËÓÉÏÍÁ | ÁËÓÉÏÍÁ ÁÄÄÉÔÉ×ÎÏÓÔÉ (ÉÌÉ T).åÅ ÍÏÖÎÏ ÚÁÍÅÎÉÔØ ÎÁ ÐÒÉ×ÏÄÉÍÕÀ ÎÉÖÅ ÁËÓÉÏÍÕ ÍÁÒÇÉÎÁÌØÎÏÇÏ ×ËÌÁÄÁ. üÔÏÓÄÅÌÁÎÏ × [97] ÄÌÑ ÉÎÄÅËÓÁ ûÅÐÌÉ|ûÕÂÉËÁ É × [78] ÄÌÑ ÉÎÄÅËÓÁ âÁÎÃÁÆÁ.áËÓÉÏÍÁ ÍÁÒÇÉÎÁÌØÎÏÇÏ ×ËÌÁÄÁ / Marginal Contributions axiom ðÕÓÔØv; w ∈ SGn. ôÏÇÄÁ ÅÓÌÉ ÉÇÒÏË i ×ÎÏÓÉÔ ÏÄÉÎ É ÔÏÔ ÖÅ ×ËÌÁÄ, ÐÒÉÓÏÅÄÉÎÑÑÓØ ËÌÀÂÏÊ ËÏÁÌÉÃÉÉ S , Ô.Å.
∀ S ⊆ N \ {i}v(S ∪ {i}) − v(S ) = w(S ∪ {i}) − w(S );ÔÏ i(v) = i(w).äÒÕÇÉÅ ÁËÓÉÏÍÁÔÉËÉ ÄÌÑ ÉÎÄÅËÓÁ âÁÎÃÁÆÁ ÐÒÉ×ÅÄÅÎÙ × [52, 58, 81, 84].îÁËÏÎÅÃ, × ÁËÓÉÏÍÁÔÉËÁÈ ìÁÒÕÅÌÌØ É ÷ÁÌÅÎÓÉÁÎÏ [65] ÐÅÒÅÒÁÂÏÔËÅ ÐÏÄ×ÅÒÇÌÉÓØ ×ÓÅ ÁËÓÉÏÍÙ, ÉÓËÌÀÞÁÑ ÁËÓÉÏÍÕ ÁÎÏÎÉÍÎÏÓÔÉ.1055.1. óÒÁ×ÎÅÎÉÅ ÁËÓÉÏÍ äÕÂÉ|ûÅÐÌÉ, ìÁÒÕÅÌÌØ{÷ÁÌÅÎÓÉÁÎÏÉ ÓÌÅÄÓÔ×ÉÊ ÉÚ ÁËÓÉÏÍÁÔÉË ÄÌÑ -ÉÎÄÅËÓÁïÔÍÅÔÉÍ, ÞÔÏ ÁËÓÉÏÍÙ ìÁÒÕÅÌÌØ|÷ÁÌÅÎÓÉÁÎÏ ÎÅÓËÏÌØËÏ ÓÌÁÂÅÅ ÁËÓÉÏÍ äÕÂÉ|ûÅÐÌÉ, ÞÔÏ É ÎÅ ÕÄÉ×ÉÔÅÌØÎÏ, ÐÏÓËÏÌØËÕ ÐÅÒ×ÙÅ ÏÐÒÅÄÅÌÑÀÔ ÉÎÄÅËÓ ×ÌÉÑÎÉÑ ÎÅÏÄÎÏÚÎÁÞÎÏ, Á Ó ÔÏÞÎÏÓÔØÀ ÄÏ ÁÆÆÉÎÎÏÇÏ ÐÒÅÏÂÒÁÚÏ×ÁÎÉÑ (x → ax + b). îÏ× ÏÓÔÁÌØÎÏÍ ÁËÓÉÏÍÙ ÂÌÉÚËÉ.
ôÏÞÎÅÅ, ×ÅÒÅÎ ÓÌÅÄÕÀÝÉÊ ÎÁÂÏÒ ÕÔ×ÅÒÖÄÅÎÉÊ,ÄÏËÁÚÁÎÎÙÊ × [66].ôÅÏÒÅÍÁ 15. áËÓÉÏÍÙ T É T∗ ÜË×É×ÁÌÅÎÔÎÙ.áËÓÉÏÍÁ NP∗ ÓÌÁÂÅÅ ÁËÓÉÏÍÙ NP, ÎÏ, ÅÓÌÉ ÉÎÄÅËÓ ×ÌÉÑÎÉÑ ÕÄÏ×ÌÅÔ×ÏÒÑÅÔÁËÓÉÏÍÁÍ NP∗ É An, ÔÏ ×ÙÉÇÒÙÛ ÂÏÌ×ÁÎÁ i(v) ÎÅ ÚÁ×ÉÓÉÔ ÎÉ ÏÔ i ÎÉ ÏÔ v.éÚ ÁËÓÉÏÍ An É T∗ ÓÌÅÄÕÅÔ SymGl.áËÓÉÏÍÁ TGLB ÓÌÁÂÅÅ ÁËÓÉÏÍÙ ÜÆÆÅËÔÉ×ÎÏÓÔÉ É ÒÁ×ÎÏÓÉÌØÎÁ ÔÏÍÕ, ÞÔÏÓÕÍÍÁ ×ÌÉÑÎÉÊ ×ÓÅÈ ÉÇÒÏËÏ× ÎÅ ÚÁ×ÉÓÉÔ ÏÔ ÉÇÒÙ: ∀ v; w ∈ SGn, v; w 6= 0; 1Xi∈Ni(v) =Xi∈Ni(w):áËÓÉÏÍÁÔÉËÉ ìÁÒÕÅÌÌØ|÷ÁÌÅÎÓÉÁÎÏ É ÔÅÏÒÅÍÁ 8 ÐÏËÁÚÙ×ÁÀÔ, ÞÔÏ ÁËÓÉÏÍÙAn, T (T∗) É SymGL (SymGL1) ÐÒÉÍÅÒÎÏ ÒÁ×ÎÏÃÅÎÎÙ | × ÁËÓÉÏÍÁÔÉËÕ ÍÏÖÎÏ×ËÌÀÞÉÔØ ÌÀÂÙÅ Ä×Å ÉÚ ÎÉÈ.
ðÒÉ ÜÔÏÍ SymGL ÓÌÅÄÕÅÔ ÉÚ An É T∗, Á An | ÉÚT∗ É SymGL (ÚÁÍÅÞÁÎÉÅ 2).ó ÔÏÞËÉ ÚÒÅÎÉÑ ÁËÓÉÏÍ, ÏÓÎÏ×ÎÏÅ ÏÔÌÉÞÉÅ ÉÎÄÅËÓÏ× ×ÌÉÑÎÉÑ, ÚÁ×ÉÓÑÝÉÈ ÏÔÐÒÅÄÐÏÞÔÅÎÉÊ ÕÞÁÓÔÎÉËÏ×, ÏÔ ËÌÁÓÓÉÞÅÓËÉÈ ÉÎÄÅËÓÏ× × ÁËÓÉÏÍÅ ÁÎÏÎÉÍÎÏÓÔÉ.óÕÝÅÓÔ×ÕÅÔ Ä×Á ÓÐÏÓÏÂÁ ÏÂÏÂÝÉÔØ ÜÔÕ ÁËÓÉÏÍÕ ÎÁ ÉÇÒÙ Ó ÐÒÅÄÐÏÞÔÅÎÉÑÍÉ.
åÓÌÉ ÓÞÉÔÁÔØ, ÞÔÏ ÐÒÉ ÐÅÒÅÓÔÁÎÏ×ËÅ ÉÇÒÏËÏ× ÐÅÒÅÓÔÁ×ÌÑÀÔÓÑ É ÆÕÎËÃÉÉ ÉÎÔÅÎÓÉ×ÎÏÓÔÉ, ÔÏ ÁËÓÉÏÍÁ ÂÕÄÅÔ ×ÅÒÎÁ, ÎÏ ÎÅ ÐÒÉÍÅÎÉÍÁ Ë ÄÏËÁÚÁÔÅÌØÓÔ×ÁÍ. åÓÌÉÖÅ ÓÞÉÔÁÔØ, ÞÔÏ ÆÕÎËÃÉÉ ÉÎÔÅÎÓÉ×ÎÏÓÔÉ ÎÅ ÐÅÒÅÓÔÁ×ÌÑÀÔÓÑ, ÔÏ ÁËÓÉÏÍÁ ÂÕÄÅÔ106ÎÅ ×ÅÒÎÁ ÄÌÑ |ÉÎÄÅËÓÁ. ðÏÜÔÏÍÕ ÁËÓÉÏÍÁ ÁÎÏÎÉÍÎÏÓÔÉ ÏÓÌÁÂÌÑÅÔÓÑ ÄÏ WAnÉ ÄÏËÁÚÁÔÅÌØÓÔ×Á ÐÒÏ×ÏÄÑÔÓÑ ÔÏÌØËÏ ÄÌÑ ÓÉÍÍÅÔÒÉÞÎÙÈ ÉÇÒ.
îÅÏÂÈÏÄÉÍÏÓÔØÜÔÏÇÏ ÐÏËÁÚÙ×ÁÅÔ ÓÌÅÄÕÀÝÁÑ ÌÅÍÍÁ.ìÅÍÍÁ 7. åÓÌÉ -ÉÎÄÅËÓ ÕÄÏ×ÌÅÔ×ÏÒÑÅÔ ÓÌÁÂÏÍÕ ÕÓÌÏ×ÉÀ ÁÎÏÎÉÍÎÏÓÔÉ, ÔÏÐÒÅÄÐÏÞÔÅÎÉÑ ÓÉÍÍÅÔÒÉÞÎÙ, Ô.Å. ∀i; j ∈ S f (i; S ) = f (j; S ).äÏËÁÚÁÔÅÌØÓÔ×Ï. ðÕÓÔØ i(uS ) = j (uS ) ÄÌÑ ×ÓÅÈ i; j ∈ S .äÏËÁÖÅÍ, ÞÔÏ f (i; S ) = f (j; S ) ÕÂÙ×ÁÀÝÅÊ ÉÎÄÕËÃÉÅÊ ÐÏ ÒÁÚÍÅÒÕ S . åÓÌÉS = N , ÔÏ × uS ÔÏÌØËÏ ÏÄÎÁ ×ÙÉÇÒÙ×ÁÀÝÁÑ ËÏÁÌÉÃÉÑ (N ) Éf (i; N ) = i(uN ) = j (uN ) = f (j; S ):ðÕÓÔØ ÔÅÐÅÒØ ÕÔ×ÅÒÖÄÅÎÉÅ ÄÏËÁÚÁÎÏ ÄÌÑ ×ÓÅÈ ËÏÁÌÉÃÉÊ ÂÏÌØÛÅÇÏ, ÞÅÍ S ÒÁÚÍÅÒÁ.i(uS ) =j(uS )=XT ⊇SXT ⊇Sf (i; T ) = f (i; S ) +f (j; T ) = f (j; S ) +XT ⊃SXT ⊃Sf (i; T );f (j; T ):ìÅ×ÙÅ ÞÁÓÔÉ ÒÁ×ÅÎÓÔ× ÒÁ×ÎÙ ÐÏ ÕÓÌÏ×ÉÀ, ÓÕÍÍÙ × ÐÒÁ×ÏÊ ÞÁÓÔÉ ÐÏ ÐÒÅÄÐÏÌÏÖÅÎÉÀ ÉÎÄÕËÃÉÉ. úÎÁÞÉÔ, ÒÁ×ÎÙ É ÏÓÔÁ×ÛÉÅÓÑ ÓÌÁÇÁÅÍÙÅ: f (i; S ) = f (j; S ).¥5.2.
áËÓÉÏÍÁÔÉËÉ ÄÌÑ ÎÏÒÍÉÒÏ×ÁÎÎÙÈ ÉÎÄÅËÓÏ× ×ÌÉÑÎÉÑéÎÄÅËÓÙ âÁÎÃÁÆÁ, äÖÏÎÓÔÏÎÁ, äÉÇÅÎÁ|ðÁËÅÌÁ É èÏÌÅÒÁ|ðÁËÅÌÁ ÕÄÏ×ÌÅÔ×ÏÒÑÀÔ ÁËÓÉÏÍÁÍ ÂÏÌ×ÁÎÁ, ÜÆÆÅËÔÉ×ÎÏÓÔÉ É ÁÎÏÎÉÍÎÏÓÔÉ. ðÅÒ×ÏÅ É ×ÔÏÒÏÅ ÓÌÅ107ÄÕÅÔ ÉÚ ÏÐÒÅÄÅÌÅÎÉÑ, ÔÒÅÔØÅ ÏÞÅ×ÉÄÎÏ. óÌÅÄÏ×ÁÔÅÌØÎÏ, ÎÉ ÏÄÉÎ ÉÚ ÜÔÉÈ ÉÎÄÅËÓÏ× ÎÅ ÕÄÏ×ÌÅÔ×ÏÒÑÅÔ ÁËÓÉÏÍÅ T, ÐÏÓËÏÌØËÕ ÅÄÉÎÓÔ×ÅÎÎÙÊ ÉÎÄÅËÓ, ÕÄÏ×ÌÅÔ×ÏÒÑÀÝÉÊ ×ÓÅÍ ÞÅÔÙÒÅÍ ÁËÓÉÏÍÁÍ | ÜÔÏ ÉÎÄÅËÓ ûÅÐÌÉ|ûÕÂÉËÁ. ðÏÜÔÏÍÕ ÄÌÑÁËÓÉÏÍÁÔÉÞÅÓËÏÇÏ ÏÐÉÓÁÎÉÑ ÜÔÉÈ ÉÎÄÅËÓÏ× ÎÕÖÎÏ ÞÅÍ-ÔÏ ÚÁÍÅÎÉÔØ ÁËÓÉÏÍÕ T.ðÒÏÓÔÙÅ ÉÇÒÙ v É w ÎÁÚÙ×ÁÀÔÓÑ ÏÂßÅÄÉÎÑÅÍÙÍÉ, ÅÓÌÉ ÉÈ ÍÉÎÉÍÁÌØÎÙÅ×ÙÉÇÒÙ×ÁÀÝÉÅ ËÏÁÌÉÃÉÉ ÎÅ ÓÏÄÅÒÖÁÔÓÑ ÏÄÎÁ × ÄÒÕÇÏÊ, Ô.Å. ÅÓÌÉ S ∈ M (v),S 0 ∈ M (w), ÔÏ S 6⊆ S 0 É S 0 6⊆ S .÷ [45, 46, 59] ÄÏËÁÚÙ×ÁÅÔÓÑ, ÞÔÏ ÁËÓÉÏÍÙ NP, E É An ÏÄÎÏÚÎÁÞÎÏ ÏÐÒÅÄÅÌÑÀÔ ÉÎÄÅËÓÙ äÉÇÅÎÁ|ðÁËÅÌÁ É èÏÌÅÒÁ|ðÁËÅÌÁ ×ÍÅÓÔÅ Ó ÓÏÏÔ×ÅÔÓÔ×ÕÀÝÅÊÁËÓÉÏÍÏÊ.áËÓÉÏÍÁ ÄÌÑ ÉÎÄÅËÓÁ äÉÇÅÎÁ|ðÁËÅÌÁ. äÌÑ ÌÀÂÙÈ ÏÂßÅÄÉÎÑÅÍÙÈ ÉÇÒvÉw(v ∨ w) =|M (v )|(v ) + |M (w)|(w):|M (v ∨ w)|áËÓÉÏÍÁ ÄÌÑ ÉÎÄÅËÓÁ èÏÌÅÒÁ|ðÁËÅÌÁ.
äÌÑ ÌÀÂÙÈ ÏÂßÅÄÉÎÑÅÍÙÈ ÉÇÒv É w É ÌÀÂÏÇÏ ÉÇÒÏËÁ ii(v ∨ w) =|ci (v )|(v ) + |ci (w)|(w);|ci (v ∨ w)|ÇÄÅ ci(v) | ÞÉÓÌÏ ÍÉÎÉÍÁÌØÎÙÈ ×ÙÉÇÒÙ×ÁÀÝÉÈ ËÏÁÌÉÃÉÊ, × ËÏÔÏÒÙÅ ×ÈÏÄÉÔÉÇÒÏË i.÷ ÐÁÒÁÇÒÁÆÅ 4.4.1 ÐÏËÁÚÙ×ÁÅÔÓÑ, ÞÔÏ ÁËÓÉÏÍÁ ÔÒÁÎÓÆÅÒÁ ÄÌÑ ÎÏÒÍÉÒÏ×ÁÎÎÏÇÏ ÉÎÄÅËÓÁ (Tn) ÉÇÒÁÅÔ ÔÕ ÖÅ ÒÏÌØ ÄÌÑ ÉÎÄÅËÓÁ âÁÎÃÁÆÁ.108çÌÁ×Á 3.ïÃÅÎËÉ É ÁÌÇÏÒÉÔÍÙ ÄÌÑ ÒÁÓÞÅÔÁÉÎÄÅËÓÏ× ×ÌÉÑÎÉÑ1. ôÅÏÒÅÍÁ Ï ÓÒÅÄÎÅÍ ÄÌÑ ÉÎÄÅËÓÏ× ×ÌÉÑÎÉÑëÁË ÕÖÅ ÏÂÓÕÖÄÁÌÏÓØ × ÐÁÒÁÇÒÁÆÅ 2.5, ×ÌÉÑÎÉÅ ÉÇÒÏËÁ × ÇÏÌÏÓÏ×ÁÎÉÉ Ó Ë×ÏÔÏÊ (ÎÅÚÁ×ÉÓÉÍÏ ÏÔ ÔÏÇÏ, ÐÏ ËÁËÏÍÕ ÉÚ ÉÎÄÅËÓÏ× ÏÎÏ ÓÞÉÔÁÌÏÓØ) ÎÅ ÐÒÏÐÏÒÃÉÏÎÁÌØÎÏ ÞÉÓÌÕ ÇÏÌÏÓÏ×, ÐÒÉÞÅÍ ×ÌÉÑÎÉÅ ÍÏÖÅÔ ÂÙÔØ ËÁË ÂÏÌØÛÅ, ÔÁË É ÍÅÎØÛÅÄÏÌÉ ÞÉÓÌÁ ÇÏÌÏÓÏ×, ÞÔÏ ÐÏËÁÚÙ×ÁÅÔ ÓÌÅÄÕÀÝÉÊ ÐÒÉÍÅÒ.ðÒÉÍÅÒ 1.
òÁÓÓÍÏÔÒÉÍ Ä×Á ÐÒÉÍÅÒÁ ÇÏÌÏÓÏ×ÁÎÉÊ Ó Ë×ÏÔÏÊ Ó ÔÒÅÍÑ ÕÞÁÓÔÎÉËÁÍÉ. éÇÒÏË A ÉÍÅÅÔ 2 ÇÏÌÏÓÁ, B É C ÐÏ ÏÄÎÏÍÕ, Ô.Å. A ÏÂÌÁÄÁÅÔ ÐÏÌÏ×ÉÎÏÊ×ÓÅÈ ÇÏÌÏÓÏ×, B É C | ÞÅÔ×ÅÒÔØÀ ËÁÖÄÙÊ.1) ðÕÓÔØ Ë×ÏÔÁ ÒÁ×ÎÁ 3. ÷ÙÉÇÒÙ×ÁÀÝÉÍÉ ËÏÁÌÉÃÉÑÍÉ ÂÕÄÕÔ A + B , A + C ,A + B + C . éÇÒÏË A ËÌÀÞÅ×ÏÊ ×Ï ×ÓÅÈ ÔÒÅÈ ËÏÁÌÉÃÉÑÈ, B | × A + B , C | ×A + C .
BzA = 3=5, BzB = BzC = 1=5.2) ðÕÓÔØ ÔÅÐÅÒØ Ë×ÏÔÁ ÒÁ×ÎÁ 4. ÷ÙÉÇÒÙ×ÁÀÝÅÊ ÂÕÄÅÔ ÔÏÌØËÏ ËÏÁÌÉÃÉÑ A +B + C , × ËÏÔÏÒÏÊ ËÌÀÞÅ×ÙÍÉ ÂÕÄÕÔ ×ÓÅ ÔÒÉ ÉÇÒÏËÁ. BzA = BzB = BzC = 1=3.÷ ÐÅÒ×ÏÊ ÞÁÓÔÉ ÐÒÉÍÅÒÁ ×ÌÉÑÎÉÅ ÉÇÒÏËÏ× A ÂÏÌØÛÅ ÄÏÌÉ ÅÇÏ ÇÏÌÏÓÏ×, ×ÌÉÑÎÉÅB É C ÍÅÎØÛÅ. ÷Ï ×ÔÏÒÏÊ ÞÁÓÔÉ | ÎÁÏÂÏÒÏÔ. ÷ÏÚÎÉËÁÅÔ ÐÏÄÏÚÒÅÎÉÅ, ÞÔÏ "×109ÓÒÅÄÎÅÍ ÐÏ Ë×ÏÔÅ" ×ÌÉÑÎÉÅ ÉÇÒÏËÁ ÐÒÏÐÏÒÃÉÏÎÁÌØÎÏ ÞÉÓÌÕ ÅÇÏ ÇÏÌÏÓÏ×.äÌÑ ÉÎÄÅËÓÁ âÁÎÃÁÆÁ (É ÌÀÂÏÇÏ ÄÒÕÇÏÇÏ ÉÎÄÅËÓÁ, ÎÅ ÕÄÏ×ÌÅÔ×ÏÒÑÀÝÅÇÏ ÁËÓÉÏÍÅ ÁÄÄÉÔÉ×ÎÏÓÔÉ) ÓÔÒÏÇÏ ÓÆÏÒÍÕÌÉÒÏ×ÁÔØ ÜÔÏ ÕÔ×ÅÒÖÄÅÎÉÅ ÐÒÏÂÌÅÍÁÔÉÞÎÏ.îÏ ÄÌÑ ÁÄÄÉÔÉ×ÎÙÈ ÉÎÄÅËÓÏ× ×ÌÉÑÎÉÑ ÍÏÖÎÏ ÐÒÏ×ÅÓÔÉ ÓÌÅÄÕÀÝÅÅ ÒÁÓÓÕÖÄÅÎÉÅ.ïÂÏÚÎÁÞÉÍ ÞÅÒÅÚ vq ÇÏÌÏÓÏ×ÁÎÉÅ Ó Ë×ÏÔÏÊ (q; w1; : : : ; wn), Ô.Å.
ÞÉÓÌÏ ÇÏÌÏÓÏ×ÕÞÁÓÔÎÉËÏ× ÆÉËÓÉÒÏ×ÁÎÏ, q | ÐÁÒÁÍÅÔÒ.ðÕÓÔØ ÉÎÄÅËÓ ×ÌÉÑÎÉÑ ÕÄÏ×ÌÅÔ×ÏÒÑÅÔ ÁËÓÉÏÍÁÍ NP É T. ôÏÇÄÁ ÐÏ ÐÅÒ×ÏÊÞÁÓÔÉ ÔÅÏÒÅÍÙ 5 ÓÕÝÅÓÔ×ÕÀÔ ÔÁËÉÅ ÞÉÓÌÁ g(i; S ), ÞÔÏi(v) =XS ∈Wi (v)g(i; S );(3.1)äÌÑ "ÕÓÒÅÄÎÅÎÉÑ" ÒÁÓÓÍÏÔÒÉÍ (É ×ÙÞÉÓÌÉÍ) ÉÎÔÅÇÒÁÌ ÐÏ Ë×ÏÔÅ ÏÔ ×ÌÉÑÎÉÑÉÇÒÏËÁ iZ∞0i(vq ) dq:âÅÓËÏÎÅÞÎÏÓÔØ × ËÁÞÅÓÔ×Å ×ÅÒÈÎÅÇÏ ÐÒÅÄÅÌÁ ÉÎÔÅÇÒÉÒÏ×ÁÎÉÑ ÐÏÓÔÁ×ÌÅÎÁ ÔÏÌØËÏ ÄÌÑ ÅÓÔÅÓÔ×ÅÎÎÏÓÔÉ ÆÏÒÍÕÌÉÒÏ×ËÉ. äÅÊÓÔ×ÉÔÅÌØÎÏ, ÅÓÌÉ Ë×ÏÔÁ ÂÏÌØÛÅ w(N )(ÓÕÍÍÙ ÇÏÌÏÓÏ× ×ÓÅÈ ÉÇÒÏËÏ×), × ÉÇÒÅ ÎÅ ÂÕÄÅÔ ×ÙÉÇÒÙ×ÁÀÝÉÈ ËÏÁÌÉÃÉÊ, Wi(v) =∅É, ÐÏ ÆÏÒÍÕÌÅ (3.1), i(vq ) = 0 ÄÌÑ ×ÓÅÈ i.
ðÏÜÔÏÍÕZ∞0úÁÍÅÔÉÍ, ÞÔÏi(vq ) dq =v(S ) − v(S \ {i}) =Z w (N )0i(vq ) dq:(3.2)1; ÅÓÌÉ i ËÌÀÞÅ×ÏÊ × S ;0; ÉÎÁÞÅ,ÐÏÜÔÏÍÕ × ÆÏÒÍÕÌÅ (3.1) ÓÕÍÍÉÒÏ×ÁÎÉÅ ÔÏÌØËÏ ÐÏ ËÌÀÞÅ×ÙÍ ËÏÁÌÉÃÉÑÍ ÍÏÖÎÏ ÚÁÍÅÎÉÔØ ÎÁ ÓÕÍÍÉÒÏ×ÁÎÉÅ ÐÏ ×ÓÅÍ ËÏÁÌÉÃÉÑÍ Ó ÕÍÎÏÖÅÎÉÅÍ ÓÌÁÇÁÅÍÙÈ ÎÁv(S ) − v(S \ {i}):110i(v) =XS ⊆Ng(i; S ) (vq (S ) − vq (S \ {i})) :ðÏÄÓÔÁ×ÉÍ i(v) × ÆÏÒÍÕÌÕ (3:2) É ÐÏÍÅÎÑÅÍ ÐÏÒÑÄÏË ÓÕÍÍÉÒÏ×ÁÎÉÑ É ÉÎÔÅÇÒÉÒÏ×ÁÎÉÑ. üÔÏ ÍÏÖÎÏ ÓÄÅÌÁÔØ, ÔÁË ËÁË ÓÕÍÍÁ ËÏÎÅÞÎÁ É ÉÎÔÅÇÒÉÒÏ×ÁÎÉÅÐÒÏÉÓÈÏÄÉÔ ÐÏ ÏÔÒÅÚËÕ.Z w(N )0i(vq ) dq =Z w(N ) X0S ⊆Ng(i; S ) (vq (S ) − vq (S \ {i})) dq ==X Z w (N )S ⊆N 0g(i; S ) (vq (S ) − vq (S \ {i})) dq:òÁÓÓÍÏÔÒÉÍ ÐÏÄÙÎÔÅÇÒÁÌØÎÕÀ ÆÕÎËÃÉÀ (É ÏÂÏÚÎÁÞÉÍ ÅÅ ÞÅÒÅÚ h(q)).
åÓÌÉi ∈= S , ÔÏ S = S \ {i} É h(q) = 0, ÐÏÜÔÏÍÕ ÉÎÔÅÇÒÁÌ ÏÔ ÎÅÅ ÒÁ×ÅÎ 0.åÓÌÉ i ∈ S , ÔÏ h(q) ÒÁ×ÎÁ ÌÉÂÏ 0, ÌÉÂÏ g(i; S ), ÐÒÉÞÅÍ f (q) = g(i; S ), ÅÓÌÉ ÉÔÏÌØËÏ ÅÓÌÉ S ×ÙÉÇÒÙ×ÁÀÝÁÑ É i | ËÌÀÞÅ×ÏÊ ÕÞÁÓÔÎÉË × S , Ô.Å. w(S ) − ki <q ≤ w(s).h(q)g(i, s)0w(S) − wiw(S)qòÉÓ. 3.1.éÎÔÅÇÒÁÌ ÏÔ ÆÕÎËÃÉÉ ÅÓÔØ ÐÌÏÝÁÄØ ÐÏÄ ÅÅ ÇÒÁÆÉËÏÍ, ÐÏÜÔÏÍÕ ÉÎÔÅÇÒÁÌ ÏÔf (q) | ÐÌÏÝÁÄØ ÐÒÑÍÏÕÇÏÌØÎÉËÁ ×ÙÓÏÔÙ g(i; S ) É ÄÌÉÎÙ wi, ÒÁ×ÎÁÑ wi · g(i; S ).éÔÁË111Z∞0i(vq ) dq =XS 3iwi · g(i; S ) = wi ·XS 3ig(i; S ):(3.3)óÌÅÄÕÀÝÁÑ ÔÅÏÒÅÍÁ ÂÕÄÅÔ ÓÌÅÄÓÔ×ÉÅÍ ÆÏÒÍÕÌÙ (3.3)ôÅÏÒÅÍÁ 1. 1) äÌÑ |ÉÎÄÅËÓÁ:Z∞0i(vq ) dq = wi ·XS 3if (i; S ):2) ðÕÓÔØ ÉÎÄÅËÓ ×ÌÉÑÎÉÑ (v) ÕÄÏ×ÌÅÔ×ÏÒÑÅÔ ÁËÓÉÏÍÁÍ NP, T É SymGL.ôÏÇÄÁR∞0i(vq ) dq ÐÒÏÐÏÒÃÉÏÎÁÌÅÎ wi.3) äÌÑ ÉÎÄÅËÓÏ× ðÅÎÒÏÕÚÁ É ûÅÐÌÉ|ûÕÂÉËÁ:Z∞0Pi(vq ) dq =Z∞0SSi(vq ) dq = wi:äÏËÁÚÁÔÅÌØÓÔ×Ï.
1) óÌÅÄÕÅÔ ÉÚ ÔÏÇÏ, ÞÔÏ -ÉÎÄÅËÓ ÕÄÏ×ÌÅÔ×ÏÒÑÅÔ ÆÏÒÍÕÌÅ(3.1) ÐÒÉ g(i; S ) = f (i; S ).2) ðÏ ÞÁÓÔÉ 3) ÔÅÏÒÅÍÙ 5 × ÜÔÏÍ ÓÌÕÞÁÅi(v) =XS ∈Wi (v)g(|S |);ÐÏÜÔÏÍÕZ0∞i(vq ) dq = wi ·XS 3ig(|S |) dq:ïÓÔÁÌÏÓØ ÚÁÍÅÔÉÔØ, ÞÔÏ ×ÔÏÒÏÊ ÍÎÏÖÉÔÅÌØ ÎÅ ÚÁ×ÉÓÉÔ ÏÔ i.3) éÎÄÅËÓÙ ðÅÎÒÏÕÚÁ É ûÅÐÌÉ|ûÕÂÉËÁ ÍÏÖÎÏ ÒÁÓÓÍÁÔÒÉ×ÁÔØ, ËÁË ÞÁÓÔÎÙÊÓÌÕÞÁÊ -ÉÎÄÅËÓÁ. ðÏÜÔÏÍÕ ÄÏÓÔÁÔÏÞÎÏ ÄÏËÁÚÁÔØ ÞÔÏ ÎÉÈÃXS 3i!f (i; S ) = 1:112äÌÑ ÉÎÄÅËÓÁ ðÅÎÒÏÕÚÁ f (i; S ) = 1=2n−1 ÉXS 3i12n−111|{S ⊂ N |i ∈ S }| = n−1 · 2n−1n−122== 1:äÌÑ ÉÎÄÅËÓÁ ûÅÐÌÉ|ûÕÂÉËÁ f (i; S ) = (s − 1)!(n − s)!=n! ÉX (s − 1)!(n − s)!S 3in!=nX(k − 1)!(n − k)!n!k=1· |{S ⊂ N |i ∈ S; |S | = k }| =µ¶nX(k − 1)!(n − k)! n − 1·==n!k−1k=1=nX(k − 1)!(n − k)!k=1n!n(k − 1)!(n − k)! X1·== 1:(n − 1)!nk=1¥úÁÍÅÞÁÎÉÅ 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
