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

[Larsonsager]

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

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

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

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

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

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

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

[Lisa]

Я восхищаюсь вашим терпением, коллега.

[tessob]

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

Это как бы не совсем так, ну, ...или совсем не так...

Сначала был мой пост:

Lisa, вам формально нужно найти оптимальный гамильтонов путь в полносвязном графе в 8’000 вершин. Число возможных гамильтоновых путей у такого графа будет примерно 10 ^ 30’000.

Следом ваш:

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

Смотрите внимательно на даты и время. Все ходы записаны.
Рюкзак к обсуждению, в качестве аргумента, приплели вы, а не я.

FPTASность не имеет никакого отношения к динамичности. Если конкретная реализация использует динамику - ну, хорошо, почему бы и нет.

Понятие "FPTASность" мы оставим за скобками.
Правильно ли я понимаю, что вы знаете другой FTPAS для рюкзака, который не использует динамическое программирование?

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

Динамика ровно та самая, которая единственная. Если вы откроете книжку Вазирани, которой тыкали мне в нос, то на страничке 70 будет описан ровно тот самый алгоритм, который имплементирован студентом бауманки. Динамика просто итерирует по предметам и капасити и для каждого нового значения матрицы решений выполняет довольно жадную проверку на максимум. Где там хоть намек на тот оптимум, про который вы тут пишете? В каком месте алгоритм ищет "оптимум, отстоящий от глобального на приемлемую величину"? Где именно задана эта приемлемая величина, в какой строке имплементации!?

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

Возвращаясь к вашим словам, будто я "заявил, что способен установить отличие глобального минимума от локального": я этого не заявлял, а заявлял я, цитирую: "вместо глобального минимума находится тот из локальных, что мало отличается от глобального".

Как вы определяете меру отличия!?!?!?

Larsonsager, если хотите, то я вам сведу задачу о контейнерах к канонической задаче о Гамильтоновом пути? Сможете продемонстрировать:

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

Словами не передать как я хочу увидеть "рандомизированные алгоритмы, решающие, например, задачу рюкзака за полиномиальное время". Вы бы хоть пример такого алгоритма привели. Это же прорыв в математике будет, не иначе.
Что касается LP-релаксации, то я бы с удовольствием посмотрел:
1) Как вы будете приводить к линейной канонической форме задачу о гамильтоновом пути. В первую очередь мне будет интересно глянуть как вы будете решать проблему коммутативности иксов.
2) Как вы будете эвристиками возвращаться к целочисленности в задаче о рюкзаке, где у вас сложность 2^n. У вас для всех иксов будет задано неравенство 0 <= X <= 1. Зато линейные уравнения сформулировать просто.

Я восхищаюсь вашим терпением, коллега.

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

[Lisa]

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

Larsonsager вам там уже выше все очень подробно расписал.

[Lisa]

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

[tessob]

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

Lisa, к вам third party провайдеры в снах являться стали?

Вы уж простите, но я не верю ни единому вашему слову. Вы, в этой теме, привели ровно 0 аргументов по-существу и целую кучу громких заявлений.

[Lisa]

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

Lisa, к вам third party провайдеры в снах являться стали?

Вы уж простите, но я не верю ни единому вашему слову. Вы, в этой теме, привели ровно 0 аргументов по-существу и целую кучу громких заявлений.

Мне совершенно все равно чему вы верите или не верите. Это ваши проблемы. У меня только больше выбор работ будет.

[alex_127]

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