Page 114 - 6109

обчислення евристик також вимагає певних витрат. В цьому випадку виникає
питання мінімізації загального процесорного часу, затрачуваного на пошук
рішення.

11.6 Пошук з розповсюдженням обмежень

Існують задачі, де необхідно брати до уваги діючі обмеження на переходи
станів, і завдяки цьому цілеспрямовано йти до її рішення. Як приклад можна
привести задачу розпізнавання мови або задачу інтерпретації тривимірних
контурних малюнків.
Одна з технологій розпізнавання мови заснована на розбитті мовного
сигналу на елементарні ділянки і привласненні кожній ділянці мітки у вигляді
фонеми. Послідовність фонем, одержувана в результаті такої розмітки, повинна
бути злагодженою і не суперечити правилам вимовлення слів. Обмеження,
діючі між можливими взаємними поєднаннями фонем, дозволяють виключити з
розгляду варіанти, які не формують акустичні аналоги слів. Таким чином,
елементарні ділянки мови, представлені фонемами, забезпечують формування
правильного слова, а послідовність слів - граматично коректну фразу. В цьому
значенні обмеження, що накладаються, дозволяють по елементах відновлювати
ціле і їх часто називають обмеженнями цілісності.
Якщо одна і та ж змінна бере участь одночасно в декількох обмеженнях,
то утворюються мережі (системи) обмежень. Рішення задачі в цьому випадку
полягає у визначенні всіх поєднань значень змінних, які задовольняють
обмеженням цілісності.
Розглянемо задачу злагодженої розмітки (consistent labeling), при рішенні
якої аналізується m елементів, пронумерованих n 1, n 2,..., n m. Припустимо, що
кожний елемент n i, може бути помічений (інтерпретований) декількома
способами. Кількість можливих інтерпретацій кожного елемента задається
числами b 1, b 2,…, b m. Якщо розглядати можливі інтерпретації всієї сукупності
елементів і перевіряти їх на дотримання обмежень цілісності (тобто з'ясовувати
чи відображають вони допустимі рішення), то необхідно проаналізувати:
b 1b 2b 3...b m випадків. Хоча дана задача легко представляється у вигляді графа
станів, доцільно все ж таки перейти до іншого представлення – до графа,
вершини якого є елементи n i а ребра відповідають бінарним відносинам між
відповідними елементами.
Нехай для кожного з елементів n i,  {n 1, n 2,.., n m} є кінцева множина
інтерпретації (міток) L і, потужністю G i. Можливість або неможливість

злагодженої інтерпретації двох елементів n i i n j - за допомогою міток l i  L i i
l j  L j задається бінарним відношенням b ij. Якщо певна мітка l i, для елемента n i,
не узгоджується з відповідною міткою l j для елемента n j (тобто не задовольняє
відношенню b ij, то дана мітка видаляється з множини L i. Аналогічним чином
досліджуються всі мітки, що входять в множину l j. В ході вказаного процесу з
кожною вершиною графа зв'язується мітка (або множина міток). При цьому
мітки на кінцях ребер графа повинні задовольняти заданим відносинам.
Розглянемо приклад злагодженої розмітки вершин графа, зображеного на
рис.12.2 Біля вершин графа вказана множина можливих міток, а обмеження,

114