ΠΡΠΈΠΌΠ΅Π½Π΅Π½ΠΈΠ΅ ΠΌΡΡΠ°Π²ΡΠΈΠ½ΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠΎΠ² ΠΏΡΠΈ ΡΠ΅ΡΠ΅Π½ΠΈΠΈ Π·Π°Π΄Π°Ρ ΠΎΠΏΡΠΈΠΌΠΈΠ·Π°ΡΠΈΠΈ
Π Π½Π°ΡΠ°Π»Π΅ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²Π° ΡΠ΅ΡΠΎΠΌΠΎΠ½Π° Π½Π° ΡΡΠ±ΡΠ°Ρ ΠΏΡΠΈΠ½ΠΈΠΌΠ°Π΅ΡΡΡ ΡΠ°Π²Π½ΡΠΌ Π½Π΅Π±ΠΎΠ»ΡΡΠΎΠΌΡ ΠΏΠΎΠ»ΠΎΠΆΠΈΡΠ΅Π»ΡΠ½ΠΎΠΌΡ ΡΠΈΡΠ»Ρ. ΠΠ±ΡΠ΅Π΅ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ ΠΌΡΡΠ°Π²ΡΡΠ² ΠΎΡΡΠ°ΡΡΡΡ ΠΏΠΎΡΡΠΎΡΠ½Π½ΡΠΌ ΠΈ ΡΠ°Π²Π½ΡΠΌ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²Ρ Π³ΠΎΡΠΎΠ΄ΠΎΠ², ΠΊΠ°ΠΆΠ΄ΡΠΉ ΠΌΡΡΠ°Π²Π΅ΠΉ Π½Π°ΡΠΈΠ½Π°Π΅Ρ ΠΌΠ°ΡΡΡΡΡ ΠΈΠ· ΡΠ²ΠΎΠ΅Π³ΠΎ Π³ΠΎΡΠΎΠ΄Π°. ΠΡΡΠ°Π²ΡΠΈ ΠΎΠ±Π»Π°Π΄Π°ΡΡ «ΠΎΠ±ΠΎΠ½ΡΠ½ΠΈΠ΅ΠΌ» — ΠΎΠ½ΠΈ ΠΌΠΎΠ³ΡΡ ΡΠ»Π°Π²Π»ΠΈΠ²Π°ΡΡ ΡΠ»Π΅Π΄ ΡΠ΅ΡΠΎΠΌΠΎΠ½Π°, ΠΏΠΎΠ΄ΡΠ²Π΅ΡΠΆΠ΄Π°ΡΡΠΈΠΉ ΠΆΠ΅Π»Π°Π½ΠΈΠ΅ ΠΏΠΎΡΠ΅ΡΠΈΡΡ Π³ΠΎΡΠΎΠ΄ j ΠΈΠ· Π³ΠΎΡΠΎΠ΄Π° i Π½Π° ΠΎΡΠ½ΠΎΠ²Π°Π½ΠΈΠΈ ΠΎΠΏΡΡΠ° Π΄ΡΡΠ³ΠΈΡ ΠΌΡΡΠ°Π²ΡΡΠ². ΠΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ… Π§ΠΈΡΠ°ΡΡ Π΅ΡΡ >
ΠΡΠΈΠΌΠ΅Π½Π΅Π½ΠΈΠ΅ ΠΌΡΡΠ°Π²ΡΠΈΠ½ΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠΎΠ² ΠΏΡΠΈ ΡΠ΅ΡΠ΅Π½ΠΈΠΈ Π·Π°Π΄Π°Ρ ΠΎΠΏΡΠΈΠΌΠΈΠ·Π°ΡΠΈΠΈ (ΡΠ΅ΡΠ΅ΡΠ°Ρ, ΠΊΡΡΡΠΎΠ²Π°Ρ, Π΄ΠΈΠΏΠ»ΠΎΠΌ, ΠΊΠΎΠ½ΡΡΠΎΠ»ΡΠ½Π°Ρ)
ΠΡΠΈΠΌΠ΅Π½Π΅Π½ΠΈΠ΅ ΠΌΡΡΠ°Π²ΡΠΈΠ½ΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠΎΠ² Π΄Π»Ρ Π·Π°Π΄Π°ΡΠΈ ΠΊΠΎΠΌΠΌΠΈΠ²ΠΎΡΠΆΡΡΠ°
ΠΠ°Π΄Π°ΡΠ° ΡΠΎΡΠΌΡΠ»ΠΈΡΡΠ΅ΡΡΡ ΠΊΠ°ΠΊ Π·Π°Π΄Π°ΡΠ° ΠΏΠΎΠΈΡΠΊΠ° ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ³ΠΎ ΠΏΠΎ ΡΡΠΎΠΈΠΌΠΎΡΡΠΈ Π·Π°ΠΌΠΊΠ½ΡΡΠΎΠ³ΠΎ ΠΌΠ°ΡΡΡΡΡΠ° ΠΏΠΎ Π²ΡΠ΅ΠΌ Π²Π΅ΡΡΠΈΠ½Π°ΠΌ Π±Π΅Π· ΠΏΠΎΠ²ΡΠΎΡΠ΅Π½ΠΈΠΉ Π½Π° ΠΏΠΎΠ»Π½ΠΎΠΌ Π²Π·Π²Π΅ΡΠ΅Π½Π½ΠΎΠΌ Π³ΡΠ°ΡΠ΅ Ρ n Π²Π΅ΡΡΠΈΠ½Π°ΠΌΠΈ. Π‘ΠΎΠ΄Π΅ΡΠΆΠ°ΡΠ΅Π»ΡΠ½ΠΎ Π²Π΅ΡΡΠΈΠ½Ρ Π³ΡΠ°ΡΠ° ΡΠ²Π»ΡΡΡΡΡ Π³ΠΎΡΠΎΠ΄Π°ΠΌΠΈ, ΠΊΠΎΡΠΎΡΡΠ΅ Π΄ΠΎΠ»ΠΆΠ΅Π½ ΠΏΠΎΡΠ΅ΡΠΈΡΡ ΠΊΠΎΠΌΠΌΠΈΠ²ΠΎΡΠΆΡΡ, Π° Π²Π΅ΡΠ° ΡΡΠ±Π΅Ρ ΠΎΡΡΠ°ΠΆΠ°ΡΡ ΡΠ°ΡΡΡΠΎΡΠ½ΠΈΡ (Π΄Π»ΠΈΠ½Ρ) ΠΈΠ»ΠΈ ΡΡΠΎΠΈΠΌΠΎΡΡΠΈ ΠΏΡΠΎΠ΅Π·Π΄Π°. ΠΡΠ° Π·Π°Π΄Π°ΡΠ° ΡΠ²Π»ΡΠ΅ΡΡΡ NP-ΡΡΡΠ΄Π½ΠΎΠΉ, ΠΈ ΡΠΎΡΠ½ΡΠΉ ΠΏΠ΅ΡΠ΅Π±ΠΎΡΠ½ΡΠΉ Π°Π»Π³ΠΎΡΠΈΡΠΌ Π΅Ρ ΡΠ΅ΡΠ΅Π½ΠΈΡ ΠΈΠΌΠ΅Π΅Ρ ΡΠ°ΠΊΡΠΎΡΠΈΠ°Π»ΡΠ½ΡΡ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΡ.
ΠΠΎΠ΄Π΅Π»ΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅ ΠΏΠΎΠ²Π΅Π΄Π΅Π½ΠΈΡ ΠΌΡΡΠ°Π²ΡΡΠ² ΡΠ²ΡΠ·Π°Π½ΠΎ Ρ ΡΠ°ΡΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΠ΅ΠΌ ΡΠ΅ΡΠΎΠΌΠΎΠ½Π° Π½Π° ΡΡΠΎΠΏΠ΅ — ΡΠ΅Π±ΡΠ΅ Π³ΡΠ°ΡΠ° Π² Π·Π°Π΄Π°ΡΠ΅ ΠΊΠΎΠΌΠΌΠΈΠ²ΠΎΡΠΆΡΡΠ°. ΠΡΠΈ ΡΡΠΎΠΌ Π²Π΅ΡΠΎΡΡΠ½ΠΎΡΡΡ Π²ΠΊΠ»ΡΡΠ΅Π½ΠΈΡ ΡΠ΅Π±ΡΠ° Π² ΠΌΠ°ΡΡΡΡΡ ΠΎΡΠ΄Π΅Π»ΡΠ½ΠΎΠ³ΠΎ ΠΌΡΡΠ°Π²ΡΡ ΠΏΡΠΎΠΏΠΎΡΡΠΈΠΎΠ½Π°Π»ΡΠ½Π° ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²Ρ ΡΠ΅ΡΠΎΠΌΠΎΠ½Π° Π½Π° ΡΡΠΎΠΌ ΡΠ΅Π±ΡΠ΅, Π° ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ ΠΎΡΠΊΠ»Π°Π΄ΡΠ²Π°Π΅ΠΌΠΎΠ³ΠΎ ΡΠ΅ΡΠΎΠΌΠΎΠ½Π° ΠΏΡΠΎΠΏΠΎΡΡΠΈΠΎΠ½Π°Π»ΡΠ½ΠΎ Π΄Π»ΠΈΠ½Π΅ ΠΌΠ°ΡΡΡΡΡΠ°. Π§Π΅ΠΌ ΠΊΠΎΡΠΎΡΠ΅ ΠΌΠ°ΡΡΡΡΡ, ΡΠ΅ΠΌ Π±ΠΎΠ»ΡΡΠ΅ ΡΠ΅ΡΠΎΠΌΠΎΠ½Π° Π±ΡΠ΄Π΅Ρ ΠΎΡΠ»ΠΎΠΆΠ΅Π½ΠΎ Π½Π° Π΅Π³ΠΎ ΡΡΠ±ΡΠ°Ρ , ΡΠ»Π΅Π΄ΠΎΠ²Π°ΡΠ΅Π»ΡΠ½ΠΎ, Π±ΠΎΠ»ΡΡΠ΅Π΅ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ ΠΌΡΡΠ°Π²ΡΡΠ² Π±ΡΠ΄Π΅Ρ Π²ΠΊΠ»ΡΡΠ°ΡΡ Π΅Π³ΠΎ Π² ΡΠΈΠ½ΡΠ΅Π· ΡΠΎΠ±ΡΡΠ²Π΅Π½Π½ΡΡ ΠΌΠ°ΡΡΡΡΡΠΎΠ². ΠΠΎΠ΄Π΅Π»ΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅ ΡΠ°ΠΊΠΎΠ³ΠΎ ΠΏΠΎΠ΄Ρ ΠΎΠ΄Π°, ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΡΡΠ΅Π³ΠΎ ΡΠΎΠ»ΡΠΊΠΎ ΠΏΠΎΠ»ΠΎΠΆΠΈΡΠ΅Π»ΡΠ½ΡΡ ΠΎΠ±ΡΠ°ΡΠ½ΡΡ ΡΠ²ΡΠ·Ρ, ΠΏΡΠΈΠ²ΠΎΠ΄ΠΈΡ ΠΊ ΠΏΡΠ΅ΠΆΠ΄Π΅Π²ΡΠ΅ΠΌΠ΅Π½Π½ΠΎΠΉ ΡΡ ΠΎΠ΄ΠΈΠΌΠΎΡΡΠΈ — Π±ΠΎΠ»ΡΡΠΈΠ½ΡΡΠ²ΠΎ ΠΌΡΡΠ°Π²ΡΡΠ² Π΄Π²ΠΈΠ³Π°Π΅ΡΡΡ ΠΏΠΎ Π»ΠΎΠΊΠ°Π»ΡΠ½ΠΎ ΠΎΠΏΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΠΌΡ ΠΌΠ°ΡΡΡΡΡΡ. ΠΠ·Π±Π΅ΠΆΠ°ΡΡ ΡΡΠΎΠ³ΠΎ ΠΌΠΎΠΆΠ½ΠΎ, ΠΌΠΎΠ΄Π΅Π»ΠΈΡΡΡ ΠΎΡΡΠΈΡΠ°ΡΠ΅Π»ΡΠ½ΡΡ ΠΎΠ±ΡΠ°ΡΠ½ΡΡ ΡΠ²ΡΠ·Ρ Π² Π²ΠΈΠ΄Π΅ ΠΈΡΠΏΠ°ΡΠ΅Π½ΠΈΡ ΡΠ΅ΡΠΎΠΌΠΎΠ½Π°. ΠΡΠΈ ΡΡΠΎΠΌ Π΅ΡΠ»ΠΈ ΡΠ΅ΡΠΎΠΌΠΎΠ½ ΠΈΡΠΏΠ°ΡΡΠ΅ΡΡΡ Π±ΡΡΡΡΠΎ, ΡΠΎ ΡΡΠΎ ΠΏΡΠΈΠ²ΠΎΠ΄ΠΈΡ ΠΊ ΠΏΠΎΡΠ΅ΡΠ΅ ΠΏΠ°ΠΌΡΡΠΈ ΠΊΠΎΠ»ΠΎΠ½ΠΈΠΈ ΠΈ Π·Π°Π±ΡΠ²Π°Π½ΠΈΡ Ρ ΠΎΡΠΎΡΠΈΡ ΡΠ΅ΡΠ΅Π½ΠΈΠΉ, Ρ Π΄ΡΡΠ³ΠΎΠΉ ΡΡΠΎΡΠΎΠ½Ρ, Π±ΠΎΠ»ΡΡΠΎΠ΅ Π²ΡΠ΅ΠΌΡ ΠΈΡΠΏΠ°ΡΠ΅Π½ΠΈΡ ΠΌΠΎΠΆΠ΅Ρ ΠΏΡΠΈΠ²Π΅ΡΡΠΈ ΠΊ ΠΏΠΎΠ»ΡΡΠ΅Π½ΠΈΡ ΡΡΡΠΎΠΉΡΠΈΠ²ΠΎΠ³ΠΎ Π»ΠΎΠΊΠ°Π»ΡΠ½ΠΎΠ³ΠΎ ΠΎΠΏΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ³ΠΎ ΡΠ΅ΡΠ΅Π½ΠΈΡ. [1].
Π’Π΅ΠΏΠ΅ΡΡ Ρ ΡΡΡΡΠΎΠΌ ΠΎΡΠΎΠ±Π΅Π½Π½ΠΎΡΡΠ΅ΠΉ Π·Π°Π΄Π°ΡΠΈ ΠΊΠΎΠΌΠΌΠΈΠ²ΠΎΡΠΆΡΡΠ°, ΠΌΡ ΠΌΠΎΠΆΠ΅ΠΌ ΠΎΠΏΠΈΡΠ°ΡΡ Π»ΠΎΠΊΠ°Π»ΡΠ½ΡΠ΅ ΠΏΡΠ°Π²ΠΈΠ»Π° ΠΏΠΎΠ²Π΅Π΄Π΅Π½ΠΈΡ ΠΌΡΡΠ°Π²ΡΡΠ² ΠΏΡΠΈ Π²ΡΠ±ΠΎΡΠ΅ ΠΏΡΡΠΈ.
1. ΠΡΡΠ°Π²ΡΠΈ ΠΈΠΌΠ΅ΡΡ ΡΠΎΠ±ΡΡΠ²Π΅Π½Π½ΡΡ «ΠΏΠ°ΠΌΡΡΡ». ΠΠΎΡΠΊΠΎΠ»ΡΠΊΡ ΠΊΠ°ΠΆΠ΄ΡΠΉ Π³ΠΎΡΠΎΠ΄ ΠΌΠΎΠΆΠ΅Ρ Π±ΡΡΡ ΠΏΠΎΡΠ΅ΡΡΠ½ ΡΠΎΠ»ΡΠΊΠΎ ΠΎΠ΄ΠΈΠ½ ΡΠ°Π·, ΡΠΎ Ρ ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ ΠΌΡΡΠ°Π²ΡΡ Π΅ΡΡΡ ΡΠΏΠΈΡΠΎΠΊ ΡΠΆΠ΅ ΠΏΠΎΡΠ΅ΡΡΠ½Π½ΡΡ Π³ΠΎΡΠΎΠ΄ΠΎΠ² — ΡΠΏΠΈΡΠΎΠΊ Π·Π°ΠΏΡΠ΅ΡΠΎΠ². ΠΠ±ΠΎΠ·Π½Π°ΡΠΈΠΌ ΡΠ΅ΡΠ΅Π· J i, k ΡΠΏΠΈΡΠΎΠΊ Π³ΠΎΡΠΎΠ΄ΠΎΠ², ΠΊΠΎΡΠΎΡΡΠ΅ Π½Π΅ΠΎΠ±Ρ ΠΎΠ΄ΠΈΠΌΠΎ ΠΏΠΎΡΠ΅ΡΠΈΡΡ ΠΌΡΡΠ°Π²ΡΡ k, Π½Π°Ρ ΠΎΠ΄ΡΡΠ΅ΠΌΡΡΡ Π² Π³ΠΎΡΠΎΠ΄Π΅ i. 2. ΠΡΡΠ°Π²ΡΠΈ ΠΎΠ±Π»Π°Π΄Π°ΡΡ «Π·ΡΠ΅Π½ΠΈΠ΅ΠΌ» — Π²ΠΈΠ΄ΠΈΠΌΠΎΡΡΡ Π΅ΡΡΡ ΡΠ²ΡΠΈΡΡΠΈΡΠ΅ΡΠΊΠΎΠ΅ ΠΆΠ΅Π»Π°Π½ΠΈΠ΅ ΠΏΠΎΡΠ΅ΡΠΈΡΡ Π³ΠΎΡΠΎΠ΄ j, Π΅ΡΠ»ΠΈ ΠΌΡΡΠ°Π²Π΅ΠΉ Π½Π°Ρ ΠΎΠ΄ΠΈΡΡΡ Π² Π³ΠΎΡΠΎΠ΄Π΅ i. ΠΡΠ΄Π΅ΠΌ ΡΡΠΈΡΠ°ΡΡ, ΡΡΠΎ Π²ΠΈΠ΄ΠΈΠΌΠΎΡΡΡ ΠΎΠ±ΡΠ°ΡΠ½ΠΎ ΠΏΡΠΎΠΏΠΎΡΡΠΈΠΎΠ½Π°Π»ΡΠ½Π° ΡΠ°ΡΡΡΠΎΡΠ½ΠΈΡ ΠΌΠ΅ΠΆΠ΄Ρ Π³ΠΎΡΠΎΠ΄Π°ΠΌΠΈ.
3. ΠΡΡΠ°Π²ΡΠΈ ΠΎΠ±Π»Π°Π΄Π°ΡΡ «ΠΎΠ±ΠΎΠ½ΡΠ½ΠΈΠ΅ΠΌ» — ΠΎΠ½ΠΈ ΠΌΠΎΠ³ΡΡ ΡΠ»Π°Π²Π»ΠΈΠ²Π°ΡΡ ΡΠ»Π΅Π΄ ΡΠ΅ΡΠΎΠΌΠΎΠ½Π°, ΠΏΠΎΠ΄ΡΠ²Π΅ΡΠΆΠ΄Π°ΡΡΠΈΠΉ ΠΆΠ΅Π»Π°Π½ΠΈΠ΅ ΠΏΠΎΡΠ΅ΡΠΈΡΡ Π³ΠΎΡΠΎΠ΄ j ΠΈΠ· Π³ΠΎΡΠΎΠ΄Π° i Π½Π° ΠΎΡΠ½ΠΎΠ²Π°Π½ΠΈΠΈ ΠΎΠΏΡΡΠ° Π΄ΡΡΠ³ΠΈΡ ΠΌΡΡΠ°Π²ΡΡΠ². ΠΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ ΡΠ΅ΡΠΎΠΌΠΎΠ½Π° Π½Π° ΡΠ΅Π±ΡΠ΅ (i, j) Π² ΠΌΠΎΠΌΠ΅Π½Ρ Π²ΡΠ΅ΠΌΠ΅Π½ΠΈ t ΠΎΠ±ΠΎΠ·Π½Π°ΡΠΈΠΌ ΡΠ΅ΡΠ΅Π·.
ΠΠ° ΡΡΠΎΠΌ ΠΎΡΠ½ΠΎΠ²Π°Π½ΠΈΠΈ ΠΌΡ ΠΌΠΎΠΆΠ΅ΠΌ ΡΡΠΎΡΠΌΡΠ»ΠΈΡΠΎΠ²Π°ΡΡ Π²Π΅ΡΠΎΡΡΠ½ΠΎΡΡΠ½ΠΎ-ΠΏΡΠΎΠΏΠΎΡΡΠΈΠΎΠ½Π°Π»ΡΠ½ΠΎΠ΅ ΠΏΡΠ°Π²ΠΈΠ»ΠΎ, ΠΎΠΏΡΠ΅Π΄Π΅Π»ΡΡΡΠ΅Π΅ Π²Π΅ΡΠΎΡΡΠ½ΠΎΡΡΡ ΠΏΠ΅ΡΠ΅Ρ ΠΎΠ΄Π° k-ΠΎΠ³ΠΎ ΠΌΡΡΠ°Π²ΡΡ ΠΈΠ· Π³ΠΎΡΠΎΠ΄Π° i Π² Π³ΠΎΡΠΎΠ΄ j:
(1).
ΠΠ΄Π΅ Π±, Π² — ΠΏΠ°ΡΠ°ΠΌΠ΅ΡΡΡ, Π·Π°Π΄Π°ΡΡΠΈΠ΅ Π²Π΅ΡΠ° ΡΠ»Π΅Π΄Π° ΡΠ΅ΡΠΎΠΌΠΎΠ½Π°. ΠΡΠΈ Π± =0 Π°Π»Π³ΠΎΡΠΈΡΠΌ Π²ΡΡΠΎΠΆΠ΄Π°Π΅ΡΡΡ Π΄ΠΎ ΠΆΠ°Π΄Π½ΠΎΠ³ΠΎ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° (Π±ΡΠ΄Π΅Ρ Π²ΡΠ±ΡΠ°Π½ Π±Π»ΠΈΠΆΠ°ΠΉΡΠΈΠΉ Π³ΠΎΡΠΎΠ΄). ΠΠ°ΠΌΠ΅ΡΠΈΠΌ, ΡΡΠΎ Π²ΡΠ±ΠΎΡ Π³ΠΎΡΠΎΠ΄Π° ΡΠ²Π»ΡΠ΅ΡΡΡ Π²Π΅ΡΠΎΡΡΠ½ΠΎΡΡΠ½ΡΠΌ, ΠΏΡΠ°Π²ΠΈΠ»ΠΎ (1) Π»ΠΈΡΡ ΠΎΠΏΡΠ΅Π΄Π΅Π»ΡΠ΅Ρ ΡΠΈΡΠΈΠ½Ρ Π·ΠΎΠ½Ρ Π³ΠΎΡΠΎΠ΄Π° j; Π² ΠΎΠ±ΡΡΡ Π·ΠΎΠ½Ρ Π²ΡΠ΅Ρ Π³ΠΎΡΠΎΠ΄ΠΎΠ² Π±ΡΠΎΡΠ°Π΅ΡΡΡ ΡΠ»ΡΡΠ°ΠΉΠ½ΠΎΠ΅ ΡΠΈΡΠ»ΠΎ, ΠΊΠΎΡΠΎΡΠΎΠ΅ ΠΈ ΠΎΠΏΡΠ΅Π΄Π΅Π»ΡΠ΅Ρ Π²ΡΠ±ΠΎΡ ΠΌΡΡΠ°Π²ΡΡ. ΠΡΠ°Π²ΠΈΠ»ΠΎ (1) Π½Π΅ ΠΈΠ·ΠΌΠ΅Π½ΡΠ΅ΡΡΡ Π² Ρ ΠΎΠ΄Π΅ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ°, Π½ΠΎ Ρ Π΄Π²ΡΡ ΡΠ°Π·Π½ΡΡ ΠΌΡΡΠ°Π²ΡΡΠ² Π·Π½Π°ΡΠ΅Π½ΠΈΠ΅ Π²Π΅ΡΠΎΡΡΠ½ΠΎΡΡΠΈ ΠΏΠ΅ΡΠ΅Ρ ΠΎΠ΄Π° Π±ΡΠ΄ΡΡ ΠΎΡΠ»ΠΈΡΠ°ΡΡΡΡ, Ρ.ΠΊ. ΠΎΠ½ΠΈ ΠΈΠΌΠ΅ΡΡ ΡΠ°Π·Π½ΡΠΉ ΡΠΏΠΈΡΠΎΠΊ ΡΠ°Π·ΡΠ΅ΡΡΠ½Π½ΡΡ Π³ΠΎΡΠΎΠ΄ΠΎΠ².
5. ΠΡΠΎΠΉΠ΄Ρ ΡΠ΅Π±ΡΠΎ (i, j), ΠΌΡΡΠ°Π²Π΅ΠΉ ΠΎΡΠΊΠ»Π°Π΄ΡΠ²Π°Π΅Ρ Π½Π° Π½ΡΠΌ Π½Π΅ΠΊΠΎΡΠΎΡΠΎΠ΅ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ ΡΠ΅ΡΠΎΠΌΠΎΠ½Π°, ΠΊΠΎΡΠΎΡΠΎΠ΅ Π΄ΠΎΠ»ΠΆΠ½ΠΎ Π±ΡΡΡ ΡΠ²ΡΠ·Π°Π½ΠΎ Ρ ΠΎΠΏΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΡΡΡΡ ΡΠ΄Π΅Π»Π°Π½Π½ΠΎΠ³ΠΎ Π²ΡΠ±ΠΎΡΠ°. ΠΡΡΡΡ Tk (t) Π΅ΡΡΡ ΠΌΠ°ΡΡΡΡΡ, ΠΏΡΠΎΠΉΠ΄Π΅Π½Π½ΡΠΉ ΠΌΡΡΠ°Π²ΡΡΠΌ k ΠΊ ΠΌΠΎΠΌΠ΅Π½ΡΡ Π²ΡΠ΅ΠΌΠ΅Π½ΠΈ t, Lk (t) — Π΄Π»ΠΈΠ½Π° ΡΡΠΎΠ³ΠΎ ΠΌΠ°ΡΡΡΡΡΠ°, Π° Q — ΠΏΠ°ΡΠ°ΠΌΠ΅ΡΡ, ΠΈΠΌΠ΅ΡΡΠΈΠΉ Π·Π½Π°ΡΠ΅Π½ΠΈΠ΅ ΠΏΠΎΡΡΠ΄ΠΊΠ° Π΄Π»ΠΈΠ½Ρ ΠΎΠΏΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ³ΠΎ ΠΏΡΡΠΈ. Π’ΠΎΠ³Π΄Π° ΠΎΡΠΊΠ»Π°Π΄ΡΠ²Π°Π΅ΠΌΠΎΠ΅ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ ΡΠ΅ΡΠΎΠΌΠΎΠ½Π° ΠΌΠΎΠΆΠ΅Ρ Π±ΡΡΡ Π·Π°Π΄Π°Π½ΠΎ Π² Π²ΠΈΠ΄Π΅.
ΠΡΠ°Π²ΠΈΠ»Π° Π²Π½Π΅ΡΠ½Π΅ΠΉ ΡΡΠ΅Π΄Ρ ΠΎΠΏΡΠ΅Π΄Π΅Π»ΡΡΡ, Π² ΠΏΠ΅ΡΠ²ΡΡ ΠΎΡΠ΅ΡΠ΅Π΄Ρ, ΠΈΡΠΏΠ°ΡΠ΅Π½ΠΈΠ΅ ΡΠ΅ΡΠΎΠΌΠΎΠ½Π°. ΠΡΡΡΡ Π΅ΡΡΡ ΠΊΠΎΡΡΡΠΈΡΠΈΠ΅Π½Ρ ΠΈΡΠΏΠ°ΡΠ΅Π½ΠΈΡ, ΡΠΎΠ³Π΄Π° ΠΏΡΠ°Π²ΠΈΠ»ΠΎ ΠΈΡΠΏΠ°ΡΠ΅Π½ΠΈΡ ΠΈΠΌΠ΅Π΅Ρ Π²ΠΈΠ΄.
Π³Π΄Π΅ m — ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ ΠΌΡΡΠ°Π²ΡΡΠ² Π² ΠΊΠΎΠ»ΠΎΠ½ΠΈΠΈ.
Π Π½Π°ΡΠ°Π»Π΅ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²Π° ΡΠ΅ΡΠΎΠΌΠΎΠ½Π° Π½Π° ΡΡΠ±ΡΠ°Ρ ΠΏΡΠΈΠ½ΠΈΠΌΠ°Π΅ΡΡΡ ΡΠ°Π²Π½ΡΠΌ Π½Π΅Π±ΠΎΠ»ΡΡΠΎΠΌΡ ΠΏΠΎΠ»ΠΎΠΆΠΈΡΠ΅Π»ΡΠ½ΠΎΠΌΡ ΡΠΈΡΠ»Ρ. ΠΠ±ΡΠ΅Π΅ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ ΠΌΡΡΠ°Π²ΡΡΠ² ΠΎΡΡΠ°ΡΡΡΡ ΠΏΠΎΡΡΠΎΡΠ½Π½ΡΠΌ ΠΈ ΡΠ°Π²Π½ΡΠΌ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²Ρ Π³ΠΎΡΠΎΠ΄ΠΎΠ², ΠΊΠ°ΠΆΠ΄ΡΠΉ ΠΌΡΡΠ°Π²Π΅ΠΉ Π½Π°ΡΠΈΠ½Π°Π΅Ρ ΠΌΠ°ΡΡΡΡΡ ΠΈΠ· ΡΠ²ΠΎΠ΅Π³ΠΎ Π³ΠΎΡΠΎΠ΄Π°.
ΠΠΎΠΏΠΎΠ»Π½ΠΈΡΠ΅Π»ΡΠ½Π°Ρ ΠΌΠΎΠ΄ΠΈΡΠΈΠΊΠ°ΡΠΈΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° ΠΌΠΎΠΆΠ΅Ρ ΡΠΎΡΡΠΎΡΡΡ Π² Π²Π΅Π΄Π΅Π½ΠΈΠΈ ΡΠ°ΠΊ Π½Π°Π·ΡΠ²Π°Π΅ΠΌΡΡ «ΡΠ»ΠΈΡΠ½ΡΡ » ΠΌΡΡΠ°Π²ΡΡΠ², ΠΊΠΎΡΠΎΡΡΠ΅ ΡΡΠΈΠ»ΠΈΠ²Π°ΡΡ ΡΡΠ±ΡΠ° Π½Π°ΠΈΠ»ΡΡΡΠ΅Π³ΠΎ ΠΌΠ°ΡΡΡΡΡΠ°, Π½Π°ΠΉΠ΄Π΅Π½Π½ΠΎΠ³ΠΎ Ρ Π½Π°ΡΠ°Π»Π° ΡΠ°Π±ΠΎΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ°. ΠΠ±ΠΎΠ·Π½Π°ΡΠΈΠΌ ΡΠ΅ΡΠ΅Π· T* Π½Π°ΠΈΠ»ΡΡΡΠΈΠΉ ΡΠ΅ΠΊΡΡΠΈΠΉ ΠΌΠ°ΡΡΡΡΡ, ΡΠ΅ΡΠ΅Π· L* — Π΅Π³ΠΎ Π΄Π»ΠΈΠ½Ρ. Π’ΠΎΠ³Π΄Π° Π΅ΡΠ»ΠΈ Π² ΠΊΠΎΠ»ΠΎΠ½ΠΈΠΈ Π΅ΡΡΡ e ΡΠ»ΠΈΡΠ½ΡΡ ΠΌΡΡΠ°Π²ΡΡΠ², ΡΠΎ ΡΡΠ±ΡΠ° ΠΌΠ°ΡΡΡΡΡΠ° ΠΏΠΎΠ»ΡΡΠ°Ρ Π΄ΠΎΠΏΠΎΠ»Π½ΠΈΡΠ΅Π»ΡΠ½ΠΎΠ΅ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ ΡΠ΅ΡΠΎΠΌΠΎΠ½Π°.
(3).