Comments 48
Это безумно интересно! Неожиданное и изящное применение мат.аппарата.
А игроки потом прыгают по горам и бегают голышом по полям нетчей.
Если не надо никуда бежать, то все квесты проходятся в 100500 раз быстрее и соответсвенно быстрее надоедают/их надо больше.
Как бы разнесены в пространстве они СПЕЦИАЛЬНО.
Только вот квесты типа перейти через улицу, отнести письмо, вернутся назад и полочить 1опыта еще быстрее надоедают.
А фаст тревел делаются для смены локаций квестов, а не для «более быстрого прохождения».
Ничто не надоедает больше, чем бессмысленная беготня с одного конца карты на другой.
В морровинде есть квесты паломника. Один из них именно такой. Нужно пересечь всю карту, ни с кем не разговаривая.
Одного такого квеста как раз достаточно.
P.S. На карте не отмечено побережье Шеогората.
Вообще там много эксплойтов: http://en.uesp.net/wiki/Morrowind:Cheats
2. Дано: ациклический граф квестов. Найти: кратчайшие пути из заданного источника (у нас 0 фракций) в набор стоков (мы во всех фракциях). Зачем отжиг, если эта задача решается за O(M)? Поправьте, если не понял Вашу формулировку задачи.
PS: про морроувинд почти ничего не знаю
Граф квестов — это граф зависимостей — правил, что можно делать после чего. Но набор этих правил не полный, поэтому есть варианты и их много.
Каждое действие происходит в какой-то локации. Несколько действий могут быть в одной локации, локации могут быть далеко и близко (по времени перемещения).
Не уверен, что ясно выразился. Узлы графа квестовых зависимостей можно обходить не по рёбрам этого графа. И таких обходов очень много. Тут и появляется задача коммивояжера.
Узлы графа квестовых зависимостей можно обходить не по рёбрам этого графа.
Фактически, вы сейчас сказали, что на графе квестов дуги отражают не все зависимости. Тогда совершенно не понятно зачем он нужен, если он не отражает всю картину.
Тут и появляется задача коммивояжера.
Где тут? У автора это следует из задачи перебора всех правильных нумераций на графе зависимостей, который по вашим словам не все зависимости отражает. А у вас коммивояжер вообще из ниоткуда появляется. Если вы поняли автора, укажите граф, на котором коммивояжера запускаем.
Вы, видимо не поняли, что речь не о пути в графе квестов, а о пути в игровом мире.
Это как раз понятно, что мы хотим сократить время прохождения в итоге. Но для этого нужно выполнить квесты! Напишу как я понимаю эту задачу в постановке автора. Каждый квест переводит персонажа в некоторое состояние описываемое числовым вектором. У автора есть два графа. Один геометрический и описывает локации и расстояния между ними, второй граф зависимостей по квестам. Автор пытается осуществить одновременное перемещение по обоим графам так, чтобы на втором прийти в целевую вершину, а в первом пройти минимальный путь. Такая формулировка задачи понятна, исходя из моих знаний о ММОРПГ. Но в такой постановке ее решать сложно и странно. Я уверен, что могу переформулировать задачу так, что она будет решаться алгоритмом Дейкстры, т.е. детерминировано без ML, отжигов и пр. Но сначала я хочу убедиться, что правильно понимаю задачу, и автор понимает о чем пишет.
Как я понял, автор считает эту задачу задачей коммивояжера с дополнительными ограничениями.
Также автор отмечает, что эти дополнительные ограничения сокращают пространство решений NP-полной задачи коммивояжера недостаточно сильно. Кроме того. для упрощения задачи автор неоднократно вводил упрощения и условности, которые, строго говоря, могли оставить за пределами рассмотрения ряд претендентов на оптимальное решение.
Мне кажется вы правильно понимаете задачу и мне очень интересно как вы сведёте её к алгоритму дейкстры не потеряв потенциально более эффективных путей.
Единственная сложность — как раз с заклинанием телепортации, но именно его-то автор еще не рассматривал.
К сожалению такое объединение нерационально, так как для любой локации у нас может быть произвольный набор выполненных квестов.
В худшем случае в едином графе будет (количество локаций)*2^(количество квестов) вершин.
В любом случае, искать кратчайший путь на этом графе намного проще чем решать задачу коммивояжера на нем же.
Я по прежнему не вижу на каком графе автор планировал решать задачу коммивояжера. У игрока нет цели обойти все, как у коммивояжера.
Каждое прохождение из графа зависимостей дает подграф соответствующих вершин в геометрическом графе локаций. В этом подграфе и решается задача коммивояжера (с ограничениями — например, может быть фиксировано, что вершины из множества А должны быть посещены строго после вершин Б). В данном случае задач коммивояжера решается много (по одной для каждого пути в графе зависимостей квестов). Надо для всех этих задач найти ту, в которой обход будет минимальным, и потом, с-но, сам обход.
В любом случае, спасибо за разъяснения. Теперь вижу коммивояжера, но я бы так не решал эту задачу.
Задача коммивояжера с ограничениями может быть совсем даже полиномиальной.
Это все зависит от конкретного множества ограничений. Может, у вас останется всего один возможный путь (и считать уже, собственно, нечего), а может — множество пустое, и тогда мы получаем неограниченную задачу. Поскольку никакой информации о характере множества ограничений у нас нет, то мы остаемся в ситуации общего положения, то есть NP-complete.
Теперь вижу коммивояжера, но я бы так не решал эту задачу.
А как? В том и смысл NP-complete задач, что единственный способ их решения — это перебор. Других вариантов просто не существует.
Поскольку никакой информации о характере множества ограничений у нас нет, то мы остаемся в ситуации общего положения
Если Вы не смогли доказать, что ограничения достаточно строгие, чтобы она перестала быть NP-complete, то это не значит что это не так. Если докажете, что она сводится к любой NP-полной задаче, то соглашусь, а пока ничего не доказано, спорить бесполезно.
Если Вы не смогли доказать, что ограничения достаточно строгие, чтобы она перестала быть NP-complete, то это не значит что это не так.
Вы, видимо, не в курсе, как считается сложность. Именно что значит. Любая задача имеет сложность Х, пока не доказано, что она может быть решена быстрее. То есть это, наоборот, надо доказывать, что любые ограничения будут достаточно строгими, чтобы задачу упростить.И если существует хоть одно ограничение, которое сводит к задачу к NP-complete — то она NP-complete. И у нас такое ограничение есть — это пустое ограничение, так что все доказано математически строго :)
Ну а если говорить о практике, а не о математической теории — задача коммивояжера нерешаема уже для 20 локаций (по крайней мере на домашнем пека за разумное время). То есть нам во время выполнения надо иметь 20 локаций с независимыми посещениями, чтобы показать, что беда. У нас в практически любом прохождении будет заведомо больше таких локаций.
Ну а если говорить о практике, а не о математической теории — задача коммивояжера нерешаема уже для 20 локаций (по крайней мере на домашнем пека за разумное время).
Вы очень плохо информированы. Если откроете работу Костюка 2013г., то у него вроде написано про 100 вершин за минуту. Ну, и посмотрите работу 2017г, начиная с 8 слайда (за минуту 150 вершин последовательный алгоритм).
Т.е. строим граф состояний, в котором вершина соответствует географической локации
Проблема заключается в том, что поиск в графе состояний — NP-complete. Задачу коммивояжера ведь тоже можно рассмотреть, как поиск кратчайшего пути в графе состояний коммивояжера (от исходного состояния к состоянию, в котором посещены все вершины), которая решается Дийсктрой. Но это не дает ускорения в решении исходной задачи.
Проблема заключается в том, что поиск в графе состояний — NP-complete
Утверждение в целом не верно, могу привести примеры задач, где все вполне полиномиально. Для задачи коммивояжера — верно. Но посмотрите на мою формулировку задачи: я решаю не задачу коммивояжера.
Вижу ваш комментарий выше, в котором говорится почему автор решает коммивояжера. Буду думать.
Утверждение в целом не верно
Оно в целом верно.
Но посмотрите на мою формулировку задачи: я решаю не задачу коммивояжера.
Именно ее вы и решаете. От того, что вы переформулировали задачу коммивояжера в задачу поиска кратчайшего пути в графе состояний, как выше я сделал в моем посте — ее сложность не меняется.
Задача состоит в том, что вам дано N вершин, и вы должны найти кратчайший вариант их обхода. И как не меняй формулировку — это задача, эквивалентная задаче коммивояжера.
Задача состоит в том, что вам дано N вершин, и вы должны найти кратчайший вариант их обхода. И как не меняй формулировку — это задача, эквивалентная задаче коммивояжера.
Даже если рассмотреть ваш подход к решению задачи, то цитируемая мной фраза ошибочна. На самом деле, у вас серия из K задач коммивояжера на подграфах исходного графа с размерностями N1, N2,… ,NK. И, совершенно очевидно, что для каждого следующего подграфа будут пути, которые вы уже рассматривали.
В качестве аналога рассмотрите задачу о рюкзаке. Ее можно решать полным перебором, но если делать это правильно (динамикой), т.е. повторно не рассматривать уже рассмотренные частичные решения, то вы получаете полиномиальный алгоритм.
Поэтому я настаиваю, что если правильно организовать перебор, то решение полиномиально.
На самом деле, у вас серия из K задач коммивояжера
Но К задач коммивояжера не может быть проще, чем одна единственная. А одна единственная решается перебором. Даже если все остальные вообще решать не нужно, пусть они решаются хоть за константу — это уже не важно.
Ее можно решать полным перебором, но если делать это правильно (динамикой), т.е. повторно не рассматривать уже рассмотренные частичные решения, то вы получаете полиномиальный алгоритм.
Нет, не получите.
Поэтому я настаиваю, что если правильно организовать перебор, то решение полиномиально.
Вы говорите о том, что если у вас уже есть решение задачи, то эту задачу можно не решать. Это очевидно. Но чтобы решение было, его нужно получить. Это первое. Второе — решение кусочка коммивояжера никак вам не поможет при решении более широкой задачи. Если вы сперва решили задачу для 20 точек, потом одну единственную (!) точку поменяли, то придется решать целиком заново. Никакой динамики для коммивояжера (ну и для рюкзака, конечно же) не существует.
Если вы настаиваете, что вам известно полиномиальное решение задачи коммивояжера, то даже не тратьте время на то, чтобы писать его здесь — сразу научную публикацию делайте.
Если вы настаиваете, что вам известно полиномиальное решение задачи коммивояжера, то даже не тратьте время на то, чтобы писать его здесь — сразу научную публикацию делайте.
Я вам уже несколько раз сказал, что я решаю не задачу коммивояжера, а ту задачу которая описана в этой статье. И она задачей коммивояжера не является. Но, видимо, мне действительно стоит прекратить писать здесь, т.к. мы с вами друг друга не слышим.
Никакой динамики для коммивояжера (ну и для рюкзака, конечно же) не существует.
Для рюкзака существует. Смиритесь.
Я вам уже несколько раз сказал, что я решаю не задачу коммивояжера, а ту задачу которая описана в этой статье.
А в статье решается задача коммивояжера.
И она задачей коммивояжера не является.
Как это не является? Вам дано n вершин, вам надо найти кратчайший обход. Что это если не задача коммивояжера?
Для рюкзака существует. Смиритесь.
Динамики, про которую вы говорили (позволяющую решить рюкзак за полиномиальное время) не существует. Читайте внимательнее материал, на который ссылаетесь.
Для рюкзака существует.
Вот только сложность линейно зависит от размера рюкзака.
Таким образом увеличение входа на один бит удваивает время решения.
Правда, там локаций знацительно меньше, обошелся обыкновенной комбинаторикой с перебором.
Планирование спидрана Morrowind с помощью имитации отжига