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

[Larsonsager]

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

Да даже простые числа именно так и ищут. Берут наугад взятое число и тестируют его Миллиром-Рабином столько раз, сколько сочтут разумным.

[Lisa]

Сколько раз я зарекался не спорить с искусственным интеллектом….

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

При этом предельное «отлежание» от оптимума у жадного гамильтонова пути математически доказано, а наихудший гамильтонов путь может «отлежать» сколь угодно далеко.

Вы шутите, да? Вы хоть что-нибудь знаете про современные методы Исследования Операций, а? Ну хоть что-нибудь?

[tessob]

Что вас не устраивает? Так, например, решают задачу о рюкзаке за полиномиальное время. Но за этим хоть математика стоит.

Дело Петрика живет и крепнет.

Вы меня обижаете.

Простите, не хотел.
Просто, Larsonsagerы имеют такие же шансы попасть в индустрию, как вы или я. По факту даже бОльшие. Их просто тупо больше. Я хотел привести Физику-Лирику примеры текущей ситуации, а получилось, что примеры привели Larsonsager и Lisa. Не исключено, что Ф-Л сейчас "бьется в алгебраическом припадке перед монитором". Он работу найти не может, просто на просто, а они на Абелевку претендуют.

Вы шутите, да? Вы хоть что-нибудь знаете про современные методы Исследования Операций, а? Ну хоть что-нибудь?

Ну давайте, не томите, как решать такие задачи?
Только имейте ввиду, что на земле всего примерно 10 ^ 30 FLOPS вычислительных мощностей.

[Larsonsager]

Что вас не устраивает? Так, например, решают задачу о рюкзаке за полиномиальное время. Но за этим хоть математика стоит.

Дело Петрика живет и крепнет.

Хорошо, что здесь все анонимные, правда? А то работодатели могут узнать, насколько tessob отстал от жизни.

Просвещайтесь:
http://theory.stanford.edu/~tim/w16/w16.html
Lecture 15 (Tue Feb 23): Introduction to approximation algorithms. Scheduling, knapsack, Steiner tree, set coverage, influence maximization.
CS161-level videos on NP-completeness (Part XVI) and approximation algorithms for the knapsack problem (Part XVIII).

Ну или прямо тут:
https://books.google.com/books?id=EILqA ... ck&f=false

[tessob]

Larsonsager, давайте вы просто выложите сюда на форум полиномиальный алгоритм для сета Р08 реализованный на любом языке? Там размерность пространства решений всего 24, а не 8'000.

[Larsonsager]

Залезаете сюда:
https://github.com/madcat1991/knapsack
- скачиваете код на питоне.

Там есть разные варианты:
-m {brute,ratio,dynamic,bandb,fptas,sa}

Полиномиальное решение, судя по названию, это FPTAS. Так как вы не знаете, что это значит, можете посмотреть в википедии.
Я в код не лез. Доверимся молодому человеку с ником madcat1991, который, судя по содержанию его гитхаба, к моменту написания этого кода был выпускником Бауманки. Вероятно, он просто взял один из стандартных алгоритмов, которые уже лет 20 как известны и уже лет 10 как входят в бакалаврские курсы.


Я запустил с коэффициентом 1.001 (если я правильно понимаю, это означает, что нас интересует ответ, отличающийся от оптимального не более чем на 0.1%). И получил ответ:
8 24 13549094 1 1 0 1 1 1 0 0 0 1 1 0 1 0 0 1 0 0 0 0 0 1 1 1
- в точности совпадающий с оптимумом.

Если вы не верите выпускникам Бауманки, попробуйте взять код у этого корейского чеха, бауманок не кончавшего: https://github.com/martinkersner/Knapsa ... master/src - честно говоря, я сходу не разобрался.

[Lisa]

Просто, Larsonsagerы имеют такие же шансы попасть в индустрию, как вы или я. По факту даже бОльшие. Их просто тупо больше. Я хотел привести Физику-Лирику примеры текущей ситуации, а получилось, что примеры привели Larsonsager и Lisa.

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

А когда возвращаешься через годика 2, то там всю твою математику вспоминают просто как нечто из разряда мифологии.

?

[tessob]

Полиномиальное решение, судя по названию, это FPTAS.

Короче говоря, вы заявляете, что знаете FPTAS, который решает задачу о Гамильтоновом пути на неметрическом графе!?

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

То есть, мне сейчас нужно, вот просто так, взять и поверить вам на слово?

[Lisa]

То есть, мне сейчас нужно, вот просто так, взять и поверить вам на слово?

Как хотите
Добавлю, что мне совершенно все равно верите вы мне или нет. Моё образование, опыт и достижения никуда от меня не денутся. Это у вас проблема с тем что ваши математические разработки никому не нужны. Вы можете послушать про опыт тех, у кого есть не одно успешное внедрение. А можете просто считать всех остальных идиотами и обижаться на индустрию, которая не такая как вам хочется.

[Think_Different]

Просто, Larsonsagerы имеют такие же шансы попасть в индустрию, как вы или я. По факту даже бОльшие. Их просто тупо больше. Я хотел привести Физику-Лирику примеры текущей ситуации, а получилось, что примеры привели Larsonsager и Lisa.

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

А в каких индустриях, если не секрет?

[tessob]

Lisa, чтоб потешить ваше самолюбие, я вам больше скажу. У меня, вот прям успешных-успешных решений, пожалуй, не больше 20%. Сложно сказать сколько точно. Может и того меньше. Задача о размещении контейнеров была у меня в Maersk. Мое решение так и не попало в продакшен. Внутреннее решение оказалось сильнее. Попали только 2 релаксации, которые мы притащили с проекта Дойче Поста. При этом решение в Дойче Посте благополучно сдохло в руках индийского аутсорса. И там вообще ничего не осталось. Короче, мне до вас далеко.

Не поделитесь, случаем, рецептом как спасать решения от аутсорсов?

[Мальчик-Одуванчик]

Именно поэтому книжка, отправленная USPS Media Mail из Плезант-Хилла в Сан-Франциско сначала едет почему-то в Лос-Анжелес.

[Lisa]

Не поделитесь, случаем, рецептом как спасать решения от аутсорсов?

А что с ними происходит? Их выкидывают и отдают в аутсорс переделать? Или отдают туда поддержку? Или что?

[Lisa]

Именно поэтому книжка, отправленная USPS Media Mail из Плезант-Хилла в Сан-Франциско сначала едет почему-то в Лос-Анжелес.

Где место на траке есть туда и едет. Книжке все равно.

[tessob]

Не поделитесь, случаем, рецептом как спасать решения от аутсорсов?

А что с ними происходит? Их выкидывают и отдают в аутсорс переделать? Или отдают туда поддержку? Или что?

У вас же, с ваших слов, "больше десятка успешных разработок в разных индустриях", которые используются по много лет без вашего участия? Скажите просто как вам это удается? Кто и как их поддерживает? Кто их развивает, когда бизнес меняется? Тут уже наверное половина форума взяли блокнотики и приготовились записывать.

[tessob]

Именно поэтому книжка, отправленная USPS Media Mail из Плезант-Хилла в Сан-Франциско сначала едет почему-то в Лос-Анжелес.

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

Посмотрите историю создания FedEx. В свое время это была буквально революция. Благодаря кластеризации они смогли сделать возможной доставку из любой точки в любую другую максимум на 2 день, не считая дня отправки.

[Lisa]

Не поделитесь, случаем, рецептом как спасать решения от аутсорсов?

А что с ними происходит? Их выкидывают и отдают в аутсорс переделать? Или отдают туда поддержку? Или что?

У вас же, с ваших слов, "больше десятка успешных разработок в разных индустриях", которые используются по много лет без вашего участия? Скажите просто как вам это удается? Кто и как их поддерживает? Кто их развивает, когда бизнес меняется? Тут уже наверное половина форума взяли блокнотики и приготовились записывать.

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

[Мальчик-Одуванчик]

Именно поэтому книжка, отправленная USPS Media Mail из Плезант-Хилла в Сан-Франциско сначала едет почему-то в Лос-Анжелес.

Где место на траке есть туда и едет. Книжке все равно.

Не совсем: другие посылки нормально идут через Окланд или напрямую в Сан-Франциско. Но только медиа мейл тупо прет в собственный центр обработки в Лос-Анжелесе.
Математики и Эффективные Мэнеджеры в действии.

[Мальчик-Одуванчик]

Именно поэтому книжка, отправленная USPS Media Mail из Плезант-Хилла в Сан-Франциско сначала едет почему-то в Лос-Анжелес.

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

Ближайший кластер - в Окланде. До него примерно 20 миль. И посылки идут именно туда в большинстве случаев. Но только медиа-мейл исходя из соображений оптимизации тупо прется за сотни миль в Лос-Анжелес, а потом обратно. Без математики тут явно не обошлось.
Со стороны выглядит как феерическая тупость: сначала на месте отсортировать медиа-почту отдельно от остального потока, а потом запердолить получившееся черти-куда.

[Lisa]

Ближайший кластер - в Окланде. До него примерно 20 миль. И посылки идут именно туда в большинстве случаев. Но только медиа-мейл исходя из соображений оптимизации тупо прется за сотни миль в Лос-Анжелес, а потом обратно. Без математики тут явно не обошлось.
Со стороны выглядит как феерическая тупость: сначала на месте отсортировать медиа-почту отдельно от остального потока, а потом запердолить получившееся черти-куда.

Хорошее с точки зрения бизнеса решение не всегда интуитивно понятно человеку со стороны. Это не значит, что решение плохое, это значит что человек не видит картину целиком.

[Мальчик-Одуванчик]

Ближайший кластер - в Окланде. До него примерно 20 миль. И посылки идут именно туда в большинстве случаев. Но только медиа-мейл исходя из соображений оптимизации тупо прется за сотни миль в Лос-Анжелес, а потом обратно. Без математики тут явно не обошлось.
Со стороны выглядит как феерическая тупость: сначала на месте отсортировать медиа-почту отдельно от остального потока, а потом запердолить получившееся черти-куда.

Хорошее с точки зрения бизнеса решение не всегда интуитивно понятно человеку со стороны. Это не значит, что решение плохое, это значит что человек не видит картину целиком.

Но чаще всего - обычная тупость эффективных менеджеров. Разумеется с привлечением математики. (чтобы даже самим непонятно было)

[fruit6]

Дело в том, что media mail был введен как более дешевый способ доставки. Плюс USPS медленно реагирует на всё, например открыть или переоборудовать сортировочный центр если объемы превышают ожидаемое занимает месяц+, даже в горячий сезон типа декабрь (бугага). Я даже не уверен, что media попадает в обычные категории которыми оперирует почта: flats and packages. Это что-то третье разрядное. Хотите сервис - шлите посылку

[fruit6]

На почте кстати нет никаких эффективных менеджеров.

[Larsonsager]

Полиномиальное решение, судя по названию, это FPTAS.

Короче говоря, вы заявляете, что знаете FPTAS, который решает задачу о Гамильтоновом пути на неметрическом графе!?

Отлично, теперь вы узнали, что такое FPTAS. А теперь перечитайте тред и попытайтесь найти место, где я якобы заявляю, будто задача о гамильтоновом пути на неметрическом графе решается каким-то FPTAS. Я изначально писал про задачу о рюкзаке. Вы сперва оскорбительно проехались по моему комментарию, решив, что раз вы что-то смутно помните о NP-полных задачах - значит, мои слова о полиномиальном решении сравнимы с "делом Петрика". А когда поняли, что облажались, решили приписать мне слова о полиномиальном нахождении гамильтонова пути.

[tessob]

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

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

Вы заявили, что достаточно будет провести n экспериментов. А чё бы и нет!? Представьте что вы исследуете Y=X^Х которая задана только для X, являющихся натуральными числами на интервале 0:10^30000. Ну разве не «П####Ц»!?

Следом вы заявляете, что именно так, за полином, и решают задачу о рюкзаке, и за этим даже стоит математика. Разумно? Разумно! Рандом — верный путь к полиному! Ну чем не заявка на премию Петрика!? Разумеется, я не мог, просто из любопытства, не попросить привести этот волшебный алгоритм.

Тот алгоритм, что вы привели — обычное динамическое программирование, релаксированное пропорциональным уменьшением капасити и весов. Просто, матрица для динамики с рюкзаком строится как [ число предметов , капасити рюкзака ]. Ваш FPTAS в данном случае просто уменьшет размер матрицы, чтоб обходить не MxN, а MxN/K. Если вы посмотрите сорцы, то после деления всего и вся, идет вызов динамики. Однако, удивительным образом, никакой рандомизации в алгоритме не оказалось.

В итоге, исходя из вашей аргументации, следует, что: задача о контейнерах решается так же как и рюкзак, а рюкзак решается fptas. Следовательно, допустив транзитивность, я и решился уточнить, есть ли у вас fptas для Гамильтонова пути. Вдруг есть.

UPD:
И кстати, ваш FPTAS для рюкзака не находит решение за полином. Он работает за полином. А найдет он решение или нет, будет зависеть от входных данных. Сможете сказать почему?