Выпуск №6 (Май)
XLIV Международная научно-практическая конференция «Актуальные проблемы современной науки», 30.10.2019 (Совместная конференция с Международным научным центром развития науки и технологий)

XLIІI Международная научно-практическая конференция «Актуальные проблемы современной науки», 29.08.2019 (Совместная конференция с Международным научным центром развития науки и технологий)

XLIІI Международная научно-практическая конференция «Актуальные проблемы современной науки», 30.07.2019 (Совместная конференция с Международным научным центром развития науки и технологий)

XLII Международная научно-практическая конференция «Актуальные проблемы современной науки», 27.06.2019 (Совместная конференция с Международным научным центром развития науки и технологий)

XLI Международная научно-практическая конференция «Актуальные проблемы современной науки», 30.05.2019 (Совместная конференция с Международным научным центром развития науки и технологий)

XL Международная научно-практическая конференция «Актуальные проблемы современной науки», 28.03.2019 (Совместная конференция с Международным научным центром развития науки и технологий)

МНПК "Цифровая трансформация и инновации в экономике, праве, государственном управлении, науке и образовательных процессах", 18-21.03.2019

XXXIX Международная научно-практическая конференция «Актуальные проблемы современной науки», 27.02.2019 (Совместная конференция с Международным научным центром развития науки и технологий)

XIII Международная научно-практическая конференция «Научный диспут: вопросы экономики и финансов», 31.01.2019 (Совместная конференция с Финансово-экономическим научным советом)

XXXVIII Международная научно-практическая конференция «Актуальные проблемы современной науки», 30.01.2019 (Совместная конференция с Международным научным центром развития науки и технологий)

XXXVІI Международная научно-практическая конференция: "Актуальные проблемы современной науки", 28.12.2018 (Совместная конференция с Международным научным центром)

XXXVI Международная научно-практическая конференция: "Актуальные проблемы современной науки", 29.11.2018 (Совместная конференция с Международным научным центром)

XIII Международная научно-практическая конференция «Актуальные проблемы экономики и финансов», 31.10.2018 (Совместная конференция с Финансово-экономическим научным советом)

XXXV Международная научно-практическая конференция: "Актуальные проблемы современной науки", 30.10.2018 (Совместная конференция с Международным научным центром)

XXXIV Международная научно-практическая конференция: "Актуальные проблемы современной науки", 28.09.2018 (Совместная конференция с Международным научным центром)

ХXXIII Международная научно-практическая конференция: "Актуальные проблемы современной науки", 30.08.2018 (Совместная конференция с Международным научным центром)

ХXXII Международная научно-практическая конференция: "Актуальные проблемы современной науки", 31.07.2018 (Совместная конференция с Международным научным центром)

XII Международная научно-практическая конференция «Актуальные проблемы экономики и финансов», 31.07.2018 (Совместная конференция с Финансово-экономическим научным советом)

ХXXI Международная научно-практическая конференция: "Актуальные проблемы современной науки", 29.06.2018 (Совместная конференция с Международным научным центром)

ХІ Международная научно-практическая конференция «Глобальные проблемы экономики и финансов», 31.05.2018 (Совместная конференция с Финансово-экономическим научным советом)

XXХ Международная научно-практическая конференция: "Актуальные проблемы современной науки", 30.05.2018 (Совместная конференция с Международным научным центром)

XXIХ Международная научно-практическая конференция: "Актуальные проблемы современной науки", 30.04.2018 (Совместная конференция с Международным научным центром)

ХХVIІІ Международная научно-практическая конференция: "Актуальные проблемы современной науки", 29.03.2018 (Совместная конференция с Международным научным центром)

ІІІ МНПК "Экономика, финансы и управление в XXI веке: анализ тенденций и перспективы развития", 19-22.03.2018 (Совместная конференция с Финансово-экономическим научным советом)

X Международная научно-практическая конференция «Глобальные проблемы экономики и финансов», 28.02.2018 (Совместная конференция с Финансово-экономическим научным советом)

ХХVІІ Международная научно-практическая конференция: "Актуальные проблемы современной науки", 27.02.2018 (Совместная конференция с Международным научным центром)

ХХVІ Международная научно-практическая конференция: "Актуальные проблемы современной науки", 30.01.2018 (Совместная конференция с Международным научным центром)

XІІ Международная научно-практическая конференция «Научный диспут: вопросы экономики и финансов», 29.12.2017 (Совместная конференция с Финансово-экономическим научным советом)

ХХV Международная научно-практическая конференция: "Актуальные проблемы современной науки", 28.12.2017 (Совместная конференция с Международным научным центром)

ХХІV Международная научно-практическая конференция: "Актуальные проблемы современной науки", 29.11.2017 (Совместная конференция с Международным научным центром)

XI Международная научно-практическая конференция «Актуальные проблемы экономики и финансов», 31.10.2017 (Совместная конференция с Финансово-экономическим научным советом)

XІ Международная научно-практическая конференция «Научный диспут: вопросы экономики и финансов», 29.09.2017 (Совместная конференция с Финансово-экономическим научным советом)

ХХIІІ Международная научно-практическая конференция: "Актуальные проблемы современной науки", 28.09.2017 (Совместная конференция с Международным научным центром)

X Международная научно-практическая конференция «Актуальные проблемы экономики и финансов», 31.07.2017 (Совместная конференция с Финансово-экономическим научным советом)

ХXII Международная научно-практическая конференция: "Актуальные проблемы современной науки", 28.07.2017 (Совместная конференция с Международным научным центром)

ХXI Международная научно-практическая конференция: "Актуальные проблемы современной науки", 29.06.2017 (Совместная конференция с Международным научным центром)

IX Международная научно-практическая конференция «Глобальные проблемы экономики и финансов», 31.05.2017 (Совместная конференция с Финансово-экономическим научным советом)

ХX Международная научно-практическая конференция: "Актуальные проблемы современной науки", 30.05.2017 (Совместная конференция с Международным научным центром)

"Тенденции развития национальных экономик: экономическое и правовое измерение" 18-19.05.2017 (Совместная конференция с Финансово-экономическим научным советом и ККИБиП)

ХIX Международная научно-практическая конференция: "Актуальные проблемы современной науки", 27.04.2017 (Совместная конференция с Международным научным центром)

IX Международная научно-практическая конференция "Научный диспут: вопросы экономики и финансов", 31.03.2017 (Совместная конференция с Финансово-экономическим научным советом)

ХVIII Международная научно-практическая конференция: "Актуальные проблемы современной науки", 30.03.2017 (Совместная конференция с Международным научным центром)

МНПК "Экономика, финансы и управление в XXI веке: анализ тенденций и перспективы развития", 20–23.03.2017 (Совместная конференция с Финансово-экономическим научным советом)

VIII Международная научно-практическая конференция "Глобальные проблемы экономики и финансов", 28.02.2017 (Совместная конференция с Финансово-экономическим научным советом)

ХVII Международная научно-практическая конференция: "Актуальные проблемы современной науки", 27.02.2017 (Совместная конференция с Международным научным центром)

VIII Международная научно-практическая конференция "Актуальные проблемы экономики и финансов", 31.01.2017 (Совместная конференция с Финансово-экономическим научным советом)

ХVI Международная научно-практическая конференция: "Актуальные проблемы современной науки", 30.01.2017 (Совместная конференция с Международным научным центром)

ХV Международная научно-практическая конференция: "Актуальные проблемы современной науки", 28.12.2016 (Совместная конференция с Международным научным центром)

VIII Международная научно-практическая конференция "Научный диспут: вопросы экономики и финансов", 28.12.2016 (Совместная конференция с Финансово-экономическим научным советом)

VII Международная научно-практическая конференция "Глобальные проблемы экономики и финансов", 30.11.2016 (Совместная конференция с Финансово-экономическим научным советом)

ХІV Международная научно-практическая конференция: "Актуальные проблемы современной науки", 29.11.2016 (Совместная конференция с Международным научным центром)

VII Международная научно-практическая конференция "Актуальные проблемы экономики и финансов", 31.10.2016 (Совместная конференция с Финансово-экономическим научным советом)

ХІІІ Международная научно-практическая конференция: "Актуальные проблемы современной науки", 28.10.2016 (Совместная конференция с Международным научным центром)

VII Международная научно-практическая конф. «Научный диспут: вопросы экономики и финансов», 30.09.2016 (Совместная конференция с Финансово-экономическим научным советом)

ХІІ Международная научно-практическая конференция: "Актуальные проблемы современной науки", 29.09.2016 (Совместная конференция с Международным научным центром)

XI Международная научно-практическая конференция «Актуальные проблемы современной науки», 30.08.2016 (Совместная конференция с Международным научным центром)

ІV Международная научно-практическая конф. "Экономика и управление в XXI веке: анализ тенденций и перспектив развития", 29.07.2016 (Совместная конференция с Финансово-экономическим научным советом)

X Международная научно-практическая конференция "Актуальные проблемы современной науки", 28.07.2016 (Совместная конференция с Международным научным центром)

VІ Международная научно-практическая конференция "Актуальные проблемы экономики и финансов", 30.06.2016 (Совместная конференция с Финансово-экономическим научным советом)

ІX Международная научно-практическая конференция "Актуальные проблемы современной науки", 29.06.2016 (Совместная конференция с Международным научным центром)

VI Международная научно-практическая конференция "Научный диспут: вопросы экономики и финансов", 31.05.2016 (Совместная конференция с Финансово-экономическим научным советом)

VIIІ Международная научно-практическая конференция "Актуальные проблемы современной науки", 30.05.2016 (Совместная конференция с Международным научным центром)

V Международная научно-практическая конференция "Глобальные проблемы экономики и финансов", 29.04.2016 (Совместная конференция с Финансово-экономическим научным советом)

VIІ Международная научно-практическая конференция "Актуальные проблемы современной науки", 28.04.2016 (Совместная конференция с Международным научным центром)

VІ Международная научно-практическая конференция "Актуальные проблемы современной науки", 31.03.2016 (Совместная конференция с Международным научным центром)

ІI Международная научно-практическая конф. "Экономика и управление в XXI веке: анализ тенденций и перспектив развития", 30.03.2016 (Совместная конференция с Финансово-экономическим научным советом)

V Международная научно-практическая конференция "Актуальные проблемы экономики и финансов", 21-24.03.2016 (Совместная конференция с Финансово-экономическим научным советом)

V Международная научно-практическая конференция "Научный диспут: вопросы экономики и финансов", 26.02.2016 (Совместная конференция с Финансово-экономическим научным советом)

II Международная научно-практическая конференция: "Научный диспут: актуальные вопросы медицины" 20.02.2016 (Совместная конференция с Международным научным центром)

ІV Международная научно-практическая конференция "Актуальные проблемы современной науки", 29.12.2015 (Совместная конференция с Международным научным центром)

IV Международная научно-практическая конференция "Глобальные проблемы экономики и финансов", 28.12.2015 (Совместная конференция с Финансово-экономическим научным советом)

IV Международная научно-практическая конференция "Актуальные проблемы экономики и финансов", 30.11.2015 (Совместная конференция с Финансово-экономическим научным советом)

IV Международная научно-практическая конференция "Научный диспут: вопросы экономики и финансов", 29.10.2015 (Совместная конференция с Финансово-экономическим научным советом)

Международная научно-практическая конференция: "Научный диспут: актуальные вопросы медицины" 28.10.2015 (Совместная конференция с Международным научным центром)

III Международная научно-практическая конференция "Глобальные проблемы экономики и финансов", 30.09.2015 (Совместная конференция с Финансово-экономическим научным советом)

III Международная научно-практическая конференция "Актуальные проблемы экономики и финансов", 31.08.2015 (Совместная конференция с Финансово-экономическим научным советом)

ІІІ Международная научно-практическая конференция "Научный диспут: вопросы экономики и финансов", 30.06.2015 (Совместная конференция с Финансово-экономическим научным советом)

ІІ Международная научно-практическая конференция "Актуальные проблемы современной науки", 29.06.2015 (Совместная конференция с Международным научным центром)

II Международная научно-практическая конференция "Глобальные проблемы экономики и финансов", 28.05.2015 (Совместная конференция с Финансово-экономическим научным советом)

Актуальные проблемы экономики и финансов, 29.04.2015 (Совместная конференция с Финансово-экономическим научным советом)

Научный диспут: вопросы экономики и финансов, 31.03.2015 (Совместная конференция с Финансово-экономическим научным советом)

Актуальные проблемы современной науки, 27.03.2015 (Совместная конференция с Международным научным центром)

Глобальные проблемы экономики и финансов, 27.02.2015 (Совместная конференция с финансово-экономическим научным советом)



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

Ключевые слова: случайная карта, лабиринт, бионический метод.


Отрасль науки: Технические науки
Скачать статью (pdf)

Технічні науки

УДК 004.942     

Соболь Єгор Ігорович

магістрант кафедри ПМІ, ДонНТУ

Дмитрієва Ольга Анатолівна

зав. кафедри прикладної математики,

д.т.н., ДонНТУ

Соболь Егор Игоревич

магистрант кафедры ПМИ, ДонНТУ

Дмитриева Ольга Анатольевна

зав. кафедры прикладной математики,

д.т.н., ДонНТУ

Sobol Y.

undergraduate of AMI, DonNTU

Dmitrieva O.

Head Department of Applied Mathematics,

 Ph.D., DonNTU

ПОРІВНЯЛЬНИЙ АНАЛІЗ АЛГОРИТМІВ ФОРМУВАННЯ ВИПАДКОВИХ КАРТ

СРАВНИТЕЛЬНЫЙ АНАЛИЗ АЛГОРИТМОВ ФОРМИРОВАНИЯ СЛУЧАЙНЫХ КАРТ

COMPARATIVE ANALYSIS OF THE ALGORITHMS FOR GENERATING RANDOM MAPS

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

Ключові слова: випадкова карта, лабіринт, біонічний метод.

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

Ключевые слова: случайная карта, лабиринт, бионический метод.

Summary. A comparative analysis of selected bionic and procedural methods for generating random maps is carried out.

Keywords: random map, labyrinth, bionic method.

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

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

  1. Розпочати з сіткою, заповненої стінами.
  2. Обрати клітину, помітити її як частину лабіринту. Додати стіни клітини до списку стін.
  3. Доки список стін не порожній:
    • вибрати випадкову стіну зі списку. Якщо тільки одна з клітин, які стіна розділяє, переглянута, тоді: зробити стіну проходом і позначити не відвідувану клітку як частину лабіринту;додати стіни поміченої клітини до списку стін;
    • видалити стіну зі списку

У якості альтернативи для процедурного підходу запропоновано модифікацію методу диференціальної еволюції[3]. У його базовому вигляді алгоритм можна описати таким чином. Спочатку генерується деяка множина векторів, так зване покоління. На кожній ітерації алгоритм генерує нове покоління векторів, випадковим чином комбінуючи вектори з попереднього покоління. Число векторів в кожному поколінні одне й те саме і є одним з параметрів методу. Нове покоління векторів генерується в такий спосіб. Для кожного вектора x i {\displaystyle x_{i}} xi зі старого покоління вибираються три різних випадкових вектори v 1 {\displaystyle v_{1}} v1, v 2 {\displaystyle v_{2}} v2, v 3 {\displaystyle v_{3}} v3 серед векторів старого покоління, за винятком самого вектора x i {\displaystyle x_{i}} xi, і генерується так званий мутантний вектор за формулою(1)

                                        (1)

де F {\displaystyle F} F - один з параметрів методу, позитивна дійсна константа в інтервалі [0, 2].

Над мутантним вектором v {\displaystyle v} v виконується операція «схрещування», яка полягає в тому, що деякі його координати заміщаються відповідними координатами з початкового вектора x i {\displaystyle x_{i}} xi (кожна координата заміщається з деякою ймовірністю, яка також є ще одним з параметрів цього методу). Отриманий після схрещування вектор називається пробним вектором. Якщо він виявляється кращим за вектор x i {\displaystyle x_{i}} xi (тобто значення цільової функції стало меншим), то в новому поколінні вектор x i {\displaystyle x_{i}} xi замінюється на пробний вектор, а в іншому разі — залишаєтьсяx i {\displaystyle x_{i}} .

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

Формула отримання нового нащадка (2) виглядає наступним чином

                   (2)

де m – результуюча матриця;

m1, m2, m3, m4 – матриці-предки;

С2– функція вторинного схрещування;

С1–функція первинного схрещування.

Функція первинного схрещування повертає матрицю m2, яка заповнюється наступним чином:

(3)

де F є одним з параметрів методу, що відповідає за ймовірність первинного схрещування, приймає значення від 0,0 до 1,0.

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

                                      (4)

де Cr відповідає за вірогідність вторинної передачі генів, і приймаючим значення від 0,1 до 0,9.

Також важливими параметрами методу є:

W - щільність заповнення нульового покоління карт стінами;

N - кількість поколінь метода диференціальної еволюції.

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

Порівняння результатів роботи алгоритмів

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

         D1, де W= 0.4, C1 = 0.5, C2 = 0.5, N = 500

         D2, де W = 0.4, C1 = 0.7, C2 = 0.55, N = 500.

Рисунок 1 - Результати роботи алгоритмів

Висновки

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

Перелік літератури:

  1. Мозговой М. Занимательное программирование: Самоучитель / Мозговой М. // СПб: Питер, 2004. — 208 с. — ISBN 5-94723-853-5.
  2. Pettie, S. An optimal minimum spanning tree algorithm / S. Pettie, V. Ramachandran // Journal of the ACM. – 2000. – Vol 1. –  P. 16–34.
  3. StornR.Differential Evolution A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces / R. Storn, K. Price // Journal of Global Optimization. – Vol. 11,№ 4. – 1997. –P.341-359.