Учитывая набор 256 цветов, я хочу создать 16 x 16 палитру из этих цветов, где сумма всех 4-связанных различий между цветами минимальна. Конечно, есть 256! разные договоренности, поэтому грубая сила не рассматривается.
Я попытался использовать жадный алгоритм, где я начинаю с цвета, ближайшего к черному, и продолжаю движение по зигзагообразной диагонали через сетку 16x16, вставляя ближайший неиспользованный цвет к уже вставленному одному или двум соседям. В результате получилась следующая (грязная) палитра:
Я использовал перцептуальную разницу с дешевым приближением с использованием RGB . Конечно, алгоритм должен быть одинаковым независимо от разницы метрики.
Я предполагаю, что оптимальное решение (по крайней мере) является NP-сложным (я не уверен, как будет работать верификатор NP, поэтому, возможно, эта проблема даже не в NP). Если нет, дайте мне знать. В противном случае приемлемы хорошие эвристические решения.