Рубрика «алгоритм Прима»

в 7:16, , рубрики: алгоритм Прима, Алгоритмы, графы, матрица смежности, минимальное остовное дерево

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

Начальные термины

  • Граф — это структура данных в которой хранятся вершины и связи между ними. Удобнее всего представлять графы в виде матрицы смежности.

  • Матрица смежности — эта квадратная матрица, размер матрицы равен количеству вершин в графе. В ней хранится информация о соседях вершин графа.

  • Минимальное остовное деревоЧитать полностью »

в 5:40, , рубрики: postgresql, sql, sql tips and tricks, алгоритм Прима, Алгоритмы, Блог компании Тензор, Занимательные задачки, лабиринтостроительство
Пример сгенерированного дерева для лабиринта 21x21
Пример сгенерированного дерева для лабиринта 21x21

SQL является мощным инструментом для обработки множеств, а функционал PostgreSQL позволяет делать многие вещи еще проще, поэтому идеально подходит для реализации некоторых алгоритмов на графах.

Читать полностью »

в 6:33, , рубрики: алгоритм Прима, Алгоритмы, генерация лабиринтов, клеточные автоматы, пещеры, процедурная генерация карт, разработка игр

Использование алгоритма Прима для генерации соединённых друг с другом пещер - 1 Использование алгоритма Прима для генерации соединённых друг с другом пещер - 2 Использование алгоритма Прима для генерации соединённых друг с другом пещер - 3

Я решил объяснить один из алгоритмов генерации карты, используемых в моей игре In the House of Silence. Главное преимущество этого способа заключается в том, что в отличие от других алгоритмов, он никаким образом не может сгенерировать карту с разделёнными частями.

Генерация идеального лабиринта

Использование алгоритма Прима для генерации соединённых друг с другом пещер - 4

Как понятно из названия, я использую хорошо задокументированный рандомизированный алгоритм Прима. Описание этого алгоритма можно найти на Википедии, однако вы можете применить любой другой алгоритм генерации лабиринтов.

Для понятности я привёл псевдокод, описывающий алгоритм Прима. Будет довольно просто приспособить его под любой язык программирования.
Читать полностью »

в 6:07, , рубрики: astar, Julia, алгоритм Прима, Лабиринты, ненормальное программирование, олимпиадные задачи, поиск в глубину, Программирование, Спортивное программирование

Джулия в лабиринте - 1

Разбирая одну олимпиадную задачу мы отправимся по петляющим коридорам генерации лабиринтов и их прохождения, а также увидим, что на языке Julia простота реализаций алгоритмов граничит с их псевдокодом.

Читать полностью »

в 12:31, , рубрики: 30 строк js, javascript, алгоритм Прима, Алгоритмы, Лабиринт, ненормальное программирование, метки:

Начитавшись статей про [все что угодно] на JavaScript в 30 строк кода, я подумал: чем я хуже? Не найдя в перечне своих недостатков пункт «написание плохого кода», решил сделать что-нибудь интересное.

Лабиринты всегда веяли в мою сторону некоторой магией и загадками, поэтому поиск «чего-нибудь интересного» закончился достаточно быстро. К сожалению, создание игры затянулось на долгие часы экспериментов над консолью и моими нервами.

Изначально, осознавая размеры праведного гнева адептов непорочного программирования, я не планировал публиковать свои труды, но после того, как игра понравилась коту, паре друзей и моему самолюбию — решил написать статью (благо в нее можно внедрить теоретическую часть).

Для сторонников принципа «меньше знаешь — крепче спишь» предлагается cсылка на JSFiddle (управление стрелочками).
Читать полностью »

Главная   |  Архив новостей  |   Android  |   Google  |   Apple  |   Microsoft  |   Информационная безопасность  |   Веб – разработка
Публикации RSS  |  Комментарии RSS
https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js