Побудова дерева обходу в ширину в середовищі програмування delphi

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

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

Пошук в ширину на delphi

Головне вікно проекту "Побудова дерева обходу в ширину для неорієнтованого графа"

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

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

Побудова дерева обходу в глибину в середовищі програмування delphi

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

Головна форма розглядуваного delphi-проекту ділиться на дві частини і складається з панелі інструментів  та графічного редактора. Розглянемо призначення кожної з них більш детально.

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

Знаходження найкоротших маршрутів від першої до всіх інших вершин в орієнтованому графі

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

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

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

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

Знаходження найкоротшого шляху між двома вершинами в орієнтованому графі використовуючи алгоритм Дейкстри

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

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

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

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

Програмна реалізація методу подвійного обходу в середовищі delphi

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

« Попередня сторінкаНаступна сторінка »