ΠΡΠ½ΠΎΠ²Ρ ΡΠ΅Ρ Π½ΠΎΠ»ΠΎΠ³ΠΈΠΉ, ΠΎΡΠ³Π°Π½ΠΈΠ·Π°ΡΠΈΠΈ ΠΈ ΠΏΡΠΎΠ΅ΠΊΡΠΈΡΠΎΠ²Π°Π½ΠΈΡ ΠΏΡΠ΅Π΄ΠΏΡΠΈΡΡΠΈΡ, Π²Π°ΡΠΈΠ°Π½Ρ 11 (ΠΈΠ½Π΄ΠΈΠ²ΠΈΠ΄ΡΠ°Π»ΡΠ½ΠΎΠ΅ Π·Π°Π΄Π°Π½ΠΈΠ΅)
ΠΠΎΠ½ΡΡΠΎΠ»ΡΠ½Π°Ρ
8 10. Π Π΅Π·ΡΠ»ΡΡΠ°ΡΡ ΡΠ°ΡΡΠ΅ΡΠ° ΠΎΡΠ½ΠΎΠ²Π½ΡΡ ΠΏΠ°ΡΠ°ΠΌΠ΅ΡΡΠΎΠ² ΡΠ΅ΡΠ΅Π²ΠΎΠ³ΠΎ Π³ΡΠ°ΡΠΈΠΊΠ° Π·Π°Π½Π΅ΡΡΠΈ Π² ΡΠ°Π±Π». 6 6. Π’Π°Π±Π». 1 — ΠΡΠ΅Π½ΠΊΠ° ΠΏΡΠΎΠ΄ΠΎΠ»ΠΆΠΈΡΠ΅Π»ΡΠ½ΠΎΡΡΠΈ Π²ΡΠΏΠΎΠ»Π½Π΅Π½ΠΈΡ ΡΠ°Π±ΠΎΡ Π Π°Π±ΠΎΡΡ (i, j) tmin tΠ½Π² tmax tΠΎΠΆij ο³2ij. 10 10. I. (j) i j tΡi tΠΏi tΡΠ½ij tΠΏΠ½ij tΡΠΎij tΠΏΠΎij Ri RΠΏij RΡΠ²ij. Π Π°Π½Π½ΠΈΠ΅ ΠΈ ΠΏΠΎΠ·Π΄Π½ΠΈΠ΅ ΡΡΠΎΠΊΠΈ ΡΠ²Π΅ΡΡΠ΅Π½ΠΈΡ ΡΠΎΠ±ΡΡΠΈΠΉ. ΠΠΎ ΠΏΡΠ΅Π΄Π»ΠΎΠΆΠ΅Π½Π½ΠΎΠΌΡ ΠΏΡΠ΅ΠΏΠΎΠ΄Π°Π²Π°ΡΠ΅Π»Π΅ΠΌ Π²Π°ΡΠΈΠ°Π½ΡΡ ΠΈΡΡ ΠΎΠ΄Π½ΡΡ Π΄Π°Π½Π½ΡΡ ΡΠ°ΡΡΡΠΈΡΠ°ΡΡ tΠΎΠΆij, ο³2ij Π΄Π»Ρ Π²ΡΠ΅Ρ ΡΠ°Π±ΠΎΡ ΠΈ Π·Π°ΠΏΠΎΠ»Π½ΠΈΡΡ ΡΠ°Π±Π». 10… Π§ΠΈΡΠ°ΡΡ Π΅ΡΡ >
Π‘ΠΎΠ΄Π΅ΡΠΆΠ°Π½ΠΈΠ΅
- ΠΠΠΠΠΠΠΠ£ΠΠΠ¬ΠΠΠ ΠΠΠΠΠΠΠ
- 1. ΠΠΎ ΠΏΡΠ΅Π΄Π»ΠΎΠΆΠ΅Π½Π½ΠΎΠΌΡ ΠΏΡΠ΅ΠΏΠΎΠ΄Π°Π²Π°ΡΠ΅Π»Π΅ΠΌ Π²Π°ΡΠΈΠ°Π½ΡΡ ΠΈΡΡ ΠΎΠ΄Π½ΡΡ Π΄Π°Π½Π½ΡΡ ΡΠ°ΡΡΡΠΈΡΠ°ΡΡ tΠΎΠΆij, ο³2ij Π΄Π»Ρ Π²ΡΠ΅Ρ ΡΠ°Π±ΠΎΡ ΠΈ Π·Π°ΠΏΠΎΠ»Π½ΠΈΡΡ ΡΠ°Π±Π»
- Π’Π°Π±Π». 1 — ΠΡΠ΅Π½ΠΊΠ° ΠΏΡΠΎΠ΄ΠΎΠ»ΠΆΠΈΡΠ΅Π»ΡΠ½ΠΎΡΡΠΈ Π²ΡΠΏΠΎΠ»Π½Π΅Π½ΠΈΡ ΡΠ°Π±ΠΎΡ Π Π°Π±ΠΎΡΡ (i, j) tmin tΠ½Π² tmax tΠΎΠΆij ο³2ij
- 2. Π‘ΡΠΎΡΠΌΠΈΡΠΎΠ²Π°ΡΡ ΡΠ΅ΡΠ΅Π²ΠΎΠΉ Π³ΡΠ°ΡΠΈΠΊ, Π² ΠΊΠΎΡΠΎΡΠΎΠΌ ΡΠ°Π±ΠΎΡΡ ΠΎΠ±ΠΎΠ·Π½Π°ΡΠ°ΡΡΡΡ Π΄ΡΠ³Π°ΠΌΠΈ, ΡΠΎΠ±ΡΡΠΈΡ — Π²Π΅ΡΡΠΈΠ½Π°ΠΌΠΈ, ΠΎΡΡΠ°Π·ΠΈΡΡ Π² Π½Π΅ΠΌ tΠΎΠΆij, ΠΈ ΡΠ°ΡΡΡΠΈΡΠ°ΡΡ ΡΠ»Π΅Π΄ΡΡΡΠΈΠ΅ ΠΏΠ°ΡΠ°ΠΌΠ΅ΡΡΡ: ΠΊΡΠΈΡΠΈΡΠ΅ΡΠΊΠΈΠΉ ΠΏΡΡΡ ()
- ΡΠ°Π½Π½ΠΈΠ΅ ΠΈ ΠΏΠΎΠ·Π΄Π½ΠΈΠ΅ ΡΡΠΎΠΊΠΈ ΡΠ²Π΅ΡΡΠ΅Π½ΠΈΡ ΡΠΎΠ±ΡΡΠΈΠΉ
- ΡΡΠΎΠΊΠΈ Π½Π°ΡΠ°Π»Π° ΠΈ ΠΎΠΊΠΎΠ½ΡΠ°Π½ΠΈΡ ΡΠ°Π±ΠΎΡ
- ΡΠ΅Π·Π΅ΡΠ²Ρ Π²ΡΠ΅ΠΌΠ΅Π½ΠΈ
- 3. Π Π΅Π·ΡΠ»ΡΡΠ°ΡΡ ΡΠ°ΡΡΠ΅ΡΠ° ΠΎΡΠ½ΠΎΠ²Π½ΡΡ ΠΏΠ°ΡΠ°ΠΌΠ΅ΡΡΠΎΠ² ΡΠ΅ΡΠ΅Π²ΠΎΠ³ΠΎ Π³ΡΠ°ΡΠΈΠΊΠ° Π·Π°Π½Π΅ΡΡΠΈ Π² ΡΠ°Π±Π»
- Π’Π°Π±Π».2 — Π Π΅Π·ΡΠ»ΡΡΠ°ΡΡ ΡΠ°ΡΡΠ΅ΡΠΎΠ² ΠΎΡΠ½ΠΎΠ²Π½ΡΡ ΠΏΠ°ΡΠ°ΠΌΠ΅ΡΡΠΎΠ² ΡΠ΅ΡΠ΅Π²ΠΎΠ³ΠΎ Π³ΡΠ°ΡΠΈΠΊΠ° Π‘ΠΎΠ±Ρ- Π Π°Π±ΠΎΡΠ° Π‘ΡΠΎΠΊΠΈ ΡΠ²Π΅ΡΡΠ΅Π½ΠΈΡ Π Π΅Π·Π΅ΡΠ²Ρ ΡΠΈΠ΅ ΡΠΎΠ±ΡΡΠΈΠΉ ΡΠ°Π±ΠΎΡ
- i. (j) i j tΡi tΠΏi tΡΠ½ij tΠΏΠ½ij tΡΠΎij tΠΏΠΎij Ri RΠΏij RΡΠ²ij
- 4. ΠΡΡΠ°Π·ΠΈΡΡ Π½Π° ΡΠ΅ΡΠ΅Π²ΠΎΠΌ Π³ΡΠ°ΡΠΈΠΊΠ΅: ΠΊΡΠΈΡΠΈΡΠ΅ΡΠΊΠΈΠΉ ΠΏΡΡΡ ()
- ΡΠ°Π½Π½ΠΈΠ΅ ΠΈ ΠΏΠΎΠ·Π΄Π½ΠΈΠ΅ ΡΡΠΎΠΊΠΈ ΡΠ²Π΅ΡΡΠ΅Π½ΠΈΡ ΡΠΎΠ±ΡΡΠΈΠΉ
- ΡΠ΅Π·Π΅ΡΠ²Ρ Π²ΡΠ΅ΠΌΠ΅Π½ΠΈ ΡΠΎΠ±ΡΡΠΈΠΉ
- 5. ΠΡΡΠΈΡΠ»ΠΈΡΡ Π²Π΅ΡΠΎΡΡΠ½ΠΎΡΡΡ ΡΠ²Π΅ΡΡΠ΅Π½ΠΈΡ Π·Π°Π²Π΅ΡΡΠ°ΡΡΠ΅Π³ΠΎ ΡΠΎΠ±ΡΡΠΈΡ Π² Π·Π°Π΄Π°Π½Π½ΡΠΉ ΡΡΠΎΠΊ, ΡΡΡΠ°Π½ΠΎΠ²ΠΈΠ² — Π·Π°Π΄Π°Π½Π½ΡΠΉ ΡΡΠΎΠΊ ΡΠ²Π΅ΡΡΠ΅Π½ΠΈΡ Π·Π°Π²Π΅ΡΡΠ°ΡΡΠ΅Π³ΠΎ ΡΠΎΠ±ΡΡΠΈΡ,
- ΠΠ°ΡΠΈΠ°Π½Ρ β
- Π Π°Π±ΠΎΡΡ (i, j) tmin tΠ½Π² tmax tΠΎΠΆij ο³2ij
- 1. — 2 16
- 1. — 3 20
- 2. — 4 10
- 2. — 5 8
- 3. — 5 Π€ΠΈΠΊΡΠΈΠ²Π½Π°Ρ ΡΠ°Π±ΠΎΡΠ°
- 3. — 6 6
- 4. — 7 3
- 5. — 8 10
- 6. — 8 Π€ΠΈΠΊΡΠΈΠ²Π½Π°Ρ ΡΠ°Π±ΠΎΡΠ°
- 6. — 9 6
- 7. — 8 2
- 7. — 10 Π€ΠΈΠΊΡΠΈΠ²Π½Π°Ρ ΡΠ°Π±ΠΎΡΠ°
- 8. — 9 6
- 8. — 10 10
- 8. — 11 Π€ΠΈΠΊΡΠΈΠ²Π½Π°Ρ ΡΠ°Π±ΠΎΡΠ°
- 9. — 11 2
- 10. — 11 6