Хорошо кодю (C++, js, python, php, go), но плох в матане.

плох в матане

Молодец, что осознал.
Качай. Найми преподавателя.

Ох блин. Ты еще скажи, что дифсчисление не нужно в прикладных не-инженерных задачах.

dB знаешь, что такое? Вот это логарифм из жизни.

И нахрена ему для понимания dB уметь решать логарифмические уравнения? Понятно, что что такое логарифм знать нужно, но зачем натренировывать на уравнения и формулы с ними?

PS: да и сколько школьников сможет сказать что такое dB и как-то это число привязать к своей задаче? Массы ориентируются все равно на какое-то число, которое «хорошо» для такой-то ситуации, по отзывам/рекомендациям, а не на формулу.

Замыкания - сравнительно простой концепт.

А конструкции из них могут быть очень сложными.

Сегодня сев пообедать решил в голове прокрутить задачку опять.

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

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

Но таки я копнул дальше и нашёл пару способов оптимизации, которые сократят перебор на порядки для классической задачи.

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

Если без возврата, то ничего страшного - это просто не гамильтонов цикл.

Про часть алгоритма - и что же там у тебя такое эффективное и не являющееся Дейкстрой, Фордом-Белмманом, Левитом? :)

Так у тебя есть решение задачи коммивояжёра (пусть без возврата в исходный город), дающее всегда ПРАВИЛЬНЫЙ ответ и с асимптотикой лучше перебора?

Способы нахождения приблизительных решений уже давно достаточно хорошо изучены. Не надо открывать своё коолесо.

Про часть алгоритма - и что же там у тебя такое эффективное и не являющееся Дейкстрой, Фордом-Белмманом, Левитом? :)

Просто волновой алгоритм. https://ru.wikipedia.org/wiki/Алгоритм_Ли

Алгоритмист - это не тот, кто знает много страшных названий и фамилий, а тот кто может правильно применить нужный алгоритм в нужном месте и эффективно его реализовать.

Так у тебя есть решение задачи коммивояжёра (пусть без возврата в исходный город), дающее всегда ПРАВИЛЬНЫЙ ответ и с асимптотикой лучше перебора?

Именно так.

А кто сказал, что я это применять не умею? :)

Я такого не говорил.

реализацию красно-чёрного дерева по памяти на бумажке сможешь написать?

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

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

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

Как все это связано с написанием реализации на бумажке – мне понять крайне сложно.

Но

Так у тебя есть решение задачи коммивояжёра (пусть без возврата в исходный город), дающее всегда ПРАВИЛЬНЫЙ ответ и с асимптотикой лучше перебора?

Есть и это факт.

Ммм, волновой алгоритм. И как там с асимптотикой дела? :)

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

При всём моём уважении, пока что это выглядит как чистой воды балабольство.

Нет, это не факт. Даже более чем уверен, что это не так.

Тут два варианта развития событий:

1) Наложены какие-то ограничения на задачу, о которых я не знаю и которые позволяют снизить асимптотическую оценку.

2) Ложь.

Как ты сделал этот вывод из моего комментария?

Лень изучить (задолбал ты своим этим словом) в интернете самому?

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

пока что это выглядит как чистой воды балабольство.

Вот именно! Не балаболь а потрудись изучить матчасть.

Слив засчитан. Без предоставленного алгоритма.

тролль дефектеддетектед

Чё молчишь? Требую алгоритмов!

В замен расскажу про персептроны!

И про структуру стриарной коры, если интересует?

А кто сказал, что я это применять не умею? :)

Судя по всему ты не только не умеешь применять, а не хочешь в принципе.

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

Много «букоф»?

Лентяй! Ну и какаяющийся постоянно троль! (это видно из аватарки)

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

Молодец. Перечитай тот комментарий ещё раз.

Ок. А разве 90% работы программиста - автоматизация инженерных и т.п. задач?

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

Правда суть логарифмов для быдла^W обычных человеков - это конечно не dB, а сложный процент для всякой банковской мути.

Ок. А разве 90% работы программиста - автоматизация инженерных и т.п. задач?

Нет.

Все правильно 90% работы программиста - это формочки клепать и чужой код с гитхаба воровать

Все правильно 90% работы программиста - это формочки клепать и чужой код с гитхаба воровать

Зависит от программиста, но обычно тоже нет.

С просоня опять подумал над этой задачей.

То что ты троль - это понятно. Но это не отменяет варианта, что может ты действительно интересуешься алгоритмами.

Нашёл в нете, что волновой метод - это в принципе тот же метод «ветвей и границ».

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

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

Суть «красоты» этих алгоритмов в том, что автоматически отсеиваются все не оптимальные варианты пути без траты на их рассмотрение вычислительных ресурсов. К тому же, не оптимальных путей какраз и есть то громадное количество, которое просчитать «тупым» перебором очень долго. За одиночный проход волны по карте путей, алгоритм находит оптимальный путь либо все равнозначные.

Примеров применения этого алгоритма в интернете тонны, в том числе и для коммивояжёра.

Примеров тонны, но этот алгоритм не даёт гарантировано правильного ответа. Вот что я пытался донести. Он даёт приближение, хорошее приближение. Но на абсолютно любом графе он не даёт гарантировано правильного ответа.

с этим соглашусь, чуть поторопился.

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

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

Допишу движок под андроид запущу пару прог на нём, а там может развлекалочкой займусь вычислительной.

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

Вау! Ты изобрёл алгоритм Дейкстры?

Что, он и тебя посчитал? Добро пожаловать в «клуб троллей».

Уже лучше :)

Волновой алгоритм даёт правильный ответ, я даже это не пытался оспорить. Но делает это медленно. Есть алгоритмы быстрее (если мы строим граф, то дейкстра очень хорош).

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

Не-не, у него волновой алгоритм

Да ладно, ничего страшного:)

Волновой алгоритм даёт правильный ответ, я даже это не пытался оспорить. Но делает это медленно. Есть алгоритмы быстрее (если мы строим граф, то дейкстра очень хорош).

Как по мне - это идентичные алгоритмы. просто дейкстр варьирует размер ячеек (так сказать размер ячейки - это расстояние до следующего разветвления)

Вообще Ринату я предлагал, если ему действительно было интересно, разобраться в принципе как работал мой интерпретатор для МК-61 и даже вместе с ним написать его заново.

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

Из-за этой так сказать вариации размера ячеек очень сильно меняется асимптотика, как ты можешь видеть.

Ну про ваши перепалки с интерпретаторами я ничего не знаю:)

задолбал ты своей асимптотикой :)

Тут не в этом дело, просто алгоритмы работают идентично.

Для каждой задачи размер ячеек выбирается отталкиваясь от условий задачи.

Где-то размер ячейки - это стоимость участка дороги, где-то расстояние до перекрёстка, где-то размер знакоместа в игре.

Суть работы алгоритма не меняется.

Волновой алгоритм, частный случай алгоритма дейкстра, узлы графа привязаны к центрам квадратов.

Про то, что волновой алгоритм это частный случай дейкстры, я не совсем уверен. Но в чём-то ты прав, да.

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

Я признался, что ошибся.

Но есть вероятность, что получится сделать что-то работоспособное в этом направлении. Надо запустить пару проектов в начале, потом развлекалочками займусь.

Тогда считаю спор исчерпаным :)

Как сделаешь, то кастани меня плиз - очень интересно палкой потыкать это.

Тогда считаю спор исчерпаным :)

Согласен.

Давай чтобы веселее было ещё чего нибудь обсудим? ;)

Хочешь интерпретатор с тобой напишем для МК-61? :-D

Как сделаешь, то кастани меня плиз - очень интересно палкой потыкать это.

Мне с текущими разработками долго разбираться.

Могу забыть про эту задачку.

Честно - даже не знаю, что такое МК-61. Я как курсовой писал уже интерпретатор для своего ЯП. Меня как-то не вдохновило сильно.

Меня как-то не вдохновило сильно.

Тут вдохновение приходит когда ты узнаёшь, что такое МК-61 :o)

Вот для вдохновения :) Интерпретатор языка для МК-61

А есть хороший учебник по матану, чтобы дифуры объяснялись языком для гидроцефалов на примерах, собачках, машинках, листиках, яблочках? )