Ну а если говорить о практике, а не о математической теории — задача коммивояжера нерешаема уже для 20 локаций (по крайней мере на домашнем пека за разумное время).
Вы очень плохо информированы. Если откроете работу Костюка 2013г., то у него вроде написано про 100 вершин за минуту. Ну, и посмотрите работу 2017г, начиная с 8 слайда (за минуту 150 вершин последовательный алгоритм).
Если вы настаиваете, что вам известно полиномиальное решение задачи коммивояжера, то даже не тратьте время на то, чтобы писать его здесь — сразу научную публикацию делайте.
Я вам уже несколько раз сказал, что я решаю не задачу коммивояжера, а ту задачу которая описана в этой статье. И она задачей коммивояжера не является. Но, видимо, мне действительно стоит прекратить писать здесь, т.к. мы с вами друг друга не слышим.
Никакой динамики для коммивояжера (ну и для рюкзака, конечно же) не существует.
Задача состоит в том, что вам дано N вершин, и вы должны найти кратчайший вариант их обхода. И как не меняй формулировку — это задача, эквивалентная задаче коммивояжера.
Даже если рассмотреть ваш подход к решению задачи, то цитируемая мной фраза ошибочна. На самом деле, у вас серия из K задач коммивояжера на подграфах исходного графа с размерностями N1, N2,… ,NK. И, совершенно очевидно, что для каждого следующего подграфа будут пути, которые вы уже рассматривали.
В качестве аналога рассмотрите задачу о рюкзаке. Ее можно решать полным перебором, но если делать это правильно (динамикой), т.е. повторно не рассматривать уже рассмотренные частичные решения, то вы получаете полиномиальный алгоритм.
Поэтому я настаиваю, что если правильно организовать перебор, то решение полиномиально.
Поскольку никакой информации о характере множества ограничений у нас нет, то мы остаемся в ситуации общего положения
Если Вы не смогли доказать, что ограничения достаточно строгие, чтобы она перестала быть NP-complete, то это не значит что это не так. Если докажете, что она сводится к любой NP-полной задаче, то соглашусь, а пока ничего не доказано, спорить бесполезно.
Задача коммивояжера с ограничениями может быть совсем даже полиномиальной. Приведу вырожденный пример не про спидран: пусть требуется построить гамильтонов путь так, чтобы в нем вершины с меньшими номерами предшествовали вершинам с большими номерами. Таким образом, нужно либо доказывать, что эта задача сводится к коммивояжеру на полном графе, либо оговорится, что она видится таковой.
В любом случае, спасибо за разъяснения. Теперь вижу коммивояжера, но я бы так не решал эту задачу.
Проблема заключается в том, что поиск в графе состояний — NP-complete
Утверждение в целом не верно, могу привести примеры задач, где все вполне полиномиально. Для задачи коммивояжера — верно. Но посмотрите на мою формулировку задачи: я решаю не задачу коммивояжера.
Вижу ваш комментарий выше, в котором говорится почему автор решает коммивояжера. Буду думать.
Я по прежнему не вижу на каком графе автор планировал решать задачу коммивояжера. У игрока нет цели обойти все, как у коммивояжера. У него есть цель: выполнить набор линеек квестов, которые пересекаются, за минимальное время. Можете пояснить где тут гамильтонов цикл?
mayorovp чуть выше описал именно то, то я имел ввиду. Сначала построим Декартово произведение графов. Т.е. строим граф состояний, в котором вершина соответствует географической локации, набору выполненных и взятых квестов, а дуга связывает две вершины, если можно выполнить элементарное действие (перемещение, сдача квеста, взятие квеста и пр), которое позволит перейти из одного состояния в другое. Дальше Дейкстра на новом графе.
Узлы графа квестовых зависимостей можно обходить не по рёбрам этого графа.
Фактически, вы сейчас сказали, что на графе квестов дуги отражают не все зависимости. Тогда совершенно не понятно зачем он нужен, если он не отражает всю картину.
Тут и появляется задача коммивояжера.
Где тут? У автора это следует из задачи перебора всех правильных нумераций на графе зависимостей, который по вашим словам не все зависимости отражает. А у вас коммивояжер вообще из ниоткуда появляется. Если вы поняли автора, укажите граф, на котором коммивояжера запускаем.
Вы, видимо не поняли, что речь не о пути в графе квестов, а о пути в игровом мире.
Это как раз понятно, что мы хотим сократить время прохождения в итоге. Но для этого нужно выполнить квесты! Напишу как я понимаю эту задачу в постановке автора. Каждый квест переводит персонажа в некоторое состояние описываемое числовым вектором. У автора есть два графа. Один геометрический и описывает локации и расстояния между ними, второй граф зависимостей по квестам. Автор пытается осуществить одновременное перемещение по обоим графам так, чтобы на втором прийти в целевую вершину, а в первом пройти минимальный путь. Такая формулировка задачи понятна, исходя из моих знаний о ММОРПГ. Но в такой постановке ее решать сложно и странно. Я уверен, что могу переформулировать задачу так, что она будет решаться алгоритмом Дейкстры, т.е. детерминировано без ML, отжигов и пр. Но сначала я хочу убедиться, что правильно понимаю задачу, и автор понимает о чем пишет.
1. А можно пояснить каким образом задача о получении всех правильных нумераций (или как вы говорите топологических сортировок) сводится к задаче коммивояжера?
2. Дано: ациклический граф квестов. Найти: кратчайшие пути из заданного источника (у нас 0 фракций) в набор стоков (мы во всех фракциях). Зачем отжиг, если эта задача решается за O(M)? Поправьте, если не понял Вашу формулировку задачи.
Во-первых, не понятно почему среди российских конференций нет крупнейшей бесплатной DataFest.
Во-вторых, хочу поделиться своими впечатлениями: opentalks.ai гораздо информативнее, чем Deep Learning in Retail (+ еще две от REWORK). Был в этом году на обеих, с точки зрения PR своего продукта, наверное, Deep Learning in Retail сильнее, а вот контент, конечно, попроще. Для сравнения, открытие второго дня на opentalks.ai — Дэвид Ян с интересными идеями, хоть может и не c точки зрения разработчика, но этого тоже там было достаточно. Открытие первого дня в Deep Learning in Finance — рассказ об интерпретируемости моделей (не помню спикера) на примере логрегрессии и деревьев принятия решений, затем упомянуты полносвязные нейросети без деталей. Думайте сами, что вам интереснее в следующем году.
karaboz То что не учитываются аномальные зп и только последняя из введенных прекрасно. А как быть с фактором времени? Если я введу свою зп сегодня и не буду актуализировать ее в сервисе, скажем, 5 лет, то ваша система все еще будет ее учитывать при расчетах?
Прочел первую статью из серии «Необразованная молодежь», вторую статью, третью… И с каждой статьей просто «обалдеваю» как авторы выражают именно мои мысли. Средние проскочил и глянул на эту статью. Автор тебе 1000 лайков! Уверен, что это мало. Лайков на хабре ставить не имею права даже в количестве одна штука. Но виртуально, я тебе 1000 лайков ставлю.
Я в своем городе миллионнике и университете федеральнике, уже не один раз говорил, что проблема в школе. У нас не будет годных студентов ИТ-шников, пока мы не начнем отчислять неумелых студентов и массово готовить школьников. Да, у нас есть доп образование при ВУЗе и даже очень приличное, но оно не массово. А нужно поднять грамотность по всему городу, чтобы появилась конкуренция и грамотные потенциальные абитуриенты. Я устал бороться за образование в лицее в 2013г…
Удачи во всем uchitel! Сделай суперучебник и пусть у тебя все получается!
99% работают с 1% от всего функционала git. Этот 1% полностью есть и в subversion. Другое дело, что git огромный конструктор, использование которого командой необходимо ограничивать. На C++ тоже можно выстрелить в ногу, но это не значит, что его не надо изучать и использовать.
Вы оспариваете только мою последнюю фразу, при этом заявляете, что я не прав в целом. Все что я сказал про бранчи — верно и «код мастера» — это чушь. А если Вы не согласны с утверждением про наследование проблемы, код коммитов D, E в студию, плиз.
После мёржа в мастер коммиты какими были в ветке, такими и остались. Вы думаете код и мастера в них как-то проникнет? :)
На мой взгляд, вы не понимаете фундаментальное понятие «ветка в git». Ветка — это всего лишь ссылка на какой-то коммит. Алиас, указатель, ссылка — не принципиально. Главное, что у ветки нет коммитов. Удалите ветку, но коммиты останутся.
Что значит «код мастера»? Мастер — это ветка, у нее нет кода. У цепочки коммитов, начинающейся с коммита, на который ссылается мастер будет только один коммит, содержащий патчи, которые разработчик в своей ветке делал. Это будет мердж коммит. Он будет содержать проблему, и у него будет «второй родительский» коммит, который со всеми своими предками содержит проблему. И фиксить в мастере вы будете мердж коммит, а не ветку разработчика.
asterix78rus я тоже не согласен с тезисом о вреде ребейза, но вы товарищ поспешили с выводами. Во-первых, автор не школьник и входит в топ10 по рейтингу хабра. Во-вторых, статья не заказная, а переводная. Голосование в конце полезное, я наконец понял, что отношусь к негодяйским (так переводится git) меньшинствам. Ну, а комменты для того и нужны, чтобы показать другую сторону медали. Хотя тут уже треш и новичок маловероятно прочтет наш с вами диалог.
Да. Если вы задаете этот вопрос, значит вы не поняли, что я предложил. Для продолжения дискуссии необходимо, чтобы вы попробовали сделать следующее: git rebase -i --onto branch_to branch_from_start branch_from_end
Уточню: левая граница исключена, правая включена, т.е. branch_from_start не войдет в цепочку ребейза. Далее, в любимом редакторе (я, надеюсь, вы настраиваете git для использования любимого редактора) верхний коммит оставляем pick, остальные ставим squash. Сохраняем, наблюдаем, смотрим результат.
После rebase со squash вы теряете историю.
Попробуйте сделать то, что я описал Выше, а потом поясните какую историю я теряю. Но на всякий случай напишу, что у меня с историей.
Мое видение следующее: ветки разработки должны содержать всё, dev должен содержать коммиты, соответствующие завершенным изменениям (фиксам и фичам), master должен содержать только релизы. Поиск проблемы состоит из последовательно поиска релиза (обычно мы и так знаем в каком релизе проблемы), затем поиска фичи/фикса в dev, затем анализ ветки разработчика. При этом последнее не всегда необходимо, т.к. стоит править именно фичу целиком, а не отдельный ее коммит.
Кстати, а любители «железнодорожных путей» и неизменной истории в курсе, что иногда git-репо приходится архивировать? Или например, о том, что крупные компании не могут использовать git, т.к. он не тянет их большую историю?
> Есть — Git merge. Простой процесс в один этап, при котором все конфликты разрешаются в единственном коммите. Получившийся коммит ясно обозначает точку интегрирования двух веток, а наша история отразит не только что произошло, но и когда.
Этот аргумент выглядит главным в статье. Так вот, тоже самое достигается rebase со squash и сохранением ветки feature (вообще не понял зачем автор решил ее удалить). При этом мы избавляемся от «железных дорог».
Вы очень плохо информированы. Если откроете работу Костюка 2013г., то у него вроде написано про 100 вершин за минуту. Ну, и посмотрите работу 2017г, начиная с 8 слайда (за минуту 150 вершин последовательный алгоритм).
Я вам уже несколько раз сказал, что я решаю не задачу коммивояжера, а ту задачу которая описана в этой статье. И она задачей коммивояжера не является. Но, видимо, мне действительно стоит прекратить писать здесь, т.к. мы с вами друг друга не слышим.
Для рюкзака существует. Смиритесь.
Даже если рассмотреть ваш подход к решению задачи, то цитируемая мной фраза ошибочна. На самом деле, у вас серия из K задач коммивояжера на подграфах исходного графа с размерностями N1, N2,… ,NK. И, совершенно очевидно, что для каждого следующего подграфа будут пути, которые вы уже рассматривали.
В качестве аналога рассмотрите задачу о рюкзаке. Ее можно решать полным перебором, но если делать это правильно (динамикой), т.е. повторно не рассматривать уже рассмотренные частичные решения, то вы получаете полиномиальный алгоритм.
Поэтому я настаиваю, что если правильно организовать перебор, то решение полиномиально.
Если Вы не смогли доказать, что ограничения достаточно строгие, чтобы она перестала быть NP-complete, то это не значит что это не так. Если докажете, что она сводится к любой NP-полной задаче, то соглашусь, а пока ничего не доказано, спорить бесполезно.
В любом случае, спасибо за разъяснения. Теперь вижу коммивояжера, но я бы так не решал эту задачу.
Утверждение в целом не верно, могу привести примеры задач, где все вполне полиномиально. Для задачи коммивояжера — верно. Но посмотрите на мою формулировку задачи: я решаю не задачу коммивояжера.
Вижу ваш комментарий выше, в котором говорится почему автор решает коммивояжера. Буду думать.
Фактически, вы сейчас сказали, что на графе квестов дуги отражают не все зависимости. Тогда совершенно не понятно зачем он нужен, если он не отражает всю картину.
Где тут? У автора это следует из задачи перебора всех правильных нумераций на графе зависимостей, который по вашим словам не все зависимости отражает. А у вас коммивояжер вообще из ниоткуда появляется. Если вы поняли автора, укажите граф, на котором коммивояжера запускаем.
Это как раз понятно, что мы хотим сократить время прохождения в итоге. Но для этого нужно выполнить квесты! Напишу как я понимаю эту задачу в постановке автора. Каждый квест переводит персонажа в некоторое состояние описываемое числовым вектором. У автора есть два графа. Один геометрический и описывает локации и расстояния между ними, второй граф зависимостей по квестам. Автор пытается осуществить одновременное перемещение по обоим графам так, чтобы на втором прийти в целевую вершину, а в первом пройти минимальный путь. Такая формулировка задачи понятна, исходя из моих знаний о ММОРПГ. Но в такой постановке ее решать сложно и странно. Я уверен, что могу переформулировать задачу так, что она будет решаться алгоритмом Дейкстры, т.е. детерминировано без ML, отжигов и пр. Но сначала я хочу убедиться, что правильно понимаю задачу, и автор понимает о чем пишет.
2. Дано: ациклический граф квестов. Найти: кратчайшие пути из заданного источника (у нас 0 фракций) в набор стоков (мы во всех фракциях). Зачем отжиг, если эта задача решается за O(M)? Поправьте, если не понял Вашу формулировку задачи.
PS: про морроувинд почти ничего не знаю
Во-вторых, хочу поделиться своими впечатлениями: opentalks.ai гораздо информативнее, чем Deep Learning in Retail (+ еще две от REWORK). Был в этом году на обеих, с точки зрения PR своего продукта, наверное, Deep Learning in Retail сильнее, а вот контент, конечно, попроще. Для сравнения, открытие второго дня на opentalks.ai — Дэвид Ян с интересными идеями, хоть может и не c точки зрения разработчика, но этого тоже там было достаточно. Открытие первого дня в Deep Learning in Finance — рассказ об интерпретируемости моделей (не помню спикера) на примере логрегрессии и деревьев принятия решений, затем упомянуты полносвязные нейросети без деталей. Думайте сами, что вам интереснее в следующем году.
Я в своем городе миллионнике и университете федеральнике, уже не один раз говорил, что проблема в школе. У нас не будет годных студентов ИТ-шников, пока мы не начнем отчислять неумелых студентов и массово готовить школьников. Да, у нас есть доп образование при ВУЗе и даже очень приличное, но оно не массово. А нужно поднять грамотность по всему городу, чтобы появилась конкуренция и грамотные потенциальные абитуриенты. Я устал бороться за образование в лицее в 2013г…
Удачи во всем uchitel! Сделай суперучебник и пусть у тебя все получается!
Т.е. переписать историю? Вы же вроде против этого.
Пример в студию.
Вы оспариваете только мою последнюю фразу, при этом заявляете, что я не прав в целом. Все что я сказал про бранчи — верно и «код мастера» — это чушь. А если Вы не согласны с утверждением про наследование проблемы, код коммитов D, E в студию, плиз.
На мой взгляд, вы не понимаете фундаментальное понятие «ветка в git». Ветка — это всего лишь ссылка на какой-то коммит. Алиас, указатель, ссылка — не принципиально. Главное, что у ветки нет коммитов. Удалите ветку, но коммиты останутся.
Что значит «код мастера»? Мастер — это ветка, у нее нет кода. У цепочки коммитов, начинающейся с коммита, на который ссылается мастер будет только один коммит, содержащий патчи, которые разработчик в своей ветке делал. Это будет мердж коммит. Он будет содержать проблему, и у него будет «второй родительский» коммит, который со всеми своими предками содержит проблему. И фиксить в мастере вы будете мердж коммит, а не ветку разработчика.
Да. Если вы задаете этот вопрос, значит вы не поняли, что я предложил. Для продолжения дискуссии необходимо, чтобы вы попробовали сделать следующее:
git rebase -i --onto branch_to branch_from_start branch_from_endУточню: левая граница исключена, правая включена, т.е. branch_from_start не войдет в цепочку ребейза. Далее, в любимом редакторе (я, надеюсь, вы настраиваете git для использования любимого редактора) верхний коммит оставляем pick, остальные ставим squash. Сохраняем, наблюдаем, смотрим результат.
Попробуйте сделать то, что я описал Выше, а потом поясните какую историю я теряю. Но на всякий случай напишу, что у меня с историей.
Мое видение следующее: ветки разработки должны содержать всё, dev должен содержать коммиты, соответствующие завершенным изменениям (фиксам и фичам), master должен содержать только релизы. Поиск проблемы состоит из последовательно поиска релиза (обычно мы и так знаем в каком релизе проблемы), затем поиска фичи/фикса в dev, затем анализ ветки разработчика. При этом последнее не всегда необходимо, т.к. стоит править именно фичу целиком, а не отдельный ее коммит.
Кстати, а любители «железнодорожных путей» и неизменной истории в курсе, что иногда git-репо приходится архивировать? Или например, о том, что крупные компании не могут использовать git, т.к. он не тянет их большую историю?
Этот аргумент выглядит главным в статье. Так вот, тоже самое достигается rebase со squash и сохранением ветки feature (вообще не понял зачем автор решил ее удалить). При этом мы избавляемся от «железных дорог».