Что творится с дейта сайнсом?

Larsonsager
Уже с Приветом
Posts: 1860
Joined: 02 Sep 2016 20:26

Re: Что творится с дейта сайнсом?

Post by Larsonsager »

> В итоге, исходя из вашей аргументации, следует, что: задача о контейнерах решается так же как и рюкзак

Это ваши домыслы. Я не говорил, что задача о контейнерах решается так же, как и рюкзак. Было бы абсурдным говорить это, пока задача о контейнерах вообще не сформулирована. Мои слова про локальный минимум были ответом на вашу фразу:

> Это задача дискретной математики в пространстве натуральных чисел. В математике
> вообще пока нет ни одного непереборного алгоритма, который бы находил min/max решение
> подобных задач за менее чем n! шагов.

- я сказал, что так как на практике нас может устроить локальный минимум вместо глобального, если он не сильно хуже, то для ряда задач дискретной математики в пространстве натуральных чисел [не решаемых строго за приемлемое время] есть принципиально более быстрые приблизительные решения. И привёл два примера: (1) рандомизированные алгоритмы, решающие, например, задачу рюкзака за полиномиальное время и (2) релаксацию условия целочисленности [например, LP-релаксацию] с последующими эвристиками возврата к целочисленности.

> Тот алгоритм, что вы привели — обычное динамическое программирование

FPTASность не имеет никакого отношения к динамичности. Если конкретная реализация использует динамику - ну, хорошо, почему бы и нет. И нет, это не та же динамика, что при строгом решении. Суть FPTAS в том, что, хотя для глобального оптимума требуется, по сути, полный перебор всех вариантов или около того, можно найти оптимум, отстоящий от глобального на приемлемую величину, не перебирающий все варианты.

Возвращаясь к вашим словам, будто я "заявил, что способен установить отличие глобального минимума от локального": я этого не заявлял, а заявлял я, цитирую: "вместо глобального минимума находится тот из локальных, что мало отличается от глобального". Чтобы найти локальный, мало отличающийся от глобального, глобальный отличать от локального не нужно. Достаточно знать, что он не может быть гораздо лучше найденного (гарантированно не может или вероятностно вряд ли является), над чем работают математики, результатами которых могут пользоваться алгоритмисты. Например, для той же LP-релаксации задач целочисленного программирования может оказаться возможным оценить отличие найденного решения от оптимального, найдя, скажем, зазор двойственности (duality gap) с соответствующей выпуклой задачей.
Lisa
Уже с Приветом
Posts: 3209
Joined: 25 Jul 2000 09:01

Re: Что творится с дейта сайнсом?

Post by Lisa »

Larsonsager wrote: 15 May 2018 20:44
Я восхищаюсь вашим терпением, коллега.
tessob
Уже с Приветом
Posts: 576
Joined: 07 Jan 2016 13:04

Re: Что творится с дейта сайнсом?

Post by tessob »

Larsonsager wrote: 15 May 2018 20:44Это ваши домыслы. Я не говорил, что задача о контейнерах решается так же, как и рюкзак. Было бы абсурдным говорить это, пока задача о контейнерах вообще не сформулирована.
Это как бы не совсем так, ну, ...или совсем не так...

Сначала был мой пост:
tessob wrote: 10 May 2018 20:11Lisa, вам формально нужно найти оптимальный гамильтонов путь в полносвязном графе в 8’000 вершин. Число возможных гамильтоновых путей у такого графа будет примерно 10 ^ 30’000.
Следом ваш:
Larsonsager wrote: 10 May 2018 20:21Никому не нужно решать подобные задачи строго. Из того, что задача о рюкзаке или коммивояжера не решаются строго за приемлемое время, не следует, что они вообще не решаются за приемлемое время. Просто вместо глобального минимума находится тот из локальных, что мало отличается от глобального.
Смотрите внимательно на даты и время. Все ходы записаны. :nono#:
Рюкзак к обсуждению, в качестве аргумента, приплели вы, а не я.

Larsonsager wrote: 15 May 2018 20:44FPTASность не имеет никакого отношения к динамичности. Если конкретная реализация использует динамику - ну, хорошо, почему бы и нет.
Понятие "FPTASность" мы оставим за скобками. :ROFL:
Правильно ли я понимаю, что вы знаете другой FTPAS для рюкзака, который не использует динамическое программирование?
Larsonsager wrote: 15 May 2018 20:44И нет, это не та же динамика, что при строгом решении. Суть FPTAS в том, что, хотя для глобального оптимума требуется, по сути, полный перебор всех вариантов или около того, можно найти оптимум, отстоящий от глобального на приемлемую величину, не перебирающий все варианты.
Динамика ровно та самая, которая единственная. Если вы откроете книжку Вазирани, которой тыкали мне в нос, то на страничке 70 будет описан ровно тот самый алгоритм, который имплементирован студентом бауманки. Динамика просто итерирует по предметам и капасити и для каждого нового значения матрицы решений выполняет довольно жадную проверку на максимум. Где там хоть намек на тот оптимум, про который вы тут пишете? В каком месте алгоритм ищет "оптимум, отстоящий от глобального на приемлемую величину"? Где именно задана эта приемлемая величина, в какой строке имплементации!?

И что вы, в случае динамики, понимаете под "при строгом решении"? В предыдущем сообщении я вас попытался спросить знаете ли вы условия, когда динамика не сможет придти в глобальный минимум. Вы не сочли нужным отвечать. Не проблема. Однако, вместо этого, вы решили продемонстрировать свое незнание этого.
Larsonsager wrote: 15 May 2018 20:44Возвращаясь к вашим словам, будто я "заявил, что способен установить отличие глобального минимума от локального": я этого не заявлял, а заявлял я, цитирую: "вместо глобального минимума находится тот из локальных, что мало отличается от глобального".
:o Как вы определяете меру отличия!?!?!? :angry:

Larsonsager, если хотите, то я вам сведу задачу о контейнерах к канонической задаче о Гамильтоновом пути? Сможете продемонстрировать:
Larsonsager wrote: 15 May 2018 20:44(1) рандомизированные алгоритмы, решающие, например, задачу рюкзака за полиномиальное время и (2) релаксацию условия целочисленности [например, LP-релаксацию] с последующими эвристиками возврата к целочисленности.
Словами не передать как я хочу увидеть "рандомизированные алгоритмы, решающие, например, задачу рюкзака за полиномиальное время". Вы бы хоть пример такого алгоритма привели. Это же прорыв в математике будет, не иначе.
Что касается LP-релаксации, то я бы с удовольствием посмотрел:
1) Как вы будете приводить к линейной канонической форме задачу о гамильтоновом пути. В первую очередь мне будет интересно глянуть как вы будете решать проблему коммутативности иксов.
2) Как вы будете эвристиками возвращаться к целочисленности в задаче о рюкзаке, где у вас сложность 2^n. У вас для всех иксов будет задано неравенство 0 <= X <= 1. Зато линейные уравнения сформулировать просто.
Lisa wrote: 16 May 2018 01:20Я восхищаюсь вашим терпением, коллега.
Lisa, не скромничайте, пролейте уже наконец свет на современные методы исследования операций. Просто, пока ничего кроме ваших голословных утверждений о ваших выдающихся успехах, в этой теме с вашей стороны не прозвучало. У вас есть шанс это исправить.
Lisa
Уже с Приветом
Posts: 3209
Joined: 25 Jul 2000 09:01

Re: Что творится с дейта сайнсом?

Post by Lisa »

tessob wrote: 16 May 2018 08:42 Lisa, не скромничайте, пролейте уже наконец свет на современные методы исследования операций. Просто, пока ничего кроме ваших голословных утверждений о ваших выдающихся успехах, в этой теме с вашей стороны не прозвучало. У вас есть шанс это исправить.
Larsonsager вам там уже выше все очень подробно расписал.
Lisa
Уже с Приветом
Posts: 3209
Joined: 25 Jul 2000 09:01

Re: Что творится с дейта сайнсом?

Post by Lisa »

К нам тут недавно тоже приходили third party провайдеры, впаривали свою простенькую плохонькую эвристику. Потому что задача ну такая сложная, такая сложная, ничего лучше ну никак нельзя. Нарвались, конечно.
tessob
Уже с Приветом
Posts: 576
Joined: 07 Jan 2016 13:04

Re: Что творится с дейта сайнсом?

Post by tessob »

Lisa wrote: 18 May 2018 20:54К нам тут недавно тоже приходили third party провайдеры, впаривали свою простенькую плохонькую эвристику. Потому что задача ну такая сложная, такая сложная, ничего лучше ну никак нельзя. Нарвались, конечно.
:ROFL: Lisa, к вам third party провайдеры в снах являться стали? :ROFL:

Вы уж простите, но я не верю ни единому вашему слову. Вы, в этой теме, привели ровно 0 аргументов по-существу и целую кучу громких заявлений.
Lisa
Уже с Приветом
Posts: 3209
Joined: 25 Jul 2000 09:01

Re: Что творится с дейта сайнсом?

Post by Lisa »

tessob wrote: 19 May 2018 07:13
Lisa wrote: 18 May 2018 20:54К нам тут недавно тоже приходили third party провайдеры, впаривали свою простенькую плохонькую эвристику. Потому что задача ну такая сложная, такая сложная, ничего лучше ну никак нельзя. Нарвались, конечно.
:ROFL: Lisa, к вам third party провайдеры в снах являться стали? :ROFL:

Вы уж простите, но я не верю ни единому вашему слову. Вы, в этой теме, привели ровно 0 аргументов по-существу и целую кучу громких заявлений.
Мне совершенно все равно чему вы верите или не верите. Это ваши проблемы. У меня только больше выбор работ будет.
alex_127
Уже с Приветом
Posts: 7723
Joined: 29 Mar 2000 10:01
Location: Kirkland,WA

Re: Что творится с дейта сайнсом?

Post by alex_127 »

Мне говорили что потолок низковатый. Не скажите - так ли это. Есть ли куча народа с 350к+ Или мы скатываемся к единицам...

Return to “Работа и Карьера в IT”