ind = [1, 2, 3, 4, 5]
element = ind[3]
print(element)
🔗Вот вам пример работы такого алгоритма. ✅Ответ будет 4, потому что четверка имеет индекс 3, тут все логично) Мы получаем моментальный ответ, в этом и кайф константной сложности.🔝
‼️Кстати, со сложностью O(1), постоянной или константной сложностью (называйте как хотите), мы разобрались, дальше идет логарифмическое время...‼️
🥰1🤯1
Теперь, разбираем логарифмическое время O(log n), примеры также будут, но не знаю, смогу ли разобрать их сегодня. Начинаем!
🔗 Для начала, введем такое понятие как‼️Асимптотическая сложность алгоритма‼️ это оценка скорости роста времени работы алгоритма с увеличением размера входных данных, Она показывает, как время выполнения алгоритма или объем используемой памяти изменяется в зависимости от размера входных данных, когда этот размер становится очень большим. ✅ Проще говоря, найти из 1000 чисел загаданное, можно разными алгоритмами по-разному быстро, это и описывает наше новое понятие.
❗️Чтобы вы не путались, асимптотическая сложность описывает поведение алгоритма по времени в зависимости его входных данных, а Big(O) - это конкретный тип асимптотической сложности.
🔗 Для начала, введем такое понятие как
❗️Чтобы вы не путались, асимптотическая сложность описывает поведение алгоритма по времени в зависимости его входных данных, а Big(O) - это конкретный тип асимптотической сложности.
👨💻2
Теперь возвращаемся обратно к логарифмическому времени... Как раз у логарифмического времени асимптотическая сложность - O(log n) ❗️Это чисто для понимания, как это понятие будет употребляться в данном контексте❗️
Время выполнения такого алгоритма увеличивается логарифмически по мере роста размера входных данных. Щас вам объясню:
0️⃣ Вспомним сначала логарифмы, log2(8) = 3 ( Логарифм 8 по основанию 2 равен 3, потому что 2 возводим в 3 степень, первый шаг сделан )
1️⃣ Помните наш список [0, 16, 22, 4, 17, 8] пару постов назад? ‼️‼️Теперь отсортируем его [0, 4, 8, 16, 17, 22]. Зачем мы его отсортировали? Самый простой пример работы этого алгоритма - это бинарный поиск. Мы уже упоминали простой поиск, когда нам нужно перебрать все элементы, сравнивая их с нашей 'целью' (а проще сказать, с загаданным числом). пока не наткнемся на него. А бинарный поиск куда более эффективен... Суть такого поиска в постоянном делении отсортированного списка пополам, тем самым уменьшая количество возможных мест, где может находиться искомое число, но важно понимать, список для такого поиска должен быть отсортирован‼️‼️ Давайте на примере:
2️⃣ Берем наш отсортированный список [0, 4, 8, 16, 17, 22], он у нас уже отсортирован, теперь можно показать, как работает алгоритм на деле:
⭕️Допустим, ищем мы число 17. центральный элемент у нас 8. Кстати, подумайте почему 8, почему не 16, к примеру? Ведь список у нас состоит из четного количества элементов...Я отвечу чуть дальше в сообщении.
⭕️Дальше все еще проще, средний элемент 8, он сравнивается с 17, потому что это искомый элемент, в любом поиске с ним будет все сравниваться...Дак вот, 17 > 8, значит идем вправо по списку. 'Идем вправо' означает, что левую часть списка мы отбросили [0, 4, 8], 17 стоит правее середины, значит она нам не нужна...
✅Идем дальше, у нас остался список [16, 17, 22], средний элемент как раз 17!
Время выполнения такого алгоритма увеличивается логарифмически по мере роста размера входных данных. Щас вам объясню:
0️⃣ Вспомним сначала логарифмы, log2(8) = 3 ( Логарифм 8 по основанию 2 равен 3, потому что 2 возводим в 3 степень, первый шаг сделан )
1️⃣ Помните наш список [0, 16, 22, 4, 17, 8] пару постов назад? ‼️‼️Теперь отсортируем его [0, 4, 8, 16, 17, 22]. Зачем мы его отсортировали? Самый простой пример работы этого алгоритма - это бинарный поиск. Мы уже упоминали простой поиск, когда нам нужно перебрать все элементы, сравнивая их с нашей 'целью' (а проще сказать, с загаданным числом). пока не наткнемся на него. А бинарный поиск куда более эффективен... Суть такого поиска в постоянном делении отсортированного списка пополам, тем самым уменьшая количество возможных мест, где может находиться искомое число, но важно понимать, список для такого поиска должен быть отсортирован‼️‼️ Давайте на примере:
2️⃣ Берем наш отсортированный список [0, 4, 8, 16, 17, 22], он у нас уже отсортирован, теперь можно показать, как работает алгоритм на деле:
⭕️Допустим, ищем мы число 17. центральный элемент у нас 8. Кстати, подумайте почему 8, почему не 16, к примеру? Ведь список у нас состоит из четного количества элементов...Я отвечу чуть дальше в сообщении.
⭕️Дальше все еще проще, средний элемент 8, он сравнивается с 17, потому что это искомый элемент, в любом поиске с ним будет все сравниваться...Дак вот, 17 > 8, значит идем вправо по списку. 'Идем вправо' означает, что левую часть списка мы отбросили [0, 4, 8], 17 стоит правее середины, значит она нам не нужна...
✅Идем дальше, у нас остался список [16, 17, 22], средний элемент как раз 17!
🥰2
CodeLab
Теперь возвращаемся обратно к логарифмическому времени... Как раз у логарифмического времени асимптотическая сложность - O(log n) ❗️Это чисто для понимания, как это понятие будет употребляться в данном контексте❗️ Время выполнения такого алгоритма увеличивается…
Начнем пост с того, почему все-таки выбрали 8 как середину списка [0, 4, 8, 16, 17, 22]⁉️
Вообще, чтобы найти средний индекс массива,‼️нужно начальный индекс сложить с конечным и поделить все на 2‼️
✅СРЕДНИЙ ИНДЕКС = (НАЧАЛЬНЫЙ + КОНЕЧНЫЙ) / 2
В нашем случае, начальный - 0, конечный 5, пятерку делим на 2 и получаем 2 (как индекс, округлять ничего не нужно).
Вообще, чтобы найти средний индекс массива,‼️нужно начальный индекс сложить с конечным и поделить все на 2‼️
✅СРЕДНИЙ ИНДЕКС = (НАЧАЛЬНЫЙ + КОНЕЧНЫЙ) / 2
В нашем случае, начальный - 0, конечный 5, пятерку делим на 2 и получаем 2 (как индекс, округлять ничего не нужно).
🥰2
🐍 Разбор кода (Python)
Всем ку🧑💻, наконец разберем код для бинарного поиска‼️В квадратных скобках возле переменных я писал их значения на данный момент, чтобы вы не искали где- то в коде. Рекомендую отслеживать каждое действие по коду, чтобы вам был понятен смысл ‼️
Итак:
0️⃣ У нас имеется отсортированный массив из 14 элементов, ❗️наше искомое число на 2 строчке, пусть будет 23❗️, хотя вы можете поставить любое..
1️⃣ Обозначаем границы, left - это начальный индекс [0], right - конечный индекс - 1 [Это будет 13] (Вычитаем 1, потому что длинна нашего списка 14, а вот индексация начинается с 0, следовательно, чтобы получить 13 индексов, вычитаем 1).
2️⃣ Создаем цикл while. который работает до тех пор, пока пока левая граница не превысит правую⁉️. Как я вам уже говорил, суть бинарного поиска в постоянно делении отсортированного списка. Дак вот, пока цикл работает, еще есть часть массива, где есть наше число.
3️⃣ Находим средний элемент массива: 🟰
Дальше, 🟰
‼️То есть, переменная mid будет равна 6 (это средний индекс), а переменной mid_value находим элемент этого среднего индекса, это 13.‼️
4️⃣ Бывает такое, что средний элемент и будет искомым числом, первым условием это и проверяем.
Дальше, проверяем условие:
Если средний элемент меньше искомого, то left (Начальный индекс[0] = средний[6] + 1, и того получаем 7)⭕️
Первый сдвиг бинарного поиска ⬇️
5️⃣ Теперь смотрите в чем прикол. ‼️‼️Переменная left (начальный индекс) у нас теперь равен значению 7, конечный все также 13. То есть, наш диапазон для поиска элемента 23 сдвинулся вправо. Просто представьте, что список обрезали с 0 индекса по 7 (не включительно).‼️‼️
6️⃣ Мы вернулись в начало, теперь переменная mid равна 10⭕️ (Она была равна 6, а сейчас мы снова складываем начальный индекс[7] с конечным[13] и делим на 2 = 10) . Средний индекс равен 10, а вот переменная mid_value теперь равна 21, так как этот элемент как раз находится под индексом 10. ⭕️
7️⃣‼️Дальше также приходим к
Второй сдвиг бинарного поиска⏬
Если у нас mid_value[21] < aim[23], снова сдвигаем границу вправо, получаем left = 11, теперь у нас список состоит из элементов [23, 25, 27].
8️⃣ Снова находим средний индекс, это 12, затем элемент под этим индексом - 25. ⭕️
9️⃣ Не if не elif не срабатывают, срабатывает лишь последий оператор else. Переменная right[13] = mid[11] - 1. (Получаем right = 11)⭕️
Третий сдвиг бинарного поиска⏬
1️⃣0️⃣ Наконец! Теперь у нас обе переменные равны 11 (left, right). В последний раз находим средний индекс это 11, а элемент как раз 23! Наш искомый!
‼️Первое условие срабатывает и наш средний элемент как раз равен 23. ‼️
‼️Может показаться, что тут куча ненужной инфы, но такой алгоритм нужно было разобрать, поэтому я сделал это объемно‼️
‼️Возле некоторых переменных я писал квадратные скобочки, к примеру, как здесь right[13] = mid[11] - 1, внутри этих скобок находятся нынешние значения этих переменных, чтобы вы не путались и не искали выше‼️
✅Если вам есть, что добавить, пишите в комменты✅
Всем ку🧑💻, наконец разберем код для бинарного поиска‼️В квадратных скобках возле переменных я писал их значения на данный момент, чтобы вы не искали где- то в коде. Рекомендую отслеживать каждое действие по коду, чтобы вам был понятен смысл ‼️
Итак:
list = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27] # Отсортированный массив
aim = 23 #Элемент, который мы ищем, вы можете брать любой
left = 0 #Начальный индекс
right = len(list) - 1 #Конечный индекс
#Пока левая граница не превысит правую:
while left <= right:
mid = (left + right) // 2 # Находим середину массива
mid_value = list[mid] # Элемент в середине массива
if mid_value == aim:
print(f"Элемент найден на индексе: {mid}")
break # Элемент найден, выходим из цикла
elif mid_value < aim:
left = mid + 1 # Если искомый элемент больше, сдвигаем левую границу вправо на 1
else:
right = mid - 1 # Если искомый элемент меньше, сдвигаем правую границу влево на 1
else:
print("Элемент не найден")
0️⃣ У нас имеется отсортированный массив из 14 элементов, ❗️наше искомое число на 2 строчке, пусть будет 23❗️, хотя вы можете поставить любое..
1️⃣ Обозначаем границы, left - это начальный индекс [0], right - конечный индекс - 1 [Это будет 13] (Вычитаем 1, потому что длинна нашего списка 14, а вот индексация начинается с 0, следовательно, чтобы получить 13 индексов, вычитаем 1).
2️⃣ Создаем цикл while. который работает до тех пор, пока пока левая граница не превысит правую⁉️. Как я вам уже говорил, суть бинарного поиска в постоянно делении отсортированного списка. Дак вот, пока цикл работает, еще есть часть массива, где есть наше число.
3️⃣ Находим средний элемент массива: 🟰
mid = (left + right) // 2 🟰 Это получается 0 + 13 // 2 = 6 (Как раз выше писал, как найти средний индекс 🔝). Дальше, 🟰
mid_value = list[mid] 🟰 Переменная mid_value будет равна 13. ⭕️‼️То есть, переменная mid будет равна 6 (это средний индекс), а переменной mid_value находим элемент этого среднего индекса, это 13.‼️
4️⃣ Бывает такое, что средний элемент и будет искомым числом, первым условием это и проверяем.
Дальше, проверяем условие:
Если средний элемент меньше искомого, то left (Начальный индекс[0] = средний[6] + 1, и того получаем 7)⭕️
Первый сдвиг бинарного поиска ⬇️
5️⃣ Теперь смотрите в чем прикол. ‼️‼️Переменная left (начальный индекс) у нас теперь равен значению 7, конечный все также 13. То есть, наш диапазон для поиска элемента 23 сдвинулся вправо. Просто представьте, что список обрезали с 0 индекса по 7 (не включительно).‼️‼️
6️⃣ Мы вернулись в начало, теперь переменная mid равна 10⭕️ (Она была равна 6, а сейчас мы снова складываем начальный индекс[7] с конечным[13] и делим на 2 = 10) . Средний индекс равен 10, а вот переменная mid_value теперь равна 21, так как этот элемент как раз находится под индексом 10. ⭕️
7️⃣‼️Дальше также приходим к
elif mid_value < aim:
left = mid + 1 Второй сдвиг бинарного поиска⏬
Если у нас mid_value[21] < aim[23], снова сдвигаем границу вправо, получаем left = 11, теперь у нас список состоит из элементов [23, 25, 27].
8️⃣ Снова находим средний индекс, это 12, затем элемент под этим индексом - 25. ⭕️
9️⃣ Не if не elif не срабатывают, срабатывает лишь последий оператор else. Переменная right[13] = mid[11] - 1. (Получаем right = 11)⭕️
Третий сдвиг бинарного поиска⏬
1️⃣0️⃣ Наконец! Теперь у нас обе переменные равны 11 (left, right). В последний раз находим средний индекс это 11, а элемент как раз 23! Наш искомый!
‼️Первое условие срабатывает и наш средний элемент как раз равен 23. ‼️
‼️Может показаться, что тут куча ненужной инфы, но такой алгоритм нужно было разобрать, поэтому я сделал это объемно‼️
‼️Возле некоторых переменных я писал квадратные скобочки, к примеру, как здесь right[13] = mid[11] - 1, внутри этих скобок находятся нынешние значения этих переменных, чтобы вы не путались и не искали выше‼️
✅Если вам есть, что добавить, пишите в комменты✅
🥰2
Гайс, завтра постараюсь сделать пост, пока что ведутся визуальные изменения канала🧑💻. Половина канала уже изменена, так что ждать постов осталось немного. Также завтра будет оформлена навигация по числам типа float (а точнее проблема этих чисел).
👍2
⭕️‼️ Курс по Python никуда не денется, сегодня будет пост за долгое время, но, параллельно этому будем изучать новую науку 🔗
⭕️ Эти дни я занимался визуалом канала, вы можете это заметить по измененной навигации и измененным постам с самого начала создания канала.
⭕️ Теперь к каждому посту будет прилагаться код для собственной проверки.
🧑💻Всем удачного использования канала
⭕️ Эти дни я занимался визуалом канала, вы можете это заметить по измененной навигации и измененным постам с самого начала создания канала.
⭕️ Теперь к каждому посту будет прилагаться код для собственной проверки.
🧑💻Всем удачного использования канала
🔗 Гайс ку, разберем сегодня библиотеку Math 🧑💻
Она содержит полезные математические функции и константы. ⭕️ Все вычисления происходят на множестве вещественных чисел.
Для начала, нам конечно же нужно подключить эту библиотеку, чтобы мы могли с ней работать. ⭕️ Еще стоит сказать, что библиотека math является стандартной в Python и устанавливать ее отдельно не нужно.
🔗 Подключить библиотеку можно вот так:
🔗 Теперь мы можем спокойно вызывать функции библиотеки, например, можем найти логарифм:
⭕️ Выше мы используем функцию 🟰math.log(x, base)🟰 для вычисления логарифма.
Аргумент x - это число, base - основание. То есть, логарифм 128 по основанию 2 будет равен 7.
🔗 Вычисление натурального логарифма будет выглядеть немного короче:
⭕️ В примере выше подается лишь один аргумент 🟰x🟰, основание у нас итак известно, приблизительно 2,718.
🔗 Вычисление математической константы π
🔗 Вычисление числа Эйлера (e)
➗‼️Так, вроде немного разобрались, теперь перейдем к функциям (Теоретико-числовые функции и функции представления) ✖️ :
🔗 Функция 🟰math.ceil()🟰 округляет аргумент до большего целого числа:
🔗 Функция 🟰math.floor()🟰 также округляет аргумент, но, в меньшую сторону, наоборот:
🔗 Функция 🟰math.copysign()🟰 принимает два аргумента. Возвращает первый аргумент (с плавающей точкой), но со знаком второго.
🔗 Функция 🟰math.fabs()🟰 возвращает абсолютное значение аргумента:
🔗 Функция 🟰math.comb(n, k)🟰 показывает сколькими способами можно выбрать k объектов из множества n элементов. (Формулу я прикреплю после)
⁉️ Допустим, перед нами 8 футболок разных. Сколько есть способов выбрать 4 разные?
🔗 Вычисление факториала. ‼️ Входящее значение должно быть целочисленным и неотрицательным:
🔗 Функция 🟰math.fmod(a, b)🟰 считает остаток от деления a на b (По сути, аналог оператора '%' - деление по модулю ‼️).
🔗 Функция 🟰math.fsum()🟰 вычисляет сумму элементов итерируемого объекта. ⭕️ Пример для списка:
🔗 Функция 🟰math.gcd(a, b)🟰 возвращает наибольший общий делитель a и b (НОД):
🔗 Функция 🟰math.prod()🟰 принимает итерируемый объект, а возвращает произведение элементов:
⭕️ Степенные и логарифмические функции:
🔗 Возврат квадратного корня из аргумента, функция math.sqrt().
Их ,конечно, больше, но, эти ,как по мне, основные ‼️(На❌уя столько запятых придумали)
Она содержит полезные математические функции и константы. ⭕️ Все вычисления происходят на множестве вещественных чисел.
Для начала, нам конечно же нужно подключить эту библиотеку, чтобы мы могли с ней работать. ⭕️ Еще стоит сказать, что библиотека math является стандартной в Python и устанавливать ее отдельно не нужно.
🔗 Подключить библиотеку можно вот так:
import math
🔗 Теперь мы можем спокойно вызывать функции библиотеки, например, можем найти логарифм:
import math
x = 128
base = 2
result = math.log(x, base)
print(result) #Вывод: 7
⭕️ Выше мы используем функцию 🟰math.log(x, base)🟰 для вычисления логарифма.
Аргумент x - это число, base - основание. То есть, логарифм 128 по основанию 2 будет равен 7.
🔗 Вычисление натурального логарифма будет выглядеть немного короче:
import math
print(math.log(10))#Вывод: 2.302585...
⭕️ В примере выше подается лишь один аргумент 🟰x🟰, основание у нас итак известно, приблизительно 2,718.
🔗 Вычисление математической константы π
import math
print(math.pi) #Вывод: 3.14159...
🔗 Вычисление числа Эйлера (e)
import math
print(math.e)
➗‼️Так, вроде немного разобрались, теперь перейдем к функциям (Теоретико-числовые функции и функции представления) ✖️ :
🔗 Функция 🟰math.ceil()🟰 округляет аргумент до большего целого числа:
import math
print(math.ceil(6.000004)) #Вывод: 7
🔗 Функция 🟰math.floor()🟰 также округляет аргумент, но, в меньшую сторону, наоборот:
import math
print(math.floor(8.99)) #Вывод: 8
🔗 Функция 🟰math.copysign()🟰 принимает два аргумента. Возвращает первый аргумент (с плавающей точкой), но со знаком второго.
import math
print(math.copysign(9, -14)) #Вывод: -9.0
🔗 Функция 🟰math.fabs()🟰 возвращает абсолютное значение аргумента:
import math
print(math.fabs(-146)) #Вывод: 146.0
🔗 Функция 🟰math.comb(n, k)🟰 показывает сколькими способами можно выбрать k объектов из множества n элементов. (Формулу я прикреплю после)
⁉️ Допустим, перед нами 8 футболок разных. Сколько есть способов выбрать 4 разные?
import math
print(math.comb(8, 4)) #Вывод: 70
🔗 Вычисление факториала. ‼️ Входящее значение должно быть целочисленным и неотрицательным:
import math
print(math.factorial(9)) #Вывод: 362880
🔗 Функция 🟰math.fmod(a, b)🟰 считает остаток от деления a на b (По сути, аналог оператора '%' - деление по модулю ‼️).
import math
print(math.fmod(16, 5)) #Вывод: 1.0
import math
print(math.fmod(11, -4)) #Вывод: 3.0
🔗 Функция 🟰math.fsum()🟰 вычисляет сумму элементов итерируемого объекта. ⭕️ Пример для списка:
import math
arr = [1, 4, 7, 9, 13]
print(math.fsum(arr)) #Вывод: 34.0
🔗 Функция 🟰math.gcd(a, b)🟰 возвращает наибольший общий делитель a и b (НОД):
import math
a = 32
b = 8
print(math.gcd(a, b)) #Вывод: 8
🔗 Функция 🟰math.prod()🟰 принимает итерируемый объект, а возвращает произведение элементов:
import math
multiple_list = [7, 2, 6]
print(math.prod(multiple_list)) #Вывод: 84
⭕️ Степенные и логарифмические функции:
🔗 Возврат квадратного корня из аргумента, функция math.sqrt().
import math
print(math.sqrt(16)) #Вывод: 4.0
Их ,конечно, больше, но, эти ,как по мне, основные ‼️(На❌уя столько запятых придумали)
👍2
🧑💻 Давайте поговорим о синтаксисе инструкции 🟰import🟰 .
0️⃣⭕️ Мы уже разобрались с тем, что она нужна для импорта модулей в наш код.
1️⃣❗️В этом примере импортируется весь модуль math, и для доступа к его функциям используется синтаксис math.название_функции, в данном случае ( math.sqrt ):
2️⃣⭕️ Мы также можем импортировать только определённые функции или переменные из модуля:
❗️⏫Как вы можете заметить, сравнивая с прошлым примером, мы уже не ставим префикс ( или приставку 🟰math🟰, называйте как хотите ), поскольку мы уже импортировали нужные функции напрямую.
3️⃣ Теперь поговорим про псевдонимы:
⭕️ Нужно это для для сокращения имя модуля (они создаются с помощью ключевого слова 🟰as🟰), вдруг нам не нравится имя модуля или просто нужно повысить читаемость кода.
4️⃣❗️ Импорт всех функций и компонентов модуля:
Синтаксис максимально простой:
🔗 Пример кода:
0️⃣⭕️ Мы уже разобрались с тем, что она нужна для импорта модулей в наш код.
import [название модуля] #Синтаксис
1️⃣❗️В этом примере импортируется весь модуль math, и для доступа к его функциям используется синтаксис math.название_функции, в данном случае ( math.sqrt ):
import math
print(math.sqrt(16))
2️⃣⭕️ Мы также можем импортировать только определённые функции или переменные из модуля:
from math import sqrt, pi
print(sqrt(64))
print(pi)
❗️⏫Как вы можете заметить, сравнивая с прошлым примером, мы уже не ставим префикс ( или приставку 🟰math🟰, называйте как хотите ), поскольку мы уже импортировали нужные функции напрямую.
3️⃣ Теперь поговорим про псевдонимы:
from [название модуля] import [название функции] as [псевдоним] # Синтаксис
⭕️ Нужно это для для сокращения имя модуля (они создаются с помощью ключевого слова 🟰as🟰), вдруг нам не нравится имя модуля или просто нужно повысить читаемость кода.
4️⃣❗️ Импорт всех функций и компонентов модуля:
Синтаксис максимально простой:
from math import *
🔗 Пример кода:
from math import *
print(sqrt(64))
print(pi)
🔗 Средние значения 6.3
Все просто, прописываем формулу по техническому заданию и все 🧑💻
🔗 Код:
Все просто, прописываем формулу по техническому заданию и все 🧑💻
🔗 Код:
import math
a = float(input())
b = float(input())
midl_cr = (a + b)/2
midl_gr = math.sqrt(a*b)
midl_garm = (2 * a * b)/(a + b)
midl_sqr = math.sqrt((a**2 + b**2) / 2)
print(midl_cr)
print(midl_gr)
print(midl_garm)
print(midl_sqr)
🔗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