Сообщение от Red white socks Рассмотрим для начала случай, когда

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

2. Оптимизацией данной задачи и есть выбор отрезков, по которым мы переходим между хордами - если выбирать проход к ближайшей вершине, то это ОЧЕНЬ далеко от оптимальности, могу нарисовать вам пример из трех хорд, но думаю, что сможете его придумать сами =)

3. Длина же 1000 хорд будет порядка 1200-1300 (4000/pi) - согласен, что при подобном расчете, процент "зеленых отрезков" выглядит очень небольшим по сравнению с общей длиной. НО наша задача оптимизировать именно сумму длинн "зеленых отрезков" и совершенно не важно, какой процент общего "пути" это составляет.
(Представьте, что мне нужно соединять золотыми проводами имеющиеся на окружности входы электронной схемы - длина пути внутри окружности вообще не имеет значения, важна только длина соединений из золота.

Кмк, задача далеко не из школьной программы =) даже не из "олимпиадных", это уровень как минимум третьего курса мехмата, да и то я вот даже закончив мехмат 30 лет назад и защитив Диплом по сходной тематике, сумел сделать только достаточно примитивную "жадину", далекую от идеальной оптимизации.

0

Сообщение от denismix могу нарисовать

А нарисуйте, это очень интересно.

0

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

denismix, если это задача из практики, то это как раз и важно. Потому что у нас уже выделено X ресурсов и надо потратить еще 0,003Х чтобы "было хорошо". Любой бюджетный контроллер быстренько завизирует это, даже не вдаваясь в подробности. Или же я вам предоставляю право объяснить почему на практике это не важно. Не стесняйтесь.
Если это абстрактная теоретическая задача, то дайте ссылку на контест.

0

Сообщение от Red white socks denismix, если это задача из практики, то это как раз и важно. Потому что у нас уже выделено X ресурсов и надо потратить еще 0,003Х чтобы "было хорошо". Любой бюджетный контроллер быстренько завизирует это, даже не вдаваясь в подробности. Или же я вам предоставляю право объяснить почему на практике это не важно. Не стесняйтесь.

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

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

=====================

Пример "не оптимального" близкого соединения.
Слева мы "вынужденно" (по вашему алгоритму) соединили А и В, т.к. они "близкие", но более оптимально было пройти по пути указанному справа.

0

Сообщение от denismix "Представьте, что мне нужно соединять золотыми проводами имеющиеся на окружности входы электронной схемы - длина пути внутри окружности вообще не имеет значения, важна только длина соединений из золота." Т.к. сэкономить мы можем только провода, соединения внутри окружности уже есть, их не сэкономишь.

Как говорил известный персонаж, "фуфло ты гонишь, начальник". Я просил рассказать про реальный пример, а не сказки.

Сообщение от denismix Слева мы "вынужденно" (по вашему алгоритму) соединили А и В, т.к. они "близкие", но более оптимально было пройти по пути указанному справа

Это не из моего алгоритма. В моем нигде не было сказано про "вынужденно" соединили А и В.

0

Сообщение от Red white socks Это не из моего алгоритма.

Тогда поясните пожалуйста, как вы предлагаете делать первичные соединения вершин графа, на которые напускать "Эйлера"?

По поводу задачи - есть многослойная нейросеть, порядка 200 слоев по 300 выходов. Ее выходы генерируют "пары" (аналог хорд окружности). Эти пары как то там соединены внутри нейросети и мы понятия не имеем как, ибо нейросеть...

На выхлопе получаются вот такие картинки - картинка состоит из прямых разноцветных линий, которые пересекаются "по честному", т.е. нет никаких разрывов, фотошопа или еще чего то подобного.

Вышеописанные "пары" это не прямой аналог концов нитей, там все э... несколько сложнее, но позволю себе воздержаться от подробного описания.
Для получения функции оптимизации (градиентного спуска), мне нужно соединить все эти пары в цепочку, длина которой должна быть минимальной.
Представление в виде окружности возникает из-за особенной "круговой" (в виде "пирога") структуры нейросетки. Т.е. на самом деле конечно же нет никакой реальной окружности, но вес соединений между "парами" является прямым аналогом "зеленых пунктирных отрезков" из моего рисунка.
Каждая эпоха выдает некоторое приближение, которое при должном умении, можно преобразовать в набор образующих картинку линий - мне нужно "зажать" решение по признаку: длина цепочки должна быть минимальной.

Сейчас функция градиентного спуска не слишком хорошая ("жадный" алгоритм, который я описал ранее) и для получения удовлетворительного результата приходится проходить очень много эпох.

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

Нафига оно мне нужно? Ну вот такое у меня хобби - делать всякие прикольные штуки =)
Искренне надеюсь, что все вышеизложенное как то поможет найти хорошую функцию для оптимизации...



Стоит добавить, что это такой вид искусства, называется "Стрингарт" - физическая картинка получается наматыванием около 5 километров тонких нитей 5-6 цветов на рамку, по контуру которой забиты гвоздики. Многим нравится, я лично наматывать нитки не люблю, но люблю решать сложные задачи по оптимизации =)

0

Сообщение от denismix Тогда поясните пожалуйста, как вы предлагаете делать первичные соединения вершин графа, на которые напускать "Эйлера"?

Читайте внимательно, я уже это говорил. Повторять 20 раз по кругу никакого желания нет.

0

Сообщение от denismix Слева мы "вынужденно" (по вашему алгоритму) соединили А и В

Как раз мои соображения должны были вывести на правый рисунок. Поскольку мы должны исследовать сумму длин n-1 дуг расположенных так, что среди них нет смежных. Это требует перебора примерно 2n случаев.

1

Сообщение от Red white socks Читайте внимательно, я уже это говорил. Повторять 20 раз по кругу никакого желания нет.

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

===================================

Сообщение от kabenyuk Поскольку мы должны исследовать сумму длин n-1 дуг расположенных так, что среди них нет смежных. Это требует перебора примерно 2n случаев.

Кмк, отсутствие "смежных" (точнее пересекающихся) дуг в оптимальном пути - ОЧЕНЬ перспективно, но требует осмысления и хотя бы "чернового" доказательства на уровне постулатов. В смысле я от вас его не требую, просто замечание для себя...
+ мне кажется, что "наборов" из-за того, что у нас есть разрывы на начало и конец будет побольше, чем 2n, но мы можем всегда объединять в замкнутый цикл и "разрывать" самое длинное "звено"...

ОГРОМНОЕ ВАМ СПАСИБО!!! Тут точно есть над чем подумать =)
"На бумажке" я не смог найти решение для 3-х и 4-х линий, опровергающее ваш постулат.

Добавлено через 5 минут
+ где то в памяти всплывает некая теорема на эту тему... нужно думать...

0

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

Сообщение от Red white socks Если множество вершин в порядке обхода по/против часовой стрелки. Рассмотрим для начала случай, когда соседние вершины не соединены ребром. Тогда взяв в многоугольнике стороны через одну мы получим дополнение до графа с эйлеровым циклом. Таких способов два, суммарная длина таких разбиений равна периметру многоугольника и не превосходит 2pi. Значит наименьшее из двух заведомо не превосходит pi.

При цитировании латех исчезает

0

0

Сообщение от denismix Для получения функции оптимизации (градиентного спуска), мне нужно соединить все эти пары в цепочку, длина которой должна быть минимальной.

Тут выходит задача оптимизации с ограничениями (задача условной оптимизации). Вполне хорошая с точки зрения гладкости функции и простоты вычисления производных (в т.ч. производных по вхождениям оптимизируемых переменных в ограничения). Но!
Градиентным спуском условную оптимизацию не щёлкнуть при записи ограничений через множители Лагранжа (ибо экстремум функции будет достигнут простым "загоном" значений этих множителей в плюс-/минус-бесконечность, т.е. решению будет пофиг на длину пути - проще будет навесить огромные по модулю коэффициенты всем либо некоторым штрафным слагаемым).
При записи ограничений в виде штрафных функций - возникнет гемор с ручным заданием/балансировкой весов весов штрафов.
Третий способ решить задачу условной оптимизации именно градиентом - был предложен в 1987г и с тех пор набрал всего 150 цитирований в научной литературе (т.е. способ остаётся неизвестным).
Метод расщепления (попеременное чередование шага безусловной градиентной оптимизации и шага удовлетворения ограничениям через проекции значений переменных, "вылетевших" за области допустимых значений, обратно на границы их областей) - не сработает из-за наличия более сложных ограничений (где будет совместное/взаимное влияние значений переменных).

Теперь по оптимизируемой функции (как бы её для такой задачи соорудил я).
Делаем 2 трёхмерные матрицы размером N*N*4.
В первую - положим вычисленные расстояния между концами отрезков (на диагональ, вернее, на N*4 элементов, ибо матрица имеет ещё и размерность "в глубину", лягут нули). Обозначим эту матрицу буквой А.
Вторая будет матрицей связей, с элементами, у которых в итоге хочется увидеть значения из {0,1}, а первоначально все они (кроме диагональных) инициализированы одинаково, значениями 1/((N-1)*4). "Диагональные" N*4 элемента - тоже нули. Обозначим эту матрицу буквой В.
Минимизируется функция

Теперь запишем ограничения для условной оптимизации. Суммарно их выходит N*N*4+N*3 штуки (не, это совсем не "ужас-ужас-ужас!"- там всё выходит легко дифференцируемым):
1) Ограничения на итоговые значения элементов матрицы B (есть соединение между концами отрезков либо нет соединения), т.е. для приведения значений к 0/1 (и просто для невыпуска значений за пределы отрезка [0,1]):
для любых i,j,k

2) Ограничения на то, чтобы в каждом "построчном" и "постолбцовом" срезе матрицы B "в глубину" - оказалась единственная единичка, т.е. единственная связь отрезка с каким-то другим:
для каждого i

и для каждого j

3) Ограничение для предотвращения возникновения единиц на диагонали B:
для всех i=j


Не гарантирую, что выше всё наиболее оптимально записал - это был просто первый шаг раздумий (вернее, с фиксацией раздумий в виде "видимых" формул). Например, мне уже лень думать над возможным упрощением описанной постановки задачи условной оптимизации через переход к наддиагональным верхним треугольным матрицам A,B (для возможности исключения последнего набора условий на нулевые диагональные элементы матрицы B, т.е. для "автоматического", просто по построению, удовлетворения требования несоединения отрезков самих с собой).

И такая постановка задачи не привязана к размещению концов отрезков на окружности - отрезки могут быть в пространстве любой размерности, и концы их могут лежать где угодно, требуется иметь только лишь возможность вычислять расстояния между концами разных отрезков.
И как написал в начале - градиентным спуском задачу оптимизации с ограничениями можно решить либо с добавочными проблемами (если запишем ограничения через штрафные слагаемые - придётся ручками настраивать веса штрафов), либо неизвестным ширнармассам способом.
Но формально постановка задачи условной оптимизации выходит вполне корректной и решаемой, проблем вроде как не вижу (в т.ч. для других способов решения, например, классически - т.е. неградиентно - через множители Лагранжа).

1

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

Добавлено через 13 минут

Сообщение от denismix Требуется запрограммировать алгоритм, который оптимизирует расстояние которое потребуется пройти между концами отрезков.

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

Как вариант вообще убрать зеленые отрезки, будет сразу минимум нити. Искать такое положение черных чтобы был максимум покрытия растра при минимум длине ЧЕРНЫХ.

0

Сообщение от Red white socks Тогда взяв в многоугольнике стороны через одну

К сожалению, такой способ не подходит, т.к. мы таким образом насоздаем кучу разомкнутых циклов - соединим в непрерывную закольцованную цепь часть хорд. При этом в теории, таких циклов может быть n/2

Если на левом рисунке начинаем обходить "по часовой" с точки А, то получатся разомкнутые циклы.
Если начнем с B, то явно не получим оптимальное соединение.

+ существует вот такой "обобщенный вариант, для которого я не смог придумать какого то вменяемого правила соединения,
всегда есть точка, если начать с которой, то или будет "разомкнутый цикл" или не оптимальный путь - даже если модифицировать ваше правило (к примеру запретить соединять так, чтобы получались циклы)

В общем, выходит, что нужен общий перебор всех вершин, что не круто...

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

Оно так и работает - расслаивает на цвета + детали.
Поэтому я и написал заранее, что "эти хорды не являются аналогом (конечных) нитей".
Такая хорда это как раз некая "нейросетевая хреновина" =) , которая совмещает в себе цвет, точность воспроизведения деталей и еще ряд свойств.
+ "наименьшая совокупная длина пути" это как раз и есть оценка того, что оно покрывает рисунок "наименьшим числом нитей"

0

Сообщение от VTsaregorodtsev Градиентным спуском условную оптимизацию не щёлкнуть

Не-не-не, я не эту задачу решаю методом градиентного спуска.
Решение этой задачи как раз и есть оптимизационное условие для градиентного спуска при решении совсем другой задачи с помощью нейросети.

Но вам в любом случае СПАСИБО, тут есть над чем подумать, хотя в таком виде, решение "вспомогательной" задачи видится чуть ли не более сложным, чем основной. =)

0

denismix, да, действительно, надо связность еще учесть. Возможно это проблема, а возможно нет.

0

Сообщение от denismix расслаивает на цвета + детали.

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

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

Сообщение от denismix "Стрингарт"

В картинках гугла пару сотен примеров и близко нет аппроксимаций фото. Есть ссылки на повторение именно лиц?

0

Сообщение от Excalibur921 В картинках гугла пару сотен примеров и близко нет аппроксимаций фото. Есть ссылки на повторение именно лиц?

Не совсем понял о каких ссылках речь?
Если ищите стрингарт именно цветных рисунков (лиц) с фотореалистичностью, то его как бы и нет особо =)
Есть пара (муж и жена), которые делают такие картины - но там не ведомый мне алгоритм и вроде как был скандал, что они нити иногда "не честно" проводят - "подныривают" где нужно под нити других цветов, так что это не показатель...

Есть еще вот этот сайт https://app.diegumeistars.lv/projects - в нем нужно разбираться: создаете проект, потом справа выбираете бетта-версию с цветными нитками, потом задаете набор ниток...
Но результат, кмк далек от идеала.

В принципе, я могу сделать несколько фоток или рисунков, посмотрите как оно на моем алгоритме (он пока не доступен в интернетах)

Добавлено через 8 минут
Если хотите посмотреть только для черного цвета, то можете глянуть мой проект: s-art.pro - там цепочку можно получить бесплатно и даже посмотреть как она наматывается. Или там же перейти на Miracle - в нем как раз реализовано то, что вы говорите - детализация черт лица и т.п.

0

Сообщение от denismix то его как бы и нет особо

Понятно, просто всюду мелкое разрешение. Думал навалом аналогов.

Странно зачем именно 5 каналов цвета. Может возможно прозрачные нити\цветная леска и свести до 3 каналов. Кстати даже чисто оттенки серого тоже неплохо, а вычислений намного меньше и контроль качества проще. Можно выиграть за счет хорошего разрешения и количества оттенков.

Сообщение от denismix где нужно под нити других цветов

Может используют соседство и наложение цветных нитей для получения оттенков цвета.

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

0

Сообщение от Excalibur921 Странно зачем именно 5 каналов цвета

Все зависит от особенностей алгоритма.
RGB модель (та, где нужны светящиеся нити, чтобы получить цвета как в телевизоре из трех точек) - нам не подходит чисто по техническим причинам - нужны прозрачные нити, которые будут светиться чистыми цветами спектра. =)

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

В общем, данная задача у меня возникла как математическое развлечение, но как то незаметно переросла в прикладную со всякими нитками и т.п. =)

Сообщение от Excalibur921 По идее тут вся задача сводиться к аппроксимации растра малой глубины яркости плотностью отрезков

Решений не мало, но тут вопрос в скорости-качестве результата.
Как по мне - отличная возможность помериться письками с другими программистами-прикладниками - условия задачи очевидны, результат легко оценивается в определенных пределах. =))))

0