В научной фантастике распространено утверждение, что для движения корабля со скоростью, превышающей скорость света, требуется выполнить некоторые сложные математические действия, которые занимают нетривиальное количество времени.
Я хочу знать, насколько это хотя бы отдаленно правдоподобно. Другими словами: какая временная сложность разумно связана с любой произвольной формой сверхсветовой скорости?
В конце концов, по моему собственному (ограниченному) опыту почти все расчеты обычно попадают в одну из двух категорий:
Конечно, я знаю, что есть проблемы, для решения которых потребуется больше времени (и энергии), чем существует во Вселенной.
Очевидная проблема здесь в том, что у нас нет сверхсветовой скорости, и я не собираюсь описывать конкретную систему и просить вас проанализировать ее. Вместо этого я предлагаю перечислить некоторые наблюдаемые характеристики, общие для множества популярных вымышленных сверхсветовых систем, а затем рассуждать об их временной сложности.
Во-первых, давайте поговорим о наблюдаемых характеристиках сверхсветовых систем, которые я имею в виду.
Говорите ли вы о гипердвигателе из «Звездных войн» , или о сверхсветовой скорости Battlestar Galactica , или, возможно, о любом из дюжины менее известных вариантов, расчеты не могут быть подготовлены заранее. Это должно быть выполнено непосредственно перед сверхсветовым транзитом.
Даже не зная инженерных особенностей, есть несколько очевидных причин, по которым это может быть так: некоторые члены в уравнениях зависят от точки отправления или зависят от времени, т. е. если пункт назначения находится в движении, подобно планете или звезде, вы не можете вычислить ее положение без указания времени.
Таким образом, самый простой подход — считывать текущие значения из среды. Конечно, писатели делают это не поэтому: они делают это, потому что это простой способ создать тикающие часы, когда вам нужно напряжение. Но это мнимое оправдание, и оно действительно иногда упоминается персонажами.
Еще одна вещь, которая почти всегда верна, заключается в том, что нет дополнительных расчетов того, как отключить сверхсветовую скорость; Я не думаю, что когда-либо видел что-то подобное. Это верно независимо от того, является ли транзит мгновенным (как в BSG ) или нет (как в SW ). И если есть какие-то математические расчеты, которые должны быть выполнены во время транзита (например, в « Звездном пути » компьютер контролирует поле деформации и двигательную установку, чтобы вносить непрерывные корректировки), это никак не влияет на отправление или прибытие, как мы видим.
Кроме того, я говорю только о математике . Часто бывает так, что сверхсветовая система должна «разогреться» (или «остыть» после предыдущего транзита), и это тоже требует времени, но они всегда представляются как ортогональные проблемы. Предположительно, математику можно выполнить независимо от того, готовы диски или нет; вы даже можете посчитать просто для удовольствия, а не выполнять транзит, когда у вас есть решение. Меня волнует только время, требуемое математикой.
Во-вторых, давайте поговорим о некоторых ограничениях.
Очевидно, невозможно оценить временную сложность набора задач, если я не укажу эти проблемы. Однако я думаю, что мы можем разумно исключить большую часть территории.
Во-первых: хотя может существовать огромный класс проблем, которые либо буквально неразрешимы компьютерами (например, проблема остановки), либо не могут быть решены в течение полезного времени (например, взлом AES-256), кажется само собой разумеющимся, что никто на самом деле поместите эти системы на множество судов, если будет разумная вероятность того, что очень многие сверхсветовые переходы не смогут быть рассчитаны в разумные сроки.
Если бы у нас сегодня была машина, которая могла бы доставить нас к звездам со скоростью, превышающей скорость света, но она имела бы такую же временную сложность, как взлом AES, мы могли бы построить несколько таких машин и включить их, потому что, хотя вероятность краткосрочный успех низок, потенциальная отдача огромна. Но мы бы не стали ставить по одному из них на каждый космический корабль . И никто из тех, кто убегает от боя, не будет считать это устройство лучшим шансом на спасение; они, вероятно, даже не включили бы его. Если бы математика прыжка не была известна как « в P », люди не стали бы полагаться на сверхсветовую скорость как на основной транспорт. Даже не для доставки грузов:
«Я везу 20 тонн замороженных бананов на Альфу Центавра. Мы можем прибыть в любое время от 5 минут до 10 53 лет, так что не ждите». -- ≠P Космический дальнобойщик
Таким образом, я думаю, мы можем с абсолютной уверенностью сказать, что весь класс сверхсветовых приводов опирается на математику, которая, как известно , решается за полиномиальное время.
Я думаю, мы можем сказать больше: кажется вероятным, что большая часть любых вычислений будет происходить в области навигации. Итак, я ожидаю увидеть много арифметики и тригонометрии. Возможно, это может быть какая-то физическая симуляция, которая, как я полагаю, включает вычисления. Возможно, какой-то доступ к базе данных поможет определить положение известных удаленных объектов.
Проблема для меня в том, что все это попадает в категорию «легко решаемых за миллисекунды на современном оборудовании». И нелепо предполагать, что цивилизация, где сверхсветовая скорость является обычным явлением, будет иметь худшие компьютеры, чем у нас. Более того, даже если мы говорим о вычислительных затратах, подобных перекодированию видео, которые (в зависимости от ввода) могут занимать часы, абсурдно думать, что (1) цивилизация не разработала специализированное оборудование для быстрого решения этих задач, и (2) отдельные суда не будут покупать какое-либо дополнительное оборудование, необходимое для дальнейшего сокращения времени вычислений до нуля. Делаем транскодирование в облаке; Хан Соло купил бы 10 причудливых видеокарт и 64-ядерный процессор, потому что альтернатива — смерть или тюремное заключение, если он не сможет уйти в мгновение ока.собирается летать с медленной заводской моделью прыжкового процессора, если они смогут обновиться. И если «расчет» является точным описанием того, что делается, обязательно будут возможны весьма существенные апгрейды.
И давайте будем реалистами: расчет сверхсветовой скорости не будет включать фактическое перекодирование видео, потому что это явно не имеет отношения к путешествию. Он не собирается использовать преднамеренно дорогие вычисления (например, bcrypt), потому что никто не хочет , чтобы FTL занимал больше времени, чем необходимо.
Итак, мне кажется, в свете моего смутного понимания теории вычислений в сочетании с разумными ожиданиями в отношении поведения пилота, что любая версия сверхсветового полета, требующая математики перед вылетом, обязательно приведет к одному из ровно двух сценариев:
Я не очень хорошо разбираюсь в теории вычислений, и я уверен, что здесь есть люди, которые лучше меня разбираются в NP-полноте. И, возможно, есть дополнительные метаматематические области, о которых я не знаю. .
Итак, о чем я прошу:
В рамках наблюдаемых сверхсветовых характеристик, которые я описал, и без производства некоторого набора трудоемких вычислений вручную, то есть без изобретения конкретной системы , каковы самые узкие границы, которые мы можем разумно установить для количества времени, которое потребуется, чтобы рассчитать конечные точки сверхсветового транзита и/или проложить курс между ними через пространство-время?
Иными словами: можете ли вы определить какую-либо проблемную область, которая обязательно будет частью всего семейства FTL «математика перед прыжком», в которой есть много проблем, которые не могут быть решены за полиномиальное время или которые в конечном итоге не могут быть оптимизированы до < 1 секунда?
Я считаю, что оба эти вопроса являются формулировками одной и той же проблемы, поэтому ответы должны пережить оба.
Произвольный пример расчета подходящей сложности, который соответствует сложности прыжка с гипердвигателя, который не может быть рассчитан заранее, но может быть рассчитан и передан нескольким другим людям для немедленного использования:
Выберите начальные и конечные координаты:
эти координаты отображаются в многомерном фрактальном пространстве. Для простоты иллюстрации я покажу двумерное изображение фрактала Мандельброта.
Просто чтобы показать бесконечную сложность, которую могут иметь фракталы.
Теперь рассчитайте точную линию эквипотенциала между вашей начальной точкой (которая фиксирована) и приемлемой конечной точкой рядом с тем местом, где вы хотите выйти.
Этот расчет занимает много времени, но достаточно предсказуемое время для любого заданного параметра точности.
Да, это изображение ОДНОЙ ЛИНИИ вокруг эквипотенциала множества Мандельброта.
И нет, увеличение не упрощает линию. Он остается на том же уровне сложности при 10-кратном, 100000-кратном или гугол-кратном увеличении.
Нет, вы не можете рассчитать это заранее, поскольку точная форма фрактала будет варьироваться в зависимости от текущих межзвездных относительных положений, плотности энергии и гравитационных событий (например, «отскок слишком близко от сверхновой», о котором упоминает Хан). При изменении условий меняется и фрактальное представление гиперпространственного многообразия.
Но после расчета для текущих условий, начального положения и желаемого конечного положения решение останется в силе, если условия не изменятся. Это позволяет вам делиться своими расчетами с вашим флотом, обеспечивая скоординированное движение.
Вычислительный комплекс планетарного масштаба может предварительно рассчитать несколько миллионов возможных вариантов условий для известного набора начальных и конечных точек в самом ближайшем будущем, что позволит меньшим кораблям без необходимых компьютеров совершить прыжок. Но количество предварительных вычислений будет зависеть от количества независимых переменных, которых, вероятно, будет много .
Это пример очень ресурсоемкой задачи, которая требует достаточно последовательного количества времени для расчета с заданным уровнем точности. И практически не могут быть предварительно вычислены и сохранены в базе данных.
PS Пример перекодирования видео в ОП на самом деле довольно хороший пример подходящей проблемы!
Это огромная, конечная и довольно точно предсказуемая во времени задача, которая полностью зависит от входных данных, параметров и желаемого результата. Причина, по которой это занимает «часы», заключается в том, что они выбрали это как приемлемый компромисс между качеством и временем . Та же задача может быть выполнена за секунды для версии видео с очень низким разрешением или десятилетия для видеопотока со смехотворно сверхвысоким разрешением.
Когда вы совершаете сверхсветовой прыжок, благодаря задержке скорости света вы всегда оперируете информацией о вашей целевой системе, которая устарела от многих лет до десятилетий и столетий.
В норме звезда прошла бы космически ничтожное расстояние за это время, но ведь не хочется всплывать "где-то в непосредственной близости" от звезды, хочется всплывать внутри планетарной системы, а то и прямо на подходящей орбите вокруг планеты. Поэтому вам нужно прямо сейчас предсказать положение пункта назначения на основе этой устаревшей информации и сделать это с точностью с приемлемой погрешностью в несколько тысяч километров. Учитывая сложности гравитационных взаимодействий в системе из n тел, вам необходимо моделировать взаимодействия от тысяч до миллионов объектов, поскольку ошибок в расчетах, какими бы малыми они ни были, может быть достаточно, чтобы сместить вас на миллионы километров от пункта назначения. , или если вам не повезло, поместите вас внутрьэтого. Таким образом, вам нужно по существу смоделировать движение небольшого куска Млечного Пути вместе со всеми значительными источниками гравитации в нем, взаимодействующими со всеми другими источниками, такими как звезды, планеты и туманности (привет, симуляции жидкости). И для этого вам нужно сначала смоделировать звезды вокруг вас в обратном направлении, основываясь на их расстоянии от вас и данных из вашего модуля обсерватории, чтобы найти их необходимые объективные положения в начале моделирования.
Звучит как проблема типа «часы или дни, чтобы выполнить на мейнфрейме», но экстраполяция этого в будущее звучит как достойная задача для футуристического навигационного компьютера космического корабля, на которую можно было бы подумать за несколько минут. Вы не можете оптимизировать эту задачу, потому что любая оптимизация вызовет упрощения и приближения, а именно то, что вам не нужно при расчете точки прибытия и скорости.
«Чем меньше вы тратите на расчеты — тем грязнее и неточнее ваш приезд» — это может быть даже хорошим сюжетным ходом.
Шахматы.
из https://chess.stackexchange.com/questions/2422/database-of-every-possible-move-in-chess
Я полагаю, что ваш вопрос по существу сводится к теме, можно ли полностью "решить" шахматы. В Википедии есть отличная статья на эту тему, которая должна дать вам хороший обзор.
Подводя итог, можно сказать, что количество возможных вариантов игры в шахматы оценивается как 10^120. Это ошеломляюще огромное число, для сравнения, примите во внимание, что число атомов в наблюдаемой Вселенной оценивается примерно в 10^80. Другими словами, если бы вы использовали всю наблюдаемую вселенную в качестве жесткого диска, вам все равно нужно было бы хранить 10^40 комбинаций шахматных партий на каждом атоме, чтобы просто хранить все это. Излишне говорить, что это настолько далеко за пределами наших нынешних и обозримых технологий, что большинство людей считают это совершенно невозможным.
Предположим, что моделирование гиперпространственного прыжка похоже на моделирование игры в шахматы, за исключением того, что здесь больше фигур. Учитывая первоначальную настройку соответствующей вселенной, компьютер выполняет несколько прыжков, которые возвращают разные вероятности успеха. Некоторые явно имеют низкие шансы на успех. Компьютер продолжает выполнять смоделированные прыжки, пока не достигнет одного с приемлемым шансом на успех, причем «приемлемая» вероятность определяется обстоятельствами. Можно повысить шансы на успех, открыв возможные направления — например, если вы убегаете, любое открытое пространство приемлемо. Если вы хотите прыгнуть в точное место с высокой вероятностью успеха, может потребоваться множество симуляций.
«Много» — это 10^большой. Это может быть сделано. Это может быть сделано довольно быстро, если повезет. Или нет.
Время расчета на практике часто больше зависит от человеческого терпения, чем от мощности компьютера.
Расчеты могут занять много времени. В физике твердого тела люди часто вынуждены оставлять суперкомпьютер включенным на недели, чтобы смоделировать квантовую систему, а иногда и на месяцы. Это все просто числовые штуки, сложение и умножение — их просто много.
Однако решающим моментом является то, что такие виды моделирования физики твердого тела всегда будут занимать недели или месяцы, независимо от того, насколько хороши наши компьютеры. Моделирование делает все виды приближений, вам, вероятно, нужен набор атомов, который «фактически бесконечен», но у вас, вероятно, только 100, так как большее количество будет слишком сильно замедлять работу вашего терпения. Если бы компьютеры стали лучше, ваше терпение не изменилось бы, так что это заняло бы столько же времени, и у вас было бы 200 атомов. Может быть, есть какая-то переменная, которую вы сохраняете фиксированной во всех своих вычислениях, но если бы расчеты выполнялись в 10 раз быстрее, вы бы проверили эту переменную, чтобы увидеть, как она изменила ситуацию.
На практике время прыжка определяется скорее человеческим терпением, чем мощностью компьютера.
Хорошо, но сверхсветовая навигация точно другая? Возможно, в 2650 году нашей эры расчет сверхсветового прыжка занимал час, но к 2670 году тот же расчет сократился до 3 минут. К 3000 году нашей эры это 2 секунды. Тот период в истории, когда она находится посередине, скорее всего, будет коротким.
Если только нет другой переменной, например числа атомов выше. Терпение людей остается прежним, поэтому в среднем, если 1 час — это максимум, кто-то может утруждаться ожиданием прыжка со сверхсветовой скоростью (люди будущего нетерпеливы), тогда, когда компьютеры станут лучше, люди будут брать больше других вещей.
Что еще? Возможно, это размер вашего корабля, более крупный корабль -> более сложные расчеты прыжка. Затем размер корабля и мощность компьютера масштабируются вместе. Возможно, масштабирование — это что-то другое — возможно, каждый раз, когда корабль прыгает, он оставляет рябь в варпе, что усложняет математику для других кораблей поблизости. Предположим, что если прыжки занимают X секунд, выгодно иметь больше маршрутов для кораблей. Летает все больше и больше кораблей, пока прыжки не займут в среднем около X секунд и не будет найдено какое-то равновесие. Тогда компьютеры станут лучше, но экономика гарантирует, что любое сокращение времени прыжков будет недолгим, поскольку эта дополнительная мощность будет заполнена большим количеством прыгающих людей. (Движение на реальных дорогах может происходить по аналогичной схеме.)
Хорошо. Я должен тщательно подбирать слова, чтобы не попасть в поле зрения хронометриста. Кроме того, просто для начала, я не могу поделиться ни одной из задействованных формул, потому что они основаны на «истинной» математике 23-го века и не имеют никакого смысла в вашем приближении к этой более высокой номенклатуре 21-го века.
То, что в художественной литературе вашего нынешнего века называется «расчетом», на самом деле является интенсивным вычислительным упражнением в предсказании реального мира. Задача сводится к получению нескольких последовательных снимков данных датчика уровня квантовых частиц и вычислению на их основе того, где каждая часть каждой частицы на вашей непосредственной траектории будет находиться в несколько различных моментов в ближайшем будущем. Гравитационный и --CENSORED-- вклад каждой частицы в базовое пространство-время должен быть известен до того, как это произойдет, для каждой частицы в арке вперед на расстояние, необходимое для ваших двигателей, чтобы достичь сверхсветовой скорости (варп) или сверхсветовой-бесконечности. (прыжок) скорость. Причина этого проста, но неочевидна, пока вы на самом деле не начнете приближаться к этим скоростям. У меня нет времени (или редакционной свободы), чтобы вдаваться в подробности,
Таким образом, вы не ждете на своем компьютере, чтобы вычислить курс к месту назначения или какую-то эзотерическую ценность, которая необходима, чтобы получить универсальное разрешение, чтобы двигаться очень быстро. Вы ждете, пока ваш компьютер найдет возможно несуществующий экземпляр вовремя, когда путь вперед можно пройти на расстояние, необходимое для того, чтобы стать сверхсветовым.
На это вычисление влияет ряд факторов, и ни один из них не известен до момента, когда запрошен расчет FTL.
Эти факторы имеют очевидное значение для потенциальных авантюристов со сверхсветовой скоростью...
Хорошо. Я предложил то, что могу. Надеюсь, поможет. Надеюсь, я не сказал слишком много. В качестве отказа от ответственности, ни одна из идей, представленных здесь, не является реальными научными теориями, предложенными настоящими учеными, либо живыми, либо еще не родившимися. Этот ответ не нарушает запрет на раннее раскрытие информации в будущем, поскольку все изложенное здесь является чисто умозрительным, и его не следует путать с реальной реальностью. Любые сходства с реальными открытиями, как текущими, так и предстоящими, носят чисто косвенный характер. Пожалуйста, не удаляйте мою личную временную шкалу.
10 световых лет составляют около 58 786 253 700 000 миль. Предположим, вам нужно проверить весь путь на наличие препятствий диаметром более нескольких метров, так как столкновение с тенью гиперпространственной массы 50-тонного камня на скорости, кратной скорости света, расшатает болты, а затем и некоторые другие! (Из современного опыта мы знаем, что попадание в 40-граммовую пулю на скорости всего лишь 1700 миль в час нанесет некоторый ущерб.) Так что умножьте необходимое разрешение на тысячу или около того. Затем учтите, что скалы и другие гиперпространственные аномалии движутся в разных направлениях с разными скоростями, все они были измерены с конечной точностью и, вероятно, в последний раз исследовались несколько лет назад.назад. (Как повстанец/контрабандист, вы должны держаться подальше от более загруженных и лучше обследуемых космических маршрутов с их вездесущими патрулями имперской полиции.) И вы также, вероятно, не можете изменить свою траекторию слишком быстро. (По крайней мере, не без того, чтобы не обнаружить свое лицо, сильно прижатое к окну кабины, говорящее «Гнннх».)
Итак, предположим, вам нужно выполнить поиск в базе данных любых записей «звездной карты» для ячеек вдоль линии длиной 58 786 253 700 000 миль и достаточной ширины, чтобы включить любые камни, движущиеся из соседних ячеек с разрешением в несколько метров, спроецировать положение каждой обнаруженное препятствие до настоящего времени (с планками погрешностей!) проверьте пересечения, попытайтесь настроить траекторию, чтобы избежать каких-либо обнаруженных столкновений, проверьте ускорения на новом курсе для обеспечения безопасности пассажиров/работоспособности двигателя, а затем повторно проверьте новую траекторию на наличие препятствий.
И это даже без необходимости делать это в десятимерном гиперпространстве с экзотической математикой. Сложность поиска в трех измерениях возрастает с кубом размера области, сложность в десяти измерениях с десятой степенью. Таким образом, увеличьте масштаб в 10 раз, и 3D-поиск расширится в 1000 раз, а 10D-поиск расширится в 10 000 000 000 раз.
Если мы оценим, что расчет прыжка на 10 световых лет должен занять около 100 секунд, чтобы быть практичным, то мы должны обрабатывать каждую тысячу миль траектории примерно за 1,7 наносекунды. Это порядка нескольких тактов на современном процессоре.
Космос большой!
Это вызов кадра
Мне понравилось читать множество ответов, но у всех у них есть одна основная проблема: вы просите нас объяснить, используя сегодняшние предположения о технологиях, как мы могли бы сделать что-то, что не будет иметь значения в течение некоторого времени в будущем. Поэтому я сомневаюсь в полезности ответов.
Если у вас есть технология для сверхсветовых полетов, у вас определенно есть улучшенные вычислительные технологии. Поскольку мы не можем не представить технологию, необходимую для сверхсветовых полетов, разумно предположить, что мы не можем не представить вычислительную технологию, доступную для расчета навигации.
Поскольку мы ничего не знаем о сверхсветовых полетах в реальном мире (за исключением того, что считаем, что это невозможно), мы, очевидно, ничего не знаем о навигационных опасностях сверхсветовых полетов. Мы можем посмотреть на гравитационные колодцы и т. д., о которых мы знаем, но насколько это ценно для вас? Прежде чем мы научились летать, опасности полета были нам практически неизвестны. Мы узнали, что они из себя представляли, когда совершенствовали технологию.
Но, что более важно, все эти научно-фантастические шоу на самом деле перешагнули через небольшую показуху, чтобы продолжить рассказывать свою историю.
С годами я заметил, что есть люди, которые воспринимают «тяжелую научную фантастику» как нечто, чем она на самом деле не является. Они думают, что «тяжелая научная фантастика» — это история, которая жестко придерживается науки. С этой целью они ищут рациональные, полные с научной точки зрения описания причудливой кларковской магии . Я руководил издательством около 10 лет, и одна из вещей, которую я усвоил за это время, это то, что новые авторы часто зацикливаются на деталях, которые на самом деле не имеют отношения к их истории.
Итак, почему все эти замечательные научно-фантастические истории в основном пропускают математику и вычислительную реальность навигации по сверхсветовым скоростям?
Потому что это не имеет значения.
За невероятно редкими исключениями все истории попадают в один или несколько из семи основных сюжетов . Научная фантастика — не более чем показуха, используемая для рассказа истории. Посмотрим правде в глаза, если вы не пишете учебник по истории какого-либо аспекта науки или не пишете статью, в которой постулируется возможное будущее развитие указанного аспекта, на самом деле вы рассказываете пресловутую историю о парне, который встречает девушку в одежде. в выбранном вами любимом жанре.
И вот где Worldbuilding.SE становится действительно ценным
Что мы здесь делаем, так это помогаем вам разработать инфраструктуру «жанра выбора» для вашей истории. И именно поэтому я должен оспорить рамки вашего вопроса. Потому что любое объяснение того, насколько быстро или медленно, насколько эффективно или неэффективно, насколько практично или непрактично может быть рассчитана сверхсветовая навигация, принципиально неуместно, даже если ваша история зависит от фактов — потому что вы спрашиваете, как быстро что-то может быть сделано заранее. того, когда это на самом деле нужно было бы сделать, что ответ бессмысленен, и, вероятно, в любом случае бессмысленен для вашей истории.
Я думаю, что идея, стоящая за этим вопросом, слишком легко отвергается.
Например, этот комментарий — почти личная атака:
«В конце концов, по моему собственному (ограниченному) опыту, почти все расчеты обычно попадают в одну из двух категорий: «…извините, но вы правы. Нет, не о сложности расчетов, а о вашем незнании их. - ПКМан
И те ответы, которые были даны, похоже, полностью упускают суть и говорят о сложности проблемы, о которой не спрашивает вопрос.
Рассмотрим алгоритм сложности O(10 n ):
— сюжет (10^n) - Wolfram|Alpha
Приблизительно до n=6 процесс завершится относительно быстро; между 6 и 7,5 это займет все больше времени, а после 7,5 это займет смехотворно много времени. (Обратите внимание, что «n» может представлять миллион точек данных, а не обязательно небольшое целое число.)
Первая часть графика приблизительно линейна, а вторая часть графика приблизительно бесконечна.
Подавляющее большинство входных данных будет либо в первой группе, либо в последней группе: быстро решить или даже не пытаться.
Задача коммивояжера — типичный пример того, что обычно требует невероятно много времени для решения. Но если это ограничивается небольшими проблемами, есть алгоритмы, которые могут решить это быстро.
Для любого заданного алгоритма навигации будет некоторое минимальное количество требуемых входных значений. Из приведенного выше графика довольно очевидно, что решение для любого такого алгоритма почти всегда будет либо очень быстрым, либо очень медленным.
Если он относится к категории быстрых, его можно легко ускорить с помощью дополнительного оборудования (например, если обычно это занимает час, то 100 процессоров могут сделать это за 36 секунд).
Если он относится к категории медленных, ничего нельзя сделать, чтобы заставить его работать в течение полезного промежутка времени.
Если и существует практичный алгоритм сверхсветовой навигации, то он должен относиться к категории быстрых, иначе его нецелесообразно использовать. И я бы сказал, что почти наверняка, как предполагает ОП, его можно было бы закончить так быстро, как хотелось бы.
С точки зрения фантастики, плоская часть может представлять расчеты поездок на расстояние менее 25 000 световых лет между конечными точками. Один прыжок через галактику было бы невозможно рассчитать, но можно было бы достичь не более 4 более коротких прыжков в любую точку галактики.
И, возможно, плоская часть также требует, чтобы конечные точки находились рядом с большой массой, такой как звезда. Если этот фактор сочетается с первым ограничением, несмотря на возможность быстро прыгать по Млечному Пути, межгалактические путешествия останутся невозможными.
Но подождите, а что, если в глубоком межгалактическом пространстве плавают выгоревшие солнца, черные дыры и т. д.? Обнаружение их может обеспечить серию прыжков, которые могут привести к Андромеде. Ступени к звездам »?
Преобразования Фурье и принцип неопределенности
Предполагая, что вам нужно измерить некоторые спектральные свойства гиперпространственной среды, чтобы совершить прыжок, вам придется собирать данные в течение определенного периода времени, чтобы достичь определенной точности текущего спектрального состава. Чем дольше вы «слушаете», тем точнее будет ваше представление.
В самом простом случае вам нужно будет определить только одну доминирующую локальную гиперпространственную частоту, чтобы синхронизировать с ней свой прыжковый двигатель. Если вы сэмплируете гиперпространственную амплитуду в течение короткого промежутка времени, ваша неопределенность относительно ее частоты будет довольно большой, что может привести к тому, что вы установите двигатель на достаточно другую частоту, чтобы разорвать корабль на части. Чем дольше вы будете «слушать», тем безопаснее будет и тем плавнее будет работать ваш гипердвигатель.
Вы можете слушать звуки гиперпространства все время, но если это требует каких-то ресурсов (большой расход энергии конденсатора, износ дорогого сенсора, подверженность опасностям или постоянным негативным воздействиям (гравитационные флуктуации, гипервспышки, Деформация, ...), ...), было бы необходимо активировать подготовку к прыжку только в том случае, если вы действительно планируете прыгать в ближайшее время.
Более сложная взаимосвязь между спектральным составом гиперпространства, запланированным маршрутом и параметрами движения также будет включать мощность ЦП как второстепенный аспект и может позволить кораблю с хорошим ЦП/лучшей программой совершить прыжок немного раньше (эвристически оценивая некоторые параметры с несовершенными параметрами ) . измерения, приводящие к аналогичной безопасности через более короткое время), но этот эффект, вероятно, будет небольшим.
Если бы несоответствие между частотой двигателя и частотой гиперпространства (или аналогичным показателем) вызывало значительную нагрузку на гипердвигатель и/или корабль, вы бы получили практическое поведение, очень похожее на путешествие в гиперпространстве из «Звездных войн»: необходимо рассчитать некоторые параметры, прежде чем вы сможете прыгать, не взорвав свой диск, более быстрые прыжки более рискованны, и невозможность предварительно вычислить прыжки (изменяющиеся условия).
Является ли это универсальной проблемной областью?
Почти. Пока у прыжкового двигателя есть некоторые параметры, которые необходимо изменять в зависимости от «погоды», и пока эта «погода» имеет волнообразные свойства, будет существовать определенное минимальное время измерения, ниже которого безопасная оценка параметров будет невозможна. . Как долго это время зависит от чувствительности вашего привода к неточности и точного характера этой «погоды», которые в конечном итоге зависят от естественных констант (+- некоторый технический фактор, который исчезнет по мере развития технологии). В некоторых гипотетических вселенных это время может измеряться в наносекундах или галактических вращениях, но вполне разумно, что оно может попасть в диапазон «10 минут, пока мы не сможем сбежать от пиратов».
Изменение этого времени на разных уровнях технологии может быть относительно сложным, но (предполагая, что простые отношения и технологии находятся где-то рядом с физическими пределами) вы ожидаете максимум 50-процентное сокращение времени между передовым экспериментальным военным гипердвигателем и более старым, но технологически почти зрелый.
Может ли существовать действительно универсальная проблемная область?
Единственная универсальная необходимость путешествия типа гиперпространства (без каких-либо предположений о его деталях) — это знание своего пункта назначения (в некотором конкретном математическом описании, от направления до фрактальной параметризации). В принципе, двигатель может превратить вас в тахионную материю, путешествующую в гиперпространстве с идеальным вакуумом (и обратно), поэтому, по крайней мере, в некоторых случаях будет достаточно знания направления, расстояния и скорости. В этом случае путешествие от чего-либо почти всегда было бы тривиальным (просто подождите некоторое время, которое гарантированно приведет вас в межпланетное пространство, а не внутрь ядра звезды), в то время как путешествие близко к цели потребует только хранения /предварительно вычисляемые данные датчика. На практике может оказаться необходимым получить от цели информацию об управлении трафиком, поэтому скорость гиперпространственного телефона может быть ограничивающим фактором, но это не так.
Чтобы иметь возможность успешно совершить прыжок в гиперпространство, вам нужно точно знать, где вы находитесь, сколько энергии требуется для входа в гиперпространство и сколько энергии требуется для выполнения прыжка.
Требование №1 — просто Galactic GPS, и в любом случае небольшая ошибка допустима.
Требование № 3 — просто иметь хорошие карты, и снова допустима небольшая ошибка.
Проблема в требовании №2, которое зависит от условий локального пространства, а эти условия постоянно меняются . Все почти бесконечные гравитационные источники в Галактике движутся, вращаются и испускают гравитационные волны, и возникающий в результате шум препятствует гиперпроникновению.
Следовательно, чтобы «открыть портал», необходимо точно знать гиперсостояния локальной браны с запасом в несколько секунд. А для этого нужно развернуть (одноразовые) гиперсенсоры и нанести на карту достаточно большой сферический объем вокруг корабля, и передать этот набор показаний (через сверхсветовую скорость) на компьютер. Будучи переданными на сверхсветовой скорости, эти показания описывают «будущие» условия с точки зрения корабля и могут использоваться для расчета точных условий в будущем времени запланированного прыжка.
Точность показаний пропорциональна времени, покрываемому самим чтением, обычно это несколько секунд (или столько, сколько вам нужно). Поскольку судно и датчики сами влияют на показания, и делают это своими собственными гравитационными волнами, распространяющимися со скоростью света, уменьшить это «время установления» невозможно.
Обычно, кроме того, требуется немного больше времени, чтобы иметь запас, позволяющий быстро восстановить датчики, что недешево (вы можете сократить это время, отказавшись от датчиков).
В чрезвычайной ситуации вы можете развернуть датчики ближе к кораблю и использовать более короткие показания для приблизительного расчета гипервхода . Чем грубее оценка, тем выше риск катастрофического входа, когда корабль будет раздуваться как дискретный набор кусков.
Это совершенно произвольно, и как автор/строитель мира вы можете добавлять любые упрощения, которые вам нравятся. Я технический разработчик с примерно инженерно-математическим образованием и немного большим интересом.
Я думаю, что более полезно связать временную сложность с факторами, которые делают ваши решения во вселенной интересными вариациями.
Аналогия:
По мере улучшения аппаратных возможностей компьютеров работающее на них программное обеспечение становится все более требовательным к расширенным возможностям. Операционная система для новейшего оборудования будет работать намного медленнее на старом оборудовании. Таким образом, люди, как правило, получают несколько обновлений ОС, а затем в конечном итоге видят необходимость в обновлении своего оборудования, чтобы обеспечить его бесперебойную работу.
Аналогичным образом, учитывая новейшие аппаратные возможности, разработчики программного обеспечения для навигационных компьютеров пишут алгоритмы расчета FTL, которые максимально используют вычислительную мощность системы для выполнения расчета за разумное время (скажем, 30 секунд). Допустим, это ставит вероятность катастрофического отказа при сверхсветовом прыжке в среднем в 0,02%.
Несколько лет спустя стало доступно более совершенное оборудование, и теперь разработчики программного обеспечения могут улучшать и добавлять дополнительные функции в свое вычислительное программное обеспечение, что, сохраняя время расчета в пределах разумного количества секунд, повышает вероятность сбоя. в среднем до 0,0185%. Это достаточно разумное улучшение безопасности, чтобы в течение следующих нескольких лет внедрение судовладельцами нового аппаратного и программного обеспечения соответствовало стандартной S-образной кривой (некоторые первопроходцы, большинство среднего уровня, некоторые поздние).
Некоторые грузовые суда могут решить обновить только программное обеспечение, и время расчета увеличится с 30 с до 1,5 минут. Но некоторым кажется, что компромисс того стоит. Некоторые контрабандисты продолжают использовать старое программное обеспечение, но обновляют аппаратное обеспечение, чтобы вычислять прыжки всего за 24 секунды.
Таким образом, «оптимизировать до смерти» вполне может выглядеть так, как для нас выглядит прогресс аппаратного и программного обеспечения, и давать результаты, аналогичные тем, что мы видим в реальном мире. Со временем это происходит медленно, и часто мы восхищаемся тем, чего могут достичь технари, а также сожалеем: «Почему так сложно просто заставить систему X делать Y?». Это грязно, но у нас могут быть хорошие вещи. (То есть приятные вещи, которые все еще требуют некоторого времени, в отличие от единственных вариантов, которые являются либо почти мгновенными, либо неприемлемо медленными.)
Несколько вещей приходят на ум
Сдвиг кадра:
Ничто в вашей постановке задачи не препятствует предварительному вычислению ответа. Хорошо, вам нужно знать точку прыжка, но не можете ли вы просто перейти к той точке, для которой вы рассчитывали? В какой-то степени вы все равно должны это сделать, поскольку я не могу вспомнить ни одной из основных систем, требующих остановки перед прыжком. (Однако в некоторых книгах это происходит, но они всегда связаны с переходом по фиксированным ссылкам, вам просто нужно осторожно подойти к ссылке.)
Таким образом, нам нужно использовать другой подход: рассмотреть, что происходит с системой GPS. По сути, для получения исправления GPS требуется не менее 30 секунд, потому что вы должны загрузить отчет о погоде, в котором описаны ожидаемые задержки распространения.
Следовательно: Гиперпространство не плоское, в нем есть волны. В идеале вы загружаете отчет о волнах с навигационных спутников, которые сохраняют обновленные отчеты настолько далеко, насколько это возможно, но сверхмощные корабли также имеют датчик, который может собирать информацию, хотя и с меньшей точностью.
Бортовой датчик — это просто точечные показания, и он не может фактически видеть волны, их можно определить, только наблюдая, как показания меняются с течением времени. (Представьте себе полюс в океане с поплавком, который движется вверх и вниз, и вы можете только прочитать, где находится поплавок.) Получение разумного правильного состояния волны жизненно важно, поскольку оно изменяет ваш курс, когда вы входите в гиперпространство. (Представьте, что происходит с отражением в воде, когда появляется рябь.)
Таким образом, обычное судоходство просто считывает навигационные спутники и делает их прыжок. Однако, когда вы пытаетесь действовать без разрешения властей (я не могу припомнить сцену, в которой имело бы значение время расчета гиперпространства, не связанное с незаконными операциями), это не вариант, вы должны сделать свой собственный измерения - обратите внимание, что это не фактическое время ЦП, и поэтому вы не можете ускорить его, нагрузив на него больший ЦП.
Да, вы можете совершить гиперпрыжок вслепую, но если вы сделаете это, то место, куда вы прибудете, будет крайне непредсказуемым, вы вполне можете оказаться так далеко от дома, что не сможете найти дорогу назад.
Планирование полета самолета требует времени
В качестве хорошей аналогии (и, возможно, источника тропа?) я предлагаю планирование полета самолета. Пилоты обязаны ознакомиться с кучей информации, которая требуется как по регламенту, так и необходима для безопасной эксплуатации самолета. В зависимости от типа полета (авиация общего назначения, авиаперевозки, военные) и других характеристик детали будут различаться. У FAA есть консультативный циркуляр под названием «Руководство пилота по предполетному брифингу» , в котором объясняется некоторая необходимая информация и процесс.
Процесс предполетного планирования в настоящее время не ограничен вычислительными ресурсами, но, по сути, ограничен источником данных и человеком. Если вы планируете перелет на дальнее расстояние, ваш метеоинформационный брифинг должен включать в себя прогноз погоды на много часов вперед по всему маршруту полета. Он также должен включать информацию о состоянии (доступность процедуры посадки в аэропорту и т. д.) для пункта назначения и всего маршрута полета. Планирование включает в себя ветер, видимость, обледенение, отказы навигационного оборудования и т.д.
Пилоту необходимо собрать соответствующую информацию, определить маршрут, возможно, собрать больше информации, а затем, возможно, выполнить некоторые расчеты. Сами по себе расчеты не требуют значительных вычислительных ресурсов (т. е. запаса топлива для подъема на выбранную высоту при текущем весе самолета, температуре и ветре), и их можно выполнить даже с помощью моделирования довольно быстро. Но процесс занимает некоторое время.
Часть этой исходной информации, с точки зрения экспериментального проекта, поступает из источников, создание которых требует значительных вычислительных ресурсов. Моделирование погоды для создания прогнозов является одним из исторических и продолжающихся применений суперкомпьютеров.
Затем пилоты будут обновлять свой план полета по ходу полета (например, ветер сильнее, поэтому выберите другую высоту и т. д.). Автопилот в самолете приспосабливается к некоторой местной информации (местный восходящий поток, поэтому снижайтесь до желаемой высоты), но ему необходимо иметь текущее «понимание» окружающей среды. В некоторых научно-фантастических фильмах в гиперпространстве информация обрывается, поэтому невозможно приспособиться к изменениям гравитации и т. д. в режиме реального времени. Эти детали полета должны быть спланированы заранее. Если окружающая среда может меняться (звезды движутся, планеты движутся, солнечные бури, космические станции перемещаются и т. д.), то необходимо собрать или смоделировать много информации.
Если необходимо спланировать свой путь в гиперпространстве, кажется разумным, что пилоту и бортовому компьютеру необходимо иметь хороший набор данных для этого планирования. Сбор этой информации и синтез хорошего плана потребует сканирования, моделирования и связи с другими источниками данных. Мне кажется очень разумным, что гиперпространственный прыжок по крайней мере так же сложен, как и текущий план полета, и займет такое же количество времени.
Вычисление может быть полиномиальным, занимать время и не поддаваться улучшению.
Преодоление космоса
Чтобы пройти через пространство, вам просто нужно вычислить f(t) на основе g(t) для поездки при различных натуральных числах t от 0 до N. Значение N увеличивается с расстоянием. Энергия свертывания локального пространства при каждом значении t равна e(t). Неправильный ответ с большим количеством энергии разорвет ваш корабль на части, слишком мало — и он рухнет сам на себя.
Если g(t-1) > e(t): g(t) = g(t-1)-e(t)
Если g(t-1) < e(t): g(t) = g(t-1)+e(t)
f(t) = g(t)+g(N)
По сути, есть энергия, необходимая для туннеля, определяемая конечной точкой, и энергия, необходимая из-за локальных флуктуаций.
ограничения параллельных вычислений
Значит, компьютеры могут делать это параллельно, верно? Это просто добавление. Что ж, поскольку каждый ответ зависит от вычисления последнего значения, прежде чем мы узнаем какой-либо ответ, нам нужно подождать этого вычисления, чтобы получить ответ. Однако поведение ветвления делает невозможным параллельное вычисление последнего значения. Теперь не имеет значения, сколько у вас ядер, вы не можете вычислить это быстрее, чем O (N).
Заставить это занять время
Вы движетесь быстрее света, и эффект сворачивания пространства может быть очень сильным. Может быть, вам нужно запустить этот алгоритм только для каждого километра, а может быть, это каждый метр, или миллиметр. Чем выше требуемая точность, тем больше максимальное значение t в том же пространстве. Даже самые быстрые сумматоры и компараторы по-прежнему требуют ненулевого времени для запуска. Как только вы заставите наименьший компонент двигаться со скоростью света, и вы не сможете ничего ускорить, вы не сможете вычислить это быстрее. как только он будет обнаружен, он может быть на каждом корабле, но это все равно займет столько же времени.
Здесь есть несколько отличных ответов, но вот еще один.
Вычисление FTL похоже на вычисление деталей во фрактале: чем большего разрешения вы хотите во фрактале, тем больше времени занимает вычисление. С FTL высокое разрешение дает больше шансов на успешный прыжок.
Космические лайнеры, перевозящие много тысяч пассажиров, будут рассчитывать прыжки с разрешением 99,999%, каждая 9 увеличивает вероятность того, что капот корабля прибудет в пункт назначения целым, а не диффузно размазанным по вакууму на несколько световых лет.
Мошенник, у которого отключены щиты и который вот-вот будет уничтожен турболазерным выстрелом гангстеров, может рискнуть и прыгнуть с разрешением 90% (все, что ниже 90%, означает верную смерть), выбрав почти верную смерть, а не реальную . верная смерть.
Входными данными для расчета являются расстояние, направление и условия вашего локального пространства, например. плотность вакуума и количество энергии вакуума (возможно, чем дальше от гравитационного колодца, тем легче вычислить).
Показания снимаются каждые x наносекунд и подключаются к фрактальному расчету, может потребоваться y фактических секунд (или минут/часов, в зависимости от того, что требует ваш график), чтобы результаты сошлись на заданном значении, т.е. окончательный результат z% .
Есть точки прыжка и пункты назначения, где местные условия, как известно, всегда рассчитывают прыжок с коэффициентом безопасности, настолько высоким, что он практически равен 100%, это хорошо изношенные торговые пути и гипермаршруты.
Контрабандист в бегах (имеющий только ребенка и старика), который дорожит своей шкурой, вполне может рискнуть имперскими турболазерами еще на секунду или две, чтобы получить свой сверхсветовой расчет выше 98%.
Есть много физических задач, которые требуют много времени для решения, но не чрезмерно долго.
В колледже я работал ассистентом по программированию в исследовательских проектах по вычислительной химии. Для этих вычислений часто требовалось несколько часов вычислений, иногда даже ночь — и это на системах около 24 ядер с 64 ГБ памяти. Теперь они работают намного быстрее на графических процессорах, но, тем не менее, для этого требуется огромное количество дорогостоящих вычислений. Атомы и молекулы действительно сложны в том, как они взаимодействуют, и нет никаких закрытых форм уравнений, которые используются в этих вычислениях, поэтому в большинстве из них используется итерация градиентного спуска с использованием композиций гауссовских функций для аппроксимации волновых функций электронной орбиты. Пространство-время в астрономическом масштабе примерно так же сложно, как квантовый мир атомов, благодаря теории относительности и гравитации.
Вполне вероятно, что математика, необходимая для достаточно точного гиперпространственного прыжка, не имеет замкнутой формы и, следовательно, требует итеративного приближения. Кроме того, расчеты должны учитывать от сотен до миллионов небесных тел (в основном планет, лун и звезд; однако в некоторых случаях может потребоваться учет астероидов, спутников и обломков) вблизи пункта назначения прыжка из-за того, как они искривляют пространство-время своими гравитационными полями. Прямо здесь у вас есть итеративный расчет, построенный на расчет сложных уравнений, которые сами могут быть итеративными. Хотя вы, вероятно, можете распараллелить все небесные силы на архитектуре, подобной GPU, вы все равно ограничены последовательным узким местом на итерации. Вдобавок ко всему, такие вычисления могут включать в себя ряд рандомизированных предположений, чтобы избежать локальных оптимумов, что означает, что они могут повторяться на нескольких сотнях предположений, пока не станет достаточно уверенным, что решение было достигнуто с достаточной точностью.
Конечным результатом является гиперпространственный прыжок, расчет которого занимает от нескольких минут до нескольких часов, в зависимости от того, сколько значимых небесных тел задействовано и сколько догадок требуется для достижения глобального оптимума.
Кроме того, поскольку небесные тела, влияющие на прыжок, всегда движутся, эти скачки нельзя рассчитать заранее. Кроме того, прыгающий космический корабль должен учитывать свое собственное положение и импульс, поэтому каждый космический корабль должен выполнять свои собственные расчеты.
Интересно то, что вы можете совершить «рискованный» прыжок до того, как расчеты будут полностью готовы, но потенциально это может привести к отклонению от курса на несколько световых лет, где ваши импульсные двигатели STL бесполезны. Это отлично подходит для быстрого побега, если у вас достаточно топлива Hyperjump для другого правильно рассчитанного прыжка после этого, но это не сократит его при преследовании другого космического корабля.
В «Звездных войнах» вы перемещаетесь по гиперпространственным путям, уклоняясь от массовых теней тяжелых объектов. Логично, что для расчета потребуется произвольное количество времени, потому что им нужно проложить маршрут через сложную среду. Есть много возможных решений того, как они могут летать, а также изменяющихся и сложных ситуаций от момента к моменту.
В Battlestar Galactica нет хорошего компьютера. У них старый корабль со старыми данными, а сайлоны намного лучше прыгают. Логично, что им понадобилась бы целая вечность, чтобы рассчитать прыжки, потому что у них нет суперкомпьютеров. Когда базовая звезда повстанцев предлагает присоединиться к ним, их модификации, которые они предлагают, значительно улучшат их прыжки.
Взять, к примеру, «Звездный путь». Они могут просто уйти в варп по прихоти. Это потому, что им не нужно просчитывать маршруты, они просто летают по вселенной в подпространственном пузыре. Они могут реагировать на локальные угрозы на лету.
Итак, решите, какой ftl имеет ваша вселенная — это может быть симуляция, и поэтому она может иметь произвольную сложность в зависимости от того, что вам нужно смоделировать (упрощено известными способами или лучшими данными), это может быть простой расчет, быстрые компьютеры могут сделать проще, или вы просто быстро перемещаетесь в пространстве и вам не нужно время для вычислений.
Я собирался прокомментировать n-body, но вижу, что Вотан сделал это.
Различные люди комментировали прогнозы, основанные на препятствиях на «траектории полета» или рядом с ней, но для их обнаружения потребуется сверхсветовая способность перед полетом.
Вместо этого предположим, что возможность запуска зависит от способности вычислять локальные ограничения n-тел до определенного уровня точности.
Такие объекты, как внутрисистемные планеты или местная звезда, имеют минимальный эффект, умирают по закону обратных квадратов (или какому-то другому), и/или они заранее предсказуемы.
Любые локальные «корабли» или тела имеют больший эффект, и если их действия не поддаются контролю, все, что сильно отклоняется от кривой, ограниченной гравитацией, или постоянного ускорения, необходимо учитывать в то время.
Было обнаружено, что очень маленькие частицы (пыль, газовые облака) на очень близком расстоянии оказывают значительное влияние и должны быть включены в расчет n тел.
Ничто из вышеперечисленного не зависит от типа используемого FTL - это расчет, необходимый для определения подходящих параметров для совершения «прыжка к скорости света».
Все дело в страховке...
Расчет траектории полета сопряжен с определенным риском. В бесконечной вселенной возможны бесконечные пути полета. Хитрость заключается в том, чтобы найти те пути, которые приведут вас из пункта А в пункт Б и не приведут к гибели вас (или других).
Не быть убитым не гарантируется. (Решение этой задачи будет NP-задачей.) Лучшее, что вы можете сделать за разумное время вычислений, — это найти решение с приемлемым риском.
По мере того, как компьютеры становятся более мощными, это становится компромиссом:
Страховые компании не любят риск по понятным причинам. Им действительно больно, если им придется платить страховку за половину населения планеты, если какой-нибудь космический ковбой прыгнет на своем грузовом корабле на поверхность планеты, а не на парковочную орбиту. (И даже не упоминать весь материальный ущерб.)
Однако страховые компании «Галактики» — довольно богатые предприятия, обладающие достаточным политическим и экономическим влиянием, чтобы что-то с этим делать.
Им удалось подтолкнуть все межзвездные правительства к разработке законодательства, согласно которому любые улучшения вычислительных возможностей должны быть направлены на повышение безопасности прыжков за счет снижения риска. И сделать любой навигационный компьютер, который не играет по этим правилам, незаконным в их юрисдикции.
Это по-прежнему оставляет некоторых ковбоев на окраинах известной Галактики без этих предохранителей, которые могут быстрее рассчитывать менее безопасные прыжки, но они не имеют большого значения. Они все равно не могут получить страховку сами.
А страховые компании категорически отказываются возмещать ущерб, причиненный ими. Они просто заявляют: «Эта авария могла произойти из-за использования нерегулируемых навигационных компьютеров. Ваше правительство должно было обеспечить соблюдение правил. Мы не несем ответственности. Поговорите с вашим правительством о компенсации».
Этот ответ представляет собой небольшое изменение ответа Нуллиуса в ответе Вербы .
Предполагая, что вам нужно проверить всю траекторию полета на наличие объектов размером более нескольких сантиметров, существует нетривиальное время интегрирования, необходимое для того, чтобы телескоп (или другие датчики) мог «увидеть» все объекты на траектории. Обратите внимание, что этот телескоп должен быть на много порядков более чувствительным, чем наши нынешние телескопы, чтобы выполнить задачу за разумное время.
Как уже говорилось в других ответах, речь идет не об обработке данных, а о получении данных.
Теоретически полиномиальное время быстрое, но на практике оно зависит от двух вещей:
С обеими этими вещами вы должны поиграть, чтобы заставить эту предпосылку работать.
Что касается размера входа, нам действительно нужно учитывать только что-либо со значительным гравитационным воздействием. Каждая субатомная частица между здесь и там быстро переносит вас в область вычислительно невозможного. Все карликовые планеты и больше могут дать вам пару тысяч объектов для разумных прыжков в длину. Теперь все, что нам нужно, чтобы найти нужные вам тайминги, — это алгоритм полиномиального времени высокой степени.
Возьмем потенциально релевантный алгоритм реального мира: Parzen Windowing . Это попытка найти группы точек путем суммирования вероятностных распределений (например, гауссовых) вокруг каждой точки и использования восхождения на холм для поиска пиков. Это может иметь отношение к гиперпространству, потому что вам нужно определить, какие физические тела связаны в гиперплане, чтобы вы могли правильно определить искажение, которое они будут иметь во время вашего путешествия через пустоту.
Parzen Windowing — это алгоритм полиномиального времени, но степень полиномиальной шкалы зависит от размерности ваших данных. В зависимости от реализации сложность может быть на один полином выше, чем количество измерений. Таким образом, пытаясь выполнить парзеновское окно для трехмерных данных (объектов в пространстве), вы получили алгоритм времени четвертой степени, т. е. O(N 4 ). Это будет медленно даже при умеренных значениях N (например, несколько тысяч). Есть много ярлыков, которые вы можете сделать, чтобы ускорить его, но все они приводят к потере точности.
Компромисс между скоростью и точностью является ключевым и, вероятно, всегда присутствует. Рассмотрите более мелкие объекты, и ваш результат будет более точным, но N возрастет. Используйте большее приближение, чтобы уменьшить полиномиальную сложность, и время выполнения снизится, как и ваша точность. На самом деле это упоминается в главном научно-фантастическом свойстве: в Battlestar Galactica Хелена Кейн совершает прыжок вслепую (опасный сверхсветовой прыжок, выполняемый без предварительного вычисления случайных координат), чтобы выбраться из плохой ситуации.
Возможны ли прыжки вслепую, зависит от вашей системы FTL. Если речь идет только о вычислении космических координат, прыжок в случайное место безопасен на 99,9999+% . Хан Соло даже не знает, что такое парсек, так почему вы доверяете его объяснениям о сверхсветовой скорости ? Реальный риск плохо рассчитанного сверхсветового перемещения, особенно если вы используете какой-то механизм пространственного туннелирования, заключается не в том, чтобы добраться туда, а в обратном направлении.
Если вы окажетесь где-то полностью за пределами нанесенного на карту пространства, у вас может не быть пути назад, поскольку вам нужно достаточно знать об объектах между вашим источником и пунктом назначения, чтобы точно нанести его на карту. Теперь вам нужно вернуться до того, как у вас кончится еда/топливо. Но даже умеренная неточность может привести к потере большого количества времени и топлива, пытаясь исправить ошибку, особенно если сверхсветовые прыжки требуют большого количества топлива (если это не так, просто сделайте крошечный сверхсветовой прыжок для исправления). В результате было бы разумно, чтобы обычные (т. е. неэкстренные) переходы включали в себя большой объем вычислений. Это также может быть более важным, когда задействовано несколько кораблей, поскольку вы хотите, чтобы они достигли одного и того же пункта назначения.
Результат всего этого следующий:
Может ли специализированное оборудование улучшить эти цифры? Конечно. Сделайте это частью сюжета. «Тысячелетний сокол» «лучше справляется с гиперпространством», и, согласно фильму «Соло», это потому, что у него лучшее вычислительное устройство для гиперпространства [осторожно, спойлер].
Я программист, и довольно часто бывают процессы, длящиеся от долей секунды до часов.
Это не одно уравнение, а ряд поисковых данных и вычислений результата. Учитывая, что вы путешествуете в космосе, вполне вероятно, что частью того, что вы собираетесь делать, является разработка хорошей модели вашего положения и окружения. Обратный отсчет возможен как процент выполненной фоновой задачи, возможно, не очень точный, но должен ли он быть таким? Или, возможно, это может быть сюжетной точкой, он дает 30 секунд до конца и прыгает раньше, говорит, что это сделано, а затем прыгает через 5 секунд.
Вы можете сделать расчеты сколь угодно долгими, сказав, что точного «решения» не существует. Вместо этого есть только приближение, которое пилот может счесть «достаточно близким».
Например, может случиться так, что решение для гиперпрыжка должно быть получено путем моделирования прыжка на основе известных значений (возможно, сил гравитации и расстояний). Результатом будут места и вероятности, где корабль может оказаться. Незначительное изменение входных данных гипердвигателя может привести к совершенно другим результатам. (Входные данные могут включать массу корабля, начальные векторы, начальную скорость, сколько энергии сбрасывается в гипердвигатель и т. д.)
Плохое решение может разбрызгать корабль по всей Солнечной системе. Или приземлиться внутри звезды. Или укажите почти бесконечное количество мест, где корабль может оказаться, каждое с примерно равной вероятностью.
Проблемы с оптимизацией могут занять любое количество времени, поэтому они являются отличным инструментом для использования здесь. Хитрость оптимизации заключается в том, что обычно реальная задача является NP-сложной, но ее можно аппроксимировать с помощью P-алгоритмов. Чем больше процессорного времени вы готовы потратить, тем ближе будет приближение к идеальному ответу NP-сложной задачи.
Во многих физических ситуациях реальной жизни систему можно описать как набор нелинейных дифференциальных уравнений. Учитывая текущее состояние и желаемое состояние, вы можете вычислить оптимальный путь. Учитывая достаточно вымученный набор уравнений динамики, вы можете обнаружить, что есть очень тонкие пути с приемлемыми затратами, окруженные огромными ямами, где затраты совершенно неприемлемы. Поиск решения для пути через такую систему может быть чрезвычайно дорогим.
Они также могут сильно зависеть от начального состояния. На основе реального проекта, над которым я работал, ваши сверхсветовые компьютеры могли постоянно рассчитывать планы добраться из точки А в точку Б, где точка А где-то рядом, а точка Б далеко. Когда приходит время прыгать, вы решаете проблему для вашей точной точки А', засеянной вашим самым последним планом. Есть много оптимизаторов, которые работают намного лучше, если им задана близлежащая точка.
Также помните, что прыжок может состоять не только из одного импульса. Это может быть полное динамическое решение на время нахождения корабля в гиперпространстве. Излишне говорить, что это резко увеличивает пространство состояний для этой задачи оптимизации, увеличивая сложность настолько, насколько вам нравится.
Возможно, это немного похоже на вызов кадра, но может быть не так много проблем с математическими вычислениями на самом корабельном компьютере — выяснить, как безопасно совершить прыжок с другими кораблями, которые также совершают прыжки по тому же пути, и не столкновение с ними на сверхсветовых скоростях — вот где сложность ограничивает время, необходимое для совершения сверхсветового прыжка.
По общему признанию, это немного вдохновлено Guardians of the Galaxy Vol.2, другой космической историей, в которой использовались прыжки через портал для достижения «FTL», не обязательно просто двигаясь со скоростью выше скорости света, но тот же основной принцип может быть применен к Star Гипердвигатели в стиле «Войн» и их заявление о том, что просто прыгнуть не так просто, и это может объяснить, почему звездному разрушителю требуется столько же времени, сколько «Тысячелетнему соколу», чтобы совершить сверхсветовой прыжок, и даже зная, где находится пункт назначения, используя отслеживание гиперпространства, они не могли обязательно просто доберитесь до локации раньше другого корабля в FTL.
Таким образом, корабельный компьютер будет полагаться не на свой компьютер, а на способность его компьютера отправить запрос другим компьютерам-ретрансляторам и убедиться, что они могут безопасно совершить прыжок в одно место и использовать его для перехода в другое, потенциально предварительное. -нанесенное на карту местоположение с определенной сверхсветовой скоростью (скажем, 1,25с вместо 1,5с или 2,5с, в зависимости от того, до чего их корабль может ускоряться/замедляться).
Указанные ретрансляторы, скорее всего, будут вести учет общедоступного времени для кораблей, чтобы гарантировать, что они не конфликтуют — возможно, с учетом размеров кораблей, чтобы они могли знать, насколько эффективно они могут работать с кораблями, и проверять, могут ли они безопасно покинуть гиперпространство без крушения. в другой корабль, который покидал те же ворота и замедлялся первым, и подтверждал определенный временной интервал или отклонял определенный временной интервал, запрошенный для корабля, пытающегося совершить гиперпространственное путешествие.
По общему признанию, объяснение портала/ретранслятора довольно близко к нарушению:
В пределах наблюдаемых сверхсветовых характеристик, которые я описал, и без производства некоторого набора трудоемких ручных вычислений, то есть без изобретения конкретной системы.
Но те же расчеты можно применить к гиперпространственным прыжкам в стиле «Звездных войн», тем более, что иногда в «Звездных войнах» корабли проходят через гиперпространство в строю . Так что по крайней мере какое-то подтверждение того, когда войти и откуда войти и как безопасно выйти, должно быть подтверждено, так как вы не захотите двигаться быстрее, чем корабль прямо перед вами, даже если, гипотетически, ваш Корабль мог пройти через FTL быстрее.
Однако для этого может потребоваться связь с другими кораблями, а система перехода через ретрансляцию/портал позволит кораблю не обязательно сообщать вражеским кораблям, куда они направляются, не конфликтуя с ними.
Это также дает возможный пример более масштабного способа масштабирования транзакций, необходимых для обеспечения сверхсветовой скорости, учитывая разницу в том, сколько времени требуется кораблю, чтобы добраться до сверхсветовой скорости...
В конечном счете, эти ретрансляторы, вероятно, хотели бы иметь способ обеспечить, чтобы никто не нарушал правила, которые они установили с точки зрения доступных временных рамок, и пытались вмешаться, когда другой корабль также занимает точно такое же место в FTL-емкости.
Учитывая, что эти ретрансляторы, вероятно, автоматизированы для их уровней трафика и не разрешаются, как современные самолеты, летящие над Северной Атлантикой , и необходимость управлять гораздо большим количеством ретрансляторов, которые, возможно, могут быть подключены к одному и тому же соединению, вы хотели бы представить временные рамки таким образом, чтобы максимально использовать имеющееся у них время, оставляя пробелы для тех, кто совершает импровизированный прыжок и, надеюсь, решает свою проблему быстрее.
В результате для выполнения действий могут быть запрошены различные корабельные компьютеры, или вместо этого могут потребоваться различные компьютеры, специфичные для ретрансляции, набора транзакций, связанных с блокчейном, на временном интервале, через который они проходят, и какие ретрансляторы чтобы перейти от одного получения к следующему.
Количество блоков транзакций в блокчейне, необходимое для обеспечения актуальности и точности реестра для предотвращения конфликтов при поездках, может быть причиной значительного количества времени, что дает бортовому компьютеру, возможно, только столько же, сколько IP-адрес маршрутизатора способ указать, где они хотят уйти, и пусть остальная часть ретрансляционной сети определяет, как они на самом деле туда доберутся. и когда они будут приходить и уходить каждую эстафету так, чтобы это было гладко.
Или, короче говоря, гиперпространственный трафик является причиной того, почему расчет маршрута занимает так много времени, учитывая, что вы не можете пересчитать промежуточное путешествие на задействованных сверхсветовых скоростях.
Итак , ЭФЭ
Выглядит довольно просто, не так ли? Но это не так.
ваша отправная точка в этом упрощенном кошмаре. Это выражение вашей системы координат. Это может быть 3 измерения пространства + 1 времени (обычные 3+1 = 4D), что-то более простое или (для вычисления более высоких измерений (таких как «гиперпространство») более сложное.
ваша вторая производная от , относительно каждого элемента . Так что это , но это также и . Все сказано, есть уравнения для любого заданного , где N — количество измерений (4 для трехмерного пространства + 1 для времени) = 64 уравнения.
Многие из этих 64 уравнений предварительно выгружаются при выполнении этого вручную, предполагая, что некоторые значения будут нулевыми, постоянными или дублируют другие. Но мы пытаемся выяснить, насколько большим может быть вычисление, так что давайте ничего не пропустим.
R является продуктом , — это ваш тензор энергии напряжения и может быть мощность двигателя корабля, искривляющего пространство, которое вы пытаетесь вычислить, хотя другие массивные и энергичные тела вносят свой вклад в эту энергию напряжения. Предполагается, что G постоянна, но может и не быть таковой.
Как только вы вычислите это уравнение для одного набора точек, вы можете вычислить геодезическую (основные уравнения гравитационного движения).
Каждое уравнение имеет по крайней мере одно «тело» или «компонент», вносящий вклад в него (это не совсем так, решение с нулевым телом равно нулю, но это ни к чему не приводит). Каждый «компонент» может вносить как минимум один член (n = 1), так и столько, сколько n =
Если теория струн верна, то существует 10 измерений пространства + 1 измерения времени, и если предположить, что для вашего расчета гиперпространства вы не можете пренебречь ни одним из них.
Это N = 11, = 1331 уравнение различных свойств, которые вы просматриваете в своем альманахе или в данных датчиков, прежде чем сможете вычислить расход топлива двигателя.
Итак, допустим, вы прыгаете на орбиту:
Но предположим, что солнечный ветер вносит большой вклад в навигационную ошибку в гиперпространстве, и вам нужно пересчитывать, скажем, каждую тысячу километров между этим местом и Луной (400 000 километров). Всего у вас будет около 2,1 миллиарда вычислений. Не так уж и плохо для современного компьютера.
Но предположим, что вы направляетесь с Земли на Марс: нужно беспокоиться еще о 3 телах (Марс и две его луны) и 2,1 миллиарда километров расстояния при максимальном сближении между Землей и Марсом (в пять раз больше, чем при наибольшем расстоянии между Землей и Марсом). и Марс, который пройдет по путям Венеры и Меркурия). миллион = 22 триллиона вычислений. Что заняло бы 372 минуты на современном процессоре с частотой 1 гигагерц.
Представьте себе не самый лучший подход к Марсу мимо Венеры и Меркурия: миллион = 141 триллион вычислений, что занимает 39 часов на современном компьютере (вам понадобится более быстрый компьютер будущего, чтобы выполнять такие вычисления на лету).
Это также может объяснить, почему в этих научно-фантастических сценариях точное попадание в пункт назначения обычно является чем-то вроде неожиданности: вы пренебрегаете всевозможными вещами, такими как космическая пыль, более мелкие камни и другие корабли, просто для того, чтобы вычислить это вовремя. способ. В расчете много ошибок, потому что вы сознательно игнорируете многие вещи, которые способствуют получению ответа, просто для того, чтобы вы могли получить какой-либо ответ своевременно.
Это также может объяснить, почему в некоторых научно-фантастических сценариях, использующих эту идею, большинство специалистов в области математики рассматривают «высокоточные» прыжки (например, в атмосферу планеты или вообще «слишком близко» к планете). -вселенная, чтобы быть самоубийственной. Это.
И давайте будем реалистами: расчет сверхсветовой скорости не будет включать фактическое перекодирование видео, потому что это явно не имеет отношения к путешествию.
На самом деле, транскодирование может быть именно тем, что делает ваш корабль! Нормальная материя ограничена скоростью света; так что, чтобы превысить скорость света, вам может понадобиться стать чем-то совершенно другим... Итак, что делает ваш корабль, так это он учитывает каждый атом на вашем корабле и переводит его в поток данных сверхсветовой энергии, который затем собирается заново. обратно в нормальную материю где-то еще, как транспортер в стиле «Звездного пути».
Но прежде чем ваш корабль сможет это сделать, он должен просканировать себя целиком и перекодировать его в точный поток данных. Вы не можете заранее рассчитать это, потому что точный состав и расположение вашего корабля и вещей на нем меняется от момента к моменту, когда люди ходят и что-то делают. Если бы вы сказали, например, просканировать свой корабль за 3 недели, то весь груз, который вы собрали на прошлой неделе, исчез бы, и все забыли бы, чем они занимались последние 3 недели, потому что вы в основном «используете старый файл сохранения». . Но что еще хуже, если вы использовали расчет, предполагающий существование чего-то, чего больше нет, то у вас не будет достаточно материи, чтобы полностью перевести ее в сверхсветовой поток данных; таким образом, вы можете выйти с другой стороны, упустив что-то еще, что нужно было собрать из той же массы; Итак, поздравляю,
Так что долго рассчитывается не траектория полета, а точное состояние вашего корабля в момент активации прыжкового двигателя. Вы делаете «моментальный снимок» своего корабля очень быстро, но затем тратите минуты или около того на перекодирование этого снимка в поток данных.
Итак, как это гарантирует, что вычисление занимает время в человеческом масштабе?
Ответ Рэя Баттерворта отлично объясняет, почему существует такое узкое окно между смехотворно длинным и коротким вычислением, когда вычисления экспоненциально масштабируются в соответствии с задачей типа коммивояжера или задачи с несколькими телами. Но транскодирование следует другому набору правил. Фактическая математика транскодирования видео очень проста до такой степени, что одна операция может быть измерена в миллиардных долях секунды, но в любом случае это занимает много времени, потому что процесс содержит триллионы операций, которые должны произойти.
Ваш транспортер следует той же логике. Ваш корабль начинается с молекулярного снимка всего корабля... скажем, мы смотрим на эсминец водоизмещением 10 000 тонн.
Если мы предположим, что средняя молярная масса составляет около 45 г/моль, мы можем сказать, что ваш корабль содержит около 1,34e32 молекул, которые необходимо преобразовать в какую-либо точку данных. С современными компьютерами это заняло бы тупо много времени и потребовало бы компьютера гораздо более массивного, чем сам ваш корабль, но мы не говорим о современных компьютерах. Если ваша цивилизация научилась упаковывать данные в ложный космический вакуум или в еще не открытые субатомные частицы, из которых состоят все остальные субатомные частицы, тогда вы сможете хранить и обрабатывать огромные объемы данных в одном атоме. . Поскольку единственное, что ваш корабль делает в этом масштабе, — это буферизация боевого двигателя, это означает, что вы можете сканировать в атомном масштабе и терять свой варп-буфер только во время прыжка.
Причина, по которой это хорошо масштабируется для вашего сеттинга, заключается в том, что его сложность имеет линейную зависимость от размера вашего корабля. Таким образом, расчеты для корабля водоизмещением 10 000 тонн всего в 5 раз сложнее, чем для корабля водоизмещением 2 000 тонн. Таким образом, в этом отношении вы не можете просто добавлять компьютеры до тех пор, пока вычисление не станет произвольно коротким, потому что чем быстрее вы хотите, чтобы транскодирование происходило, тем больший процент вашего корабля вам нужно выделить для вычислительной мощности. Таким образом, хотя это не совсем то же самое, что перекодирование видеофайлов, оно будет следовать более или менее тем же принципам. Вам просто нужно сопоставить вычислительную технологию вашей настройки с общим временем ожидания, которое требуется вашему графику.
Л.Датч
Джонатан Хартли
Шейн
Мирал
Джошуа
Чиггси
Джошуа