powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритмы. Оптимизация наборов красок при печати
7 сообщений из 82, страница 4 из 4
Алгоритмы. Оптимизация наборов красок при печати
    #38711421
Фотография vmag
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
S.G.,

На самом деле в его алгоритме никогда не будет затыков, хоть оттуда иди, хоть отсюда, ибо он сначала засовывает в обойму одну из картинок (грубо говоря), а потом добивает обойму до 30 за счет добавления других картинок, по этому самый плохой исход - это печать в конце по одной картинке, но все равно без затыков... а оптимальным решением как раз будет правильный выбор сразу всех оптимальных узлов вектора, а не подбор оттуда или отсюда, но пока никто не смог эту задачу приблизить к какой-то типовой задаче с готовым оптимальным алгоритмом решения...
...
Рейтинг: 0 / 0
Алгоритмы. Оптимизация наборов красок при печати
    #38711633
Фотография S.G.
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
vmag по этому самый плохой исход - это печать в конце по одной картинке, но все равно без затыков... Именно это я и называю "затыком", когда в конце выполнения алгоритма, останутся несколько (много) картинок, с совершенно несовпадающими палитрами. Поэтому считаю, что начиная с картинок с большой палитрой, этого можно будет избежать. Но, к сожалению, доказать не могу (да и не собираюсь), назовем это интуицией ;)

vmag но пока никто не смог эту задачу приблизить к какой-то типовой задаче с готовым оптимальным алгоритмом решения...ну это уж сам автор, пусть попробует пару-тройку алгоритмов, погоняет на разных данных..
...
Рейтинг: 0 / 0
Алгоритмы. Оптимизация наборов красок при печати
    #38711685
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
S.G.Именно это я и называю "затыком", когда в конце выполнения алгоритма, останутся несколько (много) картинок, с совершенно несовпадающими палитрами. Поэтому считаю, что начиная с картинок с большой палитрой, этого можно будет избежать.
Не приходило ли Вам в голову, что одну и ту же последовательность картинок можно печатать и "он начала к концу", и "от конца к началу"? И что вопрос выбора "вначале много цветов или мало" по сути сводится к вопросу того или иного переворота этой последовательности?
...
Рейтинг: 0 / 0
Алгоритмы. Оптимизация наборов красок при печати
    #38811956
Ибн Хоттаб
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Можно написать метаэвристику, в которой пространством решений будет пространство всех возможных перестановок последовательности картинок, целевая функция будет имитировать процесс печати/перезарядки, а возвращать количество перезарядок. Какой именно алгоритм использовать - без разницы. Решение в любом случае будет достаточно неплохим. О решении этой задачи к оптимальности можете просто забыть, она NP-hard (частный случай Partition problem), при таком количестве переменных как у вас решить ее нереально.
...
Рейтинг: 0 / 0
Алгоритмы. Оптимизация наборов красок при печати
    #38827206
anvano
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Я тут наткнулся на подробное описание Bin Packing Problem
http://www.or.deis.unibo.it/kp/Chapter8.pdf

И на весьма интересное описание генетического алгоритма оптимизации в приложении к этой проблеме.
http://www.codeproject.com/Articles/633133/ga-bin-packing

Понятно, что у меня не совсем чистая Bin Packing Problem, но есть очень много общего и можно попытаться натянуть сову на глобус и закодить этот генетический алгоритм. Вдруг чего выгорит :)
...
Рейтинг: 0 / 0
Алгоритмы. Оптимизация наборов красок при печати
    #38828325
Фотография S.G.
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
anvano закодить Только возьмите компилируемый язык.
Скрипты для комбинаторных задач - не совсем то ;)
...
Рейтинг: 0 / 0
Алгоритмы. Оптимизация наборов красок при печати
    #38828710
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
anvanoИ на весьма интересное описание генетического алгоритма оптимизации в приложении к этой проблеме.
http://www.codeproject.com/Articles/633133/ga-bin-packing

Понятно, что у меня не совсем чистая Bin Packing Problem, но есть очень много общего и можно попытаться натянуть сову на глобус и закодить этот генетический алгоритм. Вдруг чего выгорит :)
Генетический алгоритм это вобщем-то даже не алгоритм а подход. К задачам поисков оптимальностей.
И выхлоп его будет зависеть от правильности оценочной формулы. И эта формула лежит не в ГА а в твоей
задаче. Ты сам должен разаработать оценку пригодности или непригодности кандидатов.
...
Рейтинг: 0 / 0
7 сообщений из 82, страница 4 из 4
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритмы. Оптимизация наборов красок при печати
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]