1. Методи побудови алгоритмів

1. Побудова алгоритмів

1.1. Формалізація алгоритмів.

Процес створення комп’ютерної програми для вирішення будь-якої практичної задачі складається з декількох етапів:

· формалізація і створення технічного завдання на вихідну задачу;

· розробка алгоритму вирішення задачі;

· написання, тестування, наладка і документування програми;

· отримання розв’язку вихідної задачі шляхом виконання програми.

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

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

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

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

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

1.2. Покрокове проектування алгоритмів.

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

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

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

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

3. Створюється образна модель процесу, який відбувається, використовуються графічні та інші способи представлення, образні „картинки”, які дозволяють краще зрозуміти виконання алгоритму в динаміці.

4. В образній моделі виділяється найбільш суттєва частина, для якої підбирається найбільш точне словесне формулювання.

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

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

7. Для інших неформалізованих частин алгоритму, які залишились у словесному формулюванні – перерахована послідовність дій повторюється.

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

Схематично узагальнений процес програмування можна представити наступною схемою.

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

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

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

1.3. Характеристики алгоритму

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

Вирішення гарантоване
Так Ні
Чи обов’язкове оптимальне вирішення Так Алгоритм Імовірнісний алгоритм
Ні Приблизний алгоритм Евристичний алгоритм

Як бачимо, алгоритм – це механізм, який не тільки повинен гарантувати те, що вирішення колись буде знайдене, але й те, що буде знайдене саме оптимальне, тобто найкраще вирішення. Крім того, алгоритм повинен мати наступні п’ять якостей:

1. Обмеженість в часі – робота алгоритму обов’язково повинна завершитись через деякий розумний період часу.

2. Правильність – алгоритм повинен знаходити правильне, а не будь-яке рішення.

3. Детермінованість – скільки б разів не виконувався алгоритм з однаковими вхідними даними, результат повинен бути однаковим.

4. Скінченність – опис роботи алгоритму повинен мати скінчену кількість кроків.

5. Однозначність – кожний крок алгоритму повинен інтерпретуватися однозначно.

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

1.4. Складність алгоритму

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

1. Бути простим для розуміння, перекладу в програмний код і наладки.

2. Ефективно використовувати комп’ютерні ресурси і виконуватися швидко.

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

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

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

Більшість алгоритмів надає вибір між швидкістю виконання і ресурсами. Задача може виконуватися швидше, використовуючи більше пам’яті, або навпаки – повільніше з меншим обсягом пам’яті.

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

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

При порівнянні різних алгоритмів важливо розуміти, як складність алгоритму співвідноситься із складністю вирішуваної задачі. При розрахунках за одним алгоритмом сортування тисячі чисел може зайняти 1 секунду, а сортування мільйона – 10 секунд, тоді як розрахунки за іншими алгоритмами можуть зайняти 2 і 5 секунд відповідно. У цьому випадку не можна однозначно сказати, яка із двох програм краща – це буде залежати від вихідних даних.

2. Методи розробки алгоритмів

Цей розділ присвячений основним методами розв’язку на комп’ютері задач, які вважалися традиційно задачами, що під силу розв’язати тільки людині. Це задачі, у яких серед великої (часто нескінченої) кількості варіантів слід визначити один-єдиний – найкращий, або кілька найкращих. Людина, розв’язуючи такі задачі, звичайно не перебирає усі варіанти – життєвий досвід дозволяє їй відразу відкинути явно дурні варіанти, зменшуючи область пошуку. Що більше у людини досвіду у розв’язку аналогічних задач, то швидше та цілеспрямовано вона веде пошук потрібного варіанту. Такі алгоритми часто називають алгоритмами штучного інтелекту.

Алгоритми відшукання найкращого варіанту серед багатьох можливих називаються звичайно алгоритмами перебору. Задача програміста-розробника алгоритму ввести у алгоритм якомога більше „досвіду” – умов, що дозволяють зменшити кількість варіантів, які перебираються. Чим більш цілеспрямовано буде проводитись пошук, тим більше програма набуває інтелектуальних рис, тим швидше буде знайдено найкращий результат. Фактично більшість з методів є саме цілеспрямованим перебором варіантів і до „інтелектуальної” групи відноситься лише традиційно.

2.1. Метод частинних цілей

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

Наприклад задача сортування масиву прямим обміном. Алгоритм сортування зводиться до відшукання мінімуму у несортованій частині масиву та дописування його до сортованої частини.

Функція пошуку проекції точки на площину зводиться до двох:

· пошуку рівняння прямої, перпендикулярної площині та такої, що проходить через задану точку;

· пошуку точки перетину перпендикуляру та площини.

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

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

Усі рекурсивні алгоритми є реалізацією методу частинних цілей.

2.2. Динамічне програмування

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

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

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

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

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

2.3. Метод сходження

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

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

Розв’язок можна шукати різними шляхами. Але самим очевидним є відшукати спочатку просто який-небудь цикл, що може вважатися „хорошим”. Для цього, наприклад, можна з першого міста їхати у найближче, звідти – у найближче з тих, що залишилися і так далі. З останнього міста треба буде повернутися назад. Це – перша вершина. Далі можна спробувати поліпшити цей варіант. Якщо це вийде, то це буде нова висота. Найкоротший цикл шукається за допомогою досить складних алгоритмів.

Ще один приклад використання методу сходження – ітерації.

Знайти значення корінь квадратний для довільного дійсного x – u = sqrt(x).

Якщо u = sqrt(x), то x/u = u;

Якщо u < sqrt(x), то x/u > sqrt(x).

Тому будь-коли середнє між u та x/u ближче до sqrt(x), ніж u. Тому, почавши з будь-якого „близького” початкового значення u(0), можна поступово поліпшувати наближення: u(n+1) := ( u(n) + x / u(n) ) / 2 доти, поки не буде виконуватися умова |u(n)- x / u(n)| < eps.

Даний тип алгоритмів має ще одну назву – „скупі” алгоритми. На кожній окремій стадії „скупий” алгоритм вибирає той варіант, який є локально оптимальним в тому чи іншому змісті. Раніше вже були розглянуті різні „скупі” алгоритми – алгоритм побудови найкоротшого шляху Дейкестри і алгоритм побудови стовбурного дерева мінімальної вартості Крускала. Алгоритм найкоротшого шляху Дейкестри є „скупим” у тому розумінні, що він вибирає вершину, найближчу до джерела, серед тих, найкоротший шлях яких ще невідомий. Алгоритм Крускала також „скупий” – він вибирає із ребер, які залишилися і не створюють цикл, ребро з мінімальною вартістю.

Потрібно зауважити, що не кожний „скупий” алгоритм дозволяє отримати оптимальний результат в цілому. Як це буває у житті, „скупа стратегія” у більшості випадків забезпечує локальний оптимум, у той же час як в цілому результат буде неоптимальним.

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

2.4. Дерева розв’язків

Багато складних реальних задач можна змоделювати за допомогою дерев розв’язків. Кожний вузол дерева представляє один крок вирішення задачі. Кожна гілка в дереві представляє розв’язок, який веде до більш повного рішення. Листки є остаточним розв’язком. Мета полягає в тому, щоб знайти „найкращий шлях” від кореня дерева до листка при виконанні певних умов. Ці умови і значення поняття „найкращий” для шляху залежить від конкретної задачі.

Стратегію настільних ігор, таких як шахи, шашки, або „хрестики-нулики” можна змоделювати за допомогою дерев гри. Якщо в який-небудь момент гри існує 30 можливих ходів, то відповідний вузол у дереві гри матиме 30 гілок. Наприклад, для гри в „хрестики-нулики” кореневий вузол відповідає початковій позиції, при якій дошка порожня. Перший гравець може помістити хрестик в будь-яку з дев’яти кліток дошки. Кожному з цих дев’яти можливих ходів відповідає гілка дерева, яка виходить з кореня. Дев’ять вузлів на кінці цих гілок відповідають дев’яти різним позиціям після першого ходу гравця.

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

Як можна здогадатися, дерево гри навіть для такої простої гри росте дуже швидко. Якщо воно буде продовжувати рости таким чином, що кожний наступний вузол в дереві матиме на одну гілку менше попереднього, то повне дерево гри матиме 9! = 362880 листки. Тобто, в дереві буде 362880 можливих шляхів розв’язку, які відповідають можливим варіантам гри.

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

Після вилучення всіх неможливих вузлів в дереві залишається біля четверті мільйона листків. Це все ще дуже велике дерево, і пошук у ньому оптимального розв’язку методом повного перебору займає достатньо багато часу. Можна ще скоротити розмір цього дерева, враховуючи симетричність деяких позиція, але це підходить лише для конкретної гри. Для складніших ігор, таких як шашки, шахи або го, дерева мають величезний розмір. Якби під час кожного ходу в шахах гравець мав би 16 можливих варіантів, то дерево гри мало б більше трильйона вузлів після п’яти ходів кожного з гравців.

2.5. Програмування з поверненнями назад

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

2.6. Евристичні алгоритми

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

Наприклад, в шахах звичайною евристикою є „посилення переваги”. Якщо у супротивника менше сильних фігур і однакова кількість інших, то слід йти на розмін при кожній нагоді. Зменшення кількості фігур робить дерево рішень коротшим і може збільшити відносну перевагу. Ця стратегія не гарантує виграшу, але підвищує його вірогідність.

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

Якщо якість рішення не так важлива, то прийнятним може бути результат, отриманий за допомогою евристики. В деяких випадках точність вхідних даних може бути недостатньою. Тоді хороше евристичне рішення може бути таким же правильним, як і теоретично „якнайкраще рішення”.

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

Отже, евристичні алгоритми – це алгоритми, які мають такі властивості:

· Вони дозволяють знайти добрі, хоча і не завжди найкращі розв’язки з усіх, що існують.

· Метод пошуку або побудови розв’язку звичайно значно простіший, ніж той що гарантує оптимальність розв’язку.

Поняття „добрий розв’язок” змінюється від задачі до задачі, тому його важко визначити точно. Припустимість використання евристики залежить від співвідношення часу та складності пошуку розв’язку обома способами та співвідношення якості обох розв’язків.

У цьому розумінні усі умови, що висуваються до розв’язку, звичайно ділять на дві групи щодо витрат праці:

· ті, які легко задовольнити;

· ті, що вимагають великої роботи.

З іншої сторони, вони поділяються на такі групи щодо їхньої важливості для кінцевої якості:

· ті, які обов’язково слід задовольнити;

· ті, що можуть бути послаблені або змінені.

Цю ситуацію образно показано в таблиці

1 2
a Слід задовольнити ?
b ? Варто відмовитися

Повернемося до нашого прикладу – задачі про мандрівного крамаря. Якщо міст, про які йдеться – багато, то пошук точно мінімального за довжиною циклу може вимагати дуже багато часу. З іншої сторони, об’їзд слід зробити лише один раз. Якщо витрати на пошук оптимального маршруту можуть виявитися більшими або еквівалентними до витрат на пальне під час подорожі, то, можливо, варто просто рушати в путь, прямуючи до найближчого міста кожного разу.

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

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

Частіше за все евристичні алгоритми базуються на методі сходження або на методі частинних цілей.

Посилання на оригінал статті - http://pzas11.at.ua/blog/lekciji_z_disciplini_quot_algoritmi_ta_strukturi_danikh_quot/2010-11-11-72

Детальнішу версію статті можна скачати за посиланням внизу.

Кiлькiсть переглядiв: 21186