Почему кошки так любят коробки

Жаль, что кошки не умеют говорить.

<зануда>Боюсь себе представить о чем мне придется говорить с некастрированным котом… А если еще и предположить, что кошки не могут быть умнее 5летнего ребенка. А потом обязательно появилась бы организация по защите прав кошек… Пусть уж лучше просто мяукают:)</зануда>

Радиоэлектроника, или как я начал её постигать

пишите дальше! но аналогии пожалуй действительно излишни

Сервис для определения имени абонента по телефонному номеру

у меня еще с 4.4 ( или еще раньше) на кастомах определяла откуда звонят

Samsung представляет SE790C — 34-дюймовый изогнутый монитор с разрешением Ultra WQHD

Вы меня не поняли, меня интересует именно ваше личное мнение о просмотре сериалов на таком широком экране, раздражают ли вас черные полосы по краям?

Samsung представляет SE790C — 34-дюймовый изогнутый монитор с разрешением Ultra WQHD

т.е. сериалы все-таки смотреть не очень удобно?

Samsung представляет SE790C — 34-дюймовый изогнутый монитор с разрешением Ultra WQHD

а сколько окон обычно держите открытыми? и не мешают ли полоски по бокам при просмотре фильмов/сериалов?
меня эти вопросы отпугивают от таких широких мониторов

Замена чипсета на материнской плате

такой вопрос: если чип на видюхе меняли, будут ли видны следы ремонта на обратной стороне видюхи?
имею в виду профессиональный ремонт

Вычислительная техника в Deutsches Museum

а есть ли эти фотографии в более высоком разрешении?

Замена чипсета на материнской плате

Клиент может вернуть ноутбук в 14-дневный срок,

это же сложная электронная техника, как я могу её просто так взять и вернуть без дефекта?

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

Решение задачи коммивояжера с помощью метода ветвей и границ

вы не правы. 5! = 120
а вот насчет расчетов дольше секунды: боюсь тут вы правы, где-то я допустил ошибку, но я её не вижу. даже если выводить только те листья, по которым прошелся алгоритм. архив с уменьшим деревом

Решение задачи коммивояжера с помощью метода ветвей и границ

данная матрица затрат — как раз таки яркий и лаконичный пример когда происходит полный перебор.
но если взять матрицу из примера 3 — то она решается за гораздо меньшее время. потому что в отличии от полного перебора были отсеяны наименее вероятные множества решений

Решение задачи коммивояжера с помощью метода ветвей и границ

пожалуй, в своем следующем посте я проведу приближенные исследования этой самой вероятности

Решение задачи коммивояжера с помощью метода ветвей и границ

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

Решение задачи коммивояжера с помощью метода ветвей и границ

добавил: n — кол-во элементов с максимальным штрафом

Решение задачи коммивояжера с помощью метода ветвей и границ

метода ветвей и границ? Вы можете с легкостью найти его в оригинале: A. H. Land and A. G. Doig. An automatic method of solving discrete programming problems, стр. 497-520.

Решение задачи коммивояжера с помощью метода ветвей и границ

Я гарантирую 100% правильное решение, иначе бы не стал писать это как решение задачи коммивояжера.
повторяюсь: я не утверждаю что алгоритм линеен, я утверждаю что он существенно быстрее полного перебора. возьмем к примеру мой график: даже отбросив последние значения (посчитав их ошибочными), и взяв за самое большее затраченное время 0.075с как время полного перебора, то самое наименьшее пусть будет 0.06с, что в несколько раз меньше максимального. а вероятность того, что матрица решится за время приблизительно в половину от максимального, достаточно высока, чтобы применять этот вместо полного перебора.
Насчет дальнейших возможных оптимизаций, которые вы предложили: они не будут гарантировать 100% правильное решения, но могут сэкономить время, но это совершенно другой разговор

Решение задачи коммивояжера с помощью метода ветвей и границ

зачем вы говорите о масштабах? речь идет именно о решении задачи коммивояжера, а не о получении равного (и правильного) или близкого (но неправильного) к равному правильного ответа к задачи Коммивояжера. Если речь бы шла именно о минимизации затрат времени и отсутствовала необходимость в 100% правильности ответа, то вы можете и обойтись делением на два подмножества. но это уже не было бы решением задачи коммивояжёра (во всех случаях, в конкретных ответы могли бы совпасть)

Решение задачи коммивояжера с помощью метода ветвей и границ

для отдельного случая взятого с потолка — можем по построенному дереву пройтись еще раз на наличие лишних ответвлений и сделать соответствующий вывод… либо мы можем сделать, то что сделал я: берем несколько случайных матриц, ищем для них решение нашей задачи, измеряем потраченное время. на основе этой статистики мы можем найти вероятность того, что случайное дерево окажется одним из тех, для которого решения будет занимать «линейное или близкое к этому время». тут еще надо не забывать что диапазон допустимых значений в матрице затрат, тоже будет влиять на эту вероятность.

Решение задачи коммивояжера с помощью метода ветвей и границ

1) оценка полиномиальное/линейное/экспоненциальное и т.д. «ставится» в случае самых наихудших условий, я упомянул что такое «линейное время» возможно в конкретных случаях, когда решение находится без возврата назад (т.е. не самых худших). и это ярко прослеживается на графике ( к сведению генерировались числа от 0 до 99)
2) исследования с большой матрицей проводил, именно поэтому там стоит галочка на то чтобы выводить дерево или нет. так как при очень больших размерах браузер попросту тормозил.

Решение задачи коммивояжера с помощью метода ветвей и границ

по каким показателям вы сравнивали полный перебор и метод ветвей и границ?
по времени — очень сильно проигрывает, так как задача в большинстве случаях может быть решена за линейное от размерности матрицы, или с небольшими лишними ответвлениями,
по памяти — либо немного выигрывает метод ветвей и границ, так как для листьев надо хранить только историю взятых или не взятых ребер, либо проигрывает если хранить все матрицы (чтобы сэкономить время)
upd: если вы считаете что самое важное — время, то лучше метод ветвей и границ, чем полный перебор