Знаходження відстані між двома точками

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

Графічне представлення алгоритму знаходження довжини відрізка

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

Читати повністю

Знаходження суми цифр цілого додатнього числа

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

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

Далі, даний алгоритм реалізуємо у вигляді delphi-програми. Для цього, запустимо середовище програмування Delphi, створимо новий delphi-проект і на головній формі розмістимо два компоненти типу TEdit та один типу TButton.

Читати повністю

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

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

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

  1. Метод редукції рядків та колонок.
  2. Метод осереднених коефіцієнтів.
  3. Метод Монте-Карло.
  4. Метод найближчого сусіда.

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

Читати повністю

Рішення задачі комівояжера методом найближчого сусіда в середовищі програмування delphi

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

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

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

Читати повністю

Знаходження ровз'язку задачі комівояжера методом найближчого сусіда

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

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

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

Читати повністю

Знаходження значення похідної функції в точці засобами delphi

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

Читати повністю

Обчислення наближеного значення похідної функції в точці

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

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

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

Читати повністю

Наступна сторінка »