Π”ΠΈΠΏΠ»ΠΎΠΌΡ‹, курсовыС, Ρ€Π΅Ρ„Π΅Ρ€Π°Ρ‚Ρ‹, ΠΊΠΎΠ½Ρ‚Ρ€ΠΎΠ»ΡŒΠ½Ρ‹Π΅...
Брочная ΠΏΠΎΠΌΠΎΡ‰ΡŒ Π² ΡƒΡ‡Ρ‘Π±Π΅

ΠœΠ΅Ρ‚ΠΎΠ΄ Π²Π΅Ρ‚Π²Π΅ΠΉ ΠΈ Π³Ρ€Π°Π½ΠΈΡ†

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

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

ΠœΠ΅Ρ‚ΠΎΠ΄ Π²Π΅Ρ‚Π²Π΅ΠΉ ΠΈ Π³Ρ€Π°Π½ΠΈΡ† (Ρ€Π΅Ρ„Π΅Ρ€Π°Ρ‚, курсовая, Π΄ΠΈΠΏΠ»ΠΎΠΌ, ΠΊΠΎΠ½Ρ‚Ρ€ΠΎΠ»ΡŒΠ½Π°Ρ)

К ΠΈΠ΄Π΅Π΅ ΠΌΠ΅Ρ‚ΠΎΠ΄Π° Π²Π΅Ρ‚Π²Π΅ΠΉ ΠΈ Π³Ρ€Π°Π½ΠΈΡ† ΠΏΡ€ΠΈΡ…ΠΎΠ΄ΠΈΠ»ΠΈ ΠΌΠ½ΠΎΠ³ΠΈΠ΅ исслСдоватСли, Π½ΠΎ Π›ΠΈΡ‚Ρ‚Π» с ΡΠΎΠ°Π²Ρ‚ΠΎΡ€Π°ΠΌΠΈ Π½Π° ΠΎΡΠ½ΠΎΠ²Π΅ ΡƒΠΊΠ°Π·Π°Π½Π½ΠΎΠ³ΠΎ ΠΌΠ΅Ρ‚ΠΎΠ΄Π° Ρ€Π°Π·Ρ€Π°Π±ΠΎΡ‚Π°Π»ΠΈ ΡƒΠ΄Π°Ρ‡Π½Ρ‹ΠΉ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ Π—Πš ΠΈ Ρ‚Π΅ΠΌ самым способствовали популяризации ΠΏΠΎΠ΄Ρ…ΠΎΠ΄Π°. Π‘ Ρ‚Π΅Ρ… ΠΏΠΎΡ€ ΠΌΠ΅Ρ‚ΠΎΠ΄ Π²Π΅Ρ‚Π²Π΅ΠΉ ΠΈ Π³Ρ€Π°Π½ΠΈΡ† Π±Ρ‹Π» ΡƒΡΠΏΠ΅ΡˆΠ½ΠΎ ΠΏΡ€ΠΈΠΌΠ΅Π½Π΅Π½ ΠΊΠΎ ΠΌΠ½ΠΎΠ³ΠΈΠΌ Π·Π°Π΄Π°Ρ‡Π°ΠΌ, для Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ Π—Πš Π±Ρ‹Π»ΠΎ ΠΏΡ€ΠΈΠ΄ΡƒΠΌΠ°Π½ΠΎ нСсколько Π΄Ρ€ΡƒΠ³ΠΈΡ… ΠΌΠΎΠ΄ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠΉ ΠΌΠ΅Ρ‚ΠΎΠ΄Π°, Π½ΠΎ Π² Π±ΠΎΠ»ΡŒΡˆΠΈΠ½ΡΡ‚Π²Π΅ ΡƒΡ‡Π΅Π±Π½ΠΈΠΊΠΎΠ² излагаСтся пионСрская Ρ€Π°Π±ΠΎΡ‚Π° Π›ΠΈΡ‚Ρ‚Π»Π°.

ΠžΠ±Ρ‰Π°Ρ идСя Ρ‚Ρ€ΠΈΠ²ΠΈΠ°Π»ΡŒΠ½Π°: Π½ΡƒΠΆΠ½ΠΎ Ρ€Π°Π·Π΄Π΅Π»ΠΈΡ‚ΡŒ ΠΎΠ³Ρ€ΠΎΠΌΠ½ΠΎΠ΅ число ΠΏΠ΅Ρ€Π΅Π±ΠΈΡ€Π°Π΅ΠΌΡ‹Ρ… Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ΠΎΠ² Π½Π° ΠΊΠ»Π°ΡΡΡ‹ ΠΈ ΠΏΠΎΠ»ΡƒΡ‡ΠΈΡ‚ΡŒ ΠΎΡ†Π΅Π½ΠΊΠΈ (снизу — Π² Π·Π°Π΄Π°Ρ‡Π΅ ΠΌΠΈΠ½ΠΈΠΌΠΈΠ·Π°Ρ†ΠΈΠΈ, свСрху — Π² Π·Π°Π΄Π°Ρ‡Π΅ максимизации) для этих классов, Ρ‡Ρ‚ΠΎΠ±Ρ‹ ΠΈΠΌΠ΅Ρ‚ΡŒ Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ ΠΎΡ‚Π±Ρ€Π°ΡΡ‹Π²Π°Ρ‚ΡŒ Π²Π°Ρ€ΠΈΠ°Π½Ρ‚Ρ‹ Π½Π΅ ΠΏΠΎ ΠΎΠ΄Π½ΠΎΠΌΡƒ, Π° Ρ†Π΅Π»Ρ‹ΠΌΠΈ классами. Π’Ρ€ΡƒΠ΄Π½ΠΎΡΡ‚ΡŒ состоит Π² Ρ‚ΠΎΠΌ, Ρ‡Ρ‚ΠΎΠ±Ρ‹ Π½Π°ΠΉΡ‚ΠΈ Ρ‚Π°ΠΊΠΎΠ΅ Ρ€Π°Π·Π΄Π΅Π»Π΅Π½ΠΈΠ΅ Π½Π° ΠΊΠ»Π°ΡΡΡ‹ (Π²Π΅Ρ‚Π²ΠΈ) ΠΈ Ρ‚Π°ΠΊΠΈΠ΅ ΠΎΡ†Π΅Π½ΠΊΠΈ (Π³Ρ€Π°Π½ΠΈΡ†Ρ‹), Ρ‡Ρ‚ΠΎΠ±Ρ‹ ΠΏΡ€ΠΎΡ†Π΅Π΄ΡƒΡ€Π° Π±Ρ‹Π»Π° эффСктивной.

ИзлоТим Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ Π›ΠΈΡ‚Ρ‚Π»Π° Π½Π° ΠΏΡ€ΠΈΠΌΠ΅Ρ€Π΅ 1 ΠΏΡ€Π΅Π΄Ρ‹Π΄ΡƒΡ‰Π΅Π³ΠΎ Ρ€Π°Π·Π΄Π΅Π»Π°. ΠŸΠΎΠ²Ρ‚ΠΎΡ€Π½ΠΎ запишСм ΠΌΠ°Ρ‚Ρ€ΠΈΡ†Ρƒ:

Ρ‚Π°Π±Π». 2.

;

Ρ‚Π°Π±Π». 3.

;

Ρ‚Π°Π±Π». 4.

;

Нам Π±ΡƒΠ΄Π΅Ρ‚ ΡƒΠ΄ΠΎΠ±Π½Π΅Π΅ Ρ‚Ρ€Π°ΠΊΡ‚ΠΎΠ²Π°Ρ‚ΡŒ Π‘ij ΠΊΠ°ΠΊ ΡΡ‚ΠΎΠΈΠΌΠΎΡΡ‚ΡŒ ΠΏΡ€ΠΎΠ΅Π·Π΄Π° ΠΈΠ· Π³ΠΎΡ€ΠΎΠ΄Π° i Π² Π³ΠΎΡ€ΠΎΠ΄ j. Допустим, Ρ‡Ρ‚ΠΎ Π΄ΠΎΠ±Ρ€Ρ‹ΠΉ мэр Π³ΠΎΡ€ΠΎΠ΄Π° j ΠΈΠ·Π΄Π°Π» ΡƒΠΊΠ°Π· Π²Ρ‹ΠΏΠ»Π°Ρ‡ΠΈΠ²Π°Ρ‚ΡŒ ΠΊΠ°ΠΆΠ΄ΠΎΠΌΡƒ Π²ΡŠΠ΅Ρ…Π°Π²ΡˆΠ΅ΠΌΡƒ Π² Π³ΠΎΡ€ΠΎΠ΄ коммивояТСру 5 Π΄ΠΎΠ»Π»Π°Ρ€ΠΎΠ². Π­Ρ‚ΠΎ ΠΎΠ·Π½Π°Ρ‡Π°Π΅Ρ‚, Ρ‡Ρ‚ΠΎ любой Ρ‚ΡƒΡ€ ΠΏΠΎΠ΄Π΅ΡˆΠ΅Π²Π΅Π΅Ρ‚ Π½Π° 5 Π΄ΠΎΠ»Π»Π°Ρ€ΠΎΠ², ΠΏΠΎΡΠΊΠΎΠ»ΡŒΠΊΡƒ Π² Π»ΡŽΠ±ΠΎΠΌ Ρ‚ΡƒΡ€Π΅ Π½ΡƒΠΆΠ½ΠΎ Π²ΡŠΠ΅Ρ…Π°Ρ‚ΡŒ Π² Π³ΠΎΡ€ΠΎΠ΄ j. Но ΠΏΠΎΡΠΊΠΎΠ»ΡŒΠΊΡƒ всС Ρ‚ΡƒΡ€Ρ‹ Ρ€Π°Π²Π½ΠΎΠΌΠ΅Ρ€Π½ΠΎ подСшСвСли, Ρ‚ΠΎ ΠΏΡ€Π΅ΠΆΠ½ΠΈΠΉ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹ΠΉ Ρ‚ΡƒΡ€ Π±ΡƒΠ΄Π΅Ρ‚ ΠΈ Ρ‚Π΅ΠΏΠ΅Ρ€ΡŒ ΡΡ‚ΠΎΠΈΡ‚ΡŒ мСньшС всСх. Π”ΠΎΠ±Ρ€Ρ‹ΠΉ ΠΆΠ΅ поступок мэра ΠΌΠΎΠΆΠ½ΠΎ ΠΏΡ€Π΅Π΄ΡΡ‚Π°Π²ΠΈΡ‚ΡŒ ΠΊΠ°ΠΊ ΡƒΠΌΠ΅Π½ΡŒΡˆΠ΅Π½ΠΈΠ΅ всСх чисСл j-Π³ΠΎ столбца ΠΌΠ°Ρ‚Ρ€ΠΈΡ†Ρ‹ Π‘ Π½Π° 5. Если Π±Ρ‹ мэр Ρ…ΠΎΡ‚Π΅Π» ΡΠΏΡ€ΠΎΠ²Π°Π΄ΠΈΡ‚ΡŒ коммивояТСров ΠΈΠ· j-Π³ΠΎ Π³ΠΎΡ€ΠΎΠ΄Π° ΠΈ ΡƒΡΡ‚Π°Π½ΠΎΠ²ΠΈΠ» Π½Π°Π³Ρ€Π°Π΄Ρƒ Π·Π° Π²Ρ‹Π΅Π·Π΄ Π² Ρ€Π°Π·ΠΌΠ΅Ρ€Π΅ 10 Π΄ΠΎΠ»Π»Π°Ρ€ΠΎΠ², это ΠΌΠΎΠΆΠ½ΠΎ Π±Ρ‹Π»ΠΎ Π±Ρ‹ Π²Ρ‹Ρ€Π°Π·ΠΈΡ‚ΡŒ Π²Ρ‹Ρ‡ΠΈΡ‚Π°Π½ΠΈΠ΅ΠΌ 10 ΠΈΠ· Π²ΡΠ΅Ρ… элСмСнтов j-ΠΉ Ρ‚ΠΎΠΉ строки. Π­Ρ‚ΠΎ снова Π±Ρ‹ ΠΈΠ·ΠΌΠ΅Π½ΠΈΠ»ΠΎ ΡΡ‚ΠΎΠΈΠΌΠΎΡΡ‚ΡŒ ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ Ρ‚ΡƒΡ€Π°, Π½ΠΎ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹ΠΉ Ρ‚ΡƒΡ€ остался Π±Ρ‹ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹ΠΌ. Π˜Ρ‚Π°ΠΊ, Π΄ΠΎΠΊΠ°Π·Π°Π½Π° ΡΠ»Π΅Π΄ΡƒΡŽΡ‰Π°Ρ Π»Π΅ΠΌΠΌΠ°.

Вычитая Π»ΡŽΠ±ΡƒΡŽ константу ΠΈΠ· Π²ΡΠ΅Ρ… элСмСнтов любой строки ΠΈΠ»ΠΈ столбца ΠΌΠ°Ρ‚Ρ€ΠΈΡ†Ρ‹ Π‘, ΠΌΡ‹ ΠΎΡΡ‚авляСм ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹ΠΉ Ρ‚ΡƒΡ€ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹ΠΌ.

Для Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° Π½Π°ΠΌ Π±ΡƒΠ΄Π΅Ρ‚ ΡƒΠ΄ΠΎΠ±Π½ΠΎ ΠΏΠΎΠ»ΡƒΡ‡ΠΈΡ‚ΡŒ побольшС Π½ΡƒΠ»Π΅ΠΉ Π² ΠΌΠ°Ρ‚Ρ€ΠΈΡ†Π΅ Π‘, Π½Π΅ ΠΏΠΎΠ»ΡƒΡ‡Π°Ρ Ρ‚Π°ΠΌ, ΠΎΠ΄Π½Π°ΠΊΠΎ, ΠΎΡ‚Ρ€ΠΈΡ†Π°Ρ‚Π΅Π»ΡŒΠ½Ρ‹Ρ… чисСл. Для этого ΠΌΡ‹ Π²Ρ‹Ρ‡Ρ‚Π΅ΠΌ ΠΈΠ· ΠΊΠ°ΠΆΠ΄ΠΎΠΉ строки Π΅Π΅ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹ΠΉ элСмСнт (это называСтся ΠΏΡ€ΠΈΠ²Π΅Π΄Π΅Π½ΠΈΠ΅ΠΌ ΠΏΠΎ ΡΡ‚Ρ€ΠΎΠΊΠ°ΠΌ, см. Ρ‚Π°Π±Π». 3), Π° Π·Π°Ρ‚Π΅ΠΌ Π²Ρ‹Ρ‡Ρ‚Π΅ΠΌ ΠΈΠ· ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ столбца ΠΌΠ°Ρ‚Ρ€ΠΈΡ†Ρ‹, ΠΏΡ€ΠΈΠ²Π΅Π΄Π΅Π½Π½ΠΎΠΉ ΠΏΠΎ ΡΡ‚Ρ€ΠΎΠΊΠ°ΠΌ, Π΅Π³ΠΎ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹ΠΉ элСмСнт, ΠΏΠΎΠ»ΡƒΡ‡ΠΈΠ² ΠΌΠ°Ρ‚Ρ€ΠΈΡ†Ρƒ, ΠΏΡ€ΠΈΠ²Π΅Π΄Π΅Π½Π½ΡƒΡŽ ΠΏΠΎ ΡΡ‚ΠΎΠ»Π±Ρ†Π°ΠΌ, см. Ρ‚Π°Π±Π». 4).

ΠŸΡ€ΠΎΡ‡Π΅Ρ€ΠΊΠΈ ΠΏΠΎ Π΄ΠΈΠ°Π³ΠΎΠ½Π°Π»ΠΈ ΠΎΠ·Π½Π°Ρ‡Π°ΡŽΡ‚, Ρ‡Ρ‚ΠΎ ΠΈΠ· Π³ΠΎΡ€ΠΎΠ΄Π° i Π² Π³ΠΎΡ€ΠΎΠ΄ i Ρ…ΠΎΠ΄ΠΈΡ‚ΡŒ нСльзя. Π—Π°ΠΌΠ΅Ρ‚ΠΈΠΌ, Ρ‡Ρ‚ΠΎ сумма констант привСдСния ΠΏΠΎ ΡΡ‚Ρ€ΠΎΠΊΠ°ΠΌ Ρ€Π°Π²Π½Π° 27, сумма ΠΏΠΎ ΡΡ‚ΠΎΠ»Π±Ρ†Π°ΠΌ 7, сумма сумм Ρ€Π°Π²Π½Π° 34.

Π’ΡƒΡ€ ΠΌΠΎΠΆΠ½ΠΎ Π·Π°Π΄Π°Ρ‚ΡŒ систСмой ΠΈΠ· ΡˆΠ΅ΡΡ‚ΠΈ ΠΏΠΎΠ΄Ρ‡Π΅Ρ€ΠΊΠ½ΡƒΡ‚Ρ‹Ρ… (Π²Ρ‹Π΄Π΅Π»Π΅Π½Π½Ρ‹Ρ… Π΄Ρ€ΡƒΠ³ΠΈΠΌ Ρ†Π²Π΅Ρ‚ΠΎΠΌ) элСмСнтов ΠΌΠ°Ρ‚Ρ€ΠΈΡ†Ρ‹ Π‘, Π½Π°ΠΏΡ€ΠΈΠΌΠ΅Ρ€, Ρ‚Π°ΠΊΠΎΠΉ, ΠΊΠ°ΠΊ ΠΏΠΎΠΊΠ°Π·Π°Π½ΠΎ Π½Π° Ρ‚Π°Π±Π». 2. ΠŸΠΎΠ΄Ρ‡Π΅Ρ€ΠΊΠΈΠ²Π°Π½ΠΈΠ΅ элСмСнта ΠΎΠ·Π½Π°Ρ‡Π°Π΅Ρ‚, Ρ‡Ρ‚ΠΎ Π² Ρ‚ΡƒΡ€Π΅ ΠΈΠ· i-Π³ΠΎ элСмСнта ΠΈΠ΄ΡƒΡ‚ ΠΈΠΌΠ΅Π½Π½ΠΎ Π² j-Ρ‚Ρ‹ΠΉ. Для Ρ‚ΡƒΡ€Π° ΠΈΠ· ΡˆΠ΅ΡΡ‚ΠΈ Π³ΠΎΡ€ΠΎΠ΄ΠΎΠ² ΠΏΠΎΠ΄Ρ‡Π΅Ρ€ΠΊΠ½ΡƒΡ‚Ρ‹Ρ… элСмСнтов Π΄ΠΎΠ»ΠΆΠ½ΠΎ Π±Ρ‹Ρ‚ΡŒ ΡˆΠ΅ΡΡ‚ΡŒ, Ρ‚Π°ΠΊ ΠΊΠ°ΠΊ Π² Ρ‚ΡƒΡ€Π΅ ΠΈΠ· ΡˆΠ΅ΡΡ‚ΠΈ Π³ΠΎΡ€ΠΎΠ΄ΠΎΠ² Π΅ΡΡ‚ΡŒ ΡˆΠ΅ΡΡ‚ΡŒ Ρ€Π΅Π±Π΅Ρ€. ΠšΠ°ΠΆΠ΄Ρ‹ΠΉ столбСц Π΄ΠΎΠ»ΠΆΠ΅Π½ ΡΠΎΠ΄Π΅Ρ€ΠΆΠ°Ρ‚ΡŒ Ρ€ΠΎΠ²Π½ΠΎ ΠΎΠ΄ΠΈΠ½ ΠΏΠΎΠ΄Ρ‡Π΅Ρ€ΠΊΠ½ΡƒΡ‚Ρ‹ΠΉ элСмСнт (Π² ΠΊΠ°ΠΆΠ΄Ρ‹ΠΉ Π³ΠΎΡ€ΠΎΠ΄ коммивояТСр Π²ΡŠΠ΅Ρ…Π°Π» ΠΎΠ΄ΠΈΠ½ Ρ€Π°Π·), Π² ΠΊΠ°ΠΆΠ΄ΠΎΠΉ строкС Π΄ΠΎΠ»ΠΆΠ΅Π½ Π±Ρ‹Ρ‚ΡŒ Ρ€ΠΎΠ²Π½ΠΎ ΠΎΠ΄ΠΈΠ½ ΠΏΠΎΠ΄Ρ‡Π΅Ρ€ΠΊΠ½ΡƒΡ‚Ρ‹ΠΉ элСмСнт (ΠΈΠ· ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ Π³ΠΎΡ€ΠΎΠ΄Π° коммивояТСр Π²Ρ‹Π΅Ρ…Π°Π» ΠΎΠ΄ΠΈΠ½ Ρ€Π°Π·); ΠΊΡ€ΠΎΠΌΠ΅ Ρ‚ΠΎΠ³ΠΎ, ΠΏΠΎΠ΄Ρ‡Π΅Ρ€ΠΊΠ½ΡƒΡ‚Ρ‹Π΅ элСмСнты Π΄ΠΎΠ»ΠΆΠ½Ρ‹ ΠΎΠΏΠΈΡΡ‹Π²Π°Ρ‚ΡŒ ΠΎΠ΄ΠΈΠ½ Ρ‚ΡƒΡ€, Π° Π½Π΅ Π½Π΅ΡΠΊΠΎΠ»ΡŒΠΊΠΎ ΠΌΠ΅Π½ΡŒΡˆΠΈΡ… Ρ†ΠΈΠΊΠ»ΠΎΠ². Π‘ΡƒΠΌΠΌΠ° чисСл ΠΏΠΎΠ΄Ρ‡Π΅Ρ€ΠΊΠ½ΡƒΡ‚Ρ‹Ρ… элСмСнтов Π΅ΡΡ‚ΡŒ ΡΡ‚ΠΎΠΈΠΌΠΎΡΡ‚ΡŒ Ρ‚ΡƒΡ€Π°. На Ρ‚Π°Π±Π». 2 ΡΡ‚ΠΎΠΈΠΌΠΎΡΡ‚ΡŒ Ρ€Π°Π²Π½Π° 36, это Ρ‚ΠΎΡ‚ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹ΠΉ Ρ‚ΡƒΡ€, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ ΠΏΠΎΠ»ΡƒΡ‡Π΅Π½ лСксикографичСским ΠΏΠ΅Ρ€Π΅Π±ΠΎΡ€ΠΎΠΌ.

Π’Π΅ΠΏΠ΅Ρ€ΡŒ Π±ΡƒΠ΄Π΅ΠΌ Ρ€Π°ΡΡΡƒΠΆΠ΄Π°Ρ‚ΡŒ ΠΎΡ‚ ΠΏΡ€ΠΈΠ²Π΅Π΄Π΅Π½Π½ΠΎΠΉ ΠΌΠ°Ρ‚Ρ€ΠΈΡ†Ρ‹ Π½Π° Ρ‚Π°Π±Π». 2. Если Π² Π½Π΅ΠΉ удастся ΠΏΠΎΡΡ‚Ρ€ΠΎΠΈΡ‚ΡŒ ΠΏΡ€Π°Π²ΠΈΠ»ΡŒΠ½ΡƒΡŽ систСму ΠΏΠΎΠ΄Ρ‡Π΅Ρ€ΠΊΠ½ΡƒΡ‚Ρ‹Ρ… элСмСнтов, Ρ‚. Π΅. систСму, ΡƒΠ΄ΠΎΠ²Π»Π΅Ρ‚Π²ΠΎΡ€ΡΡŽΡ‰ΡƒΡŽ Ρ‚Ρ€Π΅ΠΌ Π²Ρ‹ΡˆΠ΅ΠΎΠΏΠΈΡΠ°Π½Π½Ρ‹ΠΌ трСбованиям, ΠΈ ΡΡ‚ΠΈΠΌΠΈ ΠΏΠΎΠ΄Ρ‡Π΅Ρ€ΠΊΠ½ΡƒΡ‚Ρ‹ΠΌΠΈ элСмСнтами Π±ΡƒΠ΄ΡƒΡ‚ Ρ‚ΠΎΠ»ΡŒΠΊΠΎ Π½ΡƒΠ»ΠΈ, Ρ‚ΠΎ ΡΡΠ½ΠΎ, Ρ‡Ρ‚ΠΎ для этой ΠΌΠ°Ρ‚Ρ€ΠΈΡ†Ρ‹ ΠΌΡ‹ ΠΏΠΎΠ»ΡƒΡ‡ΠΈΠΌ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹ΠΉ Ρ‚ΡƒΡ€. Но ΠΎΠ½ ΠΆΠ΅ Π±ΡƒΠ΄Π΅Ρ‚ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹ΠΌ ΠΈ Π΄Π»Ρ исходной ΠΌΠ°Ρ‚Ρ€ΠΈΡ†Ρ‹ Π‘, Ρ‚ΠΎΠ»ΡŒΠΊΠΎ для Ρ‚ΠΎΠ³ΠΎ, Ρ‡Ρ‚ΠΎΠ±Ρ‹ ΠΏΠΎΠ»ΡƒΡ‡ΠΈΡ‚ΡŒ ΠΏΡ€Π°Π²ΠΈΠ»ΡŒΠ½ΡƒΡŽ ΡΡ‚ΠΎΠΈΠΌΠΎΡΡ‚ΡŒ Ρ‚ΡƒΡ€Π°, Π½ΡƒΠΆΠ½ΠΎ Π±ΡƒΠ΄Π΅Ρ‚ ΠΎΠ±Ρ€Π°Ρ‚Π½ΠΎ ΠΏΡ€ΠΈΠ±Π°Π²ΠΈΡ‚ΡŒ всС константы привСдСния, ΠΈ ΡΡ‚ΠΎΠΈΠΌΠΎΡΡ‚ΡŒ Ρ‚ΡƒΡ€Π° измСнится с 0 Π΄ΠΎ 34. Π’Π°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ, ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹ΠΉ Ρ‚ΡƒΡ€ Π½Π΅ ΠΌΠΎΠΆΠ΅Ρ‚ Π±Ρ‹Ρ‚ΡŒ мСньшС 34. ΠœΡ‹ ΠΏΠΎΠ»ΡƒΡ‡ΠΈΠ»ΠΈ ΠΎΡ†Π΅Π½ΠΊΡƒ снизу для всСх Ρ‚ΡƒΡ€ΠΎΠ².

Π’Π΅ΠΏΠ΅Ρ€ΡŒ приступим ΠΊ Π²Π΅Ρ‚Π²Π»Π΅Π½ΠΈΡŽ. Для этого ΠΏΡ€ΠΎΠ΄Π΅Π»Π°Π΅ΠΌ шаг ΠΎΡ†Π΅Π½ΠΊΠΈ Π½ΡƒΠ»Π΅ΠΉ. Рассмотрим Π½ΡƒΠ»ΡŒ Π² ΠΊΠ»Π΅Ρ‚ΠΊΠ΅ (1,2) ΠΏΡ€ΠΈΠ²Π΅Π΄Π΅Π½Π½ΠΎΠΉ ΠΌΠ°Ρ‚Ρ€ΠΈΡ†Ρ‹. Он ΠΎΠ·Π½Π°Ρ‡Π°Π΅Ρ‚, Ρ‡Ρ‚ΠΎ Ρ†Π΅Π½Π° ΠΏΠ΅Ρ€Π΅Ρ…ΠΎΠ΄Π° ΠΈΠ· Π³ΠΎΡ€ΠΎΠ΄Π° 1 Π² Π³ΠΎΡ€ΠΎΠ΄ 2 Ρ€Π°Π²Π½Π° 0. А Π΅ΡΠ»ΠΈ ΠΌΡ‹ Π½Π΅ ΠΏΠΎΠΉΠ΄Π΅ΠΌ ΠΈΠ· Π³ΠΎΡ€ΠΎΠ΄Π° 1 Π² Π³ΠΎΡ€ΠΎΠ΄ 2? Π’ΠΎΠ³Π΄Π° всС Ρ€Π°Π²Π½ΠΎ Π½ΡƒΠΆΠ½ΠΎ Π²ΡŠΠ΅Ρ…Π°Ρ‚ΡŒ Π² Π³ΠΎΡ€ΠΎΠ΄ 2 Π·Π° Ρ†Π΅Π½Ρ‹, ΡƒΠΊΠ°Π·Π°Π½Π½Ρ‹Π΅ Π²ΠΎ Π²Ρ‚ΠΎΡ€ΠΎΠΌ столбцС; дСшСвлС всСго Π·Π° 1 (ΠΈΠ· Π³ΠΎΡ€ΠΎΠ΄Π° 6). Π”Π°Π»Π΅Π΅, всС Ρ€Π°Π²Π½ΠΎ Π½Π°Π΄ΠΎ Π±ΡƒΠ΄Π΅Ρ‚ Π²Ρ‹Π΅Ρ…Π°Ρ‚ΡŒ ΠΈΠ· Π³ΠΎΡ€ΠΎΠ΄Π° 1 Π·Π° Ρ†Π΅Π½Ρƒ, ΡƒΠΊΠ°Π·Π°Π½Π½ΡƒΡŽ Π² ΠΏΠ΅Ρ€Π²ΠΎΠΉ строкС; дСшСвлС всСго Π² Π³ΠΎΡ€ΠΎΠ΄ 3 Π·Π° 0. Буммируя эти Π΄Π²Π° ΠΌΠΈΠ½ΠΈΠΌΡƒΠΌΠ°, ΠΈΠΌΠ΅Π΅ΠΌ 1+0=1: Ссли Π½Π΅ Π΅Ρ…Π°Ρ‚ΡŒ «ΠΏΠΎ Π½ΡƒΠ»ΡŽ» ΠΈΠ· Π³ΠΎΡ€ΠΎΠ΄Π° 1 Π² Π³ΠΎΡ€ΠΎΠ΄ 2, Ρ‚ΠΎ Π½Π°Π΄ΠΎ Π·Π°ΠΏΠ»Π°Ρ‚ΠΈΡ‚ΡŒ Π½Π΅ ΠΌΠ΅Π½ΡŒΡˆΠ΅ 1. Π­Ρ‚ΠΎ ΠΈ Π΅ΡΡ‚ΡŒ ΠΎΡ†Π΅Π½ΠΊΠ° нуля. ΠžΡ†Π΅Π½ΠΊΠΈ всСх Π½ΡƒΠ»Π΅ΠΉ поставлСны Π½Π° Ρ‚Π°Π±Π». 5 ΠΏΡ€Π°Π²Π΅Π΅ ΠΈ Π²Ρ‹ΡˆΠ΅ нуля (ΠΎΡ†Π΅Π½ΠΊΠΈ нуля, Ρ€Π°Π²Π½Ρ‹Π΅ Π½ΡƒΠ»ΡŽ, Π½Π΅ ΡΡ‚Π°Π²ΠΈΠ»ΠΈΡΡŒ).

Π’Ρ‹Π±Π΅Ρ€Π΅ΠΌ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡŒΠ½ΡƒΡŽ ΠΈΠ· ΡΡ‚ΠΈΡ… ΠΎΡ†Π΅Π½ΠΎΠΊ (Π² ΠΏΡ€ΠΈΠΌΠ΅Ρ€Π΅ Π΅ΡΡ‚ΡŒ нСсколько ΠΎΡ†Π΅Π½ΠΎΠΊ, Ρ€Π°Π²Π½Ρ‹Ρ… Π΅Π΄ΠΈΠ½ΠΈΡ†Π΅, Π²Ρ‹Π±Π΅Ρ€Π΅ΠΌ ΠΏΠ΅Ρ€Π²ΡƒΡŽ ΠΈΠ· Π½ΠΈΡ…, Π² ΠΊΠ»Π΅Ρ‚ΠΊΠ΅ (1,2)).

Π˜Ρ‚Π°ΠΊ, Π²Ρ‹Π±Ρ€Π°Π½ΠΎ Π½ΡƒΠ»Π΅Π²ΠΎΠ΅ Ρ€Π΅Π±Ρ€ΠΎ (1,2). РазобьСм всС Ρ‚ΡƒΡ€Ρ‹ Π½Π° Π΄Π²Π° класса — Π²ΠΊΠ»ΡŽΡ‡Π°ΡŽΡ‰ΠΈΠ΅ Ρ€Π΅Π±Ρ€ΠΎ (1,2) ΠΈ Π½Π΅ Π²ΠΊΠ»ΡŽΡ‡Π°ΡŽΡ‰ΠΈΠ΅ Ρ€Π΅Π±Ρ€ΠΎ (1,2). ΠŸΡ€ΠΎ Π²Ρ‚ΠΎΡ€ΠΎΠΉ класс ΠΌΠΎΠΆΠ½ΠΎ ΡΠΊΠ°Π·Π°Ρ‚ΡŒ, Ρ‡Ρ‚ΠΎ придСтся ΠΏΡ€ΠΈΠΏΠ»Π°Ρ‚ΠΈΡ‚ΡŒ Π΅Ρ‰Π΅ 1, Ρ‚Π°ΠΊ Ρ‡Ρ‚ΠΎ Ρ‚ΡƒΡ€Ρ‹ этого класса стоят 35 ΠΈΠ»ΠΈ большС.

Π§Ρ‚ΠΎ касаСтся ΠΏΠ΅Ρ€Π²ΠΎΠ³ΠΎ класса, Ρ‚ΠΎ Π² Π½Π΅ΠΌ Π½Π°Π΄ΠΎ Ρ€Π°ΡΡΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ ΠΌΠ°Ρ‚Ρ€ΠΈΡ†Ρƒ Π½Π° Ρ‚Π°Π±Π». 6 с Π²Ρ‹Ρ‡Π΅Ρ€ΠΊΠ½ΡƒΡ‚ΠΎΠΉ ΠΏΠ΅Ρ€Π²ΠΎΠΉ строкой ΠΈ Π²Ρ‚ΠΎΡ€Ρ‹ΠΌ столбцом.

Ρ‚Π°Π±Π». 5.

;

Ρ‚Π°Π±Π». 6.

;

Ρ‚Π°Π±Π». 7.

;

Π”ΠΎΠΏΠΎΠ»Π½ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎ Π² ΡƒΠΌΠ΅Π½ΡŒΡˆΠ΅Π½Π½ΠΎΠΉ ΠΌΠ°Ρ‚Ρ€ΠΈΡ†Π΅ поставлСн Π·Π°ΠΏΡ€Π΅Ρ‚ Π² ΠΊΠ»Π΅Ρ‚ΠΊΠ΅ (2,1), Ρ‚. ΠΊ. Π²Ρ‹Π±Ρ€Π°Π½ΠΎ Ρ€Π΅Π±Ρ€ΠΎ (1,2) ΠΈ Π·Π°ΠΌΡ‹ΠΊΠ°Ρ‚ΡŒ ΠΏΡ€Π΅ΠΆΠ΄Π΅Π²Ρ€Π΅ΠΌΠ΅Π½Π½ΠΎ Ρ‚ΡƒΡ€ Ρ€Π΅Π±Ρ€ΠΎΠΌ (2,1) нСльзя. Π£ΠΌΠ΅Π½ΡŒΡˆΠ΅Π½Π½ΡƒΡŽ ΠΌΠ°Ρ‚Ρ€ΠΈΡ†Ρƒ ΠΌΠΎΠΆΠ½ΠΎ привСсти Π½Π° 1 ΠΏΠΎ ΠΏΠ΅Ρ€Π²ΠΎΠΌΡƒ столбцу, Ρ‚Π°ΠΊ Ρ‡Ρ‚ΠΎ ΠΊΠ°ΠΆΠ΄Ρ‹ΠΉ Ρ‚ΡƒΡ€, Π΅ΠΉ ΠΎΡ‚Π²Π΅Ρ‡Π°ΡŽΡ‰ΠΈΠΉ, стоит Π½Π΅ ΠΌΠ΅Π½ΡŒΡˆΠ΅ 35. Π Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚ Π½Π°ΡˆΠΈΡ… Π²Π΅Ρ‚Π²Π»Π΅Π½ΠΈΠΉ ΠΈ ΠΏΠΎΠ»ΡƒΡ‡Π΅Π½ΠΈΡ ΠΎΡ†Π΅Π½ΠΎΠΊ ΠΏΠΎΠΊΠ°Π·Π°Π½ Π½Π° Ρ€ΠΈΡ. 6.

ΠœΠ΅Ρ‚ΠΎΠ΄ Π²Π΅Ρ‚Π²Π΅ΠΉ ΠΈ Π³Ρ€Π°Π½ΠΈΡ†.

ΠšΡ€ΡƒΠΆΠΊΠΈ ΠΏΡ€Π΅Π΄ΡΡ‚Π°Π²Π»ΡΡŽΡ‚ классы: Π²Π΅Ρ€Ρ…Π½ΠΈΠΉ ΠΊΡ€ΡƒΠΆΠΎΠΊ — класс всСх Ρ‚ΡƒΡ€ΠΎΠ²; Π½ΠΈΠΆΠ½ΠΈΠΉ Π»Π΅Π²Ρ‹ΠΉ — класс всСх Ρ‚ΡƒΡ€ΠΎΠ², Π²ΠΊΠ»ΡŽΡ‡Π°ΡŽΡ‰ΠΈΡ… Ρ€Π΅Π±Ρ€ΠΎ (1,2); Π½ΠΈΠΆΠ½ΠΈΠΉ ΠΏΡ€Π°Π²Ρ‹ΠΉ — класс всСх Ρ‚ΡƒΡ€ΠΎΠ², Π½Π΅ Π²ΠΊΠ»ΡŽΡ‡Π°ΡŽΡ‰ΠΈΡ… Ρ€Π΅Π±Ρ€ΠΎ (1,2). Числа Π½Π°Π΄ ΠΊΡ€ΡƒΠΆΠΊΠ°ΠΌΠΈ — ΠΎΡ†Π΅Π½ΠΊΠΈ снизу.

ΠœΠ΅Ρ‚ΠΎΠ΄ Π²Π΅Ρ‚Π²Π΅ΠΉ ΠΈ Π³Ρ€Π°Π½ΠΈΡ†.

ΠŸΡ€ΠΎΠ΄ΠΎΠ»ΠΆΠΈΠΌ Π²Π΅Ρ‚Π²Π»Π΅Π½ΠΈΠ΅ Π² ΠΏΠΎΠ»ΠΎΠΆΠΈΡ‚Π΅Π»ΡŒΠ½ΡƒΡŽ сторону: Π²Π»Π΅Π²ΠΎ — Π²Π½ΠΈΠ·. Для этого ΠΎΡ†Π΅Π½ΠΈΠΌ Π½ΡƒΠ»ΠΈ Π² ΡƒΠΌΠ΅Π½ΡŒΡˆΠ΅Π½Π½ΠΎΠΉ ΠΌΠ°Ρ‚Ρ€ΠΈΡ†Π΅ C[1,2] Π½Π° Ρ‚Π°Π±Π». 7. Максимальная ΠΎΡ†Π΅Π½ΠΊΠ° Π² ΠΊΠ»Π΅Ρ‚ΠΊΠ΅ (3,1) Ρ€Π°Π²Π½Π° 3. Π’Π°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ, ΠΎΡ†Π΅Π½ΠΊΠ° для ΠΏΡ€Π°Π²ΠΎΠΉ Π½ΠΈΠΆΠ½Π΅ΠΉ Π²Π΅Ρ€ΡˆΠΈΠ½Ρ‹ Π½Π° Ρ€ΠΈΡ. 7 Π΅ΡΡ‚ΡŒ 35+3=38. Для ΠΎΡ†Π΅Π½ΠΊΠΈ Π»Π΅Π²ΠΎΠΉ Π½ΠΈΠΆΠ½Π΅ΠΉ Π²Π΅Ρ€ΡˆΠΈΠ½Ρ‹ Π½Π° Ρ€ΠΈΡ. 7 Π½ΡƒΠΆΠ½ΠΎ Π²Ρ‹Ρ‡Π΅Ρ€ΠΊΠ½ΡƒΡ‚ΡŒ ΠΈΠ· ΠΌΠ°Ρ‚Ρ€ΠΈΡ†Ρ‹ C[1,2] Π΅Ρ‰Π΅ строку 3 ΠΈ ΡΡ‚ΠΎΠ»Π±Π΅Ρ† 1, ΠΏΠΎΠ»ΡƒΡ‡ΠΈΠ² ΠΌΠ°Ρ‚Ρ€ΠΈΡ†Ρƒ C[(1,2),(3,1)] Π½Π° Ρ‚Π°Π±Π». 8. Π’ ΡΡ‚Ρƒ ΠΌΠ°Ρ‚Ρ€ΠΈΡ†Ρƒ Π½ΡƒΠΆΠ½ΠΎ ΠΏΠΎΡΡ‚Π°Π²ΠΈΡ‚ΡŒ Π·Π°ΠΏΡ€Π΅Ρ‚ Π² ΠΊΠ»Π΅Ρ‚ΠΊΡƒ (2,3), Ρ‚Π°ΠΊ ΠΊΠ°ΠΊ ΡƒΠΆΠ΅ построСн Ρ„Ρ€Π°Π³ΠΌΠ΅Π½Ρ‚ Ρ‚ΡƒΡ€Π° ΠΈΠ· Ρ€Π΅Π±Π΅Ρ€ (1,2) ΠΈ (3,1), Ρ‚. Π΅. [3,1,2], ΠΈ Π½ΡƒΠΆΠ½ΠΎ Π·Π°ΠΏΡ€Π΅Ρ‚ΠΈΡ‚ΡŒ ΠΏΡ€Π΅ΠΆΠ΄Π΅Π²Ρ€Π΅ΠΌΠ΅Π½Π½ΠΎΠ΅ Π·Π°ΠΌΡ‹ΠΊΠ°Π½ΠΈΠ΅ (2,3). Π­Ρ‚Π° ΠΌΠ°Ρ‚Ρ€ΠΈΡ†Π° приводится ΠΏΠΎ ΡΡ‚ΠΎΠ»Π±Ρ†Ρƒ Π½Π° 1 (Ρ‚Π°Π±Π». 9), Ρ‚Π°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ, ΠΊΠ°ΠΆΠ΄Ρ‹ΠΉ Ρ‚ΡƒΡ€ ΡΠΎΠΎΡ‚Π²Π΅Ρ‚ΡΡ‚Π²ΡƒΡŽΡ‰Π΅Π³ΠΎ класса (Ρ‚.Π΅. Ρ‚ΡƒΡ€, содСрТащий Ρ€Π΅Π±Ρ€Π° (1,2) ΠΈ (3,1)) стоит 36 ΠΈ Π±ΠΎΠ»Π΅Π΅ Π’Π°Π±Π».8.

;

Π’Π°Π±Π».9.

Π’Π°Π±Π».10.

;

Π’Π°Π±Π».11.

;

ΠžΡ†Π΅Π½ΠΈΠ²Π°Π΅ΠΌ Ρ‚Π΅ΠΏΠ΅Ρ€ΡŒ Π½ΡƒΠ»ΠΈ Π² ΠΏΡ€ΠΈΠ²Π΅Π΄Π΅Π½Π½ΠΎΠΉ ΠΌΠ°Ρ‚Ρ€ΠΈΡ†Π΅ C[(1,2),(3,1)] Π½ΡƒΠ»ΡŒ с ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡŒΠ½ΠΎΠΉ ΠΎΡ†Π΅Π½ΠΊΠΎΠΉ 3 находится Π² ΠΊΠ»Π΅Ρ‚ΠΊΠ΅ (6,5). ΠžΡ‚Ρ€ΠΈΡ†Π°Ρ‚Π΅Π»ΡŒΠ½Ρ‹ΠΉ Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ ΠΈΠΌΠ΅Π΅Ρ‚ ΠΎΡ†Π΅Π½ΠΊΡƒ 38+3=41. Для получСния ΠΎΡ†Π΅Π½ΠΊΠΈ ΠΏΠΎΠ»ΠΎΠΆΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΠ³ΠΎ Π²Π°Ρ€ΠΈΠ°Π½Ρ‚Π° ΡƒΠ±ΠΈΡ€Π°Π΅ΠΌ строчку 6 ΠΈ ΡΡ‚ΠΎΠ»Π±Π΅Ρ† 5, ставим Π·Π°ΠΏΡ€Π΅Ρ‚ Π² ΠΊΠ»Π΅Ρ‚ΠΊΡƒ (5,6), см. Ρ‚Π°Π±Π». 10. Π­Ρ‚Π° ΠΌΠ°Ρ‚Ρ€ΠΈΡ†Π° Π½Π΅ΠΏΡ€ΠΈΠ²ΠΎΠ΄ΠΈΠΌΠ°. Π‘Π»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎ, ΠΎΡ†Π΅Π½ΠΊΠ° ΠΏΠΎΠ»ΠΎΠΆΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΠ³ΠΎ Π²Π°Ρ€ΠΈΠ°Π½Ρ‚Π° Π½Π΅ ΡƒΠ²Π΅Π»ΠΈΡ‡ΠΈΠ²Π°Π΅Ρ‚ся (рис.8).

ΠžΡ†Π΅Π½ΠΈΠ²Π°Ρ Π½ΡƒΠ»ΠΈ Π² ΠΌΠ°Ρ‚Ρ€ΠΈΡ†Π΅ Π½Π° Ρ‚Π°Π±Π». 10, ΠΏΠΎΠ»ΡƒΡ‡Π°Π΅ΠΌ Π²Π΅Ρ‚Π²Π»Π΅Π½ΠΈΠ΅ ΠΏΠΎ Π²Ρ‹Π±ΠΎΡ€Ρƒ Ρ€Π΅Π±Ρ€Π° (2,6), ΠΎΡ‚Ρ€ΠΈΡ†Π°Ρ‚Π΅Π»ΡŒΠ½Ρ‹ΠΉ Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ ΠΏΠΎΠ»ΡƒΡ‡Π°Π΅Ρ‚ ΠΎΡ†Π΅Π½ΠΊΡƒ 36+3=39, Π° Π΄Π»Ρ получСния ΠΎΡ†Π΅Π½ΠΊΠΈ ΠΏΠΎΠ»ΠΎΠΆΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΠ³ΠΎ Π²Π°Ρ€ΠΈΠ°Π½Ρ‚Π° Π²Ρ‹Ρ‡Π΅Ρ€ΠΊΠΈΠ²Π°Π΅ΠΌ Π²Ρ‚ΠΎΡ€ΡƒΡŽ строку ΠΈ ΡˆΠ΅ΡΡ‚ΠΎΠΉ столбСц, получая ΠΌΠ°Ρ‚Ρ€ΠΈΡ†Ρƒ Π½Π° Ρ‚Π°Π±Π». 11.

Π’ ΠΌΠ°Ρ‚Ρ€ΠΈΡ†Ρƒ Π½Π°Π΄ΠΎ Π΄ΠΎΠ±Π°Π²ΠΈΡ‚ΡŒ Π·Π°ΠΏΡ€Π΅Ρ‚ Π² ΠΊΠ»Π΅Ρ‚ΠΊΡƒ (5,3), ΠΈΠ±ΠΎ ΡƒΠΆΠ΅ построСн Ρ„Ρ€Π°Π³ΠΌΠ΅Π½Ρ‚ Ρ‚ΡƒΡ€Π° [3,1,2,6,5] ΠΈ Π½Π°Π΄ΠΎ Π·Π°ΠΏΡ€Π΅Ρ‚ΠΈΡ‚ΡŒ ΠΏΡ€Π΅ΠΆΠ΄Π΅Π²Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹ΠΉ Π²ΠΎΠ·Π²Ρ€Π°Ρ‚ (5,3). Π’Π΅ΠΏΠ΅Ρ€ΡŒ, ΠΊΠΎΠ³Π΄Π° ΠΎΡΡ‚Π°Π»Π°ΡΡŒ ΠΌΠ°Ρ‚Ρ€ΠΈΡ†Π° 2×2 с Π·Π°ΠΏΡ€Π΅Ρ‚Π°ΠΌΠΈ ΠΏΠΎ Π΄ΠΈΠ°Π³ΠΎΠ½Π°Π»ΠΈ, достраиваСм Ρ‚ΡƒΡ€ Ρ€Π΅Π±Ρ€Π°ΠΌΠΈ (4,3) ΠΈ (5,4). ΠœΡ‹ Π½Π΅ Π·Ρ€Ρ Π²Π΅Ρ‚Π²ΠΈΠ»ΠΈΡΡŒ, ΠΏΠΎ ΠΏΠΎΠ»ΠΎΠΆΠΈΡ‚Π΅Π»ΡŒΠ½Ρ‹ΠΌ Π²Π°Ρ€ΠΈΠ°Π½Ρ‚Π°ΠΌ. БСйчас ΠΏΠΎΠ»ΡƒΡ‡Π΅Π½ Ρ‚ΡƒΡ€:

1>2>6>5>4>3>1.

ΡΡ‚ΠΎΠΈΠΌΠΎΡΡ‚ΡŒΡŽ Π² 36. ΠŸΡ€ΠΈ достиТСнии Π½ΠΈΠ·Π° ΠΏΠΎ Π΄Π΅Ρ€Π΅Π²Ρƒ ΠΏΠ΅Ρ€Π΅Π±ΠΎΡ€Π° класс Ρ‚ΡƒΡ€ΠΎΠ² сузился Π΄ΠΎ ΠΎΠ΄Π½ΠΎΠ³ΠΎ Ρ‚ΡƒΡ€Π°, Π° ΠΎΡ†Π΅Π½ΠΊΠ° снизу ΠΏΡ€Π΅Π²Ρ€Π°Ρ‚ΠΈΠ»Π°ΡΡŒ Π² Ρ‚ΠΎΡ‡Π½ΡƒΡŽ ΡΡ‚ΠΎΠΈΠΌΠΎΡΡ‚ΡŒ.

Π˜Ρ‚Π°ΠΊ, всС классы, ΠΈΠΌΠ΅ΡŽΡ‰ΠΈΠ΅ ΠΎΡ†Π΅Π½ΠΊΡƒ 36 ΠΈ Π²Ρ‹ΡˆΠ΅, Π»ΡƒΡ‡ΡˆΠ΅Π³ΠΎ Ρ‚ΡƒΡ€Π° Π½Π΅ ΡΠΎΠ΄Π΅Ρ€ΠΆΠ°Ρ‚. ΠŸΠΎΡΡ‚ΠΎΠΌΡƒ ΡΠΎΠΎΡ‚Π²Π΅Ρ‚ΡΡ‚Π²ΡƒΡŽΡ‰ΠΈΠ΅ Π²Π΅Ρ€ΡˆΠΈΠ½Ρ‹ Π²Ρ‹Ρ‡Π΅Ρ€ΠΊΠΈΠ²Π°ΡŽΡ‚ΡΡ. Π’Ρ‹Ρ‡Π΅Ρ€ΠΊΠΈΠ²Π°ΡŽΡ‚ΡΡ Ρ‚Π°ΠΊΠΆΠ΅ Π²Π΅Ρ€ΡˆΠΈΠ½Ρ‹, ΠΎΠ±Π° ΠΏΠΎΡ‚ΠΎΠΌΠΊΠ° ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΉ Π²Ρ‹Ρ‡Π΅Ρ€ΠΊΠ½ΡƒΡ‚Ρ‹. ΠœΡ‹ ΠΊΠΎΠ»ΠΎΡΡΠ°Π»ΡŒΠ½ΠΎ сократили ΠΏΠΎΠ»Π½Ρ‹ΠΉ ΠΏΠ΅Ρ€Π΅Π±ΠΎΡ€. ΠžΡΡ‚Π°Π»ΠΎΡΡŒ ΠΏΡ€ΠΎΠ²Π΅Ρ€ΠΈΡ‚ΡŒ, Π½Π΅ ΡΠΎΠ΄Π΅Ρ€ΠΆΠΈΡ‚ Π»ΠΈ Π»ΡƒΡ‡ΡˆΠ΅Π³ΠΎ Ρ‚ΡƒΡ€Π° класс, ΡΠΎΠΎΡ‚Π²Π΅Ρ‚ΡΡ‚Π²ΡƒΡŽΡ‰ΠΈΠΉ ΠΌΠ°Ρ‚Ρ€ΠΈΡ†Π΅ Π‘[Not (1,2)], Ρ‚. Π΅. ΠΏΡ€ΠΈΠ²Π΅Π΄Π΅Π½Π½ΠΎΠΉ ΠΌΠ°Ρ‚Ρ€ΠΈΡ†Π΅ Π‘ Ρ Π·Π°ΠΏΡ€Π΅Ρ‚ΠΎΠΌ Π² ΠΊΠ»Π΅Ρ‚ΠΊΠ΅ 1,2, ΠΏΡ€ΠΈΠ²Π΅Π΄Π΅Π½Π½ΠΎΠΉ Π½Π° 1 ΠΏΠΎ ΡΡ‚ΠΎΠ»Π±Ρ†Ρƒ (Ρ‡Ρ‚ΠΎ Π΄Π°Π»ΠΎ ΠΎΡ†Π΅Π½ΠΊΡƒ 34+1=35). ΠžΡ†Π΅Π½ΠΊΠ° Π½ΡƒΠ»Π΅ΠΉ Π΄Π°Π΅Ρ‚ 3 для нуля Π² ΠΊΠ»Π΅Ρ‚ΠΊΠ΅ (1,3), Ρ‚Π°ΠΊ Ρ‡Ρ‚ΠΎ ΠΎΡ†Π΅Π½ΠΊΠ° ΠΎΡ‚Ρ€ΠΈΡ†Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΠ³ΠΎ Π²Π°Ρ€ΠΈΠ°Π½Ρ‚Π° 35+3 прСвосходит ΡΡ‚ΠΎΠΈΠΌΠΎΡΡ‚ΡŒ ΡƒΠΆΠ΅ ΠΏΠΎΠ»ΡƒΡ‡Π΅Π½Π½ΠΎΠ³ΠΎ Ρ‚ΡƒΡ€Π° 36 ΠΈ ΠΎΡ‚Ρ€ΠΈΡ†Π°Ρ‚Π΅Π»ΡŒΠ½Ρ‹ΠΉ Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ отсСкаСтся.

ΠœΠ΅Ρ‚ΠΎΠ΄ Π²Π΅Ρ‚Π²Π΅ΠΉ ΠΈ Π³Ρ€Π°Π½ΠΈΡ†.

Для получСния ΠΎΡ†Π΅Π½ΠΊΠΈ ΠΏΠΎΠ»ΠΎΠΆΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΠ³ΠΎ Π²Π°Ρ€ΠΈΠ°Π½Ρ‚Π° ΠΈΡΠΊΠ»ΡŽΡ‡Π°Π΅ΠΌ ΠΈΠ· ΠΌΠ°Ρ‚Ρ€ΠΈΡ†Ρ‹ ΠΏΠ΅Ρ€Π²ΡƒΡŽ строку ΠΈ Ρ‚Ρ€Π΅Ρ‚ΠΈΠΉ столбСц, ставим Π·Π°ΠΏΡ€Π΅Ρ‚ (3,1) ΠΈ ΠΏΠΎΠ»ΡƒΡ‡Π°Π΅ΠΌ ΠΌΠ°Ρ‚Ρ€ΠΈΡ†Ρƒ. Π­Ρ‚Π° ΠΌΠ°Ρ‚Ρ€ΠΈΡ†Π° приводится ΠΏΠΎ Ρ‡Π΅Ρ‚Π²Π΅Ρ€Ρ‚ΠΎΠΉ строкС Π½Π° 1, ΠΎΡ†Π΅Π½ΠΊΠ° класса достигаСт 36 ΠΈ ΠΊΡ€ΡƒΠΆΠΎΠΊ зачСркиваСтся. ΠŸΠΎΡΠΊΠΎΠ»ΡŒΠΊΡƒ Ρƒ Π²Π΅Ρ€ΡˆΠΈΠ½Ρ‹ «Π²ΡΠ΅» ΡƒΠ±ΠΈΡ‚Ρ‹ ΠΎΠ±Π° ΠΏΠΎΡ‚ΠΎΠΌΠΊΠ°, ΠΎΠ½Π° убиваСтся Ρ‚ΠΎΠΆΠ΅. Π’Π΅Ρ€ΡˆΠΈΠ½ Π½Π΅ ΠΎΡΡ‚Π°Π»ΠΎΡΡŒ, ΠΏΠ΅Ρ€Π΅Π±ΠΎΡ€ ΠΎΠΊΠΎΠ½Ρ‡Π΅Π½. ΠœΡ‹ ΠΏΠΎΠ»ΡƒΡ‡ΠΈΠ»ΠΈ Ρ‚ΠΎΡ‚ ΠΆΠ΅ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹ΠΉ Ρ‚ΡƒΡ€, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ ΠΏΠΎΠΊΠ°Π·Π°Π½ ΠΏΠΎΠ΄Ρ‡Π΅Ρ€ΠΊΠΈΠ²Π°Π½ΠΈΠ΅ΠΌ Π½Π° Ρ‚Π°Π±Π». 2.

Π£Π΄ΠΎΠ²Π»Π΅Ρ‚Π²ΠΎΡ€ΠΈΡ‚Π΅Π»ΡŒΠ½Ρ‹Ρ… тСорСтичСских ΠΎΡ†Π΅Π½ΠΎΠΊ быстродСйствия Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° Π›ΠΈΡ‚Ρ‚Π»Π° ΠΈ Ρ€ΠΎΠ΄ΡΡ‚Π²Π΅Π½Π½Ρ‹Ρ… Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² Π½Π΅Ρ‚, Π½ΠΎ ΠΏΡ€Π°ΠΊΡ‚ΠΈΠΊΠ° ΠΏΠΎΠΊΠ°Π·Ρ‹Π²Π°Π΅Ρ‚, Ρ‡Ρ‚ΠΎ Π½Π° ΡΠΎΠ²Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ… Π­Π’Πœ ΠΎΠ½ΠΈ часто ΠΏΠΎΠ·Π²ΠΎΠ»ΡΡŽΡ‚ Ρ€Π΅ΡˆΠΈΡ‚ΡŒ Π—Πš с n = 100. Π­Ρ‚ΠΎ ΠΎΠ³Ρ€ΠΎΠΌΠ½Ρ‹ΠΉ прогрСсс ΠΏΠΎ ΡΡ€Π°Π²Π½Π΅Π½ΠΈΡŽ с ΠΏΠΎΠ»Π½Ρ‹ΠΌ ΠΏΠ΅Ρ€Π΅Π±ΠΎΡ€ΠΎΠΌ. ΠšΡ€ΠΎΠΌΠ΅ Ρ‚ΠΎΠ³ΠΎ, Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹ Ρ‚ΠΈΠΏΠ° Π²Π΅Ρ‚Π²Π΅ΠΉ ΠΈ Π³Ρ€Π°Π½ΠΈΡ† ΡΠ²Π»ΡΡŽΡ‚ΡΡ, Ссли Π½Π΅Ρ‚ возмоТности Π΄ΠΎΠ²ΠΎΠ΄ΠΈΡ‚ΡŒ ΠΈΡ… Π΄ΠΎ ΠΊΠΎΠ½Ρ†Π°, эффСктивными эвристичСскими ΠΏΡ€ΠΎΡ†Π΅Π΄ΡƒΡ€Π°ΠΌΠΈ.

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