Тут не только окошки, но и вся логика для их содержимого. Попробуйте браузер на питоне написать, вот тогда шутки про хром, жрущий всю память, перестанут быть шутками.
Еще раз, BFS в чистом виде не применим к задаче коммивояжора. Во-первых, тут есть функия длины, во-вторых, как вы его заставите обойти все вершины по одному разу?
Сначала с этим определитесь, а потом уже подумайте, стоит ли цитировать неприменимые к задаче оценки.
BFS работает со всеми графами (и даже с направленными циклическими, но долго)
В смысле? Вы предлагаете обходить каждую вершину кучу раз, пока у нее расстояние улучшается? Ну так это не BFS уже, а совершенно другой алгоритм. Полный перебор фактически.
Не надо мне про bi-directional Bfs рассказывать. Я про него знаю. Почитайте ваши ссылки сами, убедитесь, что там нет никакой весовой функции.
Как пройдете курс, начинайте развиваться (чтобы к началу учебы в институте не ударить в грязь лицом).
Ха-ха! Молодой человек, я эти курсы преподавал. У меня, между прочим, уже давно Phd по computer science. Не в шарашке какой-нибудь, а в одном из ведущих западных университетов.
Щекотать ваш синдром Даннинга-Крюгера мне больше не интересно. Досвидания!
Не надо мне ссылки на статьи по базовым алгоритмам, пожалуйста, давать. Я всю эту базу знаю гораздо лучше вас, поэтому и придераюсь, потому что вы дичь говорите (1).
Да, все эти алгоритмы концептуально похожи, но они не взаимозаменяемы. Так, BFS не работает с графами, где у ребер разные длины (2), что как раз и наш случай.
И, кстати, все перечисленные вами алгоритмы ищут кратчайший путь в графе. Они никак не могут найти кратчайший путь, проходящий через все вершины, что надо в задаче коммивояжора, если только их не применять к некоторому особому графу, но вы про это тоже ничего не сказали. Плюс, BFS даже там не применим.
Поэтому, пожалуйста, или признайтесь, что ошибались, или расскажите мне уже хоть немного подробностей о том, как же BFS применяется к задаче коммивояжора.
Я там подробно напишу почему в этой задаче NP = SQRT(NP)/2
Вам, похоже, точно нужны ссылки на базовые курсы по теории сложности. Хотябы вики прочитайте, что бы понять, какой бред вы только что написали.
(1) может вы просто очень плохо выражаете свои мысли. Есть парочка фраз, которая бы все объяснила, но вы их из себя даже с моими подсказками выдавить не можете.
(2) Есть модификация BFS работающая с ребрами целых неотрицательных длин, ограниченных К за O(KV+E). Но обсуждаемая задача другая.
С одной стороны, вы правы - очень много сайтов и страниц, которые по уму должны быть статическим html. Это прям беда современного интернета. Но их фронтовик вообще трогать не должен.
В оставшихся же случаях - вы вообще не правы.
Вот хотя бы тот же хабр рассмотрите. Вот захотели сделать динамическую подгрузку комментариев. Ну так их с сервера получить, да в DOM воткнуть - чем не easy с литкода? А вот фичу со старого хабра, о которой я несколько раз просил, все никак не запилят - чтобы при нажатии на "следующий непрочитанный комментарий" экран прыгал не на следующий коммент в жестком списке, а следующий непрочитанный ниже текущего положения страницы. Вот тут уже и medium, потому что нужно бинпоиск воткнуть (или set какой-нибудь применить, что там у вас в js есть).
Вы возразите, что есть же готовые фреймворки, ну так, во-первых, их кто-то писать должен, а, во-вторых, они не всегда делают именно то, что нужно конкретно вам, и вам придется что-то допиливать и понимать как и что работает.
Как-то вы перемудрили. Для этой таблицы все коэффициенты подбираются за секунду руками: прирост по 0.5 от соседних значений, значит у нас y=0.5*x+b. Подстаяляем x=1, y=-127 из второй строки таблицы: -127=0.5+b, и получаем b=-127.5 в 2 тривиальнейших арифметических действия.
Можно это и в коде сделать, задав туда лишь 2 строки таблицы. И вы вместо простейшей программы ниже нагородили аж целый Solver:
printf("Введите первые 2 любые строки таблицы в виде x0 y0 x1 y1");
double x0, y0, x1, y1;
scanf("%lf%lf%lf%lf", &x0, &y0, &x1, &y1);
printf("y = %lf * x + %lf\n", (y1-y0) / (x1-x0), (x1*y0-x0*y1) / (x1-x0));
Рюкзак, задача размена монетками, одномерной упаковки - это все очень похожие задачи. Например, набрать заданную сумму или как можно к ней ближе - частный случай рюкзака, где стоимость равна весу. Это, похоже, ваш случай. И ДП там практически идентичное. Правда потом возникают ньюансы, в задаче размена можно сжать память до линии с восстановлением ответа, в задаче о рюкзаке - уже нет.
Покажите, как набрать нецелочисленную сумму порядка 10^7 с помощью нескольких сотен нецелочисленных слагаемых, хоть рюкзаком, хоть ДП, хоть ЦЛП, хоть чем.
Зависит от точности. Можно все числа домножить на общий знаменатель. Но будет очень медленно, потому что сумма и слагаемые могут быль очень большими. И быстрого точного решения, по-моему, нет. Ваш метод -аппроксимация. Аппроксимационных алгоритмов можно придумать кучу.
Вы там жадно набираете пока у вас много слагаемых, потом какой-то эвристикой выбрасываете по одному элементу, а потом делаете полный перебор. Но это лишь приближение. Вам надо доказать, что вам можно выбрасывать из рассмотрения LastSol. Что оно точно не войдет в оптимальное решение. По-моему, вы сами понимаете, что это аппроксимационный алгоритм, потому что пишите про абсолютную погрешность алгоритма.
Обратите внимание, я не говорю, что ваш алгоритм плох: точные и быстрые аппроксимации - это очень обширная тема исследований и такой алгоритм очень полезен на практике.
Но все же это другой класс алгоритмов. В статье тут рассматривается точный алгоритм.
Вы знаете, кто такие асессоры? Это должность вроде старшего дворника на заводе. Но да, аж руководитель, аж целого отдела! Хотя нет, там группа. И сколько там в ней человек было - тот еще вопрос. Но к разработке оно никакого отношения не имеет. Естественно, контрактора, который ни строчки кода не должен будет писать вообще, а лишь просматривать текст, не гоняют по задачкам по алгоритмам.
Да ну. Зависит от области, но в целом вы не правы. Если вы не 100% времени формошлепством занимаетесь, то у вас хоть какие-то данные есть и с ними хоть что-то да сделать надо. И это уже практически easy задачка с литкода. Иногда случаются и medium. А если вы пилите сложное приложение, вроде браузера, то у вас и hard запросто вылезают.
Плюс, факт в том, что крупные компании оправданно дают задачи с литкода. А куча мелких бездумно это копируют. Эта реальность дана нам в ощущениях. Вы можете или ругаться, что собеседования не нужные и вредные, и исключить для себя львиную долю рынка работы; или вы можете потратить суммарно пару дюжин часов времени, чтобы потренироваться в решении задачек с литкода. Вы же наверняка крутой специалист и, стоит лишь чуть вникнуть в терминологию и подходы, вам вообще не составит труда потом написать 5 строк кода для разворота того же пресловутого дерева? Тут вам достаточно лишь научиться решать некоторый процент medium и вы уже большинство интервью сможете пройти.
Ну, это на нобелевскую премию тянет. А еще на филдофскую медаль и несколько мелких призов по миллиону долларов, вроде Millennium Problem Prize от Clay institute.
Там полиномиальное решение NP-полной задачи. P=NP доказано - расходимся!
Другое, более вероятное объяснение заключается в том, что этот алгоритм находит лишь некоторую аппроксимацию оптимального решения. Что, возможно даже, пригодится в некоторых практических задачах, да и аппроксимации NP-полных задач со строгим доказательством точности - весьма интересная и активная тема исследований, но это параллельно обсуждаемой статье.
Так все эти ноутбуки итак на одном и том же wifi за одним и тем же НАТом сидят. Ну не могла эта Чепмен к себе домой 60 разных линий от провайдеров подключить.
Беллман тут упоминается лишь в как один из основателей идеи Динамического Программирования. Алгоритм Беллмана тут вообще никаким боком. Как и A* - прочитайте хотя бы первый абзац в статье.
Главная фишка XOR листа в том, что его можно обходить в любом направлении. А не в мифической безопасности из-за "зашифрованных" адресов. Как и в односвязном списке, нельзя удалить произвольную ноду по указателю на нее. И более того, даже вставка или обход с произвольной ноды уже невозможны.
Это называется академический код. Когда пишешь код лишь для себя и цель не код написать, а выведенные им циферки процитировать в статье - это именно та ситуация, когда "программисту" похрену.
А, понял. Тогда граф ломается, если у некоторых прямоугольников все стороны целые.
AAAA
AAAABBB
AAAABBB
CCCDD
CCC
Пусть у A все стороны целые, у B и D - горизонтальные, а у C - вертикальная. Тогда там 5 целых ребер: два у А, и по одному на каждом из остальных прямоугольников.
Тут не только окошки, но и вся логика для их содержимого. Попробуйте браузер на питоне написать, вот тогда шутки про хром, жрущий всю память, перестанут быть шутками.
Еще раз, BFS в чистом виде не применим к задаче коммивояжора. Во-первых, тут есть функия длины, во-вторых, как вы его заставите обойти все вершины по одному разу?
Сначала с этим определитесь, а потом уже подумайте, стоит ли цитировать неприменимые к задаче оценки.
В смысле? Вы предлагаете обходить каждую вершину кучу раз, пока у нее расстояние улучшается? Ну так это не BFS уже, а совершенно другой алгоритм. Полный перебор фактически.
Не надо мне про bi-directional Bfs рассказывать. Я про него знаю. Почитайте ваши ссылки сами, убедитесь, что там нет никакой весовой функции.
Ха-ха! Молодой человек, я эти курсы преподавал. У меня, между прочим, уже давно Phd по computer science. Не в шарашке какой-нибудь, а в одном из ведущих западных университетов.
Щекотать ваш синдром Даннинга-Крюгера мне больше не интересно. Досвидания!
Не надо мне ссылки на статьи по базовым алгоритмам, пожалуйста, давать. Я всю эту базу знаю гораздо лучше вас, поэтому и придераюсь, потому что вы дичь говорите (1).
Да, все эти алгоритмы концептуально похожи, но они не взаимозаменяемы. Так, BFS не работает с графами, где у ребер разные длины (2), что как раз и наш случай.
И, кстати, все перечисленные вами алгоритмы ищут кратчайший путь в графе. Они никак не могут найти кратчайший путь, проходящий через все вершины, что надо в задаче коммивояжора, если только их не применять к некоторому особому графу, но вы про это тоже ничего не сказали. Плюс, BFS даже там не применим.
Поэтому, пожалуйста, или признайтесь, что ошибались, или расскажите мне уже хоть немного подробностей о том, как же BFS применяется к задаче коммивояжора.
Вам, похоже, точно нужны ссылки на базовые курсы по теории сложности. Хотябы вики прочитайте, что бы понять, какой бред вы только что написали.
(1) может вы просто очень плохо выражаете свои мысли. Есть парочка фраз, которая бы все объяснила, но вы их из себя даже с моими подсказками выдавить не можете.
(2) Есть модификация BFS работающая с ребрами целых неотрицательных длин, ограниченных К за O(KV+E). Но обсуждаемая задача другая.
С одной стороны, вы правы - очень много сайтов и страниц, которые по уму должны быть статическим html. Это прям беда современного интернета. Но их фронтовик вообще трогать не должен.
В оставшихся же случаях - вы вообще не правы.
Вот хотя бы тот же хабр рассмотрите. Вот захотели сделать динамическую подгрузку комментариев. Ну так их с сервера получить, да в DOM воткнуть - чем не easy с литкода? А вот фичу со старого хабра, о которой я несколько раз просил, все никак не запилят - чтобы при нажатии на "следующий непрочитанный комментарий" экран прыгал не на следующий коммент в жестком списке, а следующий непрочитанный ниже текущего положения страницы. Вот тут уже и medium, потому что нужно бинпоиск воткнуть (или set какой-нибудь применить, что там у вас в js есть).
Вы возразите, что есть же готовые фреймворки, ну так, во-первых, их кто-то писать должен, а, во-вторых, они не всегда делают именно то, что нужно конкретно вам, и вам придется что-то допиливать и понимать как и что работает.
Как-то вы перемудрили. Для этой таблицы все коэффициенты подбираются за секунду руками: прирост по 0.5 от соседних значений, значит у нас
y=0.5*x+b. Подстаяляем x=1, y=-127 из второй строки таблицы:-127=0.5+b, и получаем b=-127.5 в 2 тривиальнейших арифметических действия.Можно это и в коде сделать, задав туда лишь 2 строки таблицы. И вы вместо простейшей программы ниже нагородили аж целый Solver:
Это возможно, только если вес = стоимость = B. А значит вам надо просто взять самый дорогой рюкзак вместимостью B. Это будет лучшее приближение к B.
Из-за нецелых чисел - да ДП в лоб не работает, да.
Зачем? Просто считайте в копейках. Вот у вас целые числа и ДП работает.
Рюкзак, задача размена монетками, одномерной упаковки - это все очень похожие задачи. Например, набрать заданную сумму или как можно к ней ближе - частный случай рюкзака, где стоимость равна весу. Это, похоже, ваш случай. И ДП там практически идентичное. Правда потом возникают ньюансы, в задаче размена можно сжать память до линии с восстановлением ответа, в задаче о рюкзаке - уже нет.
Зависит от точности. Можно все числа домножить на общий знаменатель. Но будет очень медленно, потому что сумма и слагаемые могут быль очень большими. И быстрого точного решения, по-моему, нет. Ваш метод -аппроксимация. Аппроксимационных алгоритмов можно придумать кучу.
Вы там жадно набираете пока у вас много слагаемых, потом какой-то эвристикой выбрасываете по одному элементу, а потом делаете полный перебор. Но это лишь приближение. Вам надо доказать, что вам можно выбрасывать из рассмотрения LastSol. Что оно точно не войдет в оптимальное решение. По-моему, вы сами понимаете, что это аппроксимационный алгоритм, потому что пишите про абсолютную погрешность алгоритма.
Обратите внимание, я не говорю, что ваш алгоритм плох: точные и быстрые аппроксимации - это очень обширная тема исследований и такой алгоритм очень полезен на практике.
Но все же это другой класс алгоритмов. В статье тут рассматривается точный алгоритм.
Вы знаете, кто такие асессоры?
Это должность вроде старшего дворника на заводе. Но да, аж руководитель, аж целого отдела! Хотя нет, там группа. И сколько там в ней человек было - тот еще вопрос. Но к разработке оно никакого отношения не имеет. Естественно, контрактора, который ни строчки кода не должен будет писать вообще, а лишь просматривать текст, не гоняют по задачкам по алгоритмам.
В общем, очень странная претензия.
Да ну. Зависит от области, но в целом вы не правы. Если вы не 100% времени формошлепством занимаетесь, то у вас хоть какие-то данные есть и с ними хоть что-то да сделать надо. И это уже практически easy задачка с литкода. Иногда случаются и medium. А если вы пилите сложное приложение, вроде браузера, то у вас и hard запросто вылезают.
Плюс, факт в том, что крупные компании оправданно дают задачи с литкода. А куча мелких бездумно это копируют. Эта реальность дана нам в ощущениях. Вы можете или ругаться, что собеседования не нужные и вредные, и исключить для себя львиную долю рынка работы; или вы можете потратить суммарно пару дюжин часов времени, чтобы потренироваться в решении задачек с литкода. Вы же наверняка крутой специалист и, стоит лишь чуть вникнуть в терминологию и подходы, вам вообще не составит труда потом написать 5 строк кода для разворота того же пресловутого дерева? Тут вам достаточно лишь научиться решать некоторый процент medium и вы уже большинство интервью сможете пройти.
Вы все еще про коммивояжора? Нет, просветите, пожалуйста, как BFS, путь и двусторонний, вообще хоть как-то применим тут.
Да, это вариант.
Ну, это на нобелевскую премию тянет. А еще на филдофскую медаль и несколько мелких призов по миллиону долларов, вроде Millennium Problem Prize от Clay institute.
Там полиномиальное решение NP-полной задачи. P=NP доказано - расходимся!
Другое, более вероятное объяснение заключается в том, что этот алгоритм находит лишь некоторую аппроксимацию оптимального решения. Что, возможно даже, пригодится в некоторых практических задачах, да и аппроксимации NP-полных задач со строгим доказательством точности - весьма интересная и активная тема исследований, но это параллельно обсуждаемой статье.
Так все эти ноутбуки итак на одном и том же wifi за одним и тем же НАТом сидят. Ну не могла эта Чепмен к себе домой 60 разных линий от провайдеров подключить.
Вы тут описываете какую-то эвристическую жадность. Этот метод не дает оптимальное решение задачи Коммивояжора.
Беллман тут упоминается лишь в как один из основателей идеи Динамического Программирования. Алгоритм Беллмана тут вообще никаким боком. Как и A* - прочитайте хотя бы первый абзац в статье.
Главная фишка XOR листа в том, что его можно обходить в любом направлении. А не в мифической безопасности из-за "зашифрованных" адресов. Как и в односвязном списке, нельзя удалить произвольную ноду по указателю на нее. И более того, даже вставка или обход с произвольной ноды уже невозможны.
Это называется академический код. Когда пишешь код лишь для себя и цель не код написать, а выведенные им циферки процитировать в статье - это именно та ситуация, когда "программисту" похрену.
Точно. Тогда, все работает.
А, понял. Тогда граф ломается, если у некоторых прямоугольников все стороны целые.
Пусть у A все стороны целые, у B и D - горизонтальные, а у C - вертикальная. Тогда там 5 целых ребер: два у А, и по одному на каждом из остальных прямоугольников.