ΠΠ΅ΡΠΎΠ΄ ΠΠ½ΠΈΡΠ΅Π½ΠΊΠΎ.
ΠΠ°Π΄Π°ΡΠ° ΠΊΠΎΠΌΠΈΠ²ΠΎΡΠΆΠ΅ΡΠ°
ΠΠ΄Π½Π°ΠΊΠΎ Π½Π΅ Π²ΡΠ΅Π³Π΄Π° ΠΌΠΎΠΆΠ½ΠΎ ΠΏΠΎΡΡΡΠΎΠΈΡΡ Π²ΡΠΏΡΠΊΠ»ΡΠΉ ΠΌΠ½ΠΎΠ³ΠΎΡΠ³ΠΎΠ»ΡΠ½ΠΈΠΊ, ΠΏΠΎ ΠΏΠ΅ΡΠΈΠΌΠ΅ΡΡΡ ΠΊΠΎΡΠΎΡΠΎΠ³ΠΎ Π»Π΅ΠΆΠ°Π»ΠΈ Π±Ρ Π²ΡΠ΅ Π³ΠΎΡΠΎΠ΄Π°. ΠΠ΅Π»ΠΈΠΊΠ° Π²Π΅ΡΠΎΡΡΠ½ΠΎΡΡΡ ΡΠΎΠ³ΠΎ, ΡΡΠΎ Π½Π΅ΠΊΠΎΡΠΎΡΡΠ΅ Π³ΠΎΡΠΎΠ΄Π° Π½Π΅ Π²ΠΎΠΉΠ΄ΡΡ Π² Π²ΡΠΏΡΠΊΠ»ΡΠΉ ΠΌΠ½ΠΎΠ³ΠΎΡΠ³ΠΎΠ»ΡΠ½ΠΈΠΊ. Π’Π°ΠΊΠΈΠ΅ Π³ΠΎΡΠΎΠ΄Π° Π±ΡΠ΄Π΅ΠΌ Π½Π°Π·ΡΠ²Π°ΡΡ «ΡΠ΅Π½ΡΡΠ°Π»ΡΠ½ΡΠΌΠΈ». Π’Π°ΠΊ ΠΊΠ°ΠΊ ΠΏΠΎΡΡΡΠΎΠΈΡΡ Π²ΡΠΏΡΠΊΠ»ΡΠΉ ΠΌΠ½ΠΎΠ³ΠΎΡΠ³ΠΎΠ»ΡΠ½ΠΈΠΊ Π΄ΠΎΠ²ΠΎΠ»ΡΠ½ΠΎ Π»Π΅Π³ΠΊΠΎ, ΡΠΎ Π·Π°Π΄Π°ΡΠ° ΡΠ²ΠΎΠ΄ΠΈΡΡΡ ΠΊ ΡΠΎΠΌΡ, ΡΡΠΎΠ±Ρ Π²ΠΊΠ»ΡΡΠΈΡΡ Π² ΡΡΡ Π² Π²ΠΈΠ΄Π΅ Π²ΡΠΏΡΠΊΠ»ΠΎΠ³ΠΎ ΠΌΠ½ΠΎΠ³ΠΎΡΠ³ΠΎΠ»ΡΠ½ΠΈΠΊΠ° Π²ΡΠ΅ ΡΠ΅Π½ΡΡΠ°Π»ΡΠ½ΡΠ΅ Π³ΠΎΡΠΎΠ΄Π°… Π§ΠΈΡΠ°ΡΡ Π΅ΡΡ >
ΠΠ΅ΡΠΎΠ΄ ΠΠ½ΠΈΡΠ΅Π½ΠΊΠΎ. ΠΠ°Π΄Π°ΡΠ° ΠΊΠΎΠΌΠΈΠ²ΠΎΡΠΆΠ΅ΡΠ° (ΡΠ΅ΡΠ΅ΡΠ°Ρ, ΠΊΡΡΡΠΎΠ²Π°Ρ, Π΄ΠΈΠΏΠ»ΠΎΠΌ, ΠΊΠΎΠ½ΡΡΠΎΠ»ΡΠ½Π°Ρ)
Π Π°ΡΡΠΌΠΎΡΡΠΈΠΌ ΡΠΈΡ. 9−10 ΠΈ ΠΏΠΎΠΏΡΡΠ°Π΅ΠΌΡΡ Π½Π°ΠΉΡΠΈ Π² Π½ΠΈΡ ΠΊΡΠ°ΡΡΠ°ΠΉΡΠΈΠ΅ ΡΡΡΡ. ΠΡΠ΅Π²ΠΈΠ΄Π½ΠΎ, ΡΡΠΎ ΠΊΡΠ°ΡΡΠ°ΠΉΡΠΈΠΉ ΡΡΡ Π½Π΅ Π΄ΠΎΠ»ΠΆΠ΅Π½ ΡΠΎΠ΄Π΅ΡΠΆΠ°ΡΡ ΠΏΠ΅ΡΠ΅ΡΠ΅ΠΊΠ°ΡΡΠΈΡ ΡΡ ΡΠ΅Π±ΡΡ (Π² ΠΏΡΠΎΡΠΈΠ²Π½ΠΎΠΌ ΡΠ»ΡΡΠ°Π΅, ΠΏΠΎΠΌΠ΅Π½ΡΠ² Π²Π΅ΡΡΠΈΠ½Ρ ΠΏΡΠΈ ΠΏΠ΅ΡΠ΅ΡΠ΅ΠΊΠ°ΡΡΠΈΡ ΡΡ ΡΡΠ±ΡΠ°Ρ ΠΌΠ΅ΡΡΠ°ΠΌΠΈ, ΠΏΠΎΠ»ΡΡΠΈΠΌ Π±ΠΎΠ»Π΅Π΅ ΠΊΠΎΡΠΎΡΠΊΠΈΠΉ ΡΡΡ).
Π ΠΏΠ΅ΡΠ²ΠΎΠΌ ΡΠ»ΡΡΠ°Π΅ ΠΊΡΠ°ΡΡΠ°ΠΉΡΠΈΠΌ ΡΠ²Π»ΡΠ΅ΡΡΡ ΡΡΡ 1−2-4−5-3−1, Π° Π²ΠΎ Π²ΡΠΎΡΠΎΠΌ — ΡΡΡ 1−2-3−4-5−1. ΠΠ½Π°Π»ΠΈΠ·ΠΈΡΡΡ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ Π΄ΡΡΠ³ΠΈΡ Π°Π½Π°Π»ΠΎΠ³ΠΈΡΠ½ΡΡ ΡΠ°ΡΠΏΠΎΠ»ΠΎΠΆΠ΅Π½ΠΈΠΉ ΠΏΡΡΠΈ ΠΈ Π±ΠΎΠ»Π΅Π΅ Π³ΠΎΡΠΎΠ΄ΠΎΠ², ΠΌΠΎΠΆΠ½ΠΎ ΡΠ΄Π΅Π»Π°ΡΡ ΡΠ»Π΅Π΄ΡΡΡΠ΅Π΅ ΠΎΠ±ΡΠ΅Π΅ ΠΏΡΠ΅Π΄ΠΏΠΎΠ»ΠΎΠΆΠ΅Π½ΠΈΠ΅:
1. ΠΡΠ»ΠΈ ΠΌΠΎΠΆΠ½ΠΎ ΠΏΠΎΡΡΡΠΎΠΈΡΡ Π²ΡΠΏΡΠΊΠ»ΡΠΉ ΠΌΠ½ΠΎΠ³ΠΎΡΠ³ΠΎΠ»ΡΠ½ΠΈΠΊ, ΠΏΠΎ ΠΏΠ΅ΡΠΈΠΌΠ΅ΡΡΡ ΠΊΠΎΡΠΎΡΠΎΠ³ΠΎ Π»Π΅ΠΆΠ°Ρ Π²ΡΠ΅ Π³ΠΎΡΠΎΠ΄Π°, ΡΠΎ ΡΠ°ΠΊΠΎΠΉ Π²ΡΠΏΡΠΊΠ»ΡΠΉ ΠΌΠ½ΠΎΠ³ΠΎΡΠ³ΠΎΠ»ΡΠ½ΠΈΠΊ ΡΠ²Π»ΡΠ΅ΡΡΡ ΠΊΡΠ°ΡΡΠ°ΠΉΡΠΈΠΌ ΡΡΡΠΎΠΌ.
ΠΠ΄Π½Π°ΠΊΠΎ Π½Π΅ Π²ΡΠ΅Π³Π΄Π° ΠΌΠΎΠΆΠ½ΠΎ ΠΏΠΎΡΡΡΠΎΠΈΡΡ Π²ΡΠΏΡΠΊΠ»ΡΠΉ ΠΌΠ½ΠΎΠ³ΠΎΡΠ³ΠΎΠ»ΡΠ½ΠΈΠΊ, ΠΏΠΎ ΠΏΠ΅ΡΠΈΠΌΠ΅ΡΡΡ ΠΊΠΎΡΠΎΡΠΎΠ³ΠΎ Π»Π΅ΠΆΠ°Π»ΠΈ Π±Ρ Π²ΡΠ΅ Π³ΠΎΡΠΎΠ΄Π°. ΠΠ΅Π»ΠΈΠΊΠ° Π²Π΅ΡΠΎΡΡΠ½ΠΎΡΡΡ ΡΠΎΠ³ΠΎ, ΡΡΠΎ Π½Π΅ΠΊΠΎΡΠΎΡΡΠ΅ Π³ΠΎΡΠΎΠ΄Π° Π½Π΅ Π²ΠΎΠΉΠ΄ΡΡ Π² Π²ΡΠΏΡΠΊΠ»ΡΠΉ ΠΌΠ½ΠΎΠ³ΠΎΡΠ³ΠΎΠ»ΡΠ½ΠΈΠΊ. Π’Π°ΠΊΠΈΠ΅ Π³ΠΎΡΠΎΠ΄Π° Π±ΡΠ΄Π΅ΠΌ Π½Π°Π·ΡΠ²Π°ΡΡ «ΡΠ΅Π½ΡΡΠ°Π»ΡΠ½ΡΠΌΠΈ». Π’Π°ΠΊ ΠΊΠ°ΠΊ ΠΏΠΎΡΡΡΠΎΠΈΡΡ Π²ΡΠΏΡΠΊΠ»ΡΠΉ ΠΌΠ½ΠΎΠ³ΠΎΡΠ³ΠΎΠ»ΡΠ½ΠΈΠΊ Π΄ΠΎΠ²ΠΎΠ»ΡΠ½ΠΎ Π»Π΅Π³ΠΊΠΎ, ΡΠΎ Π·Π°Π΄Π°ΡΠ° ΡΠ²ΠΎΠ΄ΠΈΡΡΡ ΠΊ ΡΠΎΠΌΡ, ΡΡΠΎΠ±Ρ Π²ΠΊΠ»ΡΡΠΈΡΡ Π² ΡΡΡ Π² Π²ΠΈΠ΄Π΅ Π²ΡΠΏΡΠΊΠ»ΠΎΠ³ΠΎ ΠΌΠ½ΠΎΠ³ΠΎΡΠ³ΠΎΠ»ΡΠ½ΠΈΠΊΠ° Π²ΡΠ΅ ΡΠ΅Π½ΡΡΠ°Π»ΡΠ½ΡΠ΅ Π³ΠΎΡΠΎΠ΄Π° Ρ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΡΠΌΠΈ ΠΏΠΎΡΠ΅ΡΡΠΌΠΈ. ΠΡΡΡΡ ΠΈΠΌΠ΅Π΅ΡΡΡ ΠΌΠ°ΡΡΠΈΠ² T[n+1], ΡΠΎΠ΄Π΅ΡΠΆΠ°ΡΠΈΠΉ Π² ΡΠ΅Π±Π΅ Π½ΠΎΠΌΠ΅ΡΠ° Π³ΠΎΡΠΎΠ΄ΠΎΠ² ΠΏΠΎ ΠΏΠΎΡΡΠ΄ΠΊΡ, ΠΊΠΎΡΠΎΡΡΠ΅ Π΄ΠΎΠ»ΠΆΠ΅Π½ ΠΏΠΎΡΠ΅ΡΠΈΡΡ ΠΊΠΎΠΌΠΌΠΈΠ²ΠΎΡΠΆΠ΅Ρ, Ρ. Π΅. Π²Π½Π°ΡΠ°Π»Π΅ ΠΊΠΎΠΌΠΌΠΈΠ²ΠΎΡΠΆΠ΅Ρ Π΄ΠΎΠ»ΠΆΠ΅Π½ ΠΏΠΎΡΠ΅ΡΠΈΡΡ Π³ΠΎΡΠΎΠ΄ T[1], Π·Π°ΡΠ΅ΠΌ T[2], ΠΏΠΎΡΠΎΠΌ T[3] ΠΈ Ρ. Π΄, ΠΏΡΠΈΡΡΠΌ T[n+1]=T[1] (ΠΊΠΎΠΌΠΌΠΈΠ²ΠΎΡΠΆΠ΅Ρ Π΄ΠΎΠ»ΠΆΠ΅Π½ Π²Π΅ΡΠ½ΡΡΡΡΡ Π² Π½Π°ΡΠ°Π»ΡΠ½ΡΠΉ Π³ΠΎΡΠΎΠ΄). Π’ΠΎΠ³Π΄Π°, Π΅ΡΠ»ΠΈ Π²ΡΠΏΠΎΠ»Π½ΡΠ΅ΡΡΡ ΡΠ°Π²Π΅Π½ΡΡΠ²ΠΎ «i?[1,2.n];
C[T[i], p]+C[p, T[i+1]] - C[T[I], T[i+1]]=min,.
ΡΠΎ ΡΠ΅Π½ΡΡΠ°Π»ΡΠ½ΡΠΉ Π³ΠΎΡΠΎΠ΄ Ρ Π½ΠΎΠΌΠ΅ΡΠΎΠΌ p Π½ΡΠΆΠ½ΠΎ Π²ΠΊΠ»ΡΡΠΈΡΡ Π² ΡΡΡ ΠΌΠ΅ΠΆΠ΄Ρ Π³ΠΎΡΠΎΠ΄Π°ΠΌΠΈ T[i] ΠΈ T[i+1]. ΠΡΠΎΠ΄Π΅Π»Π°Π² ΡΡΡ ΠΎΠΏΠ΅ΡΠ°ΡΠΈΡ Π΄Π»Ρ Π²ΡΠ΅Ρ ΡΠ΅Π½ΡΡΠ°Π»ΡΠ½ΡΡ Π³ΠΎΡΠΎΠ΄ΠΎΠ², Π² ΡΠ΅Π·ΡΠ»ΡΡΠ°ΡΠ΅ ΠΏΠΎΠ»ΡΡΠΈΠΌ ΠΊΡΠ°ΡΡΠ°ΠΉΡΠΈΠΉ ΡΡΡ. ΠΠ°Π½Π½ΡΠΉ Π°Π»Π³ΠΎΡΠΈΡΠΌ ΠΌΠΎΠΆΠ½ΠΎ ΡΠ΅Π°Π»ΠΈΠ·ΠΎΠ²Π°ΡΡ Π½Π° ΡΠ·ΡΠΊΠ΅ ΠΠ°ΡΠΊΠ°Π»Ρ ΠΈ ΠΏΡΠΎΠ²Π΅ΡΠΈΡΡ Π²Π΅ΡΠ½ΠΎΡΡΡ ΠΏΡΠ΅Π΄ΠΏΠΎΠ»ΠΎΠΆΠ΅Π½ΠΈΡ 1. ΠΠ»Ρ Π·Π°Π΄Π°ΡΠΈ, ΡΠ΅ΡΡΠ½Π½ΠΎΠΉ Π½Π°ΠΌΠΈ ΠΌΠ΅ΡΠΎΠ΄ΠΎΠΌ Π²Π΅ΡΠ²Π΅ΠΉ ΠΈ Π³ΡΠ°Π½ΠΈΡ, ΠΌΠΎΠΉ Π°Π»Π³ΠΎΡΠΈΡΠΌ Π΄Π°ΡΡ ΠΏΡΠ°Π²ΠΈΠ»ΡΠ½ΠΎΠ΅ ΡΠ΅ΡΠ΅Π½ΠΈΠ΅.
ΠΠΎΠΏΡΠΎΠ±ΡΠ΅ΠΌ ΡΠ΅ΡΠΈΡΡ Π΄Π°Π½Π½ΡΠΌ Π°Π»Π³ΠΎΡΠΈΡΠΌΠΎΠΌ ΠΠ Π΄Π»Ρ Π²ΠΎΡΡΠΌΠΈ Π³ΠΎΡΠΎΠ΄ΠΎΠ². ΠΡΡΡΡ ΠΈΠΌΠ΅Π΅ΠΌ Π²ΠΎΡΠ΅ΠΌΡ Π³ΠΎΡΠΎΠ΄ΠΎΠ², ΡΠ°ΡΠΏΠΎΠ»ΠΎΠΆΠ΅Π½ΠΈΠ΅ ΠΊΠΎΡΠΎΡΡΡ ΠΏΠΎΠΊΠ°Π·Π°Π½ΠΎ Π½Π° ΡΠΈΡ. 11. ΠΠ°ΡΡΠΈΡΠ° ΡΠ°ΡΡΡΠΎΡΠ½ΠΈΠΉ ΠΏΡΠΈΠ²Π΅Π΄Π΅Π½Π° ΡΡΠ΄ΠΎΠΌ Π½Π° ΡΠ°Π±Π». 13. ΠΡΠΎΠΌΠ΅ΠΆΡΡΠΎΡΠ½ΡΠ΅ ΠΏΠΎΡΡΡΠΎΠ΅Π½ΠΈΡ ΠΊΡΠ°ΡΡΠ°ΠΉΡΠ΅Π³ΠΎ ΡΡΡΠ° ΠΏΠΎΠΊΠ°Π·Π°Π½Ρ ΠΏΡΠ½ΠΊΡΠΈΡΠ½ΡΠΌΠΈ Π»ΠΈΠ½ΠΈΡΠΌΠΈ, ΡΠΈΡΡΡ — ΠΏΠΎΡΡΠ΄ΠΎΠΊ ΡΠ΄Π°Π»Π΅Π½ΠΈΡ ΡΡΠ±Π΅Ρ. Π’Π°ΠΊΠΈΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ, ΠΈΠΌΠ΅Π΅ΠΌ Π΄Π»Ρ Π΄Π°Π½Π½ΠΎΠ³ΠΎ ΡΠ»ΡΡΠ°Ρ ΠΊΡΠ°ΡΡΠ°ΠΉΡΠΈΠΉ ΡΡΡ 1−3-7−5-4−8-6−2-1. ΠΠ»ΠΈΠ½Π° ΡΡΠΎΠ³ΠΎ ΡΡΡΠ°: D=6+7+5+2+6+5+13+13=57. ΠΡΠΎΡ ΡΠ΅Π·ΡΠ»ΡΡΠ°Ρ ΡΠ²Π»ΡΠ΅ΡΡΡ ΠΏΡΠ°Π²ΠΈΠ»ΡΠ½ΡΠΌ, Ρ. ΠΊ. Π°Π»Π³ΠΎΡΠΈΡΠΌ Π»Π΅ΠΊΡΠΈΡΠ΅ΡΠΊΠΎΠ³ΠΎ ΠΏΠ΅ΡΠ΅Π±ΠΎΡΠ°, ΠΊΠΎΡΠΎΡΡΠΉ Π½ΠΈΠΊΠΎΠ³Π΄Π° Π½Π΅ ΠΎΡΠΈΠ±Π°Π΅ΡΡΡ, Π΄Π°ΡΡ ΡΠΎΡΠ½ΠΎ ΡΠ°ΠΊΠΎΠΉ ΠΆΠ΅ ΡΡΡ. (Π‘Π»Π΅Π΄ΡΠ΅Ρ ΡΠ°ΠΊΠΆΠ΅ ΠΎΡΠΌΠ΅ΡΠΈΡΡ, ΡΡΠΎ ΠΆΠ°Π΄Π½ΡΠΉ Π°Π»Π³ΠΎΡΠΈΡΠΌ Π΄Π»Ρ ΡΡΠΎΠ³ΠΎ ΡΠ»ΡΡΠ°Ρ ΠΎΡΠΈΠ±Π°Π΅ΡΡΡ Π²ΡΠ΅Π³ΠΎ Π½Π° 1 ΠΈ Π΄Π°ΡΡ ΡΡΡ 1−3-4−5-7−8-6−2-1 Π΄Π»ΠΈΠ½ΠΎΠΉ Π² 58).
ΡΠ°Π±Π». 13.