Как стать автором
Обновить
78
10
Владислав @rebuilder

Разработчик

Отправить сообщение

Коммивояжер на GPU

Уровень сложностиСредний
Время на прочтение8 мин
Количество просмотров3.4K

Мы уже решали задачу коммивояжёра точно методом динамического программирования. С тех пор прошло немало времени. Мне бы хотелось поделиться некоторыми соображениями по улучшению алгоритма, а также представить алгоритм пригодный для расчёта задачи коммивояжера на GPU.

Динамическое программирование — это метод решения сложных задач путём разбиения их на более мелкие подзадачи, решение которых легче и проще.

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

Читать далее
Всего голосов 7: ↑7 и ↓0+10
Комментарии20

Задача о сумме подмножеств

Уровень сложностиСредний
Время на прочтение6 мин
Количество просмотров7.3K

Задача о сумме подмножеств в общей формулировке звучит так:

Существует множество S чисел, вопрос состоит в том, будет ли сумма некоторого подмножества от S равна заданному числу Т.

Известно, что данная задача NP-полная.

Мы будем решать эквивалентную задачу, где все числа являются натуральными.

Частным случаем задачи о сумме подмножеств является задача разбиения множества чисел:

Множество чисел S необходимо разбить на два подмножества S1 и S2, где сумма S1 равна сумме S2.

(От задачи о сумме подмножеств текущая отличается только тем, что T = SUM(S1) / 2 = SUM(S2) / 2)

Хочу предложить вам простой и элегантный способ относительно быстрого решения обеих задач методом целочисленного линейного программирования (ЦЛП). Мы получим не только точный ответ на вопрос, но и найдём искомое подмножество.

Читать далее
Всего голосов 5: ↑4 и ↓1+4
Комментарии84

Коммивояжёр за полином*

Уровень сложностиСложный
Время на прочтение12 мин
Количество просмотров4.2K

Если вам нужно решить задачу коммивояжёра, то нет ничего проще. Нужно просто взять квантовый компьютер с числом кубитов не меньшим числа вершин рассчитываемого графа…

Нет под рукой квантового компьютера? Не беда, читайте дальше и узнаете, как можно решать данную задачу на классическом компьютере за полиномиальное время* от числа вершин.

Читать далее
Всего голосов 14: ↑12 и ↓2+12
Комментарии38

Задача коммивояжёра — ещё немного больше, ещё немного быстрее

Уровень сложностиСредний
Время на прочтение16 мин
Количество просмотров7.9K

И снова здравствуйте, уважаемые читатели Хабра. Мы продолжаем наше путешествие в мир алгоритмов поиска оптимального пути.

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

Читать далее
Всего голосов 23: ↑23 и ↓0+23
Комментарии1

Задача коммивояжера (TSP) точное решение — метод целочисленного линейного программирования (Integer programming)

Время на прочтение20 мин
Количество просмотров23K

Дочитав эту статью до конца, вы сможете решать точно задачу коммивояжёра на сотню элементов за считанные секунды!

Заинтригованы? Тогда, добро пожаловать под кат.

Читать далее
Всего голосов 124: ↑124 и ↓0+124
Комментарии40

Задача коммивояжера (TSP) точное решение — метод ветвей и границ

Время на прочтение17 мин
Количество просмотров16K

Что делает код хорошим? Большинство программистов ответят: хороший код должен быть структурирован, легко читаем и понятен. Но так ли важно качество кода, если он медленный? В большинстве задач производительность кода не критична, хотя и желательна. Но есть задачи, время выполнения которых столь огромно, что выигрыш в производительности доминирует над всем остальным.

Я говорю про NP-трудные задачи (NP-трудность - недетерминированная полиномиальная трудность по времени) и на одной из данного класса хочу акцентировать ваше внимание. Задаче коммивояжера.

Мы не будем рассматривать эвристические алгоритмы, нам нужно точное решение.

Читать далее
Всего голосов 32: ↑32 и ↓0+32
Комментарии42

Задача коммивояжера (TSP) точное решение — метод динамического программирования

Время на прочтение9 мин
Количество просмотров25K

Задача коммивояжёра – одна из интереснейших подзадач комбинаторной оптимизации. Впервые мне пришлось с ней столкнуться, работая над логистической системой торгового предприятия.

Решение методом грубой силы не подходило из-за вычислительной сложности. Была предпринята попытка реализовать метод ветвления и границ с отсечением в глубину. В целом, подход себя оправдывал, но иногда при некоторых специфических входных данных алгоритм выдавал решение далёкое от оптимального.

Типичный маршрут доставки товара предприятия состоял из пары десятков точек, изредка доходящий до 25-26. Матрица расстояний рассчитывалась с помощью алгоритма Дейкстры. Дальше нужно было выбрать оптимальный маршрут из возможных.

Читать далее
Всего голосов 10: ↑10 и ↓0+10
Комментарии17

Radix sort — выжать всё

Время на прочтение19 мин
Количество просмотров22K


Приветствую всех любителей алгоритмов. Хочу Вам поведать о своих изысканиях на тему сортировок в целом и углубиться в рассмотрение radix сортировки.
Читать дальше →
Всего голосов 10: ↑10 и ↓0+10
Комментарии43

Поразрядная сортировка LSD (Radix Sort)

Время на прочтение3 мин
Количество просмотров32K


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

Хочу рассказать про свой излюбленный алгоритм для поразрядной сортировки LSD (least significant digit — сначала младший разряд) с подсчётом (Radix Sort). Классический алгоритм был несколько переосмыслен автором в сторону некоторых оптимизаций в пользу ускорения и простоты.
Читать дальше →
Всего голосов 7: ↑7 и ↓0+7
Комментарии11

Калейдоскоп как в детстве

Время на прочтение5 мин
Количество просмотров6.4K

Иногда отражение в зеркале более реально, чем сам объект…
— Льюис Кэрролл (Алиса в зазеркалье)

В юном возрасте у меня была забавная игрушка – калейдоскоп. Часами я рассматривал правильные узоры, составленные из разноцветных осколков битого стекла. Что-то завораживающее было в этом медитативном созерцании. Ныне, будучи отцом, мне захотелось показать своим чадам красоту правильных построений хаоса.

Дети сейчас модерновые, им обычные игрушки малоинтересны, им компьютер подавай или планшет. Поэтому мне захотелось воссоздать цифровой прототип варианта калейдоскопа, а заодно по практиковать свои навыки работы с компьютерной графикой.

Приглашаю и Вас окунуться со мной в мир отражений.
Читать дальше →
Всего голосов 17: ↑17 и ↓0+17
Комментарии16

Крадущийся в тени или поиски того света

Время на прочтение7 мин
Количество просмотров4.8K

Assembler – мой любимый язык, … но жизнь так коротка.

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

Зная себя, я уверен, что игра едва получит своё воплощение, но возможно кого-то из общественности заинтересуют мои наработки на этом тернистом пути. И так приступим.
Читать дальше →
Всего голосов 21: ↑19 и ↓2+17
Комментарии8

Простая логистика своими руками

Время на прочтение8 мин
Количество просмотров18K


Хочу поделиться с Вами опытом создания логистической системы на одном торговом предприятии.

Одним прекрасным днём, в не близком 2012 году, руководитель поставил задачу: подумать над проблемой оптимизации затрат на транспортную логистику организации.
Основная сфера деятельности предприятия оптовая продажа и доставка продукции, где транспортные расходы занимают весомую долю затрат.

Руководство посчитало, что пришло время, навести порядок в расходовании средств на топливо, а также были подозрения, что водители дополнительно занимаются ещё «левой» доставкой между рейсами. В предприятиях малого-среднего звена многое строится на доверии, так как держать отдельных людей для контроля накладно и не всегда целесообразно. Когда же затраты растут, а эффективность падает, то просто необходимо что-то делать.
Читать дальше →
Всего голосов 33: ↑33 и ↓0+33
Комментарии24

В поисках перспективных теней для roguelike

Время на прочтение3 мин
Количество просмотров3.9K


Уважаемые Хабровчане, представляю вашему вниманию продолжение изысканий на тему поиска подходящих теней для 2D рогалика.

Данный пост является сиквелом публикации, своеобразной работой над ошибками и дальнейшее развитие идеи.
Читать дальше →
Всего голосов 17: ↑16 и ↓1+15
Комментарии16

Реалистичные тени для roguelike

Время на прочтение4 мин
Количество просмотров9.8K
image

Доброго времени, Хабр-сообщество.

Много лет назад, натолкнулся на пост (1). Тогда меня озадачила возможность создать интересные элементы для геймплея в roguelike (2). Допустим противник может находиться за стеной, мы его не видим, пока мы не столкнёмся с ним в зоне прямой видимости. Но более мне по душе ситуация, когда мы, путешествуя по коридорам подземелья, раскрываем особенности расположения объектов постепенно на основе области видимости.
Читать дальше →
Всего голосов 42: ↑41 и ↓1+40
Комментарии26

Информация

В рейтинге
428-й
Откуда
Краснодарский край, Россия
Зарегистрирован
Активность