Комментарии 10
Было же уже
"… грустно, что я потерял эту задачу,"
а в чем проблема, поставь следующую себе задачу: улучшить свой и последующие алгоритмы на (0,2^-30%).
а в чем проблема, поставь следующую себе задачу: улучшить свой и последующие алгоритмы на (0,2^-30%).
Может мне кто-нибудь объяснит.
Если строить замкнутый маршрут как резинку, которую натягивают на палочки, добавлять в нее новые точки по одному, для каждой точки подбирать ребро в которое она будет вставлена с наименьшим штрафом, с наименьшим натяжением.
Почему этот маршрут не будет лучшим?
Если строить замкнутый маршрут как резинку, которую натягивают на палочки, добавлять в нее новые точки по одному, для каждой точки подбирать ребро в которое она будет вставлена с наименьшим штрафом, с наименьшим натяжением.
Почему этот маршрут не будет лучшим?
Потому что можно подобрать такую очерёдность вставления палочек, которая приведёт к генерации очень затейливого маршрута.
Потому, что в том, что вы описали, нет описания того, как именно это делать в деталях.
В частности, первоначальный набор точек, если я правильно понял — это углы минимального выпуклого многоугольника, содержащего все точки. Хорошо. В каком порядке добавлять следующие точки? Ладно, допустим, берём любую ближайшую. Хорошо. Допустим, это действительно оптимальный маршрут для случая, когда цена поездки определяется исключительно расстоянием по прямой.
Но тут есть нюанс: это ОЧЕНЬ частный случай задачи коммивояжера.
В общем же случае, не только цена никак не связана с расстоянием, но есть и дополнительные ограничения, такие, например, что при путешествии между городами А и Б цена в одну сторону отличается от цены в другую, прямой переезд между конкретными городами может быть вообще недоступен в одну или обе стороны
В частности, первоначальный набор точек, если я правильно понял — это углы минимального выпуклого многоугольника, содержащего все точки. Хорошо. В каком порядке добавлять следующие точки? Ладно, допустим, берём любую ближайшую. Хорошо. Допустим, это действительно оптимальный маршрут для случая, когда цена поездки определяется исключительно расстоянием по прямой.
Но тут есть нюанс: это ОЧЕНЬ частный случай задачи коммивояжера.
В общем же случае, не только цена никак не связана с расстоянием, но есть и дополнительные ограничения, такие, например, что при путешествии между городами А и Б цена в одну сторону отличается от цены в другую, прямой переезд между конкретными городами может быть вообще недоступен в одну или обе стороны
Скажу больше, любые, естественно критичные (то есть далеко не все) не оптимальные не логичные алгоритмы будут быстрее самые оптимальных строго логичных по алгоритмам сделанных. На самом деле я не совсем понял, что тут написано, да и классическую задачу коммивояжа, но это не значит что я не могу сделать такой вывод.
И да, недавно ученые доказали что «эффект бабочки» не такой уж глобальный, что собственно и так было интуитивно понятно. Ну как минимум мне и уже лет пять или больше. Что никакое локальное событие не может повлиять на глобальные процессы. Не знаю, тут проблема в формализации или в чём, потому как в оригинальной задаче убийство бабочки повлияло на то что вымерли или не вымерли динозавры, а вот здесь и сейчас происходят войны с десятками смертей каждый день от бомб, как это повлияет на город Москву или Санкт-Петербург? Максимум, максимум, повторяю это может быть отголосок того, что иммигрант от туда приедет в тот район где я живу и совершит / или не совершит что то незаконное. Это можно сравнить от осколка от гранаты, который может случайно задеть одну молекулу за тысячи километров от места взрыва. Но это не эффект бабочки. Так и тут. Конкретно про коммивояж мне сложно сказать, но локальные оптимальные алгоритмы всегда будут быстрее общих хорошо описанных общих алгоритмов.
И да, недавно ученые доказали что «эффект бабочки» не такой уж глобальный, что собственно и так было интуитивно понятно. Ну как минимум мне и уже лет пять или больше. Что никакое локальное событие не может повлиять на глобальные процессы. Не знаю, тут проблема в формализации или в чём, потому как в оригинальной задаче убийство бабочки повлияло на то что вымерли или не вымерли динозавры, а вот здесь и сейчас происходят войны с десятками смертей каждый день от бомб, как это повлияет на город Москву или Санкт-Петербург? Максимум, максимум, повторяю это может быть отголосок того, что иммигрант от туда приедет в тот район где я живу и совершит / или не совершит что то незаконное. Это можно сравнить от осколка от гранаты, который может случайно задеть одну молекулу за тысячи километров от места взрыва. Но это не эффект бабочки. Так и тут. Конкретно про коммивояж мне сложно сказать, но локальные оптимальные алгоритмы всегда будут быстрее общих хорошо описанных общих алгоритмов.
Конкретно про коммивояж мне сложно сказать, но локальные оптимальные алгоритмы всегда будут быстрее общих хорошо описанных общих алгоритмовПроблема в том, что не существует этих локальных оптимальных алгоритмов в перечисленных областях, потому как пытаясь их создать, рано или поздно понимаешь, что решаешь всё ту же задачу коммивояжера. Зачастую они ещё и выглядят запутанней
недавно ученые доказали что «эффект бабочки» не такой уж глобальный, никакое локальное событие не может повлиять на глобальные процессы. тут проблема в формализации или в чём в оригинальной задаче убийство бабочки повлияло на то что вымерли или не вымерли динозавры, а вот здесь и сейчас происходят войны с десятками смертей каждый день от бомб, как это повлияет на город Москву или Санкт-Петербург?В оригинальной задаче убийство конкретной бабочки повлияло на динозавров, при том что убийство кучи динозавров никак ни на что не влияло.
Последнее можно рассматривать как раз как войны с десятками смертей, которые ни на что не влияют. А вот первое можно рассматривать как съеденную китайцем мышь, допустим.
Не уверены о каком доказательстве Вы говорите, но нам представляется крайне сомнительным, что никакое отдельно взятое событие не может повлиять на ход истории. В конце концов слишком многие изобретения делались случайно.
если каждый город в сети имеет чётное количество соединений, то рёбра сети должны образовывать замкнутый маршрут
Но ведь они могут образовывать несколько замкнутых маршрутов, не связанных между собой…
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Как был побит рекорд в решении задачи коммивояжёра