🔗Navigation The traveling Salesman Problem (TSP)
0️⃣⁉️ Задача коммивояжёра — как ее рассчитать?
1️⃣🔗 Расчет для 5 городов (пример)
2️⃣🧑💻 Гамильтонов цикл и Гамильтонов путь (А также два основных вида задачи)
3️⃣🟰Класс P (Полиномиальное время)🟰
4️⃣⚙️ Класс NP (Недетерминированное полиномиальное время)
5️⃣‼️ Основные тезисы ‼️
6️⃣🌶🌶 Почему задача до сих пор не решена и почему вашего компьютера на нее не хватит
7️⃣ Время выполнения различных алгоритмов (Дополнительно, но очень годно)
__________________________________
🟰Н А В И Г А Ц И Я🟰
🟰 В Е Р Н У Т Ь С Я К А Л Г О Р И Т М А М🟰
0️⃣⁉️ Задача коммивояжёра — как ее рассчитать?
1️⃣🔗 Расчет для 5 городов (пример)
2️⃣🧑💻 Гамильтонов цикл и Гамильтонов путь (А также два основных вида задачи)
3️⃣🟰Класс P (Полиномиальное время)🟰
4️⃣⚙️ Класс NP (Недетерминированное полиномиальное время)
5️⃣‼️ Основные тезисы ‼️
6️⃣🌶🌶 Почему задача до сих пор не решена и почему вашего компьютера на нее не хватит
7️⃣ Время выполнения различных алгоритмов (Дополнительно, но очень годно)
__________________________________
🟰Н А В И Г А Ц И Я🟰
🟰 В Е Р Н У Т Ь С Я К А Л Г О Р И Т М А М🟰
Так решена ли задача о коммивояжере или нет? 🔗 Пост об этом 🔗
🧑💻Вы, наверное, все спите, но, да ладно. Мы уже разбирали задачу о коммивояжере и даже решали ее (очень подробно), пост для навигации я уже написал выше⏫.
Дак вот, пару слов о задаче, чтобы вы вспомнили:
◽️ Если прям кратко, нам нужно найти кратчайший маршрут, проходящий через множество городов и возвращающийся в начальную точку (Не обязательно мы возвращаемся обратно, это скорее по классике, вариант без возврата даже будет попроще).
◽️🔗 Так, теперь смотрите, поговорим о разнице этих двух кентов:
⚪️ В классической TSP задаче нам нужно найти кратчайший путь, скажем, A → B → C → D → A. 🔗 Уже заметили, что мы возвращаемся обратно? Дак вот, то, что мы по факту ищем, называется 🟰гамильтоновым циклом🟰. Все куда проще, чем кажется! Берем тот же пример: A → B → C → D → A — это самый обычный граф, а цикл, который проходит через каждую вершину ровно один раз и возвращается обратно и называется 🟰гамильтоновым🟰. То есть, наш цикл проходит через каждую вершину ровно один раз и заходит в начальную точку! Представьте себе поставки грузовых автомобилей, которые возвращаются на склад, они выехали и заехали в одну и ту же точку.
⚪️ Теперь, касаемо Open TSP задачи (без возврата в начальную точку или вершину): допустим, A → B → C → D — такой наш маршрут, уже без возврата. В этой задаче уже попроще, на этот раз мы ищем 🟰гамильтонов путь🟰 (Начинается в одной вершине и заканчивается в другой, он проходит через все вершины графа ровно один раз, но не возвращается в исходную точку.) Я же говорил, что не так уж и сложно!
🔗 Полезная ссылочка:
https://ru.hexlet.io/courses/graphs/lessons/hamiltonian/theory_unit
🧑💻Вы, наверное, все спите, но, да ладно. Мы уже разбирали задачу о коммивояжере и даже решали ее (очень подробно), пост для навигации я уже написал выше⏫.
Дак вот, пару слов о задаче, чтобы вы вспомнили:
◽️ Если прям кратко, нам нужно найти кратчайший маршрут, проходящий через множество городов и возвращающийся в начальную точку (Не обязательно мы возвращаемся обратно, это скорее по классике, вариант без возврата даже будет попроще).
◽️🔗 Так, теперь смотрите, поговорим о разнице этих двух кентов:
⚪️ В классической TSP задаче нам нужно найти кратчайший путь, скажем, A → B → C → D → A. 🔗 Уже заметили, что мы возвращаемся обратно? Дак вот, то, что мы по факту ищем, называется 🟰гамильтоновым циклом🟰. Все куда проще, чем кажется! Берем тот же пример: A → B → C → D → A — это самый обычный граф, а цикл, который проходит через каждую вершину ровно один раз и возвращается обратно и называется 🟰гамильтоновым🟰. То есть, наш цикл проходит через каждую вершину ровно один раз и заходит в начальную точку! Представьте себе поставки грузовых автомобилей, которые возвращаются на склад, они выехали и заехали в одну и ту же точку.
⚪️ Теперь, касаемо Open TSP задачи (без возврата в начальную точку или вершину): допустим, A → B → C → D — такой наш маршрут, уже без возврата. В этой задаче уже попроще, на этот раз мы ищем 🟰гамильтонов путь🟰 (Начинается в одной вершине и заканчивается в другой, он проходит через все вершины графа ровно один раз, но не возвращается в исходную точку.) Я же говорил, что не так уж и сложно!
🔗 Полезная ссылочка:
https://ru.hexlet.io/courses/graphs/lessons/hamiltonian/theory_unit
🧑💻 Продолжаем дискуссию, решена ли она?
⚫️ Теперь говорим о классах сложности этих двух задач:
◾️ Начнем с P (Полиномиальное время). Класс P состоит из задач, которые могут быть решены детерминированным алгоритмом за полиномиальное время относительно размера входных данных. Теперь поясню:
◼️ Детерминированный алгоритм — значит предопределенный, ▪️давайте еще проще▪️, помните бинарный поиск? У нас всего один алгоритм выполнения — постоянное деление пополам и сравнение с результатом, и никуда в сторону мы не 'отходим', действуем по заданному алгоритму. ⚫️ Подводя итоги, в детерминированном алгоритме всего один возможный путь развития событий. Есть у нас входные данные, значит алгоритм будет выполнять один и тот же набор действий!
⚫️ Что такое полиномиальное время?
Представим функцию вида: T(n) = nᵏ. В данном примере, k - константа, является полиномиальной, то есть, это многочлен от размера входных данных n. 🔗Ща все поймете🔗,
Квадратичное время: T(n) = n², Здесь, если n удвоить, количество шагов увеличится в четыре раза. То есть, переменная k показывает, как быстро работает алгоритм в зависимости от размера входных данных. Эти алгоритмы сложности O(n), O(n²), O(n³) являются быстрыми с полиномиальным временем.
🖤 Задачи из класса P считаются эффективно решаемыми на практике, так как их время решения увеличивается относительно медленно с ростом размера входных данных.
⚫️ Теперь говорим о классах сложности этих двух задач:
◾️ Начнем с P (Полиномиальное время). Класс P состоит из задач, которые могут быть решены детерминированным алгоритмом за полиномиальное время относительно размера входных данных. Теперь поясню:
◼️ Детерминированный алгоритм — значит предопределенный, ▪️давайте еще проще▪️, помните бинарный поиск? У нас всего один алгоритм выполнения — постоянное деление пополам и сравнение с результатом, и никуда в сторону мы не 'отходим', действуем по заданному алгоритму. ⚫️ Подводя итоги, в детерминированном алгоритме всего один возможный путь развития событий. Есть у нас входные данные, значит алгоритм будет выполнять один и тот же набор действий!
⚫️ Что такое полиномиальное время?
Представим функцию вида: T(n) = nᵏ. В данном примере, k - константа, является полиномиальной, то есть, это многочлен от размера входных данных n. 🔗Ща все поймете🔗,
Квадратичное время: T(n) = n², Здесь, если n удвоить, количество шагов увеличится в четыре раза. То есть, переменная k показывает, как быстро работает алгоритм в зависимости от размера входных данных. Эти алгоритмы сложности O(n), O(n²), O(n³) являются быстрыми с полиномиальным временем.
🖤 Задачи из класса P считаются эффективно решаемыми на практике, так как их время решения увеличивается относительно медленно с ростом размера входных данных.
Класс NP (Недетерминированное полиномиальное время), мы уже близки.
⚫️ Класс NP состоит из задач, для которых, решение уже известно (TSP как раз сюда и относится), 🟰🟰"Мы можем проверить его правильность за полиномиальное время с помощью детерминированного алгоритма." — Это означает, что время проверки зависит от размера входных данных n и растет как многочлен от n, а процесс проверки следует одному возможному развитию событий (св-во детерминированности)🟰🟰.
⚫️ Класс NP состоит из задач, для которых, решение уже известно (TSP как раз сюда и относится), 🟰🟰"Мы можем проверить его правильность за полиномиальное время с помощью детерминированного алгоритма." — Это означает, что время проверки зависит от размера входных данных n и растет как многочлен от n, а процесс проверки следует одному возможному развитию событий (св-во детерминированности)🟰🟰.
Нам осталось действительно немного, эти классы необходимо было разобрать понимания задачи. Уже сегодня продолжим об этом, я пойду спать 💤
⚪️ Краткие тезисы прошлых постов
🔗 Класс P (Polynomial time):
0️⃣ У нас есть задачи, время выполнения которых зависит от количества входных данных, это означает, 🟰за полиноминальное время🟰.
1️⃣ Еще один момент, такие задачи решаются детерминированным алгоритмом, это означает, что есть всего один возможный путь развития событий. Все эти вышеописанные свойства характерны для класса P.
2️⃣ Задачи класса P эффективны на практике, поскольку время решения увеличивается относительно медленно с ростом размера входных данных.
⚪️ Если задача находится в классе P, значит, мы можем найти её решение относительно быстро, даже если размер входных данных огромен)
🔗 Класс NP (Non-deterministic Polynomial time):
3️⃣ Касаемо класса NP, к которому и относится наша задача о коммивояжере:
Этот класс включает задачи, которые можно проверить за полиноминальное время детерминированным алгоритмом (То есть, быстро и с определенным алгоритмом выполнения). Но, решение может занять куда больше времени, больше чем полиноминальное. Заметьте, что речь идет лишь о проверке уже найденного решения, а не о нахождении решения)
⚪️ Полиномиальное время — это мера того, насколько быстро алгоритм может решить задачу в зависимости от размера входных данных.
4️⃣ Если быть еще точнее, у класса NP есть подкласс NP - полные задачи. Это самые 🌶 сложные задачи этого класса. Туда как раз и относится наша задача о коммивояжере. Если мы найдем ее за полиноминальное время — каждая задача в классе NP могла бы быть решена за полиномиальное время (то есть очень быстро).
🔗 Класс P (Polynomial time):
0️⃣ У нас есть задачи, время выполнения которых зависит от количества входных данных, это означает, 🟰за полиноминальное время🟰.
1️⃣ Еще один момент, такие задачи решаются детерминированным алгоритмом, это означает, что есть всего один возможный путь развития событий. Все эти вышеописанные свойства характерны для класса P.
2️⃣ Задачи класса P эффективны на практике, поскольку время решения увеличивается относительно медленно с ростом размера входных данных.
⚪️ Если задача находится в классе P, значит, мы можем найти её решение относительно быстро, даже если размер входных данных огромен)
🔗 Класс NP (Non-deterministic Polynomial time):
3️⃣ Касаемо класса NP, к которому и относится наша задача о коммивояжере:
Этот класс включает задачи, которые можно проверить за полиноминальное время детерминированным алгоритмом (То есть, быстро и с определенным алгоритмом выполнения). Но, решение может занять куда больше времени, больше чем полиноминальное. Заметьте, что речь идет лишь о проверке уже найденного решения, а не о нахождении решения)
⚪️ Полиномиальное время — это мера того, насколько быстро алгоритм может решить задачу в зависимости от размера входных данных.
4️⃣ Если быть еще точнее, у класса NP есть подкласс NP - полные задачи. Это самые 🌶 сложные задачи этого класса. Туда как раз и относится наша задача о коммивояжере. Если мы найдем ее за полиноминальное время — каждая задача в классе NP могла бы быть решена за полиномиальное время (то есть очень быстро).
‼️Наконец, мы подошли к итогам (Самое важное)‼️
⭕️ Метод, который мы разбирали (брутфорс, перебор всех значений) является неэффективным, особенно для 66 городов) Вы просто прикиньте факториал из 66 перестановок! Только одни бл❌ть перестановки! А еще не забывайте, что нам нужно рассчитать маршруты между городами (или точками, как хотите), затем посчитать это все и сравнить и только потом, найти минимальный маршрут)
⭕️ Задача о коммивояжере считается NP полной (complete), это, чтобы вы просто понимали, эквивалентно по сложности всем задача класса NP)
Факториал 24 это уже 620448401733239439360000 перестановок, поэтому о 66 городах смысла говорить просто нет!
‼️На текущий момент не существует известного алгоритма, который бы мог решить задачу коммивояжера за полиномиальное время (то есть, эффективно) для всех возможных случаев. (Но при этом, есть алгоритмы покруче брутфорса, надеюсь, попозже мы их обязательно разберем)
🔗 P = NP:
Вопрос о равенстве двух классов до сих пор не решен, но многие склонны к не равенству, поскольку, вот уже более чем трех с половиной десятилетий не было найдено алгоритма с полиномиальным временем выполнения ни для одной из 3000 известных NP-complete задач.
🔗 Полезные ссылки:
https://en.wikipedia.org/wiki/List_of_NP-complete_problems (List of NP-complete problems)
https://habr.com/ru/articles/43224/ (Полезный материал)
https://ru.hexlet.io/courses/graphs/lessons/hamiltonian/theory_unit (Гамильтонов цикл и Путь)
https://skillbox.ru/media/code/big-o-notation-chto-eto-takoe-i-kak-eye-poschitat/ (Полезный материал)
⭕️ Метод, который мы разбирали (брутфорс, перебор всех значений) является неэффективным, особенно для 66 городов) Вы просто прикиньте факториал из 66 перестановок! Только одни бл❌ть перестановки! А еще не забывайте, что нам нужно рассчитать маршруты между городами (или точками, как хотите), затем посчитать это все и сравнить и только потом, найти минимальный маршрут)
⭕️ Задача о коммивояжере считается NP полной (complete), это, чтобы вы просто понимали, эквивалентно по сложности всем задача класса NP)
Факториал 24 это уже 620448401733239439360000 перестановок, поэтому о 66 городах смысла говорить просто нет!
‼️На текущий момент не существует известного алгоритма, который бы мог решить задачу коммивояжера за полиномиальное время (то есть, эффективно) для всех возможных случаев. (Но при этом, есть алгоритмы покруче брутфорса, надеюсь, попозже мы их обязательно разберем)
🔗 P = NP:
Вопрос о равенстве двух классов до сих пор не решен, но многие склонны к не равенству, поскольку, вот уже более чем трех с половиной десятилетий не было найдено алгоритма с полиномиальным временем выполнения ни для одной из 3000 известных NP-complete задач.
🔗 Полезные ссылки:
https://en.wikipedia.org/wiki/List_of_NP-complete_problems (List of NP-complete problems)
https://habr.com/ru/articles/43224/ (Полезный материал)
https://ru.hexlet.io/courses/graphs/lessons/hamiltonian/theory_unit (Гамильтонов цикл и Путь)
https://skillbox.ru/media/code/big-o-notation-chto-eto-takoe-i-kak-eye-poschitat/ (Полезный материал)
🔗 Пол и потолок (6.3)
В общем гайс, ниче сложного, подается лишь одно число x, а вычисляет значение по двум функциям:
⬜️ Функция floor() из модуля math в Python используется для округления чисел с плавающей точкой в меньшую сторону.
⬜️ Функция math.ceil() из модуля math в Python позволяет округлить число до ближайшего целого числа в большую сторону.
🔗 Теперь код:
В общем гайс, ниче сложного, подается лишь одно число x, а вычисляет значение по двум функциям:
⬜️ Функция floor() из модуля math в Python используется для округления чисел с плавающей точкой в меньшую сторону.
⬜️ Функция math.ceil() из модуля math в Python позволяет округлить число до ближайшего целого числа в большую сторону.
🔗 Теперь код:
from math import*
x = float(input())
ans = floor(x) + ceil(x)
print(ans) #Я иду спать, всем сладких
🌶🌶 Квадратное уравнение (6.3)
Думали, эти формулы вам не пригодятся?)Хуй бы не там, ща быстренько решим:
🔗 Я максимально расписывал код, но можно и намного короче:
🔗🔗 Функция pow() возводит число в степень. Она принимает два параметра: какое число возводить и в какую степень возводить.
Думали, эти формулы вам не пригодятся?)
🔗 Я максимально расписывал код, но можно и намного короче:
from math import*
a = float(input())
b = float(input())
c = float(input())
D = pow(b, 2) - (4 * a * c)
if D > 0:
x1 = ((-b + sqrt(D))/(2 * a))
x2 = ((-b - sqrt(D))/(2 * a))
print(min(x1, x2))
print(max(x1, x2))
elif D == 0:
print(-b/(2 * a))
else:
print('Нет корней')
🔗🔗 Функция pow() возводит число в степень. Она принимает два параметра: какое число возводить и в какую степень возводить.
🔗А можно и вот так:
a=float(input())
b=float(input())
c=float(input())
d=b**2-4*a*c
if d < 0:
print("Нет корней")