Теоретико-числові методи розв'язання задач комбінаторної оптимізації

Размещено на http://www.allbest.ru/

[Введите текст]

Національна академія наук України

Інститут кібернетики імені В.М. Глушкова

ТИМОФІЄВА Надія Костянтинівна

УДК 519.14+519.168

ТЕОРЕТИКО-ЧИСЛОВІ МЕТОДИ РОЗВ'ЯЗАННЯ ЗАДАЧ КОМБІНАТОРНОЇ ОПТИМІЗАЦІЇ

01.05.02 - математичне моделювання та обчислювальні методи

Автореферат

дисертації на здобуття наукового ступеня

доктора технічних наук

Київ-2007



Дисертацією є рукопис

Робота виконана в Міжнародному науково-навчальному центрі інформаційних технологій та систем НАН України та Міністерства освіти та науки України.

Науковий консультант: доктор фізико-математичних наук, професор, академік НАН України СЕРГІЄНКО Іван Васильович, Інститут кібернетики імені В.М. Глушкова НАН України, директор.

Офіційні опоненти:

доктор технічних наук, член-кореспондент НАН України ГУБАРЕВ Вячеслав Федорович, Інститут космічних досліджень НАН України та НКА України, заступник директора,

доктор технічних наук, старший науковий співробітник ТЕСЛЕР Геннадій Семенович, Інститут проблем математичних машин і систем НАН України, головний науковий співробітник,

доктор технічних наук, професор ВОРОНІН Альберт Миколайович, Національний авіаційний університет МОН України, професор.

Захист відбудеться “ 22 ” лютого 2008 р. о (об) 11 годині.

на засіданні спеціалізованої вченої ради Д 26.194.02 при Інституті кібернетики ім. В.М. Глушкова НАН України за адресою:

03680, МСП, Київ 187, проспект Академіка Глушкова, 40.

З дисертацією можна ознайомитися в науково-технічному архіві інституту.

Автореферат розіслано “_18__”____грудня___________2007 р.

Учений секретар спеціалізованої вченої ради СИНЯВСЬКИЙ В.Ф.



ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальність теми. Задачі комбінаторної оптимізації виникають у най-різноманітніших галузях людської діяльності в процесі прийняття оптимальних рішень. Вони стосуються вибору із множини різних комбінацій заданих об'єктів однієї, яка б забезпечувала оптимальне (максимальне або мінімальне) значення цільової функції. Наприклад: 1) задача розміщення, задача комівояжера, транспортна задача, трасування друкованих плат виникають при проектуванні обчислювальної апаратури, в автоматизованих системах управління тощо. Необхідність розв'язання саме цих задач стимулювало розвиток теорії комбінаторної оптимізації; 2) задачі з комбінаторики і комбінаторної оптимізації мають місце в теорії зв'язку; 3) в розпізнаванні мовних сигналів, розпізнаванні образів також є задачі комбінаторної оптимізації. Якщо детально розглянути широкий спектр задач розпізнавання, то стає зрозумілим, що вони потребують подальшого розвитку методів комбінаторної оптимізації для їхнього розв'язання.

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

В комбінаторній оптимізації виникає проблема: чи можна, не перебираючи всі або майже всі варіанти знайти глобальний розв'язок? Наука про складність обчислень твердить, що перебірні задачі із зростанням їхньої розмірності розв'язати практично неможливо, тобто вони такі, що "важко" розв'язуються, і тому таких методів ще не знайдено. Але прикладні задачі досить часто мають велику розмірність. Наприклад, при проектуванні надвеликих інтегральних мікросхем необхідно розміщувати десятки тисяч модулів. Навіть підготовка вхідної інформації в цьому разі стає досить складною задачею. Тому виникає запитання: чи можна для деяких особливих структур вхідних даних знаходити аргумент, для якого цільова функція набуває глобального оптимуму, тобто має місце проблема знаходження оптимального розв'язку поліноміальними алгоритмами, що ґрунтуються на розпізнаванні структури вхідних даних.

У теорії комбінаторної оптимізації розроблялися і розробляються поліноміальні алгоритми знаходження оптимального розв'язку, що ґрунтуються на розпізнаванні структури вхідних даних. Але таких робіт, порівняно з ітераційними методами, що ґрунтуються на частковому переборі варіантів, небагато. Цьому напряму в літературі приділено недостатньо уваги, до того ж переважна більшість результатів, отримана такими методами, далека від практичного узагальнення.

Одним із підходів до розв'язання цієї проблеми є проведення аналізу цільової функції з метою виявлення властивостей, що відображають комбінаторну природу задач комбінаторної оптимізації. Саме аналізу природи цих задач, дослідженню комбінаторних конфігурацій як аргументу цільової функції, установленню зміни значень функції цілі залежно від упорядкування аргументу і від специфіки структури вхідних даних у літературі достатньої уваги не приділяється. Як зауважив В.М. Глушков (Глушков В.М. Введение в АСУ. - К.: Техніка, 1974. - 320 с.), без системного аналізу природи певних задач з метою виявлення їхніх характерних властивостей використання для розв'язання поставленої проблеми нових підходів та відомих методів може бути не завжди ефективним.

Тому однією з важливих проблем цієї області є виявлення властивостей цільової функції задач комбінаторної оптимізації, використання яких дозволяло б установити закономірність зміни її значень від упорядкування аргументу і від специфіки структури вхідних даних, формування математичних постановок цих задач, які б відображали їхню комбінаторну природу, виявлення властивостей комбінаторних конфігурацій як аргумента цільової функції. Отримані результати повинні використовуватися при розробленні рекомендацій для створення локальних ефективних методів і алгоритмів, орієнтованих на розв'язання практичних задач різних класів.

Вагомий внесок у розвиток комбінаторики і комбінаторної оптимізації зробили такі закордонні вчені: К.О. Рибников, В.М. Сачков, В.Є. Тараканов, М.Л. Платонов, Д. Кнут, А. Кофман, В. Липський, Ф. Харарі, Дж.Г. Райзер, Дж. Ріордан, М.Х. Холл, Г. Ендрюс, Р. Стенлі, М. Гері, Д. Джонсон, В.О. Ємелічев, Ю.І. Журавльов, Ю.Ю. Фінкельштейн, О.А. Корбут, Х. Пападимитріу, К. Стайгліц; а також вчені з України: В.С. Михалевич, Н.З. Шор, І.В. Сергієнко, В.О. Трубін, В.Л. Волкович, Г.П. Донець, В.П. Шило, В.О. Перепелиця, Ю.Г. Стоян, В.Я. Бурдюк, Ю.Ю. Червак та багато інших.

Створення методології комплексного підходу до аналізу цільової функції в задачах комбінаторної оптимізації, який охоплює широкий спектр досліджень: комбінаторних матриць, комбінаторних функцій, комбінаторних конфігурацій як аргументу цільової функції, підкласів розв'язних задач із класів комбінаторної оптимізації, результати якого дають можливість розробити методи знаходження оптимального розв'язку, що ґрунтуються на розпізнаванні структури вхідних даних - актуальні проблеми комбінаторної оптимізації.

Зв'язок роботи з науковими програмами, планами, темами. Проведені в дисертаційній роботі дослідження виконувалися у МННЦ ІТіС у рамках держбюджетних тем ІП.130.01 ”Розробка принципів інформаційних технологiй та комп'ютерних структур автоматичного розпiзнавання та синтезу сигналiв мовлення для систем усного перекладу та диктувальних машин” (1996-2000 рр., номер державної реєстрації 0196U007572), ІП.130.03 ”Розроблення принципів, методів, математичного забезпечення та діючої експериментальної моделі автоматичного транскрибування усномовного сигналу - автоматичний фонетичний стенограф” (2000-2003 рр., номер державної реєстрації 0101U002676).

Мета і завдання дослідження. Метою роботи є створення нового підходу до виявлення властивостей цільової функції в задачах комбінаторної оптимізації, розроблення методу моделювання структури вхідних даних і нових загальних постановок задач комбінаторної оптимізації, які б відображали їхню комбінаторну природу, введення нових підкласів розв'язних задач із різних класів, розроблення нового локального методу знаходження оптимального розв'язку, що ґрунтується на певному способі упорядкування комбінаторних конфігурацій та моделюванні і розпізнаванні структури вхідних даних, виявлення спільних властивостей утворення та упорядкування комбінаторних конфігурацій (аргументу цільової функції), узагальнення методів їхнього генерування.

Досягнення мети роботи пов'язане із постановкою та розв'язанням таких задач.

Проведення аналізу комбінаторних конфігурацій як аргумента цільової функції з метою виявлення спільних закономірностей їхнього утворення та упорядкування. Розроблення методу їхнього генерування та методу для розв'язування перелічувальних задач.

Розроблення методу моделювання структури вхідних даних і математичних постановок двох типів задач комбінаторної оптимізації.

Розроблення способу упорядкування комбінаторних конфігурацій підмножинами з урахуванням структури матриць з метою встановлення закономірності зміни значень цільової функції для цього упорядкування.

Розроблення локального методу знаходження оптимального розв'язку задач комбінаторної оптимізації, що ґрунтується на певному впорядкуванні комбінаторних конфігурацій та моделюванні структури вхідних даних.

Виявлення нових підкласів розв'язних задач із класів задач комбінаторної оптимізації.

Розроблення способів визначення динамічних параметрів у задачах проектування електронно-обчислювальної апаратури.

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

Предмет дослідження - комбінаторні конфігурації як аргумент цільової функції, комбінаторні матриці і комбінаторні функції, якими задаються вхідні дані, структурне перетворення вхідних даних, залежність цільової функції від упорядкування комбінаторних конфігурацій та від транспозиції елементів перестановки, підкласи розв'язних задач із класів задач комбінаторної оптимізації.

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

Наукова новизна одержаних результатів. До захисту виносяться такі основні результати роботи, які визначають її наукову новизну:

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

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

Сформульовано загальні формальні постановки двох типів задач комбінаторної оптимізації, вхідні дані в яких задано двома функціями натурального аргументу, одна з яких - комбінаторна.

Описано властивості комбінаторних матриць і комбінаторних функцій, якими задаються вхідні дані в задачах комбінаторної оптимізації.

Виділено і досліджено нові підкласи розв'язних задач із класів комбінаторної оптимізації.

Розроблено локальний метод знаходження оптимального розв'язку в задачах комбінаторної оптимізації, названий методом структурно-алфавітного пошуку, який ґрунтується на моделюванні структури вхідних даних і заданому упорядкуванні комбінаторних конфігурацій.

Розроблено способи визначення динамічних параметрів у задачах проектування електронно-обчислювальної апаратури та спосіб контролю топології друкованого монтажу, що ґрунтується на розпізнаванні структури вхідних даних.

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

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

Отримані у дисертації результати реалізовані в математичному забезпеченні системи автоматизованого проектування друкованих плат САПР ДІСИО, Державний фонд алгоритмів і програм, № 50870000013 УкрРФАП інв. № АП0099 від 13.09.1986, (акт про впровадження комплексу програм САПР ДІСИО у СКБ ММС ІК ім. В.М. Глушкова АН УРСР за 1986 р.), координатному комутаторі (розробка: координатний комутатор, заявка 94051272, заявл. 29.06.93, № В 360435210211068), комплексі програм розв'язання задач комбінаторної оптимізації методом структурно-алфавітного пошуку, який включає програми генерування комбінаторних конфігурацій різних типів та програми сегментації мовного сигналу на квазіперіодичні і неперіодичні ділянки.

Особистий внесок здобувача. Усі результати, наведені в дисертації, належать дисертанту і отримані самостійно. У роботах [1, 2] дисертанту належать розроблені алгоритми і програми, що стосуються проектування друкованих плат, у [28] - аналіз координатного комутатора і запропонована його нова конструкція.

Апробація результатів дисертації. Основні результати дисертації доповідалися та обговорювалися на наукових семінарах, конференціях, симпозіумах, школах, серед яких: Республіканські семінари Наукової ради з проблеми "Кібернетика" НАН України (Київ, 1991, 1998), Міжнародні наукові конференції імені академіка М. Кравчука (Київ, VI-XI конференції 1997, 1998, 2000, 2002, 2004, 2006 років), Всеукраїнські міжнародні конференції "Оброблення сигналів і зображень та розпізнавання образів" (Київ, III, IV, VI, VII, VIII конференції 1996, 1998, 2002, 2004 та 2006 років), Міжнародна конференція "Питання оптимізації обчислень ПОО-XXVII" (Київ, 1997), Міжнародний симпозіум "Питання оптимізації обчислень-XXVIII" (Київ, 1999), Міжнародний симпозіум "Питання оптимізації обчислень-XХХ" (Кацивелі (Крим), 2001), Міжнародна конференція "Питання оптимізації обчислень ПОО-XXХII" (Кацивелі (Крим), 2005), Міжнародна конференція "Моделирование и исследование устойчивости динамических систем (DSMSI-2007)" (Київ, 2007), Міжнародні конференції з автоматичного управління (Харків, XII конференція "Автоматика-2005", 2005 р.; Вінниця, XIII конференція "Автоматика-2006", 2006 р.; Севастополь, XIV конференція "Автоматика-2007", 2007 р.), Міжнародні науково-технічні конференції "Системний аналіз та інформаційні технології" (Київ, VII, IХ конференції 2005 та 2007 р.р.), III Міжнародна школа-семінар "Теорія прийняття рішень" (Ужгород, 2006).

Основні результати роботи пройшли апробацію у провідних наукових колективах України.

Публікації. Основні результати дисертації повно викладено у 62 наукових працях, з них 25 найважливіших - у наукових фахових виданнях (журналах та збірниках наукових праць): "Кибернетика и системный анализ", "Управляющие системы и машины", "Кибернетика и вычислительная техника. Сложные системы управления", "Проблемы управления и информатики", "Вісник Київського університету", "Компьютерная математика", "Математичні машини і системи", "Вестник НТУ “ХПИ”".

Структура і обсяг дисертації. Дисертація складається із вступу, шести розділів, висновків, списку використаних джерел (357 найменувань) та двох додатків. Загальний обсяг роботи становить 299 сторінок, основний текст роботи викладено на 282 сторінках.

ЗМІСТ РОБОТИ

комбінаторний конфігурація оптимізація задача

У вступі розкрито стан наукової проблеми та її значимість, обґрунтовано необхідність проведення дослідження та актуальність теми дисертаційної роботи, її зв'язок з науковими програмами, сформульовано мету і завдання дослідження, визначені об'єкт і предмет дослідження, сформульовано наукову новизну та практичне значення отриманих результатів, зазначено особистий внесок здобувача, надаються відомості про апробацію отриманих результатів та про наявні публікації.

У першому розділі "Огляд методів розв'язання задач комбінаторної оптимізації" характеризуються задачі комбінаторної оптимізації, наводиться огляд основних напрямів їхнього дослідження і розв'язання. Проведено аналіз тих актуальних проблем, від розв'язання яких залежить подальший розвиток цього важливого наукового напряму.

Для розв'язання задач із класів комбінаторної оптимізації відомі два такі основні підходи: а) ітераційні методи та алгоритми, що ґрунтуються на частковому переборі варіантів, б) методи та алгоритми, що ґрунтуються на розпізнаванні структури вхідної інформації.

Методи і алгоритми, що ґрунтуються на розпізнаванні структури вхідної інформації, ефективні за швидкодією, але результати розв'язання при цьому можуть бути далекі від оптимальних. З цієї причини другому підходу у літературі достатньої уваги не приділяють. Але все ж таки виникає запитання: чи можна, використовуючи значну перевагу за швидкодією, за структурою вхідних даних знаходити аргумент, для якого цільова функція набуває глобального оптимуму?

Задачі комбінаторної оптимізації, як правило, задаються на одній або кількох множинах, елементи яких мають будь-яку природу.

З елементів однієї із заданих множин утворюється комбінаторна множина - сукупність комбінаторних конфігурацій певного типу (перестановки, вибірки різних типів, розбиття тощо). На елементах комбінаторної множини вводиться цільова функція . Необхідно знайти елемент множини , для якого цільова функція набуває екстремального значення (глобального мінімуму або глобального максимуму) при виконанні заданих обмежень.

В комбінаторній оптимізації часто використовують задачу цілочислового лінійного програмування

Виходячи її постановки, багато авторів вважає, що цільова функція в задачах комбінаторної оптимізації залежить від багатьох змінних. Задача цілочислового лінійного програмування не відображає суті задач комбінаторної оптимізації. Значення послідовності є вхідними даними, що задають кількість зв'язків між елементами заданої множини або відповідають властивостям цих елементів. Змінні неявно залежать від комбінаторних конфігурацій. Тоді постає проблема визначення цієї залежності в задачах комбінаторної оптимізації. Виявлення і використання комбінаторних властивостей, як буде показано нижче, відкриває нові перспективи розв'язання задач комбінаторної оптимізації, що ґрунтуються на розпізнаванні структури вхідної інформації.

Ще у 70-х роках минулого століття в математичній літературі саме вче-ними Радянського Союзу математична постановка задачі комбінаторної оптимізації описувалася з урахуванням її комбінаторної природи. Зокрема, в Інституті кібернетики цими проблемами займалися І.В. Сергієнко та його учні.

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

У другому розділі "Утворення і впорядкування комбінаторних конфігурацій" описуються властивості комбінаторних конфігурацій як аргумента цільової функції. Вводяться три рекурентні комбінаторні оператори, завдяки яким утворюються різноманітні типи цих об'єктів. Показано, що їхні множини складаються з підмножин ізоморфних комбінаторних конфігурацій. Знання структури цих множин важливе при розв'язанні задач комбінаторної оптимізації, в яких пошук оптимального значення цільової функції проводиться як на всій такій множині, так і на їхніх підмножинах. Виявлено властивість періодичності, що характерна для генерування різних типів комбінаторних конфігурацій. Показано, що за одними і тими ж правилами упорядковуються різні типи цих об'єктів, а деякі з них генеруються різними модифікаціями одного і того ж алгоритму.

На прикладі розбиття натурального числа і розбиття -елементної множини на підмножини показано, що описану властивість періодичності можна використовувати і для розв'язування перелічувальних задач.

Комбінаторною конфігурацією назвемо будь-яку сукупність елементів, яка утворюється з усіх або з деяких елементів заданої множини. Комбінаторні конфігурації можуть утворюватися одна з однієї певною операцією. Множину, з елементів якої утворюються комбінаторні конфігурації, назвемо базовою.

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

Різноманітні типи комбінаторних конфігурацій утворюються за допомогою трьох рекурентних комбінаторних операторів: вибирання, транспозиція, арифметичний.

Аналіз множин комбінаторних конфігурацій різних типів показав, що вони упорядковуються інтервалами, об'єкти в яких утворюються за одними і тими самими правилами. Назвемо їх інтервалами нульового рангу. Першу комбінаторну конфігурацію в них назвемо обмежувальною. Інтервали нульового рангу об'єднуються в більші інтервали - першого рангу, інтервали першого рангу - в інтервали другого рангу, інтервали -го рангу - в інтервали -го рангу. Величина різна для різних типів комбінаторних множин. Тобто для упорядкування множини комбінаторних конфігурацій властива періодичність.

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

З використанням цієї властивості комбінаторні конфігурації різних типів генеруються за трьома правилами, за якими утворюються: а) інтервал нульового рангу; б) обмежувальна комбінаторна конфігурація (перша в інтервалі нульового рангу), при утворенні якої забезпечується перехід до інтервалу -го рангу; в) інтервал -го рангу. Усі ці правила розробляються для кожної комбінаторної множини певного типу. Kомбінаторні конфігурації, які утворюються комбінацією двох і більше рекурентних комбінаторних операторів, генеруються комбінованими алгоритмами.

У цьому розділі показано, що властивість періодичності можна використовувати для вивчення структури упорядкованої множини комбінаторних конфігурацій і розв'язування перелічувальних задач у комбінаториці. З допомогою розробленого на її основі методу узагальнено деякі відомі формули для знаходження комбінаторних чисел. Цей метод полягає в тому, що правила генерування дозволяють визначати кількість комбінаторних об'єктів в інтервалах нульового і -го рангів, величини яких задаються скінченними послідовностями. Сума значень цих послідовностей визначає кількість комбінаторних конфігурацій у заданій множині. На прикладах розбиття -елементної множини на підмножини і неупорядкованого розбиття натурального числа показано, як цим методом розв'язувати перелічувальні задачі.

У третьому розділі "Метод моделювання структури вхідних даних" описано метод моделювання структури вхідних даних і його використання для виділення підкласів розв'язних задач із класів -повних задач. Для двох типів задач комбінаторної оптимізації, які розрізняються способом задання вхідних даних, розроблено загальні постановки, вхідні дані в яких подано двома скінченними послідовностями (функціями натурального аргументу, одна з яких - комбінаторна). На прикладі деяких відомих задач, аргументом цільової функції яких є різні типи комбінаторних конфігурацій, показано, як їх зводити до запропонованих постановок. У цьому розділі описано також властивості комбінаторних матриць, які виникають у задачах комбінаторної оптимізації.

У цьому розділі пропонується структурне перетворення структури вхідних даних задач комбінаторної оптимізації (метод моделювання структури вхідних даних) з використанням скінченних послідовностей (функцій натурального аргументу). В цьому методі враховано недоліки загальної постановки задачі комбінаторної оптимізації, описаної Д.О. Супруненком.

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

Для зведення цільової функції широкого класу задач комбінаторної оптимізації до одного виразу скінченну послідовність задамо структурною функцією, аргументом якої є комбінаторна конфігурація. Назвемо її комбінаторною функцією. Послідовність елементів симетричної чи несиметричної матриці, яка не є комбінаторною, задамо структурною числовою функцією (функцією натурального аргументу). Функція цілі для цих задач є сумарний добуток значень комбінаторної та числової функцій

За допомогою описаного методу моделювання структури вхідних даних показано, що матриці, які моделюються лінійними та унімодальними вгнутими функціями натурального аргументу, зводяться до задач Супніка, Демиденка, Кальмансона, тобто вони є також розв'язними.

У четвертому розділі "Комбінаторні і цільова функції, їхні властивості" аналізуються деякі властивості комбінаторних функцій, якими задаються вхідні дані в задачах комбінаторної оптимізації. З використанням виявлених властивостей визначено закономірність зміни значень цільової функції залежно від транспозиції елементів у перестановці і від упорядкування комбінаторних конфігурацій, знайдено множину значень цільової функції.

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

Показано, що на підмножині ізоморфних комбінаторних конфігурацій цільова функція змінюється так, як і на множині перестановок.

У п'ятому розділі "Підкласи розв'язних задач комбінаторної оптимізації і метод структурно-алфавітного пошуку" розглянуто підкласи розв'язних задач із класів комбінаторної оптимізації, які є математичними моделями таких прикладних задач, як задача комівояжера, задача про призначення, задача розміщення об'єктів на заданій поверхні, кластеризація. Для знаходження оптимального розв'язку і встановлення закономірності зміни значень цільової функції на заданому впорядкуванні підмножин комбінаторних конфігурацій запропоновано метод, що ґрунтується на моделюванні структури вхідних даних. З цією метою розроблено спосіб упорядкування множини комбінаторних конфігурацій підмножинами з використанням незалежних від вхідних даних параметрів. Оскільки множина комбінаторних конфігурацій за розробленими правилами упорядкована так, як слова у словнику, то цей метод названо методом структурно-алфавітного пошуку. Аргумент цільової функції, для якого вона набуває оптимального значення, знаходиться з використанням упорядкованих функцій натурального аргументу, якими моделюються вхідні дані. Подано обчислювальну схему запропонованого методу, роботу якої показано на розв'язних задачах.

Для фіксованого аргументу послідовність величин добутку значень числової і комбінаторної функцій є комбінаціями елементів заданої матриці, причому якщо одна із заданих функцій - бінарна послідовність, то з матриці вибираються не всі елементи. Цю послідовність назвемо варіантом розв'язання задачі. За способом утворення множина варіантів розв'язання задачі розбивається на підмножини. У першій підмножині знаходяться послідовності, значення яких вибрані з матриці, починаючи з елемента під адресою 1, у другій підмножині - починаючи з адреси 2 і т.д. Кількість таких підмножин для різних задач - різна. Відповідно на підмножини розбивається і множина комбінаторних конфігурацій. Утворені підмножини складаються з менших підмножин. Таке упорядкування множини комбінаторних об'єктів можна проводити по двох, трьох і більше значеннях варіантів розв'язання задачі, і воно не залежить від вхідних даних. Алфавітом у цьому упорядкуваннні виступають номери адрес матриці.

За допомогою правил утворення варіантів розв'язання задачі для різної структури вхідних даних (функція натурального аргументу і комбінаторна функція змінюються як лінійні, монотонні, періодичні з різними довжинами періодів) для розв'язних задач комівояжера, розміщення, задачі про призначення, задач розбиття аналітично знайдено аргумент, для якого цільова функція набуває глобального оптимального значення, а також указано підмножини, в яких вони знаходяться.

Оптимальний розв'язок задач комбінаторної оптимізації методом структурно-алфавітного пошуку знаходиться за комбінаторною та числовою функціями, упорядкованими за зростанням або спаданням їхніх значень. Аналогічний прийом використано у "жадібному" алгоритмі та методі найближчого сусіда, де формування аргументу починають з найбільшого (або найменшого) елемента заданої матриці. Але залежно від вхідних даних одержаний цими підходами результат, як правило, далекий від оптимального.

У методі структурно-алфавітного пошуку за упорядкованими комбінаторною та числовою функціями за розробленими правилами, починаючи з най-менших або найбільших їхніх значень з урахуванням структури вхідних даних і комбінації елементів у рядках і стовпцях, знаходиться локальний оптимум і для нього визначається підмножина комбінаторних конфігурацій (перестановок) , яка містить глобальний розв'язок. Потім у знайденій підмножині за другим, третім і т. д. елементами варіанту розв'язання задачі знаходяться другий, третій і т.д. локальні оптимуми, значення яких зменшуються або не змінюються. У кожній одержаній підмножині перестановок виділяються менші підмножини, які можуть містити глобальний розв'язок. Тим самим звужується область його пошуку. Пошук оптимального розв'язку за цією схемою проводиться так, як пошук слова у словнику. В результаті за розробленими правилами за комбінаторною і числовою функціями за поліноміальну часову складність знаходиться деяка послідовність локальних екстремумів, значення яких з черговою ітерацією зменшуються або не змінюються у разі мінімізації, збільшуються або не змінюються у разі максимізації і наближаються до глобального оптимального розв'язку.

У дисертації на прикладах розв'язних задач розміщення, комівояжера, задачі про призначення, для яких відомий глобальний оптимум, наведено роботу обчислювальної схеми методу структурно-алфавітного пошуку.

У додатку А дисертації наведено приклади розв'язання задач комбінаторної оптимізації запропонованим методом. Одержані результати показують, що для довільних прикладних задач метод структурно-алфавітного пошуку при високій швидкодії забезпечує точність розв'язку задач цього класу не гіршу ніж метод гілок і меж, динамічне програмування, послідовний аналіз варіантів тощо.

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

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

У шостому розділі "Прикладне застосування отриманих результатів" описано способи визначення динамічних параметрів у задачах, які виникають у конструкторському проектуванні обчислювальної апаратури, від автоматичного знаходження яких певною мірою залежить повна автоматизація процесу проектування. Подано математичні моделі цих задач і алгоритми їхнього розв'язання. Запропоновано алгоритм контролю топології друкованого монтажу, що ґрунтується на розпізнаванні структури вхідних даних. Програми їхнього розв'язання реалізовані у системі автоматизованого проектування обчислювальної апаратури ДІСИО.

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

Проведена оптимізація конструкції координатного комутатора, який являє собою матрицю з входами і виходами, з метою мінімізації кількості елементів, розміщених на його поверхні. Розв'язок поставленої задачі досягається за рахунок зменшення кількості рядків і стовпців матриці та перенесення шин комутації на паралельні поверхні. В результаті одержано багатошарову конструкцію координатного комутатора. Кожен його шар складається з діелектрика з розміщеними на ньому ортогональними шинами, в точках перетину яких знаходиться спільний для всіх шарів з'єднувальний елемент. Доведені теореми встановлюють оптимальні коефіцієнти зменшення комутатора, з урахуванням яких одержаний варіант його конструкції залишається неблокувальним. Таке його виконання значно підвищує щільність комутаційних з'єднань і спрощує технологію виготовлення так званих макетних плат, що важливо при великій номенклатурі малосерійних виробів.

Запропоновано математичну модель задач розпізнавання та синтезу мовлення як задач комбінаторної оптимізації, аргументом цільової функції в яких є вибірки різних типів. Оскільки аргументом цільової функції в задачі порівняння двох мовних сигналів є розміщення без повторень, а при пошуку в словнику мовних сигналів відповідного еталона - сполучення без повторень, то задача розпізнавання розв'язується гібридним (комбінованим) алгоритмом. Показано, що задача упорядкування мовних сигналів, що відповідають певним словам, у словнику зводиться до задачі кластеризації. Запропоновано обчислювальну схему пошуку мовного сигналу (слова) у словнику великих розмірів. Розроблено ітераційний алгоритм задачі сегментації мовного сигналу на квазіперіодичні і неперіодичні ділянки, у якому використано багатокритеріальну оптимізацію.



ВИСНОВКИ

В результаті проведених досліджень досягнута основна мета роботи - cтворено нову методологію щодо виявлення властивостей цільової функції в задачах комбінаторної оптимізації. З використанням цих властивостей розроблено метод моделювання структури вхідних даних і сформульовано нові постановки задач комбінаторної оптимізації, вхідні дані в яких задаються функціями натурального аргументу. Описано властивості комбінаторних конфігурацій як аргумента цільової функції і властивість періодичності, що має місце при упорядкуванні множин комбінаторних конфігурацій різних типів. На підставі властивості періодичності розроблено метод генерування комбінаторних конфігурацій і метод для розв'язування перелічувальних задач у комбінаториці. Розроблено локальний метод знаходження оптимального розв'язку, що ґрунтується на розпізнаванні структури вхідних даних і упорядкуванні комбінаторних конфігурацій.

Основні наукові результати дисертації.

1. Описано деякі властивості структури множин комбінаторних конфігурацій різних типів як аргумента цільової функції, виявлено спільні закономірності їхнього утворення і упорядкування. Описано властивість періодичності, що характерна для упорядкування комбінаторних множин.

2. Запропоновано узагальнений метод генерування комбінаторних конфігурацій різних типів з використанням властивості періодичності. Показано, що комбінаторні конфігурації різних типів, які утворюються одним і тим самим рекурентним комбінаторним оператором, генеруються різними модифікаціями одного і того самого алгоритму.

3. Розроблено новий метод розв'язання перелічувальних задач у комбінаториці, що ґрунтується на властивості періодичності. За допомогою запропонованого методу узагальнено деякі класичні формули комбінаторних чисел.

4. Розроблено метод моделювання структури вхідних даних з використанням скінченних послідовностей. На його основі запропоновано нові формальні постановки задач комбінаторної оптимізації, вхідні дані в яких задано функціями натурального аргументу, одна з яких - комбінаторна. Розроблено поняття класу розв'язних задач.

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

6. З використанням методу моделювання структури вхідних даних виділено новий підклас розв'язних задач із класів задачі комівояжера, задачі про призначення, задачі розміщення.

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

8. Розроблено локальний метод розв'язання задач комбінаторної оптимізації (метод структурно-алфавітного пошуку), що ґрунтується на моделюванні структури вхідних даних і впорядкуванні комбінаторних конфігурацій.

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

10. Розроблено математичні моделі для задачі розпізнавання, задачі синтезу мовних сигналів як задач комбінаторної оптимізації. Розроблено математичну модель, алгоритми і програми сегментації мовного сигналу на квазіперіодичні і неперіодичні ділянки. Запропоновано обчислювальну схему швидкого пошуку слова у словнику великих розмірностей.

11. Розроблено алгоритми і комплекс програм для генерування комбінаторних конфігурацій різних типів, для знаходження підкласів розв'язних задач із класів задачі комівояжера, задачі розміщення, задачі про призначення, для розв'язання задач комбінаторної оптимізації методом структурно-алфавітного пошуку.

12. Розроблено алгоритми і програми визначення динамічних параметрів у задачах, які виникають у конструкторському проектуванні обчислювальної апаратури, від автоматичного знаходження яких певною мірою залежить повна автоматизація процесу проектування. Запропоновано алгоритм і розроблено програму контролю топології друкованого монтажу, що ґрунтується на розпізнаванні структури вхідних даних.



ОТРИМАНІ ПОЛОЖЕННЯ ДИСЕРТАЦІЇ ОПУБЛІКОВАНО В ТАКИХ ПРАЦЯХ

1. Сергиенко И.В., Гуляницкий Л.Ф, Тимофеева Н.К. ДИСИО - пакет программ автоматизации конструкторского проектирования цифровой аппаратуры // Пакеты прикладных программ. Программное обеспечение оптимизационных задач: Сб. науч. тр. - М., 1987. - С. 3-16.

2. Сергиенко И.В., Гуляницкий Л.Ф., Тимофеева Н.К. Некоторые особенности построения математического обеспечения САПР ДИСИО // УСиМ. - 1989.- № 2. - С. 105-108.

3. Тимофеева Н.К. К вопросу формирования графической информации в САПР // Программно-алгоритмическое обеспечение пакетов программ: Сб. науч. тр. - К., 1986. - С. 39-42.

4. Тимофеева Н.К. О распределении инвариантных выводов модулей при проектировании печатных плат // Пакеты прикладных программ и численные методы: Сб. науч. тр.- К., 1988. - С. 121-125.

5. Тимофеева Н.К. Проблемы контроля топологии печатного монтажа // Численные методы и технология разработки пакетов прикладных программ: Сб. науч. тр. - К., 1990. - С. 42-47.

6. Тимофеева Н.К. Исследование функции цели в задачах оптимизации комбинаторного типа // Технология и методы решения задач прикладной математики: Сб. науч. тр. - К., 1991. - C. 52-56.

7. Тимофеева Н.К. Частный случай задачи коммивояжера // Разработка мат. и программного обеспечения ППП и решение задач дискретной оптимизации: Сб. науч. тр.- К., 1992. - С. 95-101.

8. Тимофеева Н.К. Нахождение оптимального решения в задаче коммивояжера // Программно-алгоритмическое обеспечение решения задач прикладной математики: Сб. науч. тр. - К., 1993. - С. 21-26.

9. Тимофеева Н.К. Об одном подходе к нахождению оптимального решения в задаче о назначениях // Кибернетика и системный анализ. - 1996. - № 1. - С. 104-112.

10. Тимофеева Н.К. Матрицы в задачах комбинаторной оптимизации // Проблемы управления и информатики.- 1996. - № 3. - С. 104-113.

11. Тимофеева Н.К. Нахождение оптимального решения в задаче о назначениях // Кибернетика и вычислительная техника: Сб. научн. тр. - К., 1997. - Вып. 107. - С. 80-87.

12. Тимофеева Н.К. Упорядочение множества значений аргумента целевой функции в комбинаторной оптимизации // Кибернетика и системный анализ. - 1998. - № 6. - C. 78-87.

13. Тимофеева Н.К. Определение множества значений целевой функции в задачах дискретной математики // Кибернетика и вычислительная техника. Сложные системы управления: Сб. науч. тр. - К., 1998.- Вып. 120. - С. 37-43.

14. Тимофієва Надія К. Про один спосіб розв'язання перелічувальних задач // Вісн. Київськ. ун-ту. Сер. фіз.- мат. науки. - К., 2002. - № 3. - С. 245-249.

15. Тимофеева Н.К. О некоторых свойствах разбиений множества на подмножества // УСиМ. - 2002. - № 5. - С. 6-23.

16. Тимофеева Н.К. О способах образования аргумента целевой функции в задачах комбинаторной оптимизации // Кибернетика и системный анализ. - 2002. - № 6. - C. 96-103.

17. Тимофеева Н.К. Об одном способе определения количества разбиений целого положительного числа // УСиМ.- 2004.- № 1.- С. 31-38.

18. Тимофеева Н.К. Комбинаторные функции в задаче размещения // Компьютерная математика: Сб. науч. тр. - 2004. - №1. - С. 47-56.

19. Тимофеева Н.К. Об особенностях формирования и упорядочения выборок // Кибернетика и системный анализ. - 2004. - № 3. - С. 174-182.

20. Тимофієва Надія К. Про утворення маршрутів у задачі комівояжера // Вісн. Київськ. ун-ту. Сер. фіз.-мат. науки. - К., 2004. - № 3. - С. 287 -291.

21. Тимофеева Н.К. О некоторых особенностях построения математических моделей задач комбинаторной оптимизации // УСиМ. - 2004. - № 5. - С. 38-45.

22. Тимофеева Н.К. Зависимость целевой функции задач комбинаторной оптимизации от упорядочения комбинаторных конфигураций // Компьютерная математика: Сб. науч. тр. - 2005. - № 2. - С. 135-146.

23. Тимофієва Н.К. Про оптимізацію конструкції координатного комутатора // Математичні машини і системи. - 2005. - № 1. - С. 84-92.

24. Тимофієва Н. К. Залежність цільової функції від структури вхідних даних в задачах комбінаторної оптимізації // Вестник НТУ “ХПИ”. Тематический выпуск “Системный анализ, управление и информационные технологии”: Сб. науч. тр. - Харьков, 2005. - № 55. - C. 81-86.

25. Тимофієва Надія К. Розв'язний випадок задачі розміщення // Вісн. Київськ. ун-ту. Сер. фіз.-мат. науки. - К., 2006. - № 4. - С. 227 -231.

26. Тимофієва Н.К. Представлення задач розміщення, комівояжера, кластеризації задачею про призначення. // Автоматика-2006. Матеріали XIII міжнародної конференції з автоматичного управління. Вінниця, 25-28 вересня 2006 р. - Вінниця, 2006. - С. 29-33.

27. Тимофієва Н.К. Метод структурно-алфавітного пошуку підкласів розв'язних задач із класів комбінаторної оптимізації // Теорія прийняття рішень: III Міжнар. школа-семінар. Ужгород, 2-7 жовтня 2006 р.- Ужгород, 2006. - С. 85-87.

28. Координатний комутатор: Україна, МКИ НО4 Q 3/52/ Д.М. Некрасов, Н.К. Тимофієва. - № 94051272; Заявл. 29.06.93; Опубл. 29.12.94. Бюл. № 18-1. - С. 2-105.



АНОТАЦІЯ

Тимофієва Н.К. Теоретико-числові методи розв'язання задач комбінаторної оптимізації. - Рукопис.

Дисертація на здобуття наукового ступеня доктора технічних наук за спеціальністю 01.05.02 - математичне моделювання та обчислювальні методи. - Інститут кібернетики ім. В.М. Глушкова НАН України, Київ, 2007.

Дисертація присвячена розробці методології щодо виявлення властивостей цільової функції в задачах комбінаторної оптимізації. З використанням цих властивостей розроблено метод моделювання структури вхідних даних, які подані функціями натурального аргументу, одна з яких - комбінаторна. Описано властивості комбінаторних конфігурацій різних типів як аргумента цільової функції, визначено спільні закономірності їхнього утворення і упорядкування. Виявлено властивість періодичності, яка характерна для генерування комбінаторних конфігурацій різних типів. Запропоновано узагальнений метод їхнього упорядкування і метод для розв'язування перелічувальних задач у комбінаториці. Розроблено локальний метод розв'язання задач комбінаторної оптмізації, названий методом структурно-алфавітного пошуку, який ґрунтується на розпізнаванні структури вхідних даних і упорядкуванні комбінаторних конфігурацій. Виділено новий підклас розв'язних задач із класів комбінаторної оптимізації. Розроблено новий тип координатного комутатора - об'ємний. Запропоновано математичну модель задач розпізнавання і синтезу мовлення як задач комбінаторної оптимізації.

Ключові слова: комбінаторика, комбінаторна оптимізація, цільова функція, розв'язні задачі, комбінаторна конфігурація, генерування комбінаторних конфігурацій, перелічувальні задачі, перестановка, розбиття множини на підмножини, розбиття натурального числа.



АННОТАЦИЯ

Тимофеева Н.К. Теоретико-числовые методы решения задач комбинаторной оптимизации. - Рукопись.

Диссертация на соискание ученой степени доктора технических наук по специальности 01.05.02 - математическое моделирование и численные методы. - Институт кибернетики им. В.М. Глушкова НАН Украины, Киев, 2007.

Диссертация посвящена разработке методологии по выявлению свойств целевой функции в задачах комбинаторной оптимизации. С использованием выявленных свойств разработан метод моделирования входных данных, которые представлены функциями натурального аргумента, одна из которых - комбинаторная. Выделены два типа задач этого класса, которые различаются способом задания входных данных.

Проведен анализ структуры множеств комбинаторных конфигураций разных типов как аргумента целевой функции, определены общие закономерности их образования и упорядочения. Введены три рекуррентных комбинаторных оператора, посредством которых образуются разные типы комбинаторных конфигураций. Предложен обобщенный метод генерирования комбинаторных конфигураций, в основе которого лежит свойство периодичности, характерное для упорядочения разных их типов. Использование этого метода показано на примере генерирования перестановок, разбиения натурального числа, разбиения -элементного множества на подмножества, разных типов выборок, бинарных последовательностей. Разработаны алгоритмы и программы их генерирования. Реализованный комплекс программ используется для изучения структуры этих множеств, для решения перечислительных задач, для уста-новления изменения значений целевой функции в разных задачах комбинаторной оптимизации. Разработан новый метод решения перечислительных задач в комбинаторике, в основе которого лежит свойство периодичности и с помощью которого обобщены некоторые классические формулы комбинаторных чисел.

Описаны свойства комбинаторных матриц и комбинаторных функций. Определена зависимость изменения значений целевой функции от транспозиции элементов перестановки и от упорядочения комбинаторных конфигураций. Установлена закономерность изменения значений целевой функции в за-висимости от упорядочения разбиений множества на подмножества и сочетаний без повторений. Предложен способ представления задач размещения, коммивояжера, кластеризации задачей о назначениях и способ аналитического определения множества значений целевой функции. С использованием метода моделирования структуры входных данных разработано понятие класса разрешимых задач, выделен новый подкласс этих задач из классов задачи коммивояжера, задачи о назначениях, задачи размещения.

Предложен новый метод решения задач комбинаторной оптимизации, названный методом структурно-алфавитного поиска, основанный на моделировании структуры входных данных и упорядочении комбинаторных конфигураций. С этой целью разработан способ упорядочения множества комбинаторных конфигураций подмножествами. С учетом структуры входных данных определяются те подмножества, которые содержат оптимальное значение целевой функции.

Разработаны способы определения динамических параметров в задачах проектирования электронно-вычислительной аппаратуры и способ контроля топологии печатного монтажа, основанный на распознавании структуры входных данных. С использованием свойств комбинаторных матриц разработан новый тип координатного коммутатора, у которого уменьшено количество строк и столбцов путем перенесения шин коммутации на параллельные поверхности. В результате получена многослойная конструкция координатного коммутатора (объемного).

Предложены математические модели задач распознавания и синтеза речи как задач комбинаторной оптимизации. Разработан алгоритм и программа сегментации речевого сигнала на квазипериодические и непериодические сегменты. Предложена вычислительная схема быстрого поиска слова в словаре больших размерностей.

Ключевые слова: комбинаторика, комбинаторная оптимизация, целевая функция, комбинаторная конфигурация, генерирование комбинаторных конфигураций, перечислительные задачи, перестановка, разбиение множества, разбиение натурального числа.



ABSTRACT

Tymofijeva N.K. Theoretical-Numerical Methods Used to Solve Combinatorial Optimization Problems. - Manuscript.

Тне Thesis for Doctor's Degree in Technical Sciences on Speciality 01.05.02 - Mathematical Modelling and Numerical Methods. - V.M. Glushkov Institute of Cybernetics of National Academy of Sciences of Ukraine, Kyiv, 2007.

The thesis is devoted to working out а methodology used to reveal the objective function properties within combinatorial optimization problems. With the use of such properties, a method is developed aimed at modelling of a structure of input data represented the functions of natural argument, one the functions is combinatorial. The properties of different-type combinatorial configurations as the objective function of argument are described, the conformities with the natural laws of their formation and regulation are stated. The periodicity property, typical for generation of different-type combinatorial configurations, is described. A generalized method of their regulation and a new method solving enumeration problems in combinatorics are proposed. A local method is elaborated that is used to solve combinatorial optimization problems without sorting out of variants, called a structure-alphabetical search method, by recognition of a structure of input data and ordering of combinatorial configurations. A new subclass of solvable problems is extracted out of a class of combinatorial optimization problems. A new type of crosspoint switch is constructed. It is volumetric. A mathematical model of speech recognition and synthesis problems is proposed as combinatorial optimization problems.

...