Π”ΠΈΠΏΠ»ΠΎΠΌ, курсовая, ΠΊΠΎΠ½Ρ‚Ρ€ΠΎΠ»ΡŒΠ½Π°Ρ Ρ€Π°Π±ΠΎΡ‚Π°
ΠŸΠΎΠΌΠΎΡ‰ΡŒ Π² написании студСнчСских Ρ€Π°Π±ΠΎΡ‚

ΠœΠ΅Ρ‚ΠΎΠ΄ АнищСнко. 
Π—Π°Π΄Π°Ρ‡Π° комивояТСра

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

Однако Π½Π΅ Π²ΡΠ΅Π³Π΄Π° ΠΌΠΎΠΆΠ½ΠΎ ΠΏΠΎΡΡ‚Ρ€ΠΎΠΈΡ‚ΡŒ Π²Ρ‹ΠΏΡƒΠΊΠ»Ρ‹ΠΉ ΠΌΠ½ΠΎΠ³ΠΎΡƒΠ³ΠΎΠ»ΡŒΠ½ΠΈΠΊ, ΠΏΠΎ ΠΏΠ΅Ρ€ΠΈΠΌΠ΅Ρ‚Ρ€Ρƒ ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠ³ΠΎ Π»Π΅ΠΆΠ°Π»ΠΈ Π±Ρ‹ всС Π³ΠΎΡ€ΠΎΠ΄Π°. Π’Π΅Π»ΠΈΠΊΠ° Π²Π΅Ρ€ΠΎΡΡ‚Π½ΠΎΡΡ‚ΡŒ Ρ‚ΠΎΠ³ΠΎ, Ρ‡Ρ‚ΠΎ Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ Π³ΠΎΡ€ΠΎΠ΄Π° Π½Π΅ Π²ΠΎΠΉΠ΄ΡƒΡ‚ Π² Π²Ρ‹ΠΏΡƒΠΊΠ»Ρ‹ΠΉ ΠΌΠ½ΠΎΠ³ΠΎΡƒΠ³ΠΎΠ»ΡŒΠ½ΠΈΠΊ. Π’Π°ΠΊΠΈΠ΅ Π³ΠΎΡ€ΠΎΠ΄Π° Π±ΡƒΠ΄Π΅ΠΌ Π½Π°Π·Ρ‹Π²Π°Ρ‚ΡŒ «Ρ†Π΅Π½Ρ‚Ρ€Π°Π»ΡŒΠ½Ρ‹ΠΌΠΈ». Π’Π°ΠΊ ΠΊΠ°ΠΊ ΠΏΠΎΡΡ‚Ρ€ΠΎΠΈΡ‚ΡŒ Π²Ρ‹ΠΏΡƒΠΊΠ»Ρ‹ΠΉ ΠΌΠ½ΠΎΠ³ΠΎΡƒΠ³ΠΎΠ»ΡŒΠ½ΠΈΠΊ довольно Π»Π΅Π³ΠΊΠΎ, Ρ‚ΠΎ Π·Π°Π΄Π°Ρ‡Π° сводится ΠΊ Ρ‚ΠΎΠΌΡƒ, Ρ‡Ρ‚ΠΎΠ±Ρ‹ Π²ΠΊΠ»ΡŽΡ‡ΠΈΡ‚ΡŒ Π² Ρ‚ΡƒΡ€ Π² Π²ΠΈΠ΄Π΅ Π²Ρ‹ΠΏΡƒΠΊΠ»ΠΎΠ³ΠΎ ΠΌΠ½ΠΎΠ³ΠΎΡƒΠ³ΠΎΠ»ΡŒΠ½ΠΈΠΊΠ° всС Ρ†Π΅Π½Ρ‚Ρ€Π°Π»ΡŒΠ½Ρ‹Π΅ Π³ΠΎΡ€ΠΎΠ΄Π°… Π§ΠΈΡ‚Π°Ρ‚ΡŒ Π΅Ρ‰Ρ‘ >

ΠœΠ΅Ρ‚ΠΎΠ΄ АнищСнко. Π—Π°Π΄Π°Ρ‡Π° комивояТСра (Ρ€Π΅Ρ„Π΅Ρ€Π°Ρ‚, курсовая, Π΄ΠΈΠΏΠ»ΠΎΠΌ, ΠΊΠΎΠ½Ρ‚Ρ€ΠΎΠ»ΡŒΠ½Π°Ρ)

Рассмотрим рис. 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.

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