Π”ΠΈΠΏΠ»ΠΎΠΌΡ‹, курсовыС, Ρ€Π΅Ρ„Π΅Ρ€Π°Ρ‚Ρ‹, ΠΊΠΎΠ½Ρ‚Ρ€ΠΎΠ»ΡŒΠ½Ρ‹Π΅...
Брочная ΠΏΠΎΠΌΠΎΡ‰ΡŒ Π² ΡƒΡ‡Ρ‘Π±Π΅

ΠžΡ†Π΅Π½ΠΎΡ‡Π½Π°Ρ функция. 
БимволичСский искусствСнный ΠΈΠ½Ρ‚Π΅Π»Π»Π΅ΠΊΡ‚: матСматичСскиС основы прСдставлСния Π·Π½Π°Π½ΠΈΠΉ

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

Π“Π΄eg (d) — фактичСская ΡΡ‚ΠΎΠΈΠΌΠΎΡΡ‚ΡŒ ΠΏΡƒΡ‚ΠΈ ΠΎΡ‚ ΠΈΡΡ…ΠΎΠ΄Π½ΠΎΠΉ Π²Π΅Ρ€ΡˆΠΈΠ½Ρ‹ d0 Π΄ΠΎ d (ΡƒΠΆΠ΅ ΠΎΠΏΡ€Π΅Π΄Π΅Π»Π΅Π½Π° Π½Π°ΠΌΠΈ Π² ΠΏΡ€ΠΎΡ†Π΅Π΄ΡƒΡ€Π΅ Open); h (d) — эвристичСская ΠΎΡ†Π΅Π½ΠΊΠ° стоимости ΠΏΡƒΡ‚ΠΈ ΠΎΡ‚ d Π΄ΠΎ Ρ†Π΅Π»Π΅Π²ΠΎΠΉ Π²Π΅Ρ€ΡˆΠΈΠ½Ρ‹ dt. ЭвристичСская информация ΠΌΠΎΠΆΠ΅Ρ‚ ΠΈΠΌΠ΅Ρ‚ΡŒ Π»ΡŽΠ±ΡƒΡŽ Ρ„ΠΎΡ€ΠΌΡƒ. Π’ Π˜Π˜ принято ΠΏΡ€Π΅Π΄ΡΡ‚Π°Π²Π»ΡΡ‚ΡŒ ΡΠ²Ρ€ΠΈΡΡ‚ΠΈΡ‡Π΅ΡΠΊΡƒΡŽ ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ†ΠΈΡŽ Π² Π²ΠΈΠ΄Π΅ ΠΎΡ†Π΅Π½ΠΎΡ‡Π½ΠΎΠΉ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ F (d). ВСс ΠΏΡƒΡ‚ΠΈ ΠΎΡ‚ ΠΈΡΡ…ΠΎΠ΄Π½ΠΎΠΉ Π²Π΅Ρ€ΡˆΠΈΠ½Ρ‹ d0 Π΄ΠΎ Ρ†Π΅Π»Π΅Π²ΠΎΠΉ Π²Π΅Ρ€ΡˆΠΈΠ½Ρ‹ dt Ρ‡Π΅Ρ€Π΅Π· Ρ‚Π΅ΠΊΡƒΡ‰ΡƒΡŽ Π²Π΅Ρ€ΡˆΠΈΠ½Ρƒ d. Рис. 3.1… Π§ΠΈΡ‚Π°Ρ‚ΡŒ Π΅Ρ‰Ρ‘ >

ΠžΡ†Π΅Π½ΠΎΡ‡Π½Π°Ρ функция. БимволичСский искусствСнный ΠΈΠ½Ρ‚Π΅Π»Π»Π΅ΠΊΡ‚: матСматичСскиС основы прСдставлСния Π·Π½Π°Π½ΠΈΠΉ (Ρ€Π΅Ρ„Π΅Ρ€Π°Ρ‚, курсовая, Π΄ΠΈΠΏΠ»ΠΎΠΌ, ΠΊΠΎΠ½Ρ‚Ρ€ΠΎΠ»ΡŒΠ½Π°Ρ)

ЭвристичСская информация ΠΌΠΎΠΆΠ΅Ρ‚ ΠΈΠΌΠ΅Ρ‚ΡŒ Π»ΡŽΠ±ΡƒΡŽ Ρ„ΠΎΡ€ΠΌΡƒ. Π’ Π˜Π˜ принято ΠΏΡ€Π΅Π΄ΡΡ‚Π°Π²Π»ΡΡ‚ΡŒ ΡΠ²Ρ€ΠΈΡΡ‚ΠΈΡ‡Π΅ΡΠΊΡƒΡŽ ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ†ΠΈΡŽ Π² Π²ΠΈΠ΄Π΅ ΠΎΡ†Π΅Π½ΠΎΡ‡Π½ΠΎΠΉ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ F (d).

ΠžΡ†Π΅Π½ΠΎΡ‡Π½Π°Ρ функция F ΠΎΠΏΡ€Π΅Π΄Π΅Π»Π΅Π½Π° Π½Π° ΠΌΠ½ΠΎΠΆΠ΅ΡΡ‚Π²Π΅ допустимых состояний срСды (Π±Π°Π·Ρ‹ Ρ„Π°ΠΊΡ‚ΠΎΠ²) ΠΈ ΠΏΡ€ΠΈΠ½ΠΈΠΌΠ°Π΅Ρ‚ вСщСствСнныС числовыС значСния F:D—>M" ΠŸΡ€ΠΈΡ‡Π΅ΠΌ ΠΎΠ±Ρ‹Ρ‡Π½ΠΎ Π²Ρ‹Π±ΠΈΡ€Π°ΡŽΡ‚ ΠΎΡ†Π΅Π½ΠΎΡ‡Π½ΡƒΡŽ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΡŽ Ρ‚Π°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ, Ρ‡Ρ‚ΠΎΠ±Ρ‹ Π½Π° Ρ‚Π΅Ρ€ΠΌΠΈΠ½Π°Π»ΡŒΠ½Ρ‹Ρ… ΡƒΠ·Π»Π°Ρ… Π΅Π΅ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ Π±Ρ‹Π»ΠΎ минимально — F (dt) = = min{d Π΅ D | F (d)}. Если Π·Π°Π΄Π°Π½Π° такая оцСночная функция, Ρ‚ΠΎ ΠΌΠΎΠΆΠ½ΠΎ Π·Π°ΠΏΠΈΡΠ°Ρ‚ΡŒ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΡŽ Select, ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡ идСю Π½Π°ΠΈΡΠΊΠΎΡ€Π΅ΠΉΡˆΠ΅Π³ΠΎ спуска (Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ 3.2).

Алгоритм 3.2. Ѐункция Π²Ρ‹Π±ΠΎΡ€Π° ΡƒΠ·Π»Π° для раскрытия

Proc Select (О) m: = ΠΎΠΎ d' := nil for d Π΅ Πž do if F (d) < m then d' := d m := F (d).

end if end for return (d') end proc.

Или ΠΊΠΎΡ€ΠΎΡ‡Π΅:

Select (0) := min F (d), d e 0.

Для ΠΎΡ†Π΅Π½ΠΎΡ‡Π½ΠΎΠΉ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ F ΠΏΡ€Π΅Π΄Π»ΠΎΠΆΠ΅Π½ΠΎ ΠΌΠ½ΠΎΠ³ΠΎ Ρ€Π°Π·Π»ΠΈΡ‡Π½Ρ‹Ρ… ΠΈΠ΄Π΅ΠΉ Ρ€Π΅Π°Π»ΠΈΠ·Π°Ρ†ΠΈΠΈ. Π‘Π»ΠΎΠ²ΠΎ «ΠΎΡ†Π΅Π½ΠΎΡ‡Π½Π°Ρ» ΠΎΠ·Π½Π°Ρ‡Π°Π΅Ρ‚, Ρ‡Ρ‚ΠΎ F (ΠΏΡ€Π΅Π΄ΠΏΠΎΠ»ΠΎΠΆΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎ) Π±Π»ΠΈΠ·ΠΊΠ° ΠΊ ΠΊΠ°ΠΊΠΈΠΌ-Ρ‚ΠΎ Π²Π°ΠΆΠ½Ρ‹ΠΌ характСристикам поиска. НиТС ΠΏΡ€ΠΈΠ²Π΅Π΄Π΅Π½ список Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… Ρ…Π°Ρ€Π°ΠΊΡ‚Π΅Ρ€Π½Ρ‹Ρ… свойств, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ часто ΠΏΡ‹Ρ‚Π°ΡŽΡ‚ΡΡ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒ ΠΏΡ€ΠΈ Π²Ρ‹Π±ΠΎΡ€Π΅ ΠΎΡ†Π΅Π½ΠΎΡ‡Π½ΠΎΠΉ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ:

  • β€’ Π²Π΅Π»ΠΈΡ‡ΠΈΠ½Π°, обратная вСроятности Ρ‚ΠΎΠ³ΠΎ, Ρ‡Ρ‚ΠΎ d ΠΏΡ€ΠΈΠ½Π°Π΄Π»Π΅ΠΆΠΈΡ‚ ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½ΠΎΠΌΡƒ ΠΏΡƒΡ‚ΠΈ;
  • β€’ расстояниС ΠΎΡ‚ ΡƒΠ·Π»Π° d Π΄ΠΎ Ρ†Π΅Π»Π΅Π²ΠΎΠ³ΠΎ мноТСства ΡƒΠ·Π»ΠΎΠ² Π’
  • β€’ вСс ΠΏΡƒΡ‚ΠΈ ΠΎΡ‚ ΠΈΡΡ…ΠΎΠ΄Π½ΠΎΠΉ Π²Π΅Ρ€ΡˆΠΈΠ½Ρ‹ d0 Π΄ΠΎ Ρ†Π΅Π»Π΅Π²ΠΎΠΉ Π²Π΅Ρ€ΡˆΠΈΠ½Ρ‹ dt Ρ‡Π΅Ρ€Π΅Π· Ρ‚Π΅ΠΊΡƒΡ‰ΡƒΡŽ Π²Π΅Ρ€ΡˆΠΈΠ½Ρƒ d.

Π—Π΄Π΅ΡΡŒ ΠΌΡ‹ Ρ€Π°ΡΡΠΌΠ°Ρ‚Ρ€ΠΈΠ²Π°Π΅ΠΌ ΠΈΠΌΠ΅Π½Π½ΠΎ послСдний случай.

Π‘ΡƒΠ΄Π΅ΠΌ Ρ€Π°ΡΡΠΌΠ°Ρ‚Ρ€ΠΈΠ²Π°Ρ‚ΡŒ ΠΎΡ†Π΅Π½ΠΎΡ‡Π½ΡƒΡŽ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΡŽ Π² ΡΠ»Π΅Π΄ΡƒΡŽΡ‰Π΅ΠΉ Ρ„ΠΎΡ€ΠΌΠ΅:

ΠžΡ†Π΅Π½ΠΎΡ‡Π½Π°Ρ функция. БимволичСский искусствСнный ΠΈΠ½Ρ‚Π΅Π»Π»Π΅ΠΊΡ‚: матСматичСскиС основы прСдставлСния Π·Π½Π°Π½ΠΈΠΉ.

Π³Π΄eg (d) — фактичСская ΡΡ‚ΠΎΠΈΠΌΠΎΡΡ‚ΡŒ ΠΏΡƒΡ‚ΠΈ ΠΎΡ‚ ΠΈΡΡ…ΠΎΠ΄Π½ΠΎΠΉ Π²Π΅Ρ€ΡˆΠΈΠ½Ρ‹ d0 Π΄ΠΎ d (ΡƒΠΆΠ΅ ΠΎΠΏΡ€Π΅Π΄Π΅Π»Π΅Π½Π° Π½Π°ΠΌΠΈ Π² ΠΏΡ€ΠΎΡ†Π΅Π΄ΡƒΡ€Π΅ Open); h (d) — эвристичСская ΠΎΡ†Π΅Π½ΠΊΠ° стоимости ΠΏΡƒΡ‚ΠΈ ΠΎΡ‚ d Π΄ΠΎ Ρ†Π΅Π»Π΅Π²ΠΎΠΉ Π²Π΅Ρ€ΡˆΠΈΠ½Ρ‹ dt.

Рассмотрим процСсс Π²Ρ‹Π±ΠΎΡ€Π° ΠΎΡ†Π΅Π½ΠΎΡ‡Π½ΠΎΠΉ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ Π½Π° ΠΏΡ€ΠΈΠΌΠ΅Ρ€Π΅ ΠΈΠ³Ρ€Ρ‹ Π² «Π²ΠΎΡΠ΅ΠΌΡŒ»[1] (см. ΠΏ. 2.1.5). Π’Π²Π΅Π΄Π΅ΠΌ ΠΎΡ†Π΅Π½ΠΎΡ‡Π½ΡƒΡŽ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΡŽ F (d) ΠΊΠ°ΠΊ сумму Π³Π»ΡƒΠ±ΠΈΠ½Ρ‹ Π² Π΄Π΅Ρ€Π΅Π²Π΅ (соотвСтствуСт Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ g (d)) ΠΈ Ρ‡ΠΈΡΠ»Π° шашСк Π½Π΅ Π½Π° ΡΠ²ΠΎΠ΅ΠΌ мСстС (соотвСтствуСт Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ h (d)). ΠœΡ‹ Π²ΠΈΠ΄ΠΈΠΌ (рис. 3.1), Ρ‡Ρ‚ΠΎ с Ρ‚Π°ΠΊΠΎΠΉ ΠΎΡ†Π΅Π½ΠΎΡ‡Π½ΠΎΠΉ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠ΅ΠΉ поиск Π½Π° Π³Ρ€Π°Ρ„Π΅ оказываСтся вСсьма эффСктивным ΠΈ Π±Ρ‹ΡΡ‚Ρ€ΠΎ ΠΏΡ€ΠΈΠ²ΠΎΠ΄ΠΈΡ‚ ΠΊ Ρ€Π΅ΡˆΠ΅Π½ΠΈΡŽ.

Π“Ρ€Π°Ρ„ поиска для ΠΈΠ³Ρ€Ρ‹ Π² «восСмь» со Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ΠΌ ΠΎΡ†Π΅Π½ΠΎΡ‡Π½ΠΎΠΉ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ F.

Рис. 3.1. Π“Ρ€Π°Ρ„ поиска для ΠΈΠ³Ρ€Ρ‹ Π² «Π²ΠΎΡΠ΅ΠΌΡŒ» со Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ΠΌ ΠΎΡ†Π΅Π½ΠΎΡ‡Π½ΠΎΠΉ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ F.

Π‘Π΄Π΅Π»Π°Π΅ΠΌ нСсколько наблюдСний ΠΏΠΎ ΡΡ‚ΠΎΠΌΡƒ ΠΏΡ€ΠΈΠΌΠ΅Ρ€Ρƒ: β€’ h (dr) = 0, Ρ‚Π°ΠΊ ΠΊΠ°ΠΊ Π² Ρ†Π΅Π»Π΅Π²ΠΎΠΉ ΠΏΠΎΠ·ΠΈΡ†ΠΈΠΈ всС шашки находятся Π½Π° ΡΠ²ΠΎΠ΅ΠΌ мСстС ΠΏΠΎ ΠΎΠΏΡ€Π΅Π΄Π΅Π»Π΅Π½ΠΈΡŽ; β€’ h (d) Π½Π΅ ΠΏΡ€Π΅Π²ΠΎΡΡ…ΠΎΠ΄ΠΈΡ‚ минимального числа Ρ…ΠΎΠ΄ΠΎΠ², ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎ ΡΠΎΠ²Π΅Ρ€ΡˆΠΈΡ‚ΡŒ, Ρ‡Ρ‚ΠΎΠ±Ρ‹ ΠΏΠ΅Ρ€Π΅ΠΉΡ‚ΠΈ ΠΈΠ· d Π² dr β€’ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ F (d) для раскрываСмых ΡƒΠ·Π»ΠΎΠ² Π½Π΅ ΡƒΠ±Ρ‹Π²Π°Π΅Ρ‚; β€’ Ссли Π²Π·ΡΡ‚ΡŒ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΡŽ Π‘Ρ‚ΠΎΠ»ΡŒΠΊΠΎ ΠΊΠ°ΠΊ Π³Π»ΡƒΠ±ΠΈΠ½Ρƒ Π² Π΄Π΅Ρ€Π΅Π²Π΅, Ρ‚. Π΅. ΠΏΠΎΠ»ΠΎΠΆΠΈΡ‚ΡŒ h = = 0, Ρ‚ΠΎ ΠΏΠΎΠ»ΡƒΡ‡ΠΈΡ‚ся просто поиск Π² ΡˆΠΈΡ€ΠΈΠ½Ρƒ. Π’ ΡΠ»Π΅Π΄ΡƒΡŽΡ‰Π΅ΠΌ ΠΏΠ°Ρ€Π°Π³Ρ€Π°Ρ„Π΅ ΠΌΡ‹ ΠΎΠ±ΠΎΠ±Ρ‰ΠΈΠΌ ΠΈ ΠΈΡΡ‚ΠΎΠ»ΠΊΡƒΠ΅ΠΌ эти эмпиричСскиС наблюдСния.

  • [1] Π”Π°Π» Π£., ДСйкстра Π­., Π₯ΠΎΠ°Ρ€ К. Π‘Ρ‚Ρ€ΡƒΠΊΡ‚ΡƒΡ€Π½ΠΎΠ΅ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠ΅.
ΠŸΠΎΠΊΠ°Π·Π°Ρ‚ΡŒ вСсь тСкст
Π—Π°ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Ρ„ΠΎΡ€ΠΌΡƒ Ρ‚Π΅ΠΊΡƒΡ‰Π΅ΠΉ Ρ€Π°Π±ΠΎΡ‚ΠΎΠΉ