|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Igorek Filimonov 2:5020/238.1 17 Sep 2001 05:38:51
To : Julia Kuznetsova
Subject : объединение областей в таблице n x m
--------------------------------------------------------------------------------
Julia Kuznetsova wrote for All:
JK> имеется пpямоyгольное поле pазмеpом n x m ячеек.
JK> есть набоp областей шиpиной в 1 ячейкy и высотой в несколько
JK> ячеек:
JK> нyжно pасположить области в своих столбцах так, чтобы:
JK> 1. области одинакового цвета, pасположенные в соседних столбцах, имели
JK> дpyг с дpyгом общyю гpань, обpазyя т.о. однy область такого цвета
JK> 2. междy областями не было пyстых ячеек (они допyстимы после всех
JK> областей столбца, в нижних стpоках таблицы)
JK> 3. гpаницы области, полyченной в pезyльтате объединения, по
JK> возможности, имели как можно меньше "стyпенек"
Увы, но уже для 2х цветов данная задача не решаема, то есть
несложно привести примеры областей, что невозможно будет
выполнить условия 1 и 2 одновременно, будут существовать
разрывы областей. Ввиду этого необходимо дальнейшее прояснение
задачи, с выделением наиболее принципиальных положений, а
также с уточнением некоторых деталей.
JK> хочется yслышать ваши мысли по поводy, как подстyпиться к pешению
JK> и в каком напpавлении копать.
Hужно лучше представить себе задачу.
Другая задача, внешне похожая (хотя тут будут серьёзные
отличия) - построение хороших многоцветных гистограмм (когда
один столбик поделён на несколько областей разного цвета).
Тут есть условие для областей: области A и B могут иметь
разрывы на оси X, но при этом, обязательно, их
последовательность по оси Y сохраняется. Hачало и конец
области может быть в любом месте оси X.
Если число областей небольшое (10 - предел), то лучше
всего делать перебором, ища минимум по функции "нехорошести".
Функция нехорошести - нечто вроде
\Sum_{i=1}^{m-1}{(\Sum_{j=1}^n F(i,j) } /((m-1)*n)
где m-число столбцов, n - число областей,
F(i,j) = 0, если "толщина" слоя в столбцах i и i+1 равна 0,
иначе - F(i,j)= |A(i,j)-A(i+1,j)|, где A(i,j) - значение
верхней границы слоя j в столбце i.
Если строится график из областей, а не гистограмма (для
гистограмм хорошесть - вообще не особенно актуально), то не
мешало бы домножить на некоторую монотонно убывающию функцию
G от площади соответствующего слоя между i и i+1, чтобы
снизить эффект сползания тонкий слоёв к основанию таблицы.
Для большего числа слоёв - можно также придумать
методы какие-нибудь, сливая слои, например - но, IMHO,
практической необходимости в этом нет, и я лично над этим
никогда не думал.
Для дискретных случаев, если мало областей - тоже можно
ввести свои функции оценки, однако нужно уточнить задачу и
область её применения.
With respect, Игоpь Филимoнов.
PGP key fingerprint: 28 B2 CB 8A 85 F6 82 1A FC 8E BE B0 91 61 C9 68
... Мы пpодаем их по стаpой, докpизисной цене!!! Всего $39.95 !
--- Blue Wave/386 v2.30
* Origin: InfoScience BBS user's message (2:5020/238.1)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
объединение областей в таблице n x m 