Π‘Π°ΠΊΠ°Π»Π°Π²Ρ€
Π”ΠΈΠΏΠ»ΠΎΠΌΠ½Ρ‹Π΅ ΠΈ курсовыС Π½Π° Π·Π°ΠΊΠ°Π·

ΠΠΎΡ€ΠΌΠ°Π»ΡŒΠ½Π°Ρ Ρ„ΠΎΡ€ΠΌΠ°. 
ΠœΠ°Ρ‚Π΅ΠΌΠ°Ρ‚ΠΈΡ‡Π΅ΡΠΊΠ°Ρ тСория ΠΈΠ³Ρ€

Π Π΅Ρ„Π΅Ρ€Π°Ρ‚ΠŸΠΎΠΌΠΎΡ‰ΡŒ Π² Π½Π°ΠΏΠΈΡΠ°Π½ΠΈΠΈΠ£Π·Π½Π°Ρ‚ΡŒ ΡΡ‚ΠΎΠΈΠΌΠΎΡΡ‚ΡŒΠΌΠΎΠ΅ΠΉ Ρ€Π°Π±ΠΎΡ‚Ρ‹

Π’ ΠΊΠΎΠΎΠΏΠ΅Ρ€Π°Ρ‚ΠΈΠ²Π½Ρ‹Ρ… ΠΈΠ³Ρ€Π°Ρ… с Ρ‚Ρ€Π°Π½ΡΡ„Π΅Ρ€Π°Π±Π΅Π»ΡŒΠ½ΠΎΠΉ ΠΏΠΎΠ»Π΅Π·Π½ΠΎΡΡ‚ΡŒΡŽ, Ρ‚ΠΎ Π΅ΡΡ‚ΡŒ Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎΡΡ‚ΡŒΡŽ ΠΏΠ΅Ρ€Π΅Π΄Π°Ρ‡ΠΈ срСдств ΠΎΡ‚ ΠΎΠ΄Π½ΠΎΠ³ΠΎ ΠΈΠ³Ρ€ΠΎΠΊΠ° ΠΊ Π΄Ρ€ΡƒΠ³ΠΎΠΌΡƒ, Π½Π΅Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎ ΠΏΡ€ΠΈΠΌΠ΅Π½ΡΡ‚ΡŒ понятиС ΠΈΠ½Π΄ΠΈΠ²ΠΈΠ΄ΡƒΠ°Π»ΡŒΠ½Ρ‹Ρ… ΠΏΠ»Π°Ρ‚Π΅ΠΆΠ΅ΠΉ. ВмСсто этого ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡŽΡ‚ Ρ‚Π°ΠΊ Π½Π°Π·Ρ‹Π²Π°Π΅ΠΌΡƒΡŽ Ρ…Π°Ρ€Π°ΠΊΡ‚Π΅Ρ€ΠΈΡΡ‚ΠΈΡ‡Π΅ΡΠΊΡƒΡŽ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΡŽ, ΠΎΠΏΡ€Π΅Π΄Π΅Π»ΡΡŽΡ‰ΡƒΡŽ Π²Ρ‹ΠΈΠ³Ρ€Ρ‹Ρˆ ΠΊΠ°ΠΆΠ΄ΠΎΠΉ ΠΊΠΎΠ°Π»ΠΈΡ†ΠΈΠΈ ΠΈΠ³Ρ€ΠΎΠΊΠΎΠ². ΠŸΡ€ΠΈ этом прСдполагаСтся, Ρ‡Ρ‚ΠΎ Π²Ρ‹ΠΈΠ³Ρ€Ρ‹Ρˆ пустой ΠΊΠΎΠ°Π»ΠΈΡ†ΠΈΠΈ Ρ€Π°Π²Π΅Π½ Π½ΡƒΠ»ΡŽ. Π˜Π³Ρ€ΠΎΠΊΠΈ Π²Ρ‹Π±ΠΈΡ€Π°Π»ΠΈ стратСгии с ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹ΠΌ для… Π§ΠΈΡ‚Π°Ρ‚ΡŒ Π΅Ρ‰Ρ‘ >

ΠΠΎΡ€ΠΌΠ°Π»ΡŒΠ½Π°Ρ Ρ„ΠΎΡ€ΠΌΠ°. ΠœΠ°Ρ‚Π΅ΠΌΠ°Ρ‚ΠΈΡ‡Π΅ΡΠΊΠ°Ρ тСория ΠΈΠ³Ρ€ (Ρ€Π΅Ρ„Π΅Ρ€Π°Ρ‚, курсовая, Π΄ΠΈΠΏΠ»ΠΎΠΌ, ΠΊΠΎΠ½Ρ‚Ρ€ΠΎΠ»ΡŒΠ½Π°Ρ)

Π’ Π½ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½ΠΎΠΉ, ΠΈΠ»ΠΈ стратСгичСской, Ρ„ΠΎΡ€ΠΌΠ΅ ΠΈΠ³Ρ€Π° описываСтся ΠΏΠ»Π°Ρ‚Ρ‘ΠΆΠ½ΠΎΠΉ ΠΌΠ°Ρ‚Ρ€ΠΈΡ†Π΅ΠΉ. КаТдая сторона (Ρ‚ΠΎΡ‡Π½Π΅Π΅, ΠΈΠ·ΠΌΠ΅Ρ€Π΅Π½ΠΈΠ΅) ΠΌΠ°Ρ‚Ρ€ΠΈΡ†Ρ‹ — это ΠΈΠ³Ρ€ΠΎΠΊ, строки ΠΎΠΏΡ€Π΅Π΄Π΅Π»ΡΡŽΡ‚ стратСгии ΠΏΠ΅Ρ€Π²ΠΎΠ³ΠΎ ΠΈΠ³Ρ€ΠΎΠΊΠ°, Π° ΡΡ‚ΠΎΠ»Π±Ρ†Ρ‹ — Π²Ρ‚ΠΎΡ€ΠΎΠ³ΠΎ. На ΠΏΠ΅Ρ€Π΅ΡΠ΅Ρ‡Π΅Π½ΠΈΠΈ Π΄Π²ΡƒΡ… стратСгий ΠΌΠΎΠΆΠ½ΠΎ ΡƒΠ²ΠΈΠ΄Π΅Ρ‚ΡŒ Π²Ρ‹ΠΈΠ³Ρ€Ρ‹ΡˆΠΈ, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ ΠΏΠΎΠ»ΡƒΡ‡Π°Ρ‚ ΠΈΠ³Ρ€ΠΎΠΊΠΈ. Π’ ΠΏΡ€ΠΈΠΌΠ΅Ρ€Π΅ справа, Ссли ΠΈΠ³Ρ€ΠΎΠΊ 1 Π²Ρ‹Π±ΠΈΡ€Π°Π΅Ρ‚ ΠΏΠ΅Ρ€Π²ΡƒΡŽ ΡΡ‚Ρ€Π°Ρ‚Π΅Π³ΠΈΡŽ, Π° Π²Ρ‚ΠΎΡ€ΠΎΠΉ ΠΈΠ³Ρ€ΠΎΠΊ — Π²Ρ‚ΠΎΡ€ΡƒΡŽ ΡΡ‚Ρ€Π°Ρ‚Π΅Π³ΠΈΡŽ, Ρ‚ΠΎ Π½Π° ΠΏΠ΅Ρ€Π΅ΡΠ΅Ρ‡Π΅Π½ΠΈΠΈ ΠΌΡ‹ Π²ΠΈΠ΄ΠΈΠΌ (?1, ?1), это Π·Π½Π°Ρ‡ΠΈΡ‚, Ρ‡Ρ‚ΠΎ Π² Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚Π΅ Ρ…ΠΎΠ΄Π° ΠΎΠ±Π° ΠΈΠ³Ρ€ΠΎΠΊΠ° потСряли ΠΏΠΎ ΠΎΠ΄Π½ΠΎΠΌΡƒ ΠΎΡ‡ΠΊΡƒ.

Π˜Π³Ρ€ΠΎΠΊΠΈ Π²Ρ‹Π±ΠΈΡ€Π°Π»ΠΈ стратСгии с ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹ΠΌ для сСбя Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚ΠΎΠΌ, Π½ΠΎ ΠΏΡ€ΠΎΠΈΠ³Ρ€Π°Π»ΠΈ, ΠΈΠ·-Π·Π° нСзнания Ρ…ΠΎΠ΄Π° Π΄Ρ€ΡƒΠ³ΠΎΠ³ΠΎ ΠΈΠ³Ρ€ΠΎΠΊΠ°. ΠžΠ±Ρ‹Ρ‡Π½ΠΎ Π² Π½ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½ΠΎΠΉ Ρ„ΠΎΡ€ΠΌΠ΅ ΠΏΡ€Π΅Π΄ΡΡ‚Π°Π²Π»ΡΡŽΡ‚ΡΡ ΠΈΠ³Ρ€Ρ‹, Π² ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… Ρ…ΠΎΠ΄Ρ‹ Π΄Π΅Π»Π°ΡŽΡ‚ΡΡ ΠΎΠ΄Π½ΠΎΠ²Ρ€Π΅ΠΌΠ΅Π½Π½ΠΎ, ΠΈΠ»ΠΈ хотя Π±Ρ‹ полагаСтся, Ρ‡Ρ‚ΠΎ всС ΠΈΠ³Ρ€ΠΎΠΊΠΈ Π½Π΅ Π·Π½Π°ΡŽΡ‚ ΠΎ Ρ‚ΠΎΠΌ, Ρ‡Ρ‚ΠΎ Π΄Π΅Π»Π°ΡŽΡ‚ Π΄Ρ€ΡƒΠ³ΠΈΠ΅ участники.

Π₯арактСристичСская функция

Π’ ΠΊΠΎΠΎΠΏΠ΅Ρ€Π°Ρ‚ΠΈΠ²Π½Ρ‹Ρ… ΠΈΠ³Ρ€Π°Ρ… с Ρ‚Ρ€Π°Π½ΡΡ„Π΅Ρ€Π°Π±Π΅Π»ΡŒΠ½ΠΎΠΉ ΠΏΠΎΠ»Π΅Π·Π½ΠΎΡΡ‚ΡŒΡŽ, Ρ‚ΠΎ Π΅ΡΡ‚ΡŒ Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎΡΡ‚ΡŒΡŽ ΠΏΠ΅Ρ€Π΅Π΄Π°Ρ‡ΠΈ срСдств ΠΎΡ‚ ΠΎΠ΄Π½ΠΎΠ³ΠΎ ΠΈΠ³Ρ€ΠΎΠΊΠ° ΠΊ Π΄Ρ€ΡƒΠ³ΠΎΠΌΡƒ, Π½Π΅Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎ ΠΏΡ€ΠΈΠΌΠ΅Π½ΡΡ‚ΡŒ понятиС ΠΈΠ½Π΄ΠΈΠ²ΠΈΠ΄ΡƒΠ°Π»ΡŒΠ½Ρ‹Ρ… ΠΏΠ»Π°Ρ‚Π΅ΠΆΠ΅ΠΉ. ВмСсто этого ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡŽΡ‚ Ρ‚Π°ΠΊ Π½Π°Π·Ρ‹Π²Π°Π΅ΠΌΡƒΡŽ Ρ…Π°Ρ€Π°ΠΊΡ‚Π΅Ρ€ΠΈΡΡ‚ΠΈΡ‡Π΅ΡΠΊΡƒΡŽ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΡŽ, ΠΎΠΏΡ€Π΅Π΄Π΅Π»ΡΡŽΡ‰ΡƒΡŽ Π²Ρ‹ΠΈΠ³Ρ€Ρ‹Ρˆ ΠΊΠ°ΠΆΠ΄ΠΎΠΉ ΠΊΠΎΠ°Π»ΠΈΡ†ΠΈΠΈ ΠΈΠ³Ρ€ΠΎΠΊΠΎΠ². ΠŸΡ€ΠΈ этом прСдполагаСтся, Ρ‡Ρ‚ΠΎ Π²Ρ‹ΠΈΠ³Ρ€Ρ‹Ρˆ пустой ΠΊΠΎΠ°Π»ΠΈΡ†ΠΈΠΈ Ρ€Π°Π²Π΅Π½ Π½ΡƒΠ»ΡŽ.

Основания Ρ‚Π°ΠΊΠΎΠ³ΠΎ ΠΏΠΎΠ΄Ρ…ΠΎΠ΄Π° ΠΌΠΎΠΆΠ½ΠΎ Π½Π°ΠΉΡ‚ΠΈ Π΅Ρ‰Ρ‘ Π² ΠΊΠ½ΠΈΠ³Π΅ Ρ„ΠΎΠ½ НСймана ΠΈ ΠœΠΎΡ€Π³Π΅Π½ΡˆΡ‚Π΅Ρ€Π½Π°. Π˜Π·ΡƒΡ‡Π°Ρ Π½ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½ΡƒΡŽ Ρ„ΠΎΡ€ΠΌΡƒ для ΠΊΠΎΠ°Π»ΠΈΡ†ΠΈΠΎΠ½Π½Ρ‹Ρ… ΠΈΠ³Ρ€, ΠΎΠ½ΠΈ рассудили, Ρ‡Ρ‚ΠΎ Ссли Π² ΠΈΠ³Ρ€Π΅ с Π΄Π²ΡƒΠΌΡ сторонами образуСтся коалиция C, Ρ‚ΠΎ ΠΏΡ€ΠΎΡ‚ΠΈΠ² Π½Π΅Ρ‘ выступаСт коалиция N C. ΠžΠ±Ρ€Π°Π·ΡƒΠ΅Ρ‚ΡΡ ΠΊΠ°ΠΊ Π±Ρ‹ ΠΈΠ³Ρ€Π° для Π΄Π²ΡƒΡ… ΠΈΠ³Ρ€ΠΎΠΊΠΎΠ². Но Ρ‚Π°ΠΊ ΠΊΠ°ΠΊ Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ΠΎΠ² Π²ΠΎΠ·ΠΌΠΎΠΆΠ½Ρ‹Ρ… ΠΊΠΎΠ°Π»ΠΈΡ†ΠΈΠΉ ΠΌΠ½ΠΎΠ³ΠΎ (Π° ΠΈΠΌΠ΅Π½Π½ΠΎ 2N, Π³Π΄Π΅ N — количСство ΠΈΠ³Ρ€ΠΎΠΊΠΎΠ²), Ρ‚ΠΎ Π²Ρ‹ΠΈΠ³Ρ€Ρ‹Ρˆ для C Π±ΡƒΠ΄Π΅Ρ‚ Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΉ характСристичСской Π²Π΅Π»ΠΈΡ‡ΠΈΠ½ΠΎΠΉ, зависящСй ΠΎΡ‚ ΡΠΎΡΡ‚Π°Π²Π° ΠΊΠΎΠ°Π»ΠΈΡ†ΠΈΠΈ. Π€ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½ΠΎ ΠΈΠ³Ρ€Π° Π² Ρ‚Π°ΠΊΠΎΠΉ Ρ„ΠΎΡ€ΠΌΠ΅ (Ρ‚Π°ΠΊΠΆΠ΅ называСмая TU-ΠΈΠ³Ρ€ΠΎΠΉ[7]) прСдставляСтся ΠΏΠ°Ρ€ΠΎΠΉ (N, v), Π³Π΄Π΅ N — мноТСство всСх ΠΈΠ³Ρ€ΠΎΠΊΠΎΠ², Π° v: 2N > R — это характСристичСская функция.

Подобная Ρ„ΠΎΡ€ΠΌΠ° прСдставлСния ΠΌΠΎΠΆΠ΅Ρ‚ Π±Ρ‹Ρ‚ΡŒ ΠΏΡ€ΠΈΠΌΠ΅Π½Π΅Π½Π° для всСх ΠΈΠ³Ρ€, Π² Ρ‚ΠΎΠΌ числС Π±Π΅Π· Ρ‚Ρ€Π°Π½ΡΡ„Π΅Ρ€Π°Π±Π΅Π»ΡŒΠ½ΠΎΠΉ полСзности. Π’ Π½Π°ΡΡ‚оящСС врСмя ΡΡƒΡ‰Π΅ΡΡ‚Π²ΡƒΡŽΡ‚ способы пСрСвСсти Π»ΡŽΠ±ΡƒΡŽ ΠΈΠ³Ρ€Ρƒ ΠΈΠ· Π½ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½ΠΎΠΉ Ρ„ΠΎΡ€ΠΌΡ‹ Π² Ρ…Π°Ρ€Π°ΠΊΡ‚Π΅Ρ€ΠΈΡΡ‚ΠΈΡ‡Π΅ΡΠΊΡƒΡŽ, Π½ΠΎ ΠΏΡ€Π΅ΠΎΠ±Ρ€Π°Π·ΠΎΠ²Π°Π½ΠΈΠ΅ Π² ΠΎΠ±Ρ€Π°Ρ‚Π½ΡƒΡŽ сторону Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎ Π½Π΅ Π²ΠΎ Π²ΡΠ΅Ρ… случаях.

ΠΈΠ³Ρ€Π° экстСнсивный ΠΊΠΎΠΎΠΏΠ΅Ρ€Π°Ρ‚ΠΈΠ²Π½Ρ‹ΠΉ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½Ρ‹ΠΉ.

ΠŸΠΎΠΊΠ°Π·Π°Ρ‚ΡŒ вСсь тСкст
Π—Π°ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Ρ„ΠΎΡ€ΠΌΡƒ Ρ‚Π΅ΠΊΡƒΡ‰Π΅ΠΉ Ρ€Π°Π±ΠΎΡ‚ΠΎΠΉ