|
|
|
Алгоритмы. Оптимизация наборов красок при печати
|
|||
|---|---|---|---|
|
#18+
S.G., На самом деле в его алгоритме никогда не будет затыков, хоть оттуда иди, хоть отсюда, ибо он сначала засовывает в обойму одну из картинок (грубо говоря), а потом добивает обойму до 30 за счет добавления других картинок, по этому самый плохой исход - это печать в конце по одной картинке, но все равно без затыков... а оптимальным решением как раз будет правильный выбор сразу всех оптимальных узлов вектора, а не подбор оттуда или отсюда, но пока никто не смог эту задачу приблизить к какой-то типовой задаче с готовым оптимальным алгоритмом решения... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.08.2014, 17:49 |
|
||
|
Алгоритмы. Оптимизация наборов красок при печати
|
|||
|---|---|---|---|
|
#18+
vmag по этому самый плохой исход - это печать в конце по одной картинке, но все равно без затыков... Именно это я и называю "затыком", когда в конце выполнения алгоритма, останутся несколько (много) картинок, с совершенно несовпадающими палитрами. Поэтому считаю, что начиная с картинок с большой палитрой, этого можно будет избежать. Но, к сожалению, доказать не могу (да и не собираюсь), назовем это интуицией ;) vmag но пока никто не смог эту задачу приблизить к какой-то типовой задаче с готовым оптимальным алгоритмом решения...ну это уж сам автор, пусть попробует пару-тройку алгоритмов, погоняет на разных данных.. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 03.08.2014, 17:21 |
|
||
|
Алгоритмы. Оптимизация наборов красок при печати
|
|||
|---|---|---|---|
|
#18+
S.G.Именно это я и называю "затыком", когда в конце выполнения алгоритма, останутся несколько (много) картинок, с совершенно несовпадающими палитрами. Поэтому считаю, что начиная с картинок с большой палитрой, этого можно будет избежать. Не приходило ли Вам в голову, что одну и ту же последовательность картинок можно печатать и "он начала к концу", и "от конца к началу"? И что вопрос выбора "вначале много цветов или мало" по сути сводится к вопросу того или иного переворота этой последовательности? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 03.08.2014, 19:22 |
|
||
|
Алгоритмы. Оптимизация наборов красок при печати
|
|||
|---|---|---|---|
|
#18+
Можно написать метаэвристику, в которой пространством решений будет пространство всех возможных перестановок последовательности картинок, целевая функция будет имитировать процесс печати/перезарядки, а возвращать количество перезарядок. Какой именно алгоритм использовать - без разницы. Решение в любом случае будет достаточно неплохим. О решении этой задачи к оптимальности можете просто забыть, она NP-hard (частный случай Partition problem), при таком количестве переменных как у вас решить ее нереально. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.11.2014, 14:29 |
|
||
|
Алгоритмы. Оптимизация наборов красок при печати
|
|||
|---|---|---|---|
|
#18+
Я тут наткнулся на подробное описание Bin Packing Problem http://www.or.deis.unibo.it/kp/Chapter8.pdf И на весьма интересное описание генетического алгоритма оптимизации в приложении к этой проблеме. http://www.codeproject.com/Articles/633133/ga-bin-packing Понятно, что у меня не совсем чистая Bin Packing Problem, но есть очень много общего и можно попытаться натянуть сову на глобус и закодить этот генетический алгоритм. Вдруг чего выгорит :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.12.2014, 01:24 |
|
||
|
Алгоритмы. Оптимизация наборов красок при печати
|
|||
|---|---|---|---|
|
#18+
anvano закодить Только возьмите компилируемый язык. Скрипты для комбинаторных задач - не совсем то ;) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.12.2014, 18:19 |
|
||
|
Алгоритмы. Оптимизация наборов красок при печати
|
|||
|---|---|---|---|
|
#18+
anvanoИ на весьма интересное описание генетического алгоритма оптимизации в приложении к этой проблеме. http://www.codeproject.com/Articles/633133/ga-bin-packing Понятно, что у меня не совсем чистая Bin Packing Problem, но есть очень много общего и можно попытаться натянуть сову на глобус и закодить этот генетический алгоритм. Вдруг чего выгорит :) Генетический алгоритм это вобщем-то даже не алгоритм а подход. К задачам поисков оптимальностей. И выхлоп его будет зависеть от правильности оценочной формулы. И эта формула лежит не в ГА а в твоей задаче. Ты сам должен разаработать оценку пригодности или непригодности кандидатов. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.12.2014, 11:16 |
|
||
|
|

start [/forum/topic.php?fid=16&gotonew=1&tid=1341142]: |
0ms |
get settings: |
8ms |
get forum list: |
19ms |
check forum access: |
3ms |
check topic access: |
3ms |
track hit: |
159ms |
get topic data: |
10ms |
get first new msg: |
6ms |
get forum data: |
2ms |
get page messages: |
46ms |
get tp. blocked users: |
1ms |
| others: | 207ms |
| total: | 464ms |

| 0 / 0 |
