CodeLab
145 subscribers
538 photos
20 videos
159 links
Говорим просто о сложном

Обсуждение, новости, материал и сплетни — все здесь https://t.me/CodeLabMLChat
Download Telegram
Так решена ли задача о коммивояжере или нет? 🔗 Пост об этом 🔗

🧑‍💻Вы, наверное, все спите, но, да ладно. Мы уже разбирали задачу о коммивояжере и даже решали ее (очень подробно), пост для навигации я уже написал выше.

Дак вот, пару слов о задаче, чтобы вы вспомнили:

◽️ Если прям кратко, нам нужно найти кратчайший маршрут, проходящий через множество городов и возвращающийся в начальную точку (Не обязательно мы возвращаемся обратно, это скорее по классике, вариант без возврата даже будет попроще).

◽️🔗 Так
, теперь смотрите, поговорим о разнице этих двух кентов:

⚪️ В классической 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 считаются эффективно решаемыми на практике, так как их время решения увеличивается относительно медленно с ростом размера входных данных.
Класс NP (Недетерминированное полиномиальное время), мы уже близки.

⚫️ Класс NP состоит из задач, для которых, решение уже известно (TSP как раз сюда и относится), 🟰🟰"Мы можем проверить его правильность за полиномиальное время с помощью детерминированного алгоритма." — Это означает, что время проверки зависит от размера входных данных n и растет как многочлен от n, а процесс проверки следует одному возможному развитию событий (св-во детерминированности)🟰🟰.
Нам осталось действительно немного, эти классы необходимо было разобрать понимания задачи. Уже сегодня продолжим об этом, я пойду спать 💤
BUGS
⚪️ Краткие тезисы прошлых постов

🔗 Класс 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/ (Полезный материал)
Еще вам закину классную фотаче, где очень хорошо показано, как время выполнения различных алгоритмов изменяется в зависимости от размера входных данных n и сложности алгоритма Big(O).

🧑‍💻 Самый левый столбец — значения входных данных.
🔗 Пол и потолок (6.3)

В общем гайс, ниче сложного, подается лишь одно число x, а вычисляет значение по двум функциям:

⬜️ Функция floor() из модуля math в Python используется для округления чисел с плавающей точкой в меньшую сторону.

⬜️ Функция math.ceil() из модуля math в Python позволяет округлить число до ближайшего целого числа в большую сторону.

🔗 Теперь код:

from math import*
x = float(input())
ans = floor(x) + ceil(x)
print(ans) #Я иду спать, всем сладких
🪰
🌶🌶 Квадратное уравнение (6.3)

Думали, эти формулы вам не пригодятся?) Хуй бы не там, ща быстренько решим:

🔗 Я максимально расписывал код, но можно и намного короче:

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("Нет корней")
🧑‍💻 Последнее задания данного раздела 'Правильный многоугольник (6.3)'

🔗Переписываем по формуле:

from math import*
n = float(input())
a = float(input())

S = (n * pow(a, 2)) / (4 * tan(pi/n))
print(S)
🔗 Дальше по курсу у нас 🟰циклы🟰

О том, что такое циклы и зачем они нужны, мы уже разговаривали, ссылочку вам прикрепил, почитаете !

Чисто вкратце, сама структура цикла for, с чего мы и начнем:

for название_переменной_цикла in range(количество_повторений):
блок кода
🔗 Python is awesome (7.1 )

💲 Код:

s = "Python is awesome!"
for i in range(10):
print(s)
🔗 Повторяй за мной 1 (7.1)

⭕️ Код:

s = input() #Для строки
rep= int(input()) #Количество повторений

for i in range(rep):
print(s)
⭕️ Последовательность символов (7.1)

🔗 Код:

for i in range(6):
print("AAA")

for i in range(5):
print("BBBB")

print("E")

for i in range(9):
print("TTTTT")

print("G")
⭐️ Звездный прямоугольник (7.1)

🔗 Код:

n = int(input())

for i in range(n):
print("*" * 19)
🧑‍💻 Повторяй за мной 2 (7.1)

🔗 Код:

n = input()

for i in range(10):
print(i, n)


⚪️ Переменная цикла — это величина, изменяющаяся на каждой итерации цикла.

Первый аргумент функции print() это переменная цикла 🟰 i 🟰, вторая — значение переменной, в нашем случае, любая введенная строка.
⚙️ Квадрат числа (7.1)

"Функция range возвращает последовательность чисел в заданном диапазоне." Дак вот, поскольку нам сказали, что диапазон заканчивается на число (включительно), поэтому прибавляем единицу:

for i in range(n + 1):


🔗 Код:

n = int(input())

for i in range(n + 1):
print(f'Квадрат числа {i} равен {i ** 2} '


f' строки (если забыли)