Как стать автором
Обновить
24
0

Пользователь

Отправить сообщение
Уважаемый webmasterx, а разве оценка сложности qsort o(n*log(n)) — это худший случай?
Худшее время qsort'a — квадрат…
Задача коммивояжера до данного момента не имеет решения, которое бы хотя бы за полиномиальное, не то что линейное, время находили бы решение, гарантированно отстоящее не более чем на некое эпсилон от оптимального.

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

А серьезно — просто попробуйте запуститься на графе всяко побольше, чем 15х15.
и вопрос тут далеко не в памяти. первостепенное значение — время.
Ну при таком подходе лучший вариант — честный перебор. Честный перебор — экспоненциальное время. Потому задача NP-тяжелая.
Экспоненциальное время на достаточно больших задачах настолько большое, что не вычислимо на современных мощностях за адекватное время(хотя бы десяток лет)
Отсюда приходит идея как минимум сокращения вариантов перебора — ввод различных эвристик и т.д.
Это автоматически перечеркивает гарантию нахождения точного решения, ибо не все варианты перебора просмотрены.

Точное решение находится либо потому что повезло, либо размер задачи невелик.
upd. а не пробовали на большом графе? не 15х15. Разделение на 2n на каждом шаге может привести к очень большому числу одновременно просматриваемых ветвей
плюс на большом графе вероятность попадания в «плохую ситуацию», описанную Вами в контр-примере в начале поста, уменьшается.

и я, честно, не понимаю формулировки «неправильный ответ». В любом случае это алгоритм приближенного решения, а не точного. Понятно, что на небольших задачах возможно его улучшение. Вопрос в сходимости приближенного алгоритма к точному ответу на больших задач, где точное решение за адекватное время невозможно.
Я заметил этот факт некоторое время назад :)
Вот пост, рассказывающий, как я обошел эту проблему
habrahabr.ru/post/229597/
у нас есть идеи и задумки по этому поводу, вы прям в точку =)
ограниченные, протокол менять нельзя
протокол закрыт, есть API.
ну хотя бы открыли возможность загрузки кастомного рома.
потому что буквально месяц назад загрузчик на планшетах и телефонах сони был закрыт, и мне с моим tablet s пришлось забыть о JB =(
пользуюсь больше месяца, до этого были smartwatch1, ошибки исправили, добавили возможность отключить bluetooth на часах и жить дольше как обычные наручные, но приложений по-прежнему немного, циферблатов на выбор — всего пять, и то 4 из них попарно отличаются только инвертацией цветов и наличием даты. открытый проект для кастомных ромов для SW2 не поражает количеством вариантов. документация, однако, неплохая
говорю же-задача стояла накодить.
для оценки результатов использовался результат жадины.
идея использовать оптимальное решение, данное линейным алгоритмом хороша, но имеет, на мой взгляд один минус-
мои алгоритмы сильно зависят от графа, и поэтому на разных графах будут показывать разные результаты относительно оптимального решения, но вот жадина-то тоже зависит от графа, поэтому относительно жадины мне показалось рассматривать как-то логичнее, проще анализировать
да, согласен, в первоначальном варианте ошибка, верно — NP-тяжелая или NP-трудная. спасибо за указание
круто, посмотрю утром, когда будет время
Что может быть проще пары while'ов? Если же сравнивать длину кода, то я за этим не гнался.Задача была написать понятный код, который говорит сам за себя. Поэтому кроме кода мало чего есть. Думается мне, что человек, знакомый с деревом Фенвика, легко поймет и эту его модификацию.

Про инициализацию — все равно пока не думаю, что так возможно.
Нет, на sparse это не сильно похоже.Ну только с очень-очень большой долей абстракции.
задача была не получить ответ, а накодить алгоритм. я думаю, за три дня я бы не накодил то, что установило рекорд
я недавно находил, что все-таки муравьиная колония выигрывает сейчас
вот именно, что префикс/суффикс тривиален.
когда я говорил кому-то про дерево фенвика для максимума, все именно это и говрят — префикс-суффикс.
а вот на отрезке это нечто, мало кому знакомое
Правописание исправил, спасибо указание.
Про сравнение со ST и дерево отрезков — это есть в статье, на которую я ссылаюсь.
Про реализацию. Хм, Вы первый человек от которого я слышу, что дерево отрезков проще.Мнение большинства, вроде бы, ровно наоборот.=) Да, оно может быть, чуть-чуть понятнее, но и фенвик не сложный.
Инициализация за линию? что-то мне не приходит пока в голову, как
Про старший бит — мы же идем с двух концов, и нам надо точно знать как они пересекутся
скорее, можно рассматривать этот пост как дополнение к основному посту про дерево Фенвика

Информация

В рейтинге
Не участвует
Откуда
Москва, Москва и Московская обл., Россия
Работает в
Зарегистрирован
Активность