🌌 10 Π°Π½ΠΈΠΌΠΈΡ€ΠΎΠ²Π°Π½Π½Ρ‹Ρ… Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² Π½Π° Π³Ρ€Π°Ρ„Π°Ρ…

ΠšΡ€Π°Ρ‚ΠΊΠΎΠ΅ описаниС дСсяти основных Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² Π½Π° Π³Ρ€Π°Ρ„Π°Ρ… с Π²ΠΈΠ·ΡƒΠ°Π»ΠΈΠ·Π°Ρ†ΠΈΠ΅ΠΉ Π³Ρ€Π°Ρ„ΠΎΠ² ΠΈ ΠΏΡ€ΠΈΠΌΠ΅Ρ€Π°ΠΌΠΈ использования Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² Π½Π° ΠΏΡ€Π°ΠΊΡ‚ΠΈΠΊΠ΅.

Если Ρ…ΠΎΡ‡Π΅ΡˆΡŒ ΠΏΠΎΠ΄Ρ‚ΡΠ½ΡƒΡ‚ΡŒ свои знания, загляни Π½Π° наш курс «Алгоритмы ΠΈ структуры Π΄Π°Π½Π½Ρ‹Ρ…Β», Π½Π° ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΌ Ρ‚Ρ‹:

  1. ΡƒΠ³Π»ΡƒΠ±ΠΈΡˆΡŒΡΡ Π² Ρ€Π΅ΡˆΠ΅Π½ΠΈΠ΅ практичСских Π·Π°Π΄Π°Ρ‡;
  2. ΡƒΠ·Π½Π°Π΅ΡˆΡŒ всС ΠΏΡ€ΠΎ слоТныС Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹, сортировки, сТатиС Π΄Π°Π½Π½Ρ‹Ρ… ΠΈ ΠΌΠ½ΠΎΠ³ΠΎΠ΅ Π΄Ρ€ΡƒΠ³ΠΎΠ΅.

Π’Ρ‹ Ρ‚Π°ΠΊΠΆΠ΅ Π±ΡƒΠ΄Π΅ΡˆΡŒ Π½Π° связи с ΠΏΡ€Π΅ΠΏΠΎΠ΄Π°Π²Π°Ρ‚Π΅Π»Π΅ΠΌ ΠΈ Π΄Ρ€ΡƒΠ³ΠΈΠΌΠΈ студСнтами.

Π’ ΠΈΡ‚ΠΎΠ³Π΅ Π±ΡƒΠ΄Π΅ΡˆΡŒ Π±Ρ€Π°Ρ‚ΡŒΡΡ Π·Π° слоТныС ΠΏΡ€ΠΎΠ΅ΠΊΡ‚Ρ‹ ΠΈ ΠΏΠΎΠ²Ρ‹ΡΠΈΡˆΡŒ Ρ‡Π΅ΠΊ Π·Π° свою Ρ€Π°Π±ΠΎΡ‚Ρƒ πŸ™‚

***

Π“Ρ€Π°Ρ„Ρ‹ стали ΠΌΠΎΡ‰Π½Ρ‹ΠΌ срСдством модСлирования ΠΈ прСдставлСния Π΄Π°Π½Π½Ρ‹Ρ… ΠΈΠ· Π·Π°Π΄Π°Ρ‡ Ρ€Π΅Π°Π»ΡŒΠ½ΠΎΠ³ΠΎ ΠΌΠΈΡ€Π°, Ρ‚Π°ΠΊΠΈΡ…, ΠΊΠ°ΠΊ ΡΠΎΡ†ΠΈΠ°Π»ΡŒΠ½Ρ‹Π΅ сСти, Π²Π΅Π±-страницы ΠΈ ссылки, Π° Ρ‚Π°ΠΊΠΆΠ΅ Π»ΠΎΠΊΠ°Ρ†ΠΈΠΈ ΠΈ ΠΌΠ°Ρ€ΡˆΡ€ΡƒΡ‚Ρ‹ Π² GPS. Если Π΅ΡΡ‚ΡŒ Π½Π°Π±ΠΎΡ€ связанных Π΄Ρ€ΡƒΠ³ с Π΄Ρ€ΡƒΠ³ΠΎΠΌ ΠΎΠ±ΡŠΠ΅ΠΊΡ‚ΠΎΠ², ΠΈΡ… ΠΌΠΎΠΆΠ½ΠΎ ΠΏΡ€Π΅Π΄ΡΡ‚Π°Π²ΠΈΡ‚ΡŒ Π² Π²ΠΈΠ΄Π΅ Π³Ρ€Π°Ρ„Π°.

Π’ этой ΡΡ‚Π°Ρ‚ΡŒΠ΅ ΠΌΡ‹ Π²ΠΊΡ€Π°Ρ‚Ρ†Π΅ опишСм Π΄Π΅ΡΡΡ‚ΡŒ ΡˆΠΈΡ€ΠΎΠΊΠΎ примСняСмых Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² Π½Π° Π³Ρ€Π°Ρ„Π°Ρ… ΠΈ ΠΈΡ… прилоТСния. Для Π½Π°Ρ‡Π°Π»Π° Π΄Π°Π²Π°ΠΉΡ‚Π΅ освСТим свои знания ΠΎ Π³Ρ€Π°Ρ„Π°Ρ….

ΠŸΡ€ΠΈΠΌΠ΅Ρ‡Π°Π½ΠΈΠ΅
Если Π²Ρ‹ Ρ‚ΠΎΠ»ΡŒΠΊΠΎ Π·Π½Π°ΠΊΠΎΠΌΠΈΡ‚Π΅ΡΡŒ с Π³Ρ€Π°Ρ„Π°ΠΌΠΈ, ΠΌΡ‹ ΠΏΠΎΠ΄Π³ΠΎΡ‚ΠΎΠ²ΠΈΠ»ΠΈ ΠΏΠΎΠ΄Ρ€ΠΎΠ±Π½ΠΎ ΠΈΠ»Π»ΡŽΡΡ‚Ρ€ΠΈΡ€ΠΎΠ²Π°Π½Π½ΠΎΠ΅ Π²Π²Π΅Π΄Π΅Π½ΠΈΠ΅ Π² Ρ‚Π΅ΠΎΡ€ΠΈΡŽ Π³Ρ€Π°Ρ„ΠΎΠ².

Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ Π³Ρ€Π°Ρ„?

Рис. 1. Визуализация Ρ‚Π΅Ρ€ΠΌΠΈΠ½ΠΎΠ»ΠΎΠ³ΠΈΠΈ Π³Ρ€Π°Ρ„ΠΎΠ²

Π“Ρ€Π°Ρ„ – это ΠΊΠΎΠ½Π΅Ρ‡Π½ΠΎΠ΅ мноТСство Π²Π΅Ρ€ΡˆΠΈΠ½ (ΠΈΠ»ΠΈ ΡƒΠ·Π»ΠΎΠ²) ΠΈ мноТСство Ρ€Π΅Π±Π΅Ρ€, ΡΠΎΠ΅Π΄ΠΈΠ½ΡΡŽΡ‰ΠΈΡ… эти Π²Π΅Ρ€ΡˆΠΈΠ½Ρ‹. Π”Π²Π΅ Π²Π΅Ρ€ΡˆΠΈΠ½Ρ‹ Π½Π°Π·Ρ‹Π²Π°ΡŽΡ‚ΡΡ сосСдними, Ссли ΠΎΠ½ΠΈ соСдинСны Π΄Ρ€ΡƒΠ³ с Π΄Ρ€ΡƒΠ³ΠΎΠΌ Ρ€Π΅Π±Ρ€ΠΎΠΌ. НиТС ΠΏΡ€ΠΈΠ²Π΅Π΄Π΅Π½ΠΎ нСсколько основных ΠΎΠΏΡ€Π΅Π΄Π΅Π»Π΅Π½ΠΈΠΉ, относящихся ΠΊ Π³Ρ€Π°Ρ„Π°ΠΌ, ΠΏΡ€ΠΈΠΌΠ΅Ρ€Ρ‹ ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… ΠΌΠΎΠΆΠ½ΠΎ ΡƒΠ²ΠΈΠ΄Π΅Ρ‚ΡŒ Π½Π° Рис. 1.

  • ΠŸΡƒΡ‚ΡŒ – ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΡŒ Π²Π΅Ρ€ΡˆΠΈΠ½, Π² ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΉ каТдая Π²Π΅Ρ€ΡˆΠΈΠ½Π° соСдинСна со ΡΠ»Π΅Π΄ΡƒΡŽΡ‰Π΅ΠΉ Π²Π΅Ρ€ΡˆΠΈΠ½ΠΎΠΉ Ρ€Π΅Π±Ρ€ΠΎΠΌ. На Рис. 1 красными стрСлками ΠΏΠΎΠΊΠ°Π·Π°Π½ ΠΏΡƒΡ‚ΡŒ ΠΎΡ‚ Π²Π΅Ρ€ΡˆΠΈΠ½Ρ‹ 1 ΠΊ Π²Π΅Ρ€Π΅ΡˆΠΈΠ½Π΅ 3 Ρ‡Π΅Ρ€Π΅Π· Π²Π΅Ρ€ΡˆΠΈΠ½Ρƒ 4.
  • ΠŸΠΎΡ€ΡΠ΄ΠΎΠΊ – количСство Π²Π΅Ρ€ΡˆΠΈΠ½ Π³Ρ€Π°Ρ„Π°.
  • Π Π°Π·ΠΌΠ΅Ρ€ – количСство Ρ€Π΅Π±Π΅Ρ€ Π³Ρ€Π°Ρ„Π°.
  • Π‘Π²ΡΠ·Π½ΠΎΡΡ‚ΡŒ (ΡΡ‚Π΅ΠΏΠ΅Π½ΡŒ связности) Π²Π΅Ρ€ΡˆΠΈΠ½Ρ‹ – количСство Ρ€Π΅Π±Π΅Ρ€, исходящих ΠΈΠ· этой Π²Π΅Ρ€ΡˆΠΈΠ½Ρ‹.
  • Π˜Π·ΠΎΠ»ΠΈΡ€ΠΎΠ²Π°Π½Π½Π°Ρ Π²Π΅Ρ€ΡˆΠΈΠ½Π° – Π²Π΅Ρ€ΡˆΠΈΠ½Π°, Π½Π΅ связанная с Π΄Ρ€ΡƒΠ³ΠΈΠΌΠΈ Π²Π΅Ρ€ΡˆΠΈΠ½Π°ΠΌΠΈ Π³Ρ€Π°Ρ„Π°.
  • ΠŸΠ΅Ρ‚Π»Ρ – Ρ€Π΅Π±Ρ€ΠΎ ΠΎΡ‚ Π²Π΅Ρ€ΡˆΠΈΠ½Ρ‹ ΠΊ этой ΠΆΠ΅ Π²Π΅Ρ€ΡˆΠΈΠ½Π΅.
  • ΠžΡ€ΠΈΠ΅Π½Ρ‚ΠΈΡ€ΠΎΠ²Π°Π½Π½Ρ‹ΠΉ Π³Ρ€Π°Ρ„ – Π³Ρ€Π°Ρ„, Π² ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΌ всС Ρ€Π΅Π±Ρ€Π° ΠΈΠΌΠ΅ΡŽΡ‚ Π½Π°ΠΏΡ€Π°Π²Π»Π΅Π½ΠΈΠ΅, ΡƒΠΊΠ°Π·Ρ‹Π²Π°ΡŽΡ‰Π΅Π΅, какая ΠΈΠ· Π²Π΅Ρ€ΡˆΠΈΠ½ Ρ€Π΅Π±Ρ€Π° являСтся Π½Π°Ρ‡Π°Π»ΡŒΠ½ΠΎΠΉ, Π° какая – ΠΊΠΎΠ½Π΅Ρ‡Π½ΠΎΠΉ.
  • НСориСнтированный Π³Ρ€Π°Ρ„ – Π³Ρ€Π°Ρ„, Π² ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΌ Ρƒ Ρ€Π΅Π±Π΅Ρ€ Π½Π΅Ρ‚ Π½Π°ΠΏΡ€Π°Π²Π»Π΅Π½ΠΈΠΉ.
  • Π’Π·Π²Π΅ΡˆΠ΅Π½Π½Ρ‹ΠΉ Π³Ρ€Π°Ρ„ – всС Ρ€Π΅Π±Ρ€Π° Π³Ρ€Π°Ρ„Π° ΠΈΠΌΠ΅ΡŽΡ‚ вСса.
  • ΠΠ΅Π²Π·Π²Π΅ΡˆΠ΅Π½Π½Ρ‹ΠΉ Π³Ρ€Π°Ρ„ – Ρ€Π΅Π±Ρ€Π° Π³Ρ€Π°Ρ„Π° Π½Π΅ ΠΈΠΌΠ΅ΡŽΡ‚ вСсов.

1. Поиск Π² ΡˆΠΈΡ€ΠΈΠ½Ρƒ

ΠžΠ±Ρ…ΠΎΠ΄ ΠΈΠ»ΠΈ поиск – ΠΎΠ΄Π½Π° ΠΈΠ· основных ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΉ, ΠΊΠΎΡ‚ΠΎΡ€ΡƒΡŽ ΠΌΠΎΠΆΠ½ΠΎ провСсти Π½Π° Π³Ρ€Π°Ρ„Π΅. ΠŸΡ€ΠΈ поискС Π² ΡˆΠΈΡ€ΠΈΠ½Ρƒ ΠΌΡ‹ Π½Π°Ρ‡ΠΈΠ½Π°Π΅ΠΌ с ΠΎΠΏΡ€Π΅Π΄Π΅Π»Π΅Π½Π½ΠΎΠΉ Π²Π΅Ρ€ΡˆΠΈΠ½Ρ‹ ΠΈ исслСдуСм всСх Π΅Π΅ сосСдСй Π½Π° Ρ‚ΠΎΠΌ ΠΆΠ΅ ΡƒΡ€ΠΎΠ²Π½Π΅, ΠΏΡ€Π΅ΠΆΠ΄Π΅ Ρ‡Π΅ΠΌ ΠΏΠ΅Ρ€Π΅Ρ…ΠΎΠ΄ΠΈΡ‚ΡŒ ΠΊ ΡΠ»Π΅Π΄ΡƒΡŽΡ‰Π΅ΠΌΡƒ ΡƒΡ€ΠΎΠ²Π½ΡŽ.

Π’ ΠΎΡ‚Π»ΠΈΡ‡ΠΈΠ΅ ΠΎΡ‚ Π΄Π΅Ρ€Π΅Π²ΡŒΠ΅Π², Π³Ρ€Π°Ρ„Ρ‹ ΠΌΠΎΠ³ΡƒΡ‚ ΡΠΎΠ΄Π΅Ρ€ΠΆΠ°Ρ‚ΡŒ Ρ†ΠΈΠΊΠ»Ρ‹ (ΠΏΡƒΡ‚ΠΈ, Π² ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… Π½Π°Ρ‡Π°Π»ΡŒΠ½Π°Ρ ΠΈ конСчная Π²Π΅Ρ€ΡˆΠΈΠ½Ρ‹ ΡΠΎΠ²ΠΏΠ°Π΄Π°ΡŽΡ‚), Ρ‚Π°ΠΊ Ρ‡Ρ‚ΠΎ Π½Π°ΠΌ придСтся ΠΎΡ‚ΡΠ»Π΅ΠΆΠΈΠ²Π°Ρ‚ΡŒ Π²Π΅Ρ€ΡˆΠΈΠ½Ρ‹, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ ΠΌΡ‹ посСтили. РСализуя поиск Π² ΡˆΠΈΡ€ΠΈΠ½Ρƒ, ΠΎΠ±Ρ‹Ρ‡Π½ΠΎ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡŽΡ‚ структуру Π΄Π°Π½Π½Ρ‹Ρ… ΠΎΡ‡Π΅Ρ€Π΅Π΄ΡŒ.

Рис. 2. Анимация поиска Π² ΡˆΠΈΡ€ΠΈΠ½Ρƒ

Π­Ρ‚ΠΎΡ‚ рисунок ΠΈΠ·ΠΎΠ±Ρ€Π°ΠΆΠ°Π΅Ρ‚ поиск Π² ΡˆΠΈΡ€ΠΈΠ½Ρƒ Π½Π° ΠΏΡ€ΠΈΠΌΠ΅Ρ€Π΅ Π³Ρ€Π°Ρ„Π°. ΠžΠ±Ρ€Π°Ρ‚ΠΈΡ‚Π΅ Π²Π½ΠΈΠΌΠ°Π½ΠΈΠ΅, ΠΊΠ°ΠΊ Π²Π΅Ρ€ΡˆΠΈΠ½Ρ‹ ΠΎΠ±Π½Π°Ρ€ΡƒΠΆΠΈΠ²Π°ΡŽΡ‚ΡΡ (ΠΆΠ΅Π»Ρ‚Ρ‹ΠΉ Ρ†Π²Π΅Ρ‚) ΠΈ ΠΏΠΎΡΠ΅Ρ‰Π°ΡŽΡ‚ΡΡ (красный).

ΠŸΡ€ΠΈΠ»ΠΎΠΆΠ΅Π½ΠΈΡ. Поиск Π² ΡˆΠΈΡ€ΠΈΠ½Ρƒ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅Ρ‚ΡΡ:

  • для обнаруТСния ΠΊΡ€Π°Ρ‚Ρ‡Π°ΠΉΡˆΠΈΡ… ΠΏΡƒΡ‚Π΅ΠΉ ΠΈ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹Ρ… ΠΏΠΎΠΊΡ€Ρ‹Π²Π°ΡŽΡ‰ΠΈΡ… Π΄Π΅Ρ€Π΅Π²ΡŒΠ΅Π²;
  • поисковыми систСмами для построСния индСксов Π²Π΅Π±-страниц;
  • для поиска Π² ΡΠΎΡ†ΠΈΠ°Π»ΡŒΠ½Ρ‹Ρ… сСтях;
  • для нахоТдСния доступных сосСдних ΡƒΠ·Π»ΠΎΠ² Π² ΠΎΠ΄Π½ΠΎΡ€Π°Π½Π³ΠΎΠ²Ρ‹Ρ… сСтях Π²Ρ€ΠΎΠ΄Π΅ BitTorrent.

2. Поиск Π² Π³Π»ΡƒΠ±ΠΈΠ½Ρƒ

ΠŸΡ€ΠΈ поискС Π² Π³Π»ΡƒΠ±ΠΈΠ½Ρƒ ΠΌΡ‹ Π½Π°Ρ‡ΠΈΠ½Π°Π΅ΠΌ с ΠΎΠΏΡ€Π΅Π΄Π΅Π»Π΅Π½Π½ΠΎΠΉ Π²Π΅Ρ€ΡˆΠΈΠ½Ρ‹ ΠΈ исслСдуСм ΠΊΠ°ΠΆΠ΄ΡƒΡŽ Π²Π΅Ρ‚ΠΊΡƒ Ρ‚Π°ΠΊ Π΄Π°Π»Π΅ΠΊΠΎ, насколько это Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎ, Π° ΠΏΠΎΡ‚ΠΎΠΌ возвращаСмся Π½Π°Π·Π°Π΄. ΠŸΡ€ΠΈ поискС Π² Π³Π»ΡƒΠ±ΠΈΠ½Ρƒ Ρ‚Π°ΠΊΠΆΠ΅ приходится ΠΎΡ‚ΡΠ»Π΅ΠΆΠΈΠ²Π°Ρ‚ΡŒ ΡƒΠΆΠ΅ посСщСнныС Π²Π΅Ρ€ΡˆΠΈΠ½Ρ‹. РСализуя поиск Π² Π³Π»ΡƒΠ±ΠΈΠ½Ρƒ, ΠΎΠ±Ρ‹Ρ‡Π½ΠΎ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡŽΡ‚ структуру Π΄Π°Π½Π½Ρ‹Ρ… стСк для запоминания Π²Π΅Ρ€ΡˆΠΈΠ½, ΠΊ ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΌ придСтся Π²ΠΎΠ·Π²Ρ€Π°Ρ‰Π°Ρ‚ΡŒΡΡ Π½Π°Π·Π°Π΄.

Рис. 3. Анимация поиска Π² Π³Π»ΡƒΠ±ΠΈΠ½Ρƒ

Рис. 3 ΠΈΠ·ΠΎΠ±Ρ€Π°ΠΆΠ°Π΅Ρ‚ поиск Π² Π³Π»ΡƒΠ±ΠΈΠ½Ρƒ Π½Π° ΠΏΡ€ΠΈΠΌΠ΅Ρ€Π΅ Ρ‚ΠΎΠ³ΠΎ ΠΆΠ΅ Π³Ρ€Π°Ρ„Π°. ΠžΠ±Ρ€Π°Ρ‚ΠΈΡ‚Π΅ Π²Π½ΠΈΠΌΠ°Π½ΠΈΠ΅, ΠΊΠ°ΠΊ ΠΎΠ½ Π΄ΠΎΡ…ΠΎΠ΄ΠΈΡ‚ Π΄ΠΎ ΠΊΠΎΠ½Ρ†Π° ΠΈ возвращаСтся Π½Π°Π·Π°Π΄.

ΠŸΡ€ΠΈΠ»ΠΎΠΆΠ΅Π½ΠΈΡ. Поиск Π² Π³Π»ΡƒΠ±ΠΈΠ½Ρƒ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅Ρ‚ΡΡ:

  • для нахоТдСния ΠΏΡƒΡ‚ΠΈ ΠΌΠ΅ΠΆΠ΄Ρƒ двумя Π²Π΅Ρ€ΡˆΠΈΠ½Π°ΠΌΠΈ;
  • для обнаруТСния Ρ†ΠΈΠΊΠ»ΠΎΠ² Π² Π³Ρ€Π°Ρ„Π΅;
  • для топологичСской сортировки;
  • для Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ Π³ΠΎΠ»ΠΎΠ²ΠΎΠ»ΠΎΠΌΠΎΠΊ, ΠΈΠΌΠ΅ΡŽΡ‰ΠΈΡ… Ρ‚ΠΎΠ»ΡŒΠΊΠΎ ΠΎΠ΄Π½ΠΎ Ρ€Π΅ΡˆΠ΅Π½ΠΈΠ΅ (Π½Π°ΠΏΡ€ΠΈΠΌΠ΅Ρ€, Π»Π°Π±ΠΈΡ€ΠΈΠ½Ρ‚ΠΎΠ²).

3. ΠšΡ€Π°Ρ‚Ρ‡Π°ΠΉΡˆΠΈΠΉ ΠΏΡƒΡ‚ΡŒ

ΠšΡ€Π°Ρ‚Ρ‡Π°ΠΉΡˆΠΈΠΉ ΠΏΡƒΡ‚ΡŒ ΠΎΡ‚ ΠΎΠ΄Π½ΠΎΠΉ Π²Π΅Ρ€ΡˆΠΈΠ½Ρ‹ Π³Ρ€Π°Ρ„Π° Π΄ΠΎ Π΄Ρ€ΡƒΠ³ΠΎΠΉ – это ΠΏΡƒΡ‚ΡŒ, ΠΈΠΌΠ΅ΡŽΡ‰ΠΈΠΉ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹ΠΉ суммарный вСс входящих Π² Π½Π΅Π³ΠΎ Ρ€Π΅Π±Π΅Ρ€. Π‘Π»Π΅Π΄ΡƒΡŽΡ‰ΠΈΠΉ рисунок ΠΏΠΎΠΊΠ°Π·Ρ‹Π²Π°Π΅Ρ‚ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹ΠΉ ΠΏΡƒΡ‚ΡŒ ΠΎΡ‚ Π²Π΅Ρ€ΡˆΠΈΠ½Ρ‹ 1 ΠΊ Π²Π΅Ρ€ΡˆΠΈΠ½Π΅ 6.

Рис. 4. Анимация процСсса нахоТдСния минимального ΠΏΡƒΡ‚ΠΈ

Алгоритмы:

  1. Алгоритм ДСйкстры поиска минимального ΠΏΡƒΡ‚ΠΈ.
  2. Алгоритм Π‘Π΅Π»Π»ΠΌΠ°Π½Π°-Π€ΠΎΡ€Π΄Π°.

ΠŸΡ€ΠΈΠ»ΠΎΠΆΠ΅Π½ΠΈΡ. Поиск ΠΊΡ€Π°Ρ‚Ρ‡Π°ΠΉΡˆΠ΅Π³ΠΎ ΠΏΡƒΡ‚ΠΈ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅Ρ‚ΡΡ:

  • для построСния ΠΌΠ°Ρ€ΡˆΡ€ΡƒΡ‚Π° Π² прилоТСниях Π²Ρ€ΠΎΠ΄Π΅ Google Maps;
  • ΠΏΡ€ΠΈ создании ΠΊΠΎΠΌΠΏΡŒΡŽΡ‚Π΅Ρ€Π½Ρ‹Ρ… сСтСй – Ρ‡Ρ‚ΠΎΠ±Ρ‹ ΠΎΠ±Π΅ΡΠΏΠ΅Ρ‡ΠΈΡ‚ΡŒ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡŒΠ½ΡƒΡŽ Π·Π°Π΄Π΅Ρ€ΠΆΠΊΡƒ;
  • Π² абстрактных Π°Π²Ρ‚ΠΎΠΌΠ°Ρ‚Π°Ρ… для опрСдСлСния ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½ΠΎΠΉ стратСгии достиТСния Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΉ Ρ†Π΅Π»ΠΈ Ρ‡Π΅Ρ€Π΅Π· нСсколько ΠΏΡ€ΠΎΠΌΠ΅ΠΆΡƒΡ‚ΠΎΡ‡Π½Ρ‹Ρ… состояний (Π½Π°ΠΏΡ€ΠΈΠΌΠ΅Ρ€, для подсчСта, сколько Π½ΡƒΠΆΠ½ΠΎ Ρ…ΠΎΠ΄ΠΎΠ² для ΠΏΠΎΠ±Π΅Π΄Ρ‹ Π² ΠΈΠ³Ρ€Π΅).

4. ΠžΠ±Π½Π°Ρ€ΡƒΠΆΠ΅Π½ΠΈΠ΅ Ρ†ΠΈΠΊΠ»ΠΎΠ²

Π¦ΠΈΠΊΠ» – это ΠΏΡƒΡ‚ΡŒ Π² Π³Ρ€Π°Ρ„Π΅, Ρƒ ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠ³ΠΎ Π½Π°Ρ‡Π°Π»ΡŒΠ½Π°Ρ ΠΈ конСчная Π²Π΅Ρ€ΡˆΠΈΠ½Ρ‹ ΡΠΎΠ²ΠΏΠ°Π΄Π°ΡŽΡ‚. Если ΠΌΡ‹ Π½Π°Ρ‡ΠΈΠ½Π°Π΅ΠΌ Π΄Π²ΠΈΠΆΠ΅Π½ΠΈΠ΅ с Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΉ Π²Π΅Ρ€ΡˆΠΈΠ½Ρ‹, ΠΈ Π² ΠΊΠΎΠ½Ρ†Π΅ ΠΊΠΎΠ½Ρ†ΠΎΠ² возвращаСмся ΠΊ Π½Π΅ΠΉ ΠΆΠ΅, Ρ‚ΠΎ этот ΠΏΡƒΡ‚ΡŒ – Ρ†ΠΈΠΊΠ». ΠžΠ±Π½Π°Ρ€ΡƒΠΆΠ΅Π½ΠΈΠ΅ Ρ†ΠΈΠΊΠ»ΠΎΠ² – это процСсс нахоТдСния Ρ‚Π°ΠΊΠΈΡ… Ρ†ΠΈΠΊΠ»ΠΎΠ². На рисункС ΠΏΠΎΠΊΠ°Π·Π°Π½ ΠΎΠ±Ρ…ΠΎΠ΄ Ρ†ΠΈΠΊΠ»Π°.

Рис. 5. Цикл

Алгоритмы:

  1. Алгоритм Π€Π»ΠΎΠΉΠ΄Π° для обнаруТСния Ρ†ΠΈΠΊΠ»ΠΎΠ².
  2. Алгоритм Π‘Ρ€Π΅Π½Ρ‚Π°.

ΠŸΡ€ΠΈΠ»ΠΎΠΆΠ΅Π½ΠΈΡ. ΠžΠ±Π½Π°Ρ€ΡƒΠΆΠ΅Π½ΠΈΠ΅ Ρ†ΠΈΠΊΠ»ΠΎΠ² ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅Ρ‚ΡΡ:

  • Π² Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ°Ρ…, основанных Π½Π° распрСдСлСнных сообщСниях;
  • для ΠΎΠ±Ρ€Π°Π±ΠΎΡ‚ΠΊΠΈ Π³Ρ€Π°Ρ„ΠΎΠ² ΠΊΡ€ΡƒΠΏΠ½ΠΎΠ³ΠΎ Ρ€Π°Π·ΠΌΠ΅Ρ€Π° с использованиСм распрСдСлСнной Π² ΠΏΡ€Π΅Π΄Π΅Π»Π°Ρ… кластСра систСмы ΠΎΠ±Ρ€Π°Π±ΠΎΡ‚ΠΊΠΈ;
  • для обнаруТСния Π΄Π΅Π΄Π»ΠΎΠΊΠΎΠ² Π² ΠΏΠ°Ρ€Π°Π»Π»Π΅Π»ΡŒΠ½Ρ‹Ρ… систСмах;
  • Π² криптографичСских прилоТСниях для нахоТдСния ΠΊΠ»ΡŽΡ‡Π΅ΠΉ сообщСния, ΡΠΎΠΎΡ‚Π²Π΅Ρ‚ΡΡ‚Π²ΡƒΡŽΡ‰ΠΈΡ… ΠΎΠ΄Π½ΠΎΠΌΡƒ ΠΈ Ρ‚ΠΎΠΌΡƒ ΠΆΠ΅ Π·Π°ΡˆΠΈΡ„Ρ€ΠΎΠ²Π°Π½Π½ΠΎΠΌΡƒ Π·Π½Π°Ρ‡Π΅Π½ΠΈΡŽ.

5. МинимальноС ΠΏΠΎΠΊΡ€Ρ‹Π²Π°ΡŽΡ‰Π΅Π΅ Π΄Π΅Ρ€Π΅Π²ΠΎ

МинимальноС ΠΏΠΎΠΊΡ€Ρ‹Π²Π°ΡŽΡ‰Π΅Π΅ Π΄Π΅Ρ€Π΅Π²ΠΎ – это подмноТСство Ρ€Π΅Π±Π΅Ρ€ Π³Ρ€Π°Ρ„Π°, ΡΠΎΠ΅Π΄ΠΈΠ½ΡΡŽΡ‰ΠΈΡ… всС Π΅Π³ΠΎ Π²Π΅Ρ€ΡˆΠΈΠ½Ρ‹, ΠΈΠΌΠ΅ΡŽΡ‰Π΅Π΅ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡŒΠ½ΡƒΡŽ сумму вСсов ΠΈ Π½Π΅ содСрТащСС Ρ†ΠΈΠΊΠ»ΠΎΠ². На рисункС ΠΏΠΎΠΊΠ°Π·Π°Π½ процСсс получСния минимального ΠΏΠΎΠΊΡ€Ρ‹Π²Π°ΡŽΡ‰Π΅Π³ΠΎ Π΄Π΅Ρ€Π΅Π²Π°.

Рис. 6. Анимация процСсса нахоТдСния минимального ΠΏΠΎΠΊΡ€Ρ‹Π²Π°ΡŽΡ‰Π΅Π³ΠΎ Π΄Π΅Ρ€Π΅Π²Π°

Алгоритмы:

  1. Алгоритм ΠŸΡ€ΠΈΠΌΠ°.
  2. Алгоритм ΠšΡ€Π°ΡΠΊΠ°Π»Π°.

ΠŸΡ€ΠΈΠ»ΠΎΠΆΠ΅Π½ΠΈΡ. ΠœΠΈΠ½ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹Π΅ ΠΏΠΎΠΊΡ€Ρ‹Π²Π°ΡŽΡ‰ΠΈΠ΅ Π΄Π΅Ρ€Π΅Π²ΡŒΡ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡŽΡ‚ΡΡ:

  • для создания Π΄Π΅Ρ€Π΅Π²ΡŒΠ΅Π² распространСния сигналов Π² ΠΊΠΎΠΌΠΏΡŒΡŽΡ‚Π΅Ρ€Π½Ρ‹Ρ… сСтях;
  • Π² кластСрном Π°Π½Π°Π»ΠΈΠ·Π΅, основанном Π½Π° Π³Ρ€Π°Ρ„Π°Ρ…;
  • Π² сСгмСнтации ΠΈΠ·ΠΎΠ±Ρ€Π°ΠΆΠ΅Π½ΠΈΠΉ;
  • Π² Ρ€Π΅Π³ΠΈΠΎΠ½Π°Π»ΠΈΠ·Π°Ρ†ΠΈΠΈ социо-гСографичСских Π·ΠΎΠ½, Π³Π΄Π΅ Ρ€Π΅Π³ΠΈΠΎΠ½Ρ‹ Π³Ρ€ΡƒΠΏΠΏΠΈΡ€ΡƒΡŽΡ‚ΡΡ со смСТными Ρ€Π΅Π³ΠΈΠΎΠ½Π°ΠΌΠΈ.

6. Бильно связанныС ΠΊΠΎΠΌΠΏΠΎΠ½Π΅Π½Ρ‚Ρ‹

Π“Ρ€Π°Ρ„ называСтся сильно связанным, Ссли Π΄ΠΎ ΠΊΠ°ΠΆΠ΄ΠΎΠΉ Π²Π΅Ρ€ΡˆΠΈΠ½Ρ‹ этого Π³Ρ€Π°Ρ„Π° Π΅ΡΡ‚ΡŒ ΠΏΡƒΡ‚ΡŒ ΠΈΠ· любой Π΄Ρ€ΡƒΠ³ΠΎΠΉ Π΅Π³ΠΎ Π²Π΅Ρ€ΡˆΠΈΠ½Ρ‹. На рисункС ΠΈΠ·ΠΎΠ±Ρ€Π°ΠΆΠ΅Π½ ΠΏΡ€ΠΈΠΌΠ΅Ρ€ Π³Ρ€Π°Ρ„Π° с трСмя сильно связанными ΠΊΠΎΠΌΠΏΠΎΠ½Π΅Π½Ρ‚Π°ΠΌΠΈ, Π²Π΅Ρ€ΡˆΠΈΠ½Ρ‹ ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… Ρ€Π°ΡΠΊΡ€Π°ΡˆΠ΅Π½Ρ‹ Π² красный, ΠΆΠ΅Π»Ρ‚Ρ‹ΠΉ ΠΈ Π·Π΅Π»Π΅Π½Ρ‹ΠΉ Ρ†Π²Π΅Ρ‚Π°.

Рис. 7. Бильно связанныС ΠΊΠΎΠΌΠΏΠΎΠ½Π΅Π½Ρ‚Ρ‹

Алгоритмы:

  1. Алгоритм ΠšΠΎΡΠ°Ρ€Π°Π΄ΠΆΡƒ.
  2. Алгоритм Π’Π°Ρ€ΡŒΡΠ½Π° поиска сильно связанных ΠΊΠΎΠΌΠΏΠΎΠ½Π΅Π½Ρ‚ΠΎΠ².

ΠŸΡ€ΠΈΠ»ΠΎΠΆΠ΅Π½ΠΈΡ. Бильно связанныС ΠΊΠΎΠΌΠΏΠΎΠ½Π΅Π½Ρ‚Ρ‹ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡŽΡ‚ΡΡ:

  • Π² Π΄Π΅ΠΊΠΎΠΌΠΏΠΎΠ·ΠΈΡ†ΠΈΠΈ ДалмэйдТа-МСндСльсона, ΠΏΡ€Π΅Π΄ΡΡ‚Π°Π²Π»ΡΡŽΡ‰Π΅ΠΉ собой ΠΊΠ»Π°ΡΡΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΡŽ Ρ€Π΅Π±Π΅Ρ€ двухчастного Π³Ρ€Π°Ρ„Π°;
  • Π² ΡΠΎΡ†ΠΈΠ°Π»ΡŒΠ½Ρ‹Ρ… сСтях для нахоТдСния Π³Ρ€ΡƒΠΏΠΏ людСй, сильно связанных Π΄Ρ€ΡƒΠ³ с Π΄Ρ€ΡƒΠ³ΠΎΠΌ, Ρ‡Ρ‚ΠΎΠ±Ρ‹ Π΄Π°Π²Π°Ρ‚ΡŒ Ρ€Π΅ΠΊΠΎΠΌΠ΅Π½Π΄Π°Ρ†ΠΈΠΈ Π½Π° основС ΠΈΡ… ΠΎΠ±Ρ‰ΠΈΡ… интСрСсов.

7. ВопологичСская сортировка

ВопологичСская сортировка Π³Ρ€Π°Ρ„Π° – это Π»ΠΈΠ½Π΅ΠΉΠ½ΠΎΠ΅ упорядочСниС Π²Π΅Ρ€ΡˆΠΈΠ½ Π³Ρ€Π°Ρ„Π° Ρ‚Π°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ, Ρ‡Ρ‚ΠΎΠ±Ρ‹ для ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ Π½Π°ΠΏΡ€Π°Π²Π»Π΅Π½Π½ΠΎΠ³ΠΎ Ρ€Π΅Π±Ρ€Π° Π³Ρ€Π°Ρ„Π° (u, v) Π²Π΅Ρ€ΡˆΠΈΠ½Π° u Π² спискС сортировки стояла ΠΏΠ΅Ρ€Π΅Π΄ v. На Рис. 8 ΠΈΠ·ΠΎΠ±Ρ€Π°ΠΆΠ΅Π½ ΠΏΡ€ΠΈΠΌΠ΅Ρ€ топологичСской сортировки Π²Π΅Ρ€ΡˆΠΈΠ½ (1, 2, 3, 5, 4, 6, 7, 8). Показано, Ρ‡Ρ‚ΠΎ Π²Π΅Ρ€ΡˆΠΈΠ½Π° 5 Π΄ΠΎΠ»ΠΆΠ½Π° ΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚ΡŒ послС Π²Π΅Ρ€ΡˆΠΈΠ½ 2 ΠΈ 3, Π° Π²Π΅Ρ€ΡˆΠΈΠ½Π° 6 – послС Π²Π΅Ρ€ΡˆΠΈΠ½ 4 ΠΈ 5.

Рис. 8. ВопологичСская сортировка Π²Π΅Ρ€ΡˆΠΈΠ½ Π³Ρ€Π°Ρ„Π°

Алгоритмы:

  1. Алгоритм Кана.
  2. Алгоритм, основанный Π½Π° поискС Π² Π³Π»ΡƒΠ±ΠΈΠ½Ρƒ.

ΠŸΡ€ΠΈΠ»ΠΎΠΆΠ΅Π½ΠΈΡ. ВопологичСская сортировка ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅Ρ‚ΡΡ:

  • для Π²Ρ‹Ρ€Π°Π±ΠΎΡ‚ΠΊΠΈ расписания инструкций;
  • ΠΏΡ€ΠΈ сСриализации Π΄Π°Π½Π½Ρ‹Ρ…;
  • для опрСдСлСния порядка выполнСния Π·Π°Π΄Π°Ρ‡ компиляции;
  • для Ρ€Π°Π·Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ зависимостСй символов ΠΏΡ€ΠΈ сборкС (linking).

8. Раскраска Π³Ρ€Π°Ρ„Π°

Раскраска Π³Ρ€Π°Ρ„Π° Π½Π°Π·Π½Π°Ρ‡Π°Π΅Ρ‚ Ρ†Π²Π΅Ρ‚Π° элСмСнтам Π³Ρ€Π°Ρ„Π°, обСспСчивая Π²Ρ‹ΠΏΠΎΠ»Π½Π΅Π½ΠΈΠ΅ ΠΎΠΏΡ€Π΅Π΄Π΅Π»Π΅Π½Π½Ρ‹Ρ… условий. Π§Π°Ρ‰Π΅ всСго ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅Ρ‚ΡΡ раскраска Π²Π΅Ρ€ΡˆΠΈΠ½, ΠΏΡ€ΠΈ ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΉ ΠΌΡ‹ пытаСмся Ρ€Π°ΡΠΊΡ€Π°ΡΠΈΡ‚ΡŒ Π²Π΅Ρ€ΡˆΠΈΠ½Ρ‹ Π³Ρ€Π°Ρ„Π°, ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡ k Ρ†Π²Π΅Ρ‚ΠΎΠ², Ρ‡Ρ‚ΠΎΠ±Ρ‹ сосСдниС Π²Π΅Ρ€ΡˆΠΈΠ½Ρ‹ Π½ΠΈΠΊΠΎΠ³Π΄Π° Π½Π΅ ΠΈΠΌΠ΅Π»ΠΈ ΠΎΠ΄ΠΈΠ½ ΠΈ Ρ‚ΠΎΡ‚ ΠΆΠ΅ Ρ†Π²Π΅Ρ‚. Π”Ρ€ΡƒΠ³ΠΈΠ΅ Π²ΠΈΠ΄Ρ‹ раскраски Π²ΠΊΠ»ΡŽΡ‡Π°ΡŽΡ‚ раскраску Ρ€Π΅Π±Π΅Ρ€ ΠΈ раскраску Π³Ρ€Π°Π½Π΅ΠΉ.

Π₯роматичСскоС число Π³Ρ€Π°Ρ„Π° – это минимальноС количСство Ρ†Π²Π΅Ρ‚ΠΎΠ², Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎΠ΅ для Π΅Π³ΠΎ раскраски. На рисункС ΠΈΠ·ΠΎΠ±Ρ€Π°ΠΆΠ΅Π½Π° раскраска Π²Π΅Ρ€ΡˆΠΈΠ½ Π³Ρ€Π°Ρ„Π° Ρ‡Π΅Ρ‚Ρ‹Ρ€ΡŒΠΌΡ Ρ†Π²Π΅Ρ‚Π°ΠΌΠΈ.

Рис. 9. Раскраска Π²Π΅Ρ€ΡˆΠΈΠ½ Π³Ρ€Π°Ρ„Π°

Алгоритмы:

  1. Алгоритмы, ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡŽΡ‰ΠΈΠ΅ поиск Π² ΡˆΠΈΡ€ΠΈΠ½Ρƒ ΠΈΠ»ΠΈ Π² Π³Π»ΡƒΠ±ΠΈΠ½Ρƒ.
  2. "Жадная" раскраска.

ΠŸΡ€ΠΈΠ»ΠΎΠΆΠ΅Π½ΠΈΡ. Раскраска Π³Ρ€Π°Ρ„ΠΎΠ² ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅Ρ‚ΡΡ:

  • для составлСния расписаний;
  • для назначСния радиочастот ΠΌΠΎΠ±ΠΈΠ»ΡŒΠ½Ρ‹ΠΌ сСтям;
  • для модСлирования ΠΈ Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ ΠΈΠ³Ρ€ Π²Ρ€ΠΎΠ΄Π΅ судоку;
  • для ΠΏΡ€ΠΎΠ²Π΅Ρ€ΠΊΠΈ, являСтся Π»ΠΈ Π³Ρ€Π°Ρ„ двучастным;
  • для раскраски гСографичСских ΠΊΠ°Ρ€Ρ‚, Ρ‡Ρ‚ΠΎΠ±Ρ‹ сосСдниС страны всСгда ΠΈΠΌΠ΅Π»ΠΈ Ρ€Π°Π·Π½Ρ‹Π΅ Ρ†Π²Π΅Ρ‚Π°.

9. Π—Π°Π΄Π°Ρ‡Π° ΠΎ максимальном ΠΏΠΎΡ‚ΠΎΠΊΠ΅

ΠœΡ‹ ΠΌΠΎΠΆΠ΅ΠΌ ΠΈΠ·ΠΎΠ±Ρ€Π°Π·ΠΈΡ‚ΡŒ ΡΠ΅Ρ‚ΡŒ ΠΏΠΎΡ‚ΠΎΠΊΠΎΠ² Π² Π²ΠΈΠ΄Π΅ Π³Ρ€Π°Ρ„Π°, вСса Ρ€Π΅Π±Π΅Ρ€ ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠ³ΠΎ Π±ΡƒΠ΄ΡƒΡ‚ ΡΠΎΠΎΡ‚Π²Π΅Ρ‚ΡΡ‚Π²ΠΎΠ²Π°Ρ‚ΡŒ максимальной пропускной способности ΠΏΠΎΡ‚ΠΎΠΊΠ°. Π’ Π·Π°Π΄Π°Ρ‡Π΅ ΠΎ максимальном ΠΏΠΎΡ‚ΠΎΠΊΠ΅ трСбуСтся Π½Π°ΠΉΡ‚ΠΈ ΠΏΡƒΡ‚ΡŒ ΠΏΠΎΡ‚ΠΎΠΊΠ°, ΠΎΠ±Π΅ΡΠΏΠ΅Ρ‡ΠΈΠ²Π°ΡŽΡ‰ΠΈΠΉ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡŒΠ½ΡƒΡŽ ΠΏΡ€ΠΎΠΏΡƒΡΠΊΠ½ΡƒΡŽ ΡΠΏΠΎΡΠΎΠ±Π½ΠΎΡΡ‚ΡŒ.

На рисункС ΠΏΠΎΠΊΠ°Π·Π°Π½ ΠΏΡ€ΠΈΠΌΠ΅Ρ€ опрСдСлСния максимального ΠΏΠΎΡ‚ΠΎΠΊΠ° сСти ΠΈ нахоТдСния ΠΈΡ‚ΠΎΠ³ΠΎΠ²ΠΎΠ³ΠΎ значСния ΠΏΠΎΡ‚ΠΎΠΊΠ°.

Рис. 10. НахоТдСниС максимального ΠΏΠΎΡ‚ΠΎΠΊΠ°

Алгоритмы:

  1. Алгоритм Π€ΠΎΡ€Π΄Π°-ЀалкСрсона.
  2. Алгоритм Эдмондса-ΠšΠ°Ρ€ΠΏΠ°.
  3. Алгоритм Π”ΠΈΠ½ΠΈΡ†Π°.

ΠŸΡ€ΠΈΠ»ΠΎΠΆΠ΅Π½ΠΈΡ. Π—Π°Π΄Π°Ρ‡Π° ΠΎ максимальном ΠΏΠΎΡ‚ΠΎΠΊΠ΅ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅Ρ‚ΡΡ:

  • ΠΏΡ€ΠΈ составлСнии расписаний экипаТСй самолСтов;
  • Π² сСгмСнтации ΠΈΠ·ΠΎΠ±Ρ€Π°ΠΆΠ΅Π½ΠΈΠΉ для нахоТдСния ΠΏΠ΅Ρ€Π΅Π΄Π½Π΅Π³ΠΎ ΠΏΠ»Π°Π½Π° ΠΈ Ρ„ΠΎΠ½Π° изобраТСния;
  • для вычСркивания спортивных ΠΊΠΎΠΌΠ°Π½Π΄, нСспособных Π΄ΠΎΠ±Ρ€Π°Ρ‚ΡŒΡΡ Π΄ΠΎ Π»ΠΈΠ΄Π΅Ρ€ΠΎΠ² своСй Π»ΠΈΠ³ΠΈ.

10. БоотвСтствия

БоотвСтствиСм Π² Π³Ρ€Π°Ρ„Π΅ называСтся Π½Π°Π±ΠΎΡ€ Ρ€Π΅Π±Π΅Ρ€, Π½Π΅ ΠΈΠΌΠ΅ΡŽΡ‰ΠΈΡ… ΠΎΠ±Ρ‰ΠΈΡ… Π²Π΅Ρ€ΡˆΠΈΠ½ – Ρ‚ΠΎ Π΅ΡΡ‚ΡŒ, Π½ΠΈΠΊΠ°ΠΊΠΈΠ΅ Π΄Π²Π° Ρ€Π΅Π±Ρ€Π° Π½Π΅ ΠΈΠΌΠ΅ΡŽΡ‚ ΠΎΠ΄Π½Ρƒ ΠΈ Ρ‚Ρƒ ΠΆΠ΅ Π²Π΅Ρ€ΡˆΠΈΠ½Ρƒ. БоотвСтствиС называСтся ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹ΠΌ, Ссли ΠΎΠ½ΠΎ содСрТит максимально Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎΠ΅ количСство Ρ€Π΅Π±Π΅Ρ€, Π·Π°Ρ‚Ρ€Π°Π³ΠΈΠ²Π°ΡŽΡ‰ΠΈΡ… ΠΊΠ°ΠΊ ΠΌΠΎΠΆΠ½ΠΎ большС Π²Π΅Ρ€ΡˆΠΈΠ½.

На рисункС ΠΈΠ·ΠΎΠ±Ρ€Π°ΠΆΠ΅Π½Π° анимация процСсса получСния ΠΏΠΎΠ»Π½ΠΎΠ³ΠΎ соотвСтствия Π² двухчастном Π³Ρ€Π°Ρ„Π΅, Π²Π΅Ρ€ΡˆΠΈΠ½Ρ‹ ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠ³ΠΎ Ρ€Π°ΡΠΊΡ€Π°ΡˆΠ΅Π½Ρ‹ Π² ΠΎΡ€Π°Π½ΠΆΠ΅Π²Ρ‹ΠΉ ΠΈ синий Ρ†Π²Π΅Ρ‚Π°.

Рис. 11. Поиск соотвСтствия Π² двухчастном Π³Ρ€Π°Ρ„Π΅

Алгоритмы:

  1. Алгоритм Π₯ΠΎΠΏΠΊΡ€ΠΎΡ„Ρ‚Π°-ΠšΠ°Ρ€ΠΏΠ°.
  2. ВСнгСрский Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ.
  3. Алгоритм сТатия Ρ†Π²Π΅Ρ‚ΠΊΠΎΠ².

ΠŸΡ€ΠΈΠ»ΠΎΠΆΠ΅Π½ΠΈΡ. Поиск соотвСтствий ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅Ρ‚ΡΡ:

  • для опрСдСлСния соотвСтствий Π²Π΅Ρ€ΡˆΠΈΠ½;
  • Π² логистикС для Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ Π·Π°Π΄Π°Ρ‡ распрСдСлСния рСсурсов ΠΈ ΠΎΠΏΡ‚ΠΈΠΌΠΈΠ·Π°Ρ†ΠΈΠΈ Π² ΠΏΡƒΡ‚ΠΈ.

Π—Π°ΠΊΠ»ΡŽΡ‡Π΅Π½ΠΈΠ΅

НадСюсь, Ρ‡Ρ‚ΠΎ пСрСчислСнныС Π²Ρ‹ΡˆΠ΅ Π·Π°Π΄Π°Ρ‡ΠΈ ΠΈ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹ Π±ΡƒΠ΄ΡƒΡ‚ ΠΏΠΎΠ»Π΅Π·Π½Ρ‹ ΠΈ Π½Π΅ покаТутся слишком слоТными.

Если Π²Ρ‹ Π·Π½Π°ΠΊΠΎΠΌΡ‹ с Python, Π²Ρ‹ ΠΌΠΎΠΆΠ΅Ρ‚Π΅ ΠΏΠΎΡΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ, ΠΊΠ°ΠΊ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹ Π½Π° Π³Ρ€Π°Ρ„Π°Ρ… Ρ€Π΅Π°Π»ΠΈΠ·ΠΎΠ²Π°Π½Ρ‹ Π² модулях networkx ΠΈ igraph.

Π˜ΡΡ‚ΠΎΡ‡Π½ΠΈΠΊΠΈ

Π›Π£Π§Π¨Π˜Π• БВАВЬИ ПО Π’Π•ΠœΠ•

admin
08 октября 2017

13 рСсурсов, Ρ‡Ρ‚ΠΎΠ±Ρ‹ Π²Ρ‹ΡƒΡ‡ΠΈΡ‚ΡŒ ΠΌΠ°Ρ‚Π΅ΠΌΠ°Ρ‚ΠΈΠΊΡƒ

Π‘Ρ€Π΅Π΄ΠΈ Ρ€Π°Π·Ρ€Π°Π±ΠΎΡ‚Ρ‡ΠΈΠΊΠΎΠ² часто Π²ΠΎΠ·Π½ΠΈΠΊΠ°ΡŽΡ‚ споры ΠΎ Ρ‚ΠΎΠΌ, Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎ Π»ΠΈ ΠΈΠ·ΡƒΡ‡Π°Ρ‚ΡŒ ΠΌΠ°Ρ‚Π΅...
admin
21 фСвраля 2017

КакиС Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹ Π½ΡƒΠΆΠ½ΠΎ Π·Π½Π°Ρ‚ΡŒ, Ρ‡Ρ‚ΠΎΠ±Ρ‹ ΡΡ‚Π°Ρ‚ΡŒ Ρ…ΠΎΡ€ΠΎΡˆΠΈΠΌ программистом?

Данная ΡΡ‚Π°Ρ‚ΡŒΡ содСрТит Π½Π΅ Ρ‚ΠΎΠ»ΡŒΠΊΠΎΒ ΡΠ°ΠΌΡ‹Π΅ распространСнныС Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹ ΠΈ структу...
admin
29 января 2017

Π˜Π·ΡƒΡ‡Π°Π΅ΠΌ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹: ΠΏΠΎΠ»Π΅Π·Π½Ρ‹Π΅ ΠΊΠ½ΠΈΠ³ΠΈ, Π²Π΅Π±-сайты, ΠΎΠ½Π»Π°ΠΉΠ½-курсы ΠΈ Π²ΠΈΠ΄Π΅ΠΎΠΌΠ°Ρ‚Π΅Ρ€ΠΈΠ°Π»Ρ‹

Π’ этой ΠΏΠΎΠ΄Π±ΠΎΡ€ΠΊΠ΅ прСдставлСн список ΠΊΠ½ΠΈΠ³, Π²Π΅Π±-сайтов ΠΈ ΠΎΠ½Π»Π°ΠΉΠ½-курсов, Π΄Π°ΡŽΡ‰ΠΈΡ…...