Комментарии 47
Как за полиномиальное время проверить, что мы нашли самый короткий маршрут в задаче коммивояжёра?
Автор похоже некорректно изложил мысль.
Пример: задача коммивояжёра. Дан список городов и расстояний. Нужно найти самый короткий маршрут, проходящий через каждый город ровно один раз и возвращающийся в исходную точку.
Проверка (NP): если вам дали готовый маршрут, вы легко (за полиномиальное время) сложите все расстояния и проверите его длину
)) проверка np не относится к заявленной задаче, а к другой, когда проверяется заявленная длина по известному маршруту. Сам немного завис.
Быстрое гугление показало, что NP-полной является несколько изменённый вариант задачи коммивояжёра, в котором предполагается искать не самый короткий маршрут, а маршрут не длиннее заданной длины. Проверка тут тривиальна.
Исходную задачу коммивояжёра при этом можно свести к измененной через бинарный поиск.
Для 100 городов это больше, чем атомов во Вселенной.
Если быть дотошным, то число атомов во Вселенной оценивается где-то в 10^80, это значение достигается уже при 60 городах примерно. 100! - это не просто больше, а сильно больше, порядков этак на семьдесят больше.
Глобальные цепочки поставок... Транспорт без пробок
А вот тут не всё так уж плохо, кстати. В прошлом году я сделал небольшое упражнение — оптимизацию перемещения манипулятора (скажем, сверление отверстий в печатной плате или неразрушающий контроль сложной детали). Я заполнил матрицу весов случайными значениями от одной до двух секунд, то есть в среднем получалось полторы секунды на перемещение. Так вот, если перемещать манипулятор просто последовательно, то для 60 позиций и выйдет 90 секунд, а для 120 — примерно 180. Всё сходится. Но если найти оптимальный маршрут, то получилось 61,7 секунды для 60 позиций и 121,6 — для 120, что очень хорошо, это очень близко к абсолютному минимуму. Я на Питоне набросал десяток методов с помощью копилота (без него я бы, честно говоря, офигел все эти муравьиные колонии да симуляции отжига руками программировать), и оказалось, что алгоритм смешанного целочисленного линейного программирования (который MILP) работает лучше всего. Он решает задачу на сотню позиций буквально за несколько секунд — хотя это, конечно, не гарантированный минимум, но я был впечатлён. Этот алгоритм я потом переложил на Rust. Вот тут упражнения на GitHub со всеми исходниками, если кому интересно: https://github.com/AndrDm/atsp-ndt.
Да, при этом может оказаться, что "идеальный" алгоритм коммивояжёра (в гипотетическом случае P = NP) будет значительно сложнее "приблизительного" MILP.
Если быть ещё более дотошным, то число атомов Вселенной никто не знает даже примерно, он может быть даже бесконечным. А вы пишите про число атомов наблюдаемой Вселенной.
если быть еще более дотошным, то сложность определяется не только количеством городов, а и количеством дорог между ними. N! - это только если каждый город связан с каждым прямой дорогой, что сложно представить для 100 реальных городов
В задачах реальной логистики узлами являются не города, а точки в городе. Рёбра же отражают время, требуемое чтобы добраться от одной точки до другой по дорогам общего пользования. Тут граф получается именно что полносвязный.
А мне интересно - почему всегда рассматривают\сравнивают метод тупого перебора? Он самый оптимальный?
Это как про невозможность для шахматного компьютера просчитать все партии. А не надо считать все, надо только выигрышные. А уж за века шахматная теория отделять зёрна от плевел научилась.
за века шахматная теория отделять зёрна от плевел научилась
эвристиками:)
шахматы ничейная игра, о каких выйгрышных позициях можно говорить если будут играть хорошие движки друг против друга
А это уже доказали?
Формально нет, но гипотеза о том что для белых существует выигрышная стратегия из начальной позиции, выглядит совсем уж маловероятной.
Косвенный признак "ничейности" - то что в партиях между сильными игроками ничьи случаются чаще, и с появлением движков играющих намного сильнее людей, эта тенденция продолжилась.
Пока что движки не настолько хорошие чтобы все их партии между собой заканчивались вничью.
Глобальные цепочки поставок перестанут страдать от кризисов.
Транспорт без пробок станет реальностью не за счет беспилотных машин, а за счет единого оптимального потока.
Если проблема только в задаче коммивояжёра, то для неё есть алгоритмы находящие решение близкое к оптимальному, даже для многих тысяч нод.
Особенно умиляет, когда на голубом глазу утверждают, мол, алгоритмы нам помогут, вот заживем! Хотя в этом же примере зачастую из пункта A в B без пробок все равно не проедешь, ибо суммарная пропускная способность дорог не увеличилась.
Задача коммивояжёра вообще имеет очень сильно косвенное отношение к оптимизации городского транспорта. Тут скорее алгоритмы вроде A* более актуальны, для нахождения кратчайшего пути в условиях пробок.
А* тут нафиг не нужен, в условиях города гораздо лучше работает банальнейший алгоритм Дейкстры. Однако, это позволяет найти оптимальный путь только одному автомобилю, при масштабировании же алгоритм начинает скорее создавать пробки чем позволять их объехать.
Для задачи именно оптимизации всего городского транспорта в моменте требуется что-то вроде нахождения оптимального потока. А при планировании можно ещё и остановки двигать, и задача становится ещё сложнее.
А* тут нафиг не нужен, в условиях города гораздо лучше работает банальнейший алгоритм Дейкстры.
Они же одно и то же решение найдут при одинаковых исходных данных, только A* быстрее отработает - или я что-то не догоняю?
Скорее определение точек притяжения трафика и время смены потоков от/к таким точкам/узлам, выделение основных, самых плотных потоков, и регулировка именно этих, основных потоков. Причём, не расширением дорог внутри замкнутого контура, а созданием новых путей к конечным точкам и самих точек, либо переносом точек. Например вынос рабочих мест чиновников из Москвы в Подмосковье существенно изменит утренне-вечерний трафик в городе.
Это станет интеллектуальным Big Bang. Мы сможем...
Я сколько читаю телеги по P/NP, одного не могу понять. Как в вашей цепочке рассуждений доказательство какого-то утверждения переходит в конкретные последствия? Допустим, завтра вы просыпаетесь и у вас на столе лежит железобетонное доказательство - дальше что?
Если доказательство неконструктивное - то ничего. А вот если оно конструктивное...
Да даже если конструктивное, то не факт, что оно полезно. Вон, например, метод эллипсоидов нашли полиномиальный для решения задач линейного программирования. Однако экспоненциальный симплекс-метод на пенсию, мягко скажем, не ушёл.
Для чистых математиков это вообще характерно - доказательство наличия решения важнее самого решения. Постоянно с этим с этим сталкиваюсь во всяких научных работах, причём посвященным чисто прикладным вопросам - вычислению функций или любимому мною FFT. Например, кто-то "улучшил" FFT снижением умножений заменой синуса на тангенс (грубо говоря), а то, что сам алгоритм из-за этого получается сложнее и численно неустойчивее - скромно замалчивается. И естественно никаких готовых алгоритмов, которые можно взять и запрограммировать.
Если окажется, что P=NP, то мы сможем доказывать любые теоремы за полиномиальное время, тк это тоже np полная задача (решение как сертификат). Ну а если мы можем доказать или опровергнуть любой факт из математики, то это в корни изменит математику и весь мир.
Конечно, это всё если нам крупно повезёт: константа будет не очень большой и степень у полинома)
Как нам говорил препод, если доказать np = p, можно получить миллион долларов, а потом доказать оставшиеся задачи 1000летия с помощью того алгоритма и залутать оставшиеся 5 миллионов)
Я может пропустил это в тексте, его много и он непростой. Но сама задача сравнения P и NP к какому классу относится?
Вопрос "P = NP?" не является вычислительной задачей.
И глубокий анализ РКН будут идеально блочить любой трафик!)
А ещё есть вариант, что ни доказать, ни опровергнуть нельзя. И мы навсегда остаёмся в неведении.
Транспорт без пробок уже придумали, для этого не нужно решать np
Задача «распределить миллион автомобилей по дорогам мегаполиса за час так, чтобы минимизировать среднее время в пути» будет решена
"Ох уж эти сказочники" (С). Если "среднее время в пути" 30 минут, то это значит что кто-то едет час, а кто-то минуту :). А почему час должен ехать именно я? Я поеду туда, где за минуту! И все поедут:)
Окей, ломаем биткоин. Он построен на двойном SHA-256, который принимает на вход блоки по 512 бит (ну так устроен SHA-256). "Ломаем" значит находим для нужного нам хэша любой блок входных данных, который даст этот хэш (быстро ищем хэш-коллизию).
Полиномиальный алгоритм имеет сложность минимум O(n^5). Просто потому что для O(n^4) есть формула, которую разумеется сразу же проверили.
2*512^5 ~= 70 трлн. Предположим, скорость такая же, как у SHA-256, т.е. десятки миллионов хэшей на CPU и - в перспективе - гигахэши на ASIC (которые ещё надо разработать и сделать). Т.е. порядка года на компе, сутки на асиках, но через год. Не очень похоже на "взлом к понедельнику", да? И это в самых тепличных условиях.
За это время ничего не мешает перейти скажем на 4-килобАйтные хэши (32768-битные), скорость хэширования на CPU замедлится линейно (в 64 раза), а вот скорость подбора упадёт в миллиард раз...
Максимально непонятным языком написано.
Что понимается под много раз упомянутым термином "полиномиальный", особенно "полиномиальное время"? На примерах, плз. Что, на сколько, восколько раз будет увеличиваться и при увеличении чего? В обычном многочлене n-ной степени имеет место полиномиальный рост значения при увеличении переменной?
Что такое NP, понятным языком, плз? Я-то понял (не по этой статье, конечно), но через такие описания продраться невозможно.
И наконец главное: каким же образом доказательство некоей гипотезы, т.е. констатация истинности утверждения, позволит обеспечить всю описанную матемагию? Если ни одного опровержения этого нет, то что мешает предположить, что P=NP, и по принципу "act as if" начать решать всё это? Вот если не получится решить - это, надо полагать, и будет опровержением... Или нет? Всё-таки что-то тут не то.
, где p - полином. Или многочлен, это полные синонимы.
С какого перепуга автор утверждает, что проверка задачи коммивояжера P? И решение и проверка NP.
Бот говорит, что классические NP задачи - это SAT, задача о рюкзаке, ну и факторизация.
P =? NP: самая дорогая задача в мире, которая может перевернуть всё