Читайте также:
|
|
Задача чітко поставлена, тепер потрібно сформулювати для неї математичну модель. Це дуже важливий крок у процесі розв’язання і його треба добре обміркувати. Вибір моделі істотно впливає на розв'язання інших етапів, оскільки усе, що ви пропустите зараз, доведеться робити потім, перериваючи роботу і повертаючи назад.
Як ви можете здогадатися, неможливо запропонувати набір правил, що автоматизують стадію моделювання. Вибір моделі більше справа мистецтва, ніж науки і, ймовірно, ця тенденція збережеться. Це один з безлічі випадків, коли необхідне застосування творчих здібностей людини. А найкращий спосіб придбати досвід у моделюванні – вивчення вдалих моделей. Але, і в цій справі існують кілька корисних керуючих принципів.
Приступаючи до розробки моделі, варто задати, принаймні, два основних питання:
1. Які математичні структури більше всього підходять для задачі?
2. Чи існують вирішені задачі?
Друге питання, можливо, саме корисне у всій математиці. У контексті моделювання воно часто дає відповідь на перше питання. Дійсно, більшість розв'язуваних у математиці задач, як правило, являють собою модифікації уже вирішених. Більшість з нас просто не мають талант Ньютона, Ейнштейна чи Гауса, і для просування вперед нам доводиться керуватися накопиченим досвідом.
Спочатку розглянемо перше питання. Ми повинні математично описати, що нам відомо, і що хочемо знайти. На вибір відповідної структури будуть впливати такі фактори, як:
· обмеженість наших знань відносно невеликою кількістю структур;
· зручність представлення;
· простота обчислень;
· корисність різних операцій, зв'язаних з розглянутою структурою.
Зробивши пробний вибір математичної структури, задачу варто переформулювати в термінах відповідних математичних об'єктів. Це буде одна з можливих моделей, якщо ми можемо позитивно відповісти на наступні питання:
1. Чи уся важлива інформація добре описана математичними об'єктами?
2. Чи існує математична величина, що асоціюється із шуканим результатом?
3. Чи виявили ми які-небудь корисні відносини між об'єктами моделі?
4. Чи зручно працювати з моделлю?
У переважній більшості випадків доцільним на даному етапі є застосування декомпозиції задачі.
Принцип декомпозиції – один із широко застосовуваних прийомів до технології програмування. Він полягає в тому, що складна задача розбивається на підзадачі поменше (а ті – на ще більш дрібні і т.д.). Це дає можливість надалі складати алгоритми для розв'язання задачі вроздріб, що значно полегшує роботу.
Приклад [ ]:
Повертаємося до задачі комівояжера. Починаємо з постановки задачі, заданої наприкінці приклада.
Чи вирішували ми коли-небудь подібні задачі? З математичного боку, ймовірніше за все, ні. Однак усі ми зіштовхувалися з задачами вибору шляху за картами доріг чи у лабіринтах. Чи можемо ми перейти до зручного представлення нашої задачі у виді карти?
Очевидно, потрібно взяти лист паперу і нанести на нього ряд точок, що відповідають кожному місту. Щоб не ускладнювати собі задачу, ми не будемо зображувати точки так, щоб відстань між кожною парою точок, що відповідають містам i і j, було пропорційно вартості проїзду Cij. Розташуємо точки будь-яким зручним способом, з'єднаємо точки i і j лініями і проставимо на них «ваги» Cij.
Схема, що ми тільки що зобразили, - це окремий випадок відомого в математиці графа, чи сітки. У загальному випадку сітка – це безліч точок (на площині) разом з лініями, що з'єднують усі чи деякі пари точок; над лініями також можуть бути проставлені ваги.
Припустимо також, що вартість проїзду з i в j дорівнює вартості проїзду з j в i, хоча це і необов'язково.
Що ми шукаємо в задачі? У термінах теорії графів список міст (який ми раніше описали) визначає замкнутий цикл, що починається з базового міста і повертається туди ж після проходження всіх міст по одному разу. Такий цикл відповідає спрямованому руху олівця уздовж ліній сітки, що починається і закінчується в одній і тій же точці. Обхід такого роду назвемо туром. Вартість туру визначається як сума ваг усіх пройдених ребер. Задача буде вирішена, якщо ми зможемо знайти тур з мінімальною вартістю.
Розглянута задача відома в літературі як задача комівояжера; вона стала якоюсь мірою класичною. Це один з найбільш відомих прикладів задач, що дуже легко поставити і промоделювати, але дуже важко вирішити.
Дата добавления: 2015-01-30; просмотров: 25 | Поможем написать вашу работу | Нарушение авторских прав |