πŸ” Π§Ρ‚ΠΎ ΠΎΠ·Π½Π°Ρ‡Π°Π΅Ρ‚ np Π² ΠΏΠΎΠ»Π½ΠΎΠΉ Π·Π°Π΄Π°Ρ‡Π΅ ΠΏΠΈΡ‚ΠΎΠ½Π°? 🐍

Когда ΠΌΡ‹ Π³ΠΎΠ²ΠΎΡ€ΠΈΠΌ ΠΎ "np ΠΏΠΎΠ»Π½ΠΎΠΉ Π·Π°Π΄Π°Ρ‡Π΅" Π² ΠΏΠΈΡ‚ΠΎΠ½Π΅, это ΠΎΠ±Ρ‹Ρ‡Π½ΠΎ ΠΎΠ·Π½Π°Ρ‡Π°Π΅Ρ‚, Ρ‡Ρ‚ΠΎ ΠΌΡ‹ ΠΈΠΌΠ΅Π΅ΠΌ Π΄Π΅Π»ΠΎ с Π·Π°Π΄Π°Ρ‡Π΅ΠΉ, которая являСтся ΠΏΡ€ΠΎΠ±Π»Π΅ΠΌΠΎΠΉ, Ρ€Π΅ΡˆΠ΅Π½ΠΈΠ΅ ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΉ Π·Π°Ρ‚Ρ€ΡƒΠ΄Π½ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎ Π½Π°ΠΉΡ‚ΠΈ Π² алгоритмичСской сфСрС.

НП-ΠΏΠΎΠ»Π½Ρ‹Π΅ Π·Π°Π΄Π°Ρ‡ΠΈ Π² ΠΎΠ±Ρ‰Π΅ΠΌ случаС ΡΠ²Π»ΡΡŽΡ‚ΡΡ рСсурсоСмкими, Ρ‚ΠΎ Π΅ΡΡ‚ΡŒ ΠΈΡ… Ρ€Π΅ΡˆΠ΅Π½ΠΈΠ΅ Ρ‚Ρ€Π΅Π±ΡƒΠ΅Ρ‚ большого количСства Π²Ρ€Π΅ΠΌΠ΅Π½ΠΈ ΠΈΠ»ΠΈ Π²Ρ‹Ρ‡ΠΈΡΠ»ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΠΉ мощности. Однако ΠΎΠ½ΠΈ Π½Π΅ ΠΈΠΌΠ΅ΡŽΡ‚ извСстного эффСктивного Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ.

Π§Ρ‚ΠΎΠ±Ρ‹ Π»ΡƒΡ‡ΡˆΠ΅ ΠΏΠΎΠ½ΡΡ‚ΡŒ эту ΠΊΠΎΠ½Ρ†Π΅ΠΏΡ†ΠΈΡŽ, рассмотрим ΠΏΡ€ΠΈΠΌΠ΅Ρ€ Π·Π°Π΄Π°Ρ‡ΠΈ коммивояТСра. ΠšΠΎΠΌΠΌΠΈΠ²ΠΎΡΠΆΠ΅Ρ€ β€” это ΠΏΡƒΡ‚Π΅ΡˆΠ΅ΡΡ‚Π²Π΅Π½Π½ΠΈΠΊ, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ Π΄ΠΎΠ»ΠΆΠ΅Π½ ΠΏΠΎΡΠ΅Ρ‚ΠΈΡ‚ΡŒ Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠ΅ количСство Π³ΠΎΡ€ΠΎΠ΄ΠΎΠ², Π²Π΅Ρ€Π½ΡƒΠ²ΡˆΠΈΡΡŒ Π² исходный Π³ΠΎΡ€ΠΎΠ΄, пройдя ΠΏΠΎ ΠΊΠ°ΠΆΠ΄ΠΎΠΌΡƒ Π³ΠΎΡ€ΠΎΠ΄Ρƒ Ρ‚ΠΎΠ»ΡŒΠΊΠΎ ΠΎΠ΄ΠΈΠ½ Ρ€Π°Π· ΠΈ минимизируя ΠΎΠ±Ρ‰ΡƒΡŽ ΡΡ‚ΠΎΠΈΠΌΠΎΡΡ‚ΡŒ ΠΏΡƒΡ‚Π΅ΡˆΠ΅ΡΡ‚Π²ΠΈΡ.


import numpy as np

def tsp_solver(distance_matrix):
    # РСализация эффСктивного Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° для Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ Π·Π°Π΄Π°Ρ‡ΠΈ коммивояТСра Π·Π°Π½ΠΈΠΌΠ°Π΅Ρ‚ ΠΌΠ½ΠΎΠ³ΠΎ Π²Ρ€Π΅ΠΌΠ΅Π½ΠΈ
    # ΠΈ ΠΌΠΎΠΆΠ΅Ρ‚ Π±Ρ‹Ρ‚ΡŒ NP-ΠΏΠΎΠ»Π½ΠΎΠΉ Π·Π°Π΄Π°Ρ‡Π΅ΠΉ.
    pass
  
distance_matrix = np.array([[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]])
tsp_solver(distance_matrix)

Π’ Π΄Π°Π½Π½ΠΎΠΌ ΠΏΡ€ΠΈΠΌΠ΅Ρ€Π΅ ΠΌΡ‹ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅ΠΌ Π±ΠΈΠ±Π»ΠΈΠΎΡ‚Π΅ΠΊΡƒ NumPy для создания ΠΌΠ°Ρ‚Ρ€ΠΈΡ†Ρ‹ расстояний ΠΌΠ΅ΠΆΠ΄Ρƒ Π³ΠΎΡ€ΠΎΠ΄Π°ΠΌΠΈ. Ѐункция tsp_solver прСдставляСт собой Π·Π°Π³Π»ΡƒΡˆΠΊΡƒ, Π² ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΉ Π΄ΠΎΠ»ΠΆΠ΅Π½ Π±Ρ‹Ρ‚ΡŒ Ρ€Π΅Π°Π»ΠΈΠ·ΠΎΠ²Π°Π½ эффСктивный Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ для Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ Π·Π°Π΄Π°Ρ‡ΠΈ коммивояТСра.

Π’Π°ΠΆΠ½ΠΎ ΠΎΡ‚ΠΌΠ΅Ρ‚ΠΈΡ‚ΡŒ, Ρ‡Ρ‚ΠΎ Π² Ρ€Π΅Π°Π»ΡŒΠ½Ρ‹Ρ… Π·Π°Π΄Π°Ρ‡Π°Ρ… NP-ΠΏΠΎΠ»Π½Ρ‹Π΅ ΠΏΡ€ΠΎΠ±Π»Π΅ΠΌΡ‹ ΠΌΠΎΠ³ΡƒΡ‚ ΠΈΠΌΠ΅Ρ‚ΡŒ мноТСство Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ΠΎΠ² Ρ€Π΅ΡˆΠ΅Π½ΠΈΠΉ, Π½ΠΎ поиск ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½ΠΎΠ³ΠΎ Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ ΠΌΠΎΠΆΠ΅Ρ‚ Π·Π°Π½ΠΈΠΌΠ°Ρ‚ΡŒ ΠΎΠ³Ρ€ΠΎΠΌΠ½ΠΎΠ΅ количСство Π²Ρ€Π΅ΠΌΠ΅Π½ΠΈ ΠΈΠ»ΠΈ рСсурсов.

Π”Π΅Ρ‚Π°Π»ΡŒΠ½Ρ‹ΠΉ ΠΎΡ‚Π²Π΅Ρ‚

ЗдравствуйтС! БСгодня ΠΌΡ‹ рассмотрим ΠΎΡ‡Π΅Π½ΡŒ ΠΈΠ½Ρ‚Π΅Ρ€Π΅ΡΠ½ΡƒΡŽ Ρ‚Π΅ΠΌΡƒ - "Ρ‡Ρ‚ΠΎ ΠΎΠ·Π½Π°Ρ‡Π°Π΅Ρ‚ np полная Π·Π°Π΄Π°Ρ‡Π° ΠΏΠΈΡ‚ΠΎΠ½". НачнСм с Ρ€Π°Π·Π±ΠΎΡ€Π° ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ ΠΈΠ· этих ΠΊΠΎΠΌΠΏΠΎΠ½Π΅Π½Ρ‚ΠΎΠ² ΠΈ Π·Π°Ρ‚Π΅ΠΌ свяТСм ΠΈΡ… вмСстС для ΠΏΠΎΠ»Π½ΠΎΠ³ΠΎ понимания.


np

НачнСм с Ρ€Π°Π·Π±ΠΎΡ€Π° Π°Π±Π±Ρ€Π΅Π²ΠΈΠ°Ρ‚ΡƒΡ€Ρ‹ "np". Π’ Python это ΠΎΠ±Ρ‹Ρ‡Π½ΠΎ сокращСниС для Π±ΠΈΠ±Π»ΠΈΠΎΡ‚Π΅ΠΊΠΈ NumPy. NumPy - это Π±ΠΈΠ±Π»ΠΈΠΎΡ‚Π΅ΠΊΠ° для языка Python, ΠΏΡ€Π΅Π΄ΠΎΡΡ‚Π°Π²Π»ΡΡŽΡ‰Π°Ρ ΠΏΠΎΠ΄Π΄Π΅Ρ€ΠΆΠΊΡƒ для Π±ΠΎΠ»ΡŒΡˆΠΈΡ…, ΠΌΠ½ΠΎΠ³ΠΎΠΌΠ΅Ρ€Π½Ρ‹Ρ… массивов ΠΈ ΠΌΠ°Ρ‚Ρ€ΠΈΡ†, вмСстС с большой ΠΊΠΎΠ»Π»Π΅ΠΊΡ†ΠΈΠ΅ΠΉ матСматичСских Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΉ, Ρ‡Ρ‚ΠΎΠ±Ρ‹ с Π½ΠΈΠΌΠΈ Ρ€Π°Π±ΠΎΡ‚Π°Ρ‚ΡŒ. Она являСтся ΠΎΠ΄Π½ΠΎΠΉ ΠΈΠ· основных Π±ΠΈΠ±Π»ΠΈΠΎΡ‚Π΅ΠΊ для Π½Π°ΡƒΡ‡Π½Ρ‹Ρ… вычислСний Π² Python.


Полная Π·Π°Π΄Π°Ρ‡Π°

Π’Π΅ΠΏΠ΅Ρ€ΡŒ Π΄Π°Π²Π°ΠΉΡ‚Π΅ ΠΏΠ΅Ρ€Π΅ΠΉΠ΄Π΅ΠΌ ΠΊ Ρ‚Π΅Ρ€ΠΌΠΈΠ½Ρƒ "полная Π·Π°Π΄Π°Ρ‡Π°". Π’ контСкстС программирования этот Ρ‚Π΅Ρ€ΠΌΠΈΠ½ относится ΠΊ Ρ€Π΅ΡˆΠ΅Π½ΠΈΡŽ Π·Π°Π΄Π°Ρ‡ΠΈ ΠΏΠΎΠ»Π½Ρ‹ΠΌ ΠΏΠ΅Ρ€Π΅Π±ΠΎΡ€ΠΎΠΌ всСх Π²ΠΎΠ·ΠΌΠΎΠΆΠ½Ρ‹Ρ… ΠΊΠΎΠΌΠ±ΠΈΠ½Π°Ρ†ΠΈΠΉ Π΅Ρ‘ Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ. Π’ случаС Python ΠΈ NumPy это ΠΎΠ·Π½Π°Ρ‡Π°Π΅Ρ‚ Ρ€Π΅ΡˆΠ΅Π½ΠΈΠ΅ Π·Π°Π΄Π°Ρ‡ΠΈ с использованиСм ΠΏΠΎΠ»Π½ΠΎΠ³ΠΎ ΠΏΠΎΡ‚Π΅Π½Ρ†ΠΈΠ°Π»Π° Π±ΠΈΠ±Π»ΠΈΠΎΡ‚Π΅ΠΊΠΈ NumPy.


ΠŸΡ€ΠΈΠΌΠ΅Ρ€Ρ‹

Π”Π°Π²Π°ΠΉΡ‚Π΅ рассмотрим нСсколько ΠΏΡ€ΠΈΠΌΠ΅Ρ€ΠΎΠ², Ρ‡Ρ‚ΠΎΠ±Ρ‹ Π»ΡƒΡ‡ΡˆΠ΅ ΠΏΠΎΠ½ΡΡ‚ΡŒ, Ρ‡Ρ‚ΠΎ ΠΎΠ·Π½Π°Ρ‡Π°Π΅Ρ‚ "np полная Π·Π°Π΄Π°Ρ‡Π° ΠΏΠΈΡ‚ΠΎΠ½".


ΠŸΡ€ΠΈΠΌΠ΅Ρ€ 1:


import numpy as np

# Π‘ΠΎΠ·Π΄Π°Π½ΠΈΠ΅ Π΄Π²ΡƒΠΌΠ΅Ρ€Π½ΠΎΠ³ΠΎ массива
array = np.array([[1, 2, 3], [4, 5, 6]])

# Π’Ρ‹Π²ΠΎΠ΄ размСрности массива
print("Π Π°Π·ΠΌΠ΅Ρ€Π½ΠΎΡΡ‚ΡŒ массива:", array.shape)

Π’ этом ΠΏΡ€ΠΈΠΌΠ΅Ρ€Π΅ ΠΌΡ‹ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅ΠΌ Π±ΠΈΠ±Π»ΠΈΠΎΡ‚Π΅ΠΊΡƒ NumPy, Ρ‡Ρ‚ΠΎΠ±Ρ‹ ΡΠΎΠ·Π΄Π°Ρ‚ΡŒ Π΄Π²ΡƒΠΌΠ΅Ρ€Π½Ρ‹ΠΉ массив ΠΈ вывСсти Π΅Π³ΠΎ Ρ€Π°Π·ΠΌΠ΅Ρ€Π½ΠΎΡΡ‚ΡŒ. Π—Π΄Π΅ΡΡŒ ΠΌΡ‹ ΠΏΠΎΠ»Π½ΠΎΡΡ‚ΡŒΡŽ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅ΠΌ ΠΏΠΎΡ‚Π΅Π½Ρ†ΠΈΠ°Π» NumPy для Ρ€Π°Π±ΠΎΡ‚Ρ‹ с ΠΌΠ½ΠΎΠ³ΠΎΠΌΠ΅Ρ€Π½Ρ‹ΠΌΠΈ массивами.


ΠŸΡ€ΠΈΠΌΠ΅Ρ€ 2:


import numpy as np

# ВычислСниС срСднСго значСния массива
array = np.array([1, 2, 3, 4, 5])
mean = np.mean(array)

# Π’Ρ‹Π²ΠΎΠ΄ срСднСго значСния
print("Π‘Ρ€Π΅Π΄Π½Π΅Π΅ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅:", mean)

Π’ этом ΠΏΡ€ΠΈΠΌΠ΅Ρ€Π΅ ΠΌΡ‹ вычисляСм срСднСС Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ массива, ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΡŽ mean ΠΈΠ· Π±ΠΈΠ±Π»ΠΈΠΎΡ‚Π΅ΠΊΠΈ NumPy. Π—Π΄Π΅ΡΡŒ снова ΠΌΡ‹ ΠΏΠΎΠ»Π½ΠΎΡΡ‚ΡŒΡŽ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅ΠΌ ΠΏΠΎΡ‚Π΅Π½Ρ†ΠΈΠ°Π» NumPy для Ρ€Π°Π±ΠΎΡ‚Ρ‹ с массивами ΠΈ матСматичСскими функциями.


Π’Ρ‹Π²ΠΎΠ΄

Π’Π°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ, "np полная Π·Π°Π΄Π°Ρ‡Π° ΠΏΠΈΡ‚ΠΎΠ½" ΠΎΠ·Π½Π°Ρ‡Π°Π΅Ρ‚, Ρ‡Ρ‚ΠΎ ΠΌΡ‹ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅ΠΌ Π±ΠΈΠ±Π»ΠΈΠΎΡ‚Π΅ΠΊΡƒ NumPy для Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ Π·Π°Π΄Π°Ρ‡ΠΈ, ΠΏΠΎΠ»Π½ΠΎΡΡ‚ΡŒΡŽ использовав Π΅Ρ‘ возмоТности ΠΏΠΎ Ρ€Π°Π±ΠΎΡ‚Π΅ с массивами ΠΈ матСматичСскими функциями. Π­Ρ‚ΠΎ ΠΎΠ±Ρ‹Ρ‡Π½ΠΎ ΠΏΡ€ΠΈΠ²ΠΎΠ΄ΠΈΡ‚ ΠΊ Π±ΠΎΠ»Π΅Π΅ эффСктивному ΠΈ ΡƒΠ΄ΠΎΠ±Π½ΠΎΠΌΡƒ ΠΊΠΎΠ΄Ρƒ.


НадСюсь, этот Ρ€Π°Π·Π²Π΅Ρ€Π½ΡƒΡ‚Ρ‹ΠΉ ΠΎΡ‚Π²Π΅Ρ‚ ΠΏΠΎΠΌΠΎΠ³ Π²Π°ΠΌ ΠΏΠΎΠ½ΡΡ‚ΡŒ, Ρ‡Ρ‚ΠΎ ΠΎΠ·Π½Π°Ρ‡Π°Π΅Ρ‚ "np полная Π·Π°Π΄Π°Ρ‡Π° ΠΏΠΈΡ‚ΠΎΠ½". Π£Π΄Π°Ρ‡ΠΈ Π²Π°ΠΌ Π² дальнСйшСм ΠΈΠ·ΡƒΡ‡Π΅Π½ΠΈΠΈ программирования с использованиСм Π±ΠΈΠ±Π»ΠΈΠΎΡ‚Π΅ΠΊΠΈ NumPy!

Π’ΠΈΠ΄Π΅ΠΎ ΠΏΠΎ Ρ‚Π΅ΠΌΠ΅

Алгоритмы 8 / 11. Π–Π°Π΄Π½Ρ‹Π΅ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹ ΠΈ NP-ΠΏΠΎΠ»Π½Ρ‹Π΅ Π·Π°Π΄Π°Ρ‡ΠΈ! #python #algorithm

β‰  Π‘ΠΎΠ±ΠΈΡ€Π°ΠΉ Ρ€ΡŽΠΊΠ·Π°ΠΊ ΠΏΠΎ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡƒ, Ссли Π±ΡƒΠ΄Π΅Ρ‚ NP=P

ЛСкция 6. P, NP, NP-ΠΏΠΎΠ»Π½ΠΎΡ‚Π°

ΠŸΠΎΡ…ΠΎΠΆΠΈΠ΅ ΡΡ‚Π°Ρ‚ΡŒΠΈ:

Вочная Π΄Π°Ρ‚Π° создания Python 3: интСрСсныС Ρ„Π°ΠΊΡ‚Ρ‹ ΠΈ история

Как ΠΎΠΏΡ€Π΅Π΄Π΅Π»ΠΈΡ‚ΡŒ язык строки Π² Python? 🐍 ΠŸΡ€ΠΎΡΡ‚Ρ‹Π΅ способы ΠΏΡ€ΠΎΠ²Π΅Ρ€ΠΊΠΈ

πŸ”Ž Π§Ρ‚ΠΎ Π΄Π΅Π»Π°Π΅Ρ‚ ΠΌΠ΅Ρ‚ΠΎΠ΄ append Π² Python: ΠΏΠΎΠ΄Ρ€ΠΎΠ±Π½ΠΎΠ΅ объяснСниС

πŸ” Π§Ρ‚ΠΎ ΠΎΠ·Π½Π°Ρ‡Π°Π΅Ρ‚ np Π² ΠΏΠΎΠ»Π½ΠΎΠΉ Π·Π°Π΄Π°Ρ‡Π΅ ΠΏΠΈΡ‚ΠΎΠ½Π°? 🐍

πŸ’‘ Как ΡƒΠΌΠ½ΠΎΠΆΠΈΡ‚ΡŒ числа Π² спискС с ΠΏΠΎΠΌΠΎΡ‰ΡŒΡŽ Python: простоС руководство для Π½Π°Ρ‡ΠΈΠ½Π°ΡŽΡ‰ΠΈΡ…

πŸ” Как ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒ sympy python для Ρ‡Π΅Π³ΠΎ: ΠΏΠΎΠ»Π½ΠΎΠ΅ руководство ΠΈ ΠΏΡ€ΠΈΠΌΠ΅Ρ€Ρ‹ использования

πŸ”§ Как ΠΏΠΎΠΌΠ΅Π½ΡΡ‚ΡŒ ΠΎΠ΄ΠΈΠ½ символ Π½Π° Π΄Ρ€ΡƒΠ³ΠΎΠΉ Π² Python: идСальноС руководство для Π½Π°Ρ‡ΠΈΠ½Π°ΡŽΡ‰ΠΈΡ