905 lines
26 KiB
Plaintext
Executable File
905 lines
26 KiB
Plaintext
Executable File
{
|
||
"cells": [
|
||
{
|
||
"cell_type": "markdown",
|
||
"id": "e02cd782",
|
||
"metadata": {},
|
||
"source": [
|
||
"# Практика №2\n"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"id": "48a6e585",
|
||
"metadata": {},
|
||
"source": [
|
||
"## Операции над множествами. Свойства бинарных отношений. Замыкания отношений\n"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"id": "2ae75977",
|
||
"metadata": {},
|
||
"source": [
|
||
"Множества являются неопределяемыми понятиями и представляют собой неупорядоченную коллекцию уникальных элементов.\n",
|
||
"То есть, что два множества совпадают, если содержат одинаковые элементы.\n",
|
||
"Множества, состоящие из конечного числа элементов, называются конечными, в противном случае множества являются бесконечными. Конечное множество можно задать перечислением его элементов. Рассмотрим как можно работать с множествами средствами языка Python на примере конечных множеств.\n"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"id": "ca4afee1",
|
||
"metadata": {},
|
||
"source": [
|
||
"### Способы задания множеств\n"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"id": "d848525f",
|
||
"metadata": {},
|
||
"source": [
|
||
"перечисление элементов множества в фигурных скобках:\n"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 1,
|
||
"id": "569b7ff7",
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"name": "stdout",
|
||
"output_type": "stream",
|
||
"text": [
|
||
"{'orange', 'apple', 'banana'}\n",
|
||
"<class 'set'>\n"
|
||
]
|
||
}
|
||
],
|
||
"source": [
|
||
"fruits = {\"banana\", \"apple\", \"orange\"}\n",
|
||
"print(fruits)\n",
|
||
"print(type(fruits))"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"id": "b3e9458e",
|
||
"metadata": {},
|
||
"source": [
|
||
"Единственное ограничение, что таким образом нельзя создать пустое множество. Вместо этого будет создан пустой словарь:\n"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 2,
|
||
"id": "d446184f",
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"name": "stdout",
|
||
"output_type": "stream",
|
||
"text": [
|
||
"<class 'dict'>\n"
|
||
]
|
||
}
|
||
],
|
||
"source": [
|
||
"wrong_empty_set = {}\n",
|
||
"print(type(wrong_empty_set))"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"id": "60a0a658",
|
||
"metadata": {},
|
||
"source": [
|
||
"Для создания пустого множества нужно непосредственно использовать set():\n"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 3,
|
||
"id": "3b7ce4b6",
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"name": "stdout",
|
||
"output_type": "stream",
|
||
"text": [
|
||
"<class 'set'>\n"
|
||
]
|
||
}
|
||
],
|
||
"source": [
|
||
"correct_empty_set = set()\n",
|
||
"print(type(correct_empty_set))"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"id": "47b6bfac",
|
||
"metadata": {},
|
||
"source": [
|
||
"Множество можно задать с помощью set(), если передать в нее какой-либо объект, по которому можно проитерироваться\n"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 4,
|
||
"id": "6d41db64",
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"name": "stdout",
|
||
"output_type": "stream",
|
||
"text": [
|
||
"{'orange', 'apple', 'banana'}\n",
|
||
"<class 'set'>\n"
|
||
]
|
||
}
|
||
],
|
||
"source": [
|
||
"fruits_set = set({\"banana\", \"apple\", \"banana\", \"orange\"})\n",
|
||
"print(fruits_set)\n",
|
||
"print(type(fruits_set))"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 5,
|
||
"id": "99b8c1ea",
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"name": "stdout",
|
||
"output_type": "stream",
|
||
"text": [
|
||
"True\n"
|
||
]
|
||
}
|
||
],
|
||
"source": [
|
||
"fruits_set_1 = set({\"apple\", \"orange\", \"banana\", })\n",
|
||
"print(fruits_set == fruits_set_1)"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"id": "4b420cc2",
|
||
"metadata": {},
|
||
"source": [
|
||
"### Подмножество и надмножество\n"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 6,
|
||
"id": "98eb8ea5",
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"name": "stdout",
|
||
"output_type": "stream",
|
||
"text": [
|
||
"Подмножество!\n",
|
||
"Надмножество!\n"
|
||
]
|
||
}
|
||
],
|
||
"source": [
|
||
"# Множество чисел Фибоначчи меньших 100\n",
|
||
"fibonacci_numbers = {0, 1, 2, 3, 34, 5, 8, 13, 21, 55, 89}\n",
|
||
"\n",
|
||
"# Множество натуральных чисел меньших 100\n",
|
||
"natural_numbers = set(range(100))\n",
|
||
"\n",
|
||
"# Множество чисел Фибоначчи является подмножеством множества\n",
|
||
"# натуральных чисел\n",
|
||
"if fibonacci_numbers.issubset(natural_numbers):\n",
|
||
" print(\"Подмножество!\")\n",
|
||
"\n",
|
||
"# В свою очередь множество натуральных чисел является\n",
|
||
"# надмножеством множества чисел Фибоначчи\n",
|
||
"if natural_numbers.issuperset(fibonacci_numbers):\n",
|
||
" print(\"Надмножество!\")"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"id": "6c861227",
|
||
"metadata": {},
|
||
"source": [
|
||
"Пустое множество является подмножеством абсолютно любого множества.\n"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 7,
|
||
"id": "2946f658",
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"name": "stdout",
|
||
"output_type": "stream",
|
||
"text": [
|
||
"True\n"
|
||
]
|
||
}
|
||
],
|
||
"source": [
|
||
"empty = set()\n",
|
||
"\n",
|
||
"# Методы issubset и issuperset могут принимать любой iterable-объект\n",
|
||
"print(\n",
|
||
" empty.issubset(range(100))\n",
|
||
" and empty.issubset([\"red\", \"green\", \"blue\"])\n",
|
||
" and empty.issubset(set())\n",
|
||
")"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"id": "eb5a7764",
|
||
"metadata": {},
|
||
"source": [
|
||
"Само множество является подмножеством самого себя.\n"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 8,
|
||
"id": "019bb3ac",
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"name": "stdout",
|
||
"output_type": "stream",
|
||
"text": [
|
||
"Подмножество!\n"
|
||
]
|
||
}
|
||
],
|
||
"source": [
|
||
"natural_numbers = set(range(100))\n",
|
||
"\n",
|
||
"if natural_numbers.issubset(natural_numbers):\n",
|
||
" print(\"Подмножество!\")"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"id": "effdf363",
|
||
"metadata": {},
|
||
"source": [
|
||
"### Операции над множествами\n"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"id": "1bc824be",
|
||
"metadata": {},
|
||
"source": [
|
||
"Объединение множеств\n"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 9,
|
||
"id": "ce1f88c8",
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"name": "stdout",
|
||
"output_type": "stream",
|
||
"text": [
|
||
"{'orange', 'pear', 'banana', 'apple'}\n"
|
||
]
|
||
}
|
||
],
|
||
"source": [
|
||
"my_fruits = {\"apple\", \"orange\"}\n",
|
||
"your_fruits = {\"orange\", \"banana\", \"pear\"}\n",
|
||
"\n",
|
||
"# Для объединения множеств (типа set) можно использовать оператор `|`,\n",
|
||
"\n",
|
||
"our_fruits = my_fruits | your_fruits\n",
|
||
"print(our_fruits)"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 10,
|
||
"id": "36e34918",
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"name": "stdout",
|
||
"output_type": "stream",
|
||
"text": [
|
||
"{'orange', 'pear', 'apple', 'banana'}\n"
|
||
]
|
||
}
|
||
],
|
||
"source": [
|
||
"# Также можно использовать ментод union.\n",
|
||
"# Отличие состоит в том, что метод union принимает не только\n",
|
||
"# объект типа set, а любой iterable-объект\n",
|
||
"you_fruit_list: list = list(your_fruits)\n",
|
||
"our_fruits: set = my_fruits.union(you_fruit_list)\n",
|
||
"print(our_fruits)"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"id": "edb92d2a",
|
||
"metadata": {},
|
||
"source": [
|
||
"Добавление элементов в множество.\n",
|
||
"Добавление элементов в множество можно рассматривать как частный случай объединения множеств за тем исключением, что добавление элементов изменяет исходное множество, а не создает новый объект\n"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 11,
|
||
"id": "af8a9b6a",
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"name": "stdout",
|
||
"output_type": "stream",
|
||
"text": [
|
||
"{'red', 'purple', 'green', 'blue'}\n"
|
||
]
|
||
}
|
||
],
|
||
"source": [
|
||
"colors = {\"red\", \"green\", \"blue\"}\n",
|
||
"\n",
|
||
"# Метод add добаляет новый элемент в множество\n",
|
||
"colors.add(\"purple\")\n",
|
||
"# Добавление элемента, который уже есть в множестве, не изменяет\n",
|
||
"# это множество\n",
|
||
"colors.add(\"red\")\n",
|
||
"print(colors)"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 12,
|
||
"id": "103d30b9",
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"name": "stdout",
|
||
"output_type": "stream",
|
||
"text": [
|
||
"{1, 2, 3, 4, 9}\n"
|
||
]
|
||
}
|
||
],
|
||
"source": [
|
||
"# Метод update принимает iterable-объект (список, словарь, генератор и т.п.)\n",
|
||
"# и добавляет все элементы в множество\n",
|
||
"numbers = {1, 2, 3}\n",
|
||
"numbers.update(i**2 for i in [1, 2, 3])\n",
|
||
"print(numbers)"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"id": "765338fd",
|
||
"metadata": {},
|
||
"source": [
|
||
"### Свойства множеств\n"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"id": "8cb16831",
|
||
"metadata": {},
|
||
"source": [
|
||
"К основным свойствам множеств, которые мы хотим проверять, относятся рефлексивность, антирефлексивность, симметричность, антисимметричность, транзитивность.\n",
|
||
"Сгенерируем произвольное бинарное отношение\n"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 7,
|
||
"id": "fac374b1",
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"data": {
|
||
"text/plain": [
|
||
"[[1, 1, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [1, 1, 0, 0]]"
|
||
]
|
||
},
|
||
"execution_count": 7,
|
||
"metadata": {},
|
||
"output_type": "execute_result"
|
||
}
|
||
],
|
||
"source": [
|
||
"import random\n",
|
||
"x = 4\n",
|
||
"y = 4\n",
|
||
"array = [[random.randint(0, 1) for _ in range(x)] for _ in range(y)]\n",
|
||
"array"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"id": "71d50746",
|
||
"metadata": {},
|
||
"source": [
|
||
"Проверим рефлексивность. Чтобы выявить наличие единиц на главной диагонали, сгенерируем единичную матрицу нужной размерности, и проверим включается ли она в исходное отношение. Но можно и напрямую проверить, что элементы с i=j в отношении равны 1\n"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 8,
|
||
"id": "23da8a2f",
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"data": {
|
||
"text/plain": [
|
||
"False"
|
||
]
|
||
},
|
||
"execution_count": 8,
|
||
"metadata": {},
|
||
"output_type": "execute_result"
|
||
}
|
||
],
|
||
"source": [
|
||
"# ваш код\n",
|
||
"def reflexivity_check(array: list[list[int]]) -> bool:\n",
|
||
" return all(array[i][i] == 1 for i in range(max(len(array), len(array[0]))))\n",
|
||
"\n",
|
||
"\n",
|
||
"reflexivity_check(array)"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"id": "08976a67",
|
||
"metadata": {},
|
||
"source": [
|
||
"Для проверки антирефлексивности необходимо проверить, что что элементы с i=j в отношении равны 0\n"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 9,
|
||
"id": "ab2ec981",
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"data": {
|
||
"text/plain": [
|
||
"False"
|
||
]
|
||
},
|
||
"execution_count": 9,
|
||
"metadata": {},
|
||
"output_type": "execute_result"
|
||
}
|
||
],
|
||
"source": [
|
||
"# ваш код\n",
|
||
"def antireflexivity_check(array: list[list[int]]) -> bool:\n",
|
||
" return all(array[i][i] == 0 for i in range(max(len(array), len(array[0]))))\n",
|
||
"\n",
|
||
"\n",
|
||
"antireflexivity_check(array)"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"id": "7cbc0e84",
|
||
"metadata": {},
|
||
"source": [
|
||
"Для проверки симметричности нужно проверить, что если в отношении i,j-ый элемент равен 1, то и j,i-ый элемент тоже равен единице\n"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 6,
|
||
"id": "434cfe13",
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"data": {
|
||
"text/plain": [
|
||
"False"
|
||
]
|
||
},
|
||
"execution_count": 6,
|
||
"metadata": {},
|
||
"output_type": "execute_result"
|
||
}
|
||
],
|
||
"source": [
|
||
"# ваш код\n",
|
||
"def symmetry_check(array: list[list[int]]) -> bool:\n",
|
||
" return all(array[i][j] == array[j][i] for j in range(len(array[0])) for i in range(len(array)))\n",
|
||
"\n",
|
||
"\n",
|
||
"symmetry_check(array)"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"id": "a186d882",
|
||
"metadata": {},
|
||
"source": [
|
||
"Для проверки антисимметричности нужно проверить, что если в отношении i,j-ый элемент равен единице, то и j,i-ый элемент равен нулю\n"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 10,
|
||
"id": "7727ec98",
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"data": {
|
||
"text/plain": [
|
||
"False"
|
||
]
|
||
},
|
||
"execution_count": 10,
|
||
"metadata": {},
|
||
"output_type": "execute_result"
|
||
}
|
||
],
|
||
"source": [
|
||
"# ваш код\n",
|
||
"def antisymmetry_check(array: list[list[int]]) -> bool:\n",
|
||
" return all(array[i][j] != array[j][i] or i == j for j in range(len(array[0])) for i in range(len(array)))\n",
|
||
"\n",
|
||
"\n",
|
||
"antisymmetry_check(array)"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"id": "88678087",
|
||
"metadata": {},
|
||
"source": [
|
||
"Для проверки транзитивности нужно проверить, что если i,j-ый и j,k-ый элементы принадлежат отношению, то и i,k-ый элемент тоже равен единице\n"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 11,
|
||
"id": "518a0e6c",
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"data": {
|
||
"text/plain": [
|
||
"True"
|
||
]
|
||
},
|
||
"execution_count": 11,
|
||
"metadata": {},
|
||
"output_type": "execute_result"
|
||
}
|
||
],
|
||
"source": [
|
||
"# ваш код\n",
|
||
"def transitivity_check(array: list[list[int]]) -> bool:\n",
|
||
" x = len(array[0])\n",
|
||
" y = len(array)\n",
|
||
" for x_1 in range(x):\n",
|
||
" for y_1 in range(y):\n",
|
||
" for x_2 in range(x):\n",
|
||
" if array[y_1][x_1] * array[x_1][x_2] and not array[y_1][x_2]:\n",
|
||
" return False\n",
|
||
" \n",
|
||
" return True\n",
|
||
"\n",
|
||
"\n",
|
||
"transitivity_check(array)"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"id": "16f83129",
|
||
"metadata": {},
|
||
"source": [
|
||
"### Множество всех подмножеств\n",
|
||
"\n",
|
||
"Алгоритм Грея генерирует последовательность всех подмножеств п-элементного множества, причём каждое следующее подмножество получается из предыдущего удалением или добавлением в точности одного элемента.\n"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 21,
|
||
"id": "f3f4a62f",
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"name": "stdout",
|
||
"output_type": "stream",
|
||
"text": [
|
||
"\n",
|
||
"Рефлективна - False\n",
|
||
"Антирефлективна - False\n",
|
||
"Симметрична - False\n",
|
||
"Антисимметрична - False\n",
|
||
"Транзитивна - True\n",
|
||
"Замкнута - True\n",
|
||
"\n"
|
||
]
|
||
}
|
||
],
|
||
"source": [
|
||
"# ваш код\n",
|
||
"def some_funtion(first_array: list[list[int]], second_array: list[list[int]]) -> list[list[int]]:\n",
|
||
" if len(first_array) != len(second_array) or len(first_array[0]) != len(second_array[0]):\n",
|
||
" return None\n",
|
||
"\n",
|
||
" x = len(first_array[0])\n",
|
||
" y = len(first_array)\n",
|
||
" new_matrix = [[0 for _ in range(x)] for _ in range(y)]\n",
|
||
" \n",
|
||
" for y_1 in range(y):\n",
|
||
" for x_1 in range(x):\n",
|
||
" for y_2 in range(y):\n",
|
||
" new_matrix[y_1][x_1] = int(new_matrix[y_1][x_1] or\n",
|
||
" first_array[y_1][y_2] * second_array[y_2][x_1])\n",
|
||
" \n",
|
||
" return new_matrix\n",
|
||
"\n",
|
||
"\n",
|
||
"def some_function_check(array: list[list[int]]) -> bool:\n",
|
||
" return some_funtion(some_funtion(array, array), array) == \\\n",
|
||
" some_funtion(some_funtion(some_funtion(array, array), array), array)\n",
|
||
"\n",
|
||
"\n",
|
||
"array = [[1, 1, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [1, 1, 0, 0]]\n",
|
||
"\n",
|
||
"print(f\"\"\"\n",
|
||
"Рефлективна - {reflexivity_check(array)}\n",
|
||
"Антирефлективна - {antireflexivity_check(array)}\n",
|
||
"Симметрична - {symmetry_check(array)}\n",
|
||
"Антисимметрична - {antisymmetry_check(array)}\n",
|
||
"Транзитивна - {transitivity_check(array)}\n",
|
||
"Замкнута - {some_function_check(array)}\n",
|
||
"\"\"\")"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"id": "dc2c6a7d",
|
||
"metadata": {},
|
||
"source": [
|
||
"### Транзитивное замыкание\n"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"id": "77642242",
|
||
"metadata": {},
|
||
"source": [
|
||
"Транзитивное замыкание бинарного отношения, представленного в виде бинарной матрицы,\n",
|
||
"представляет собой объединение положительных степеней (всех) исходного отношения\n"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 24,
|
||
"id": "7a3af8c2",
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"name": "stdout",
|
||
"output_type": "stream",
|
||
"text": [
|
||
"[[0 0 1 0]\n",
|
||
" [0 0 1 1]\n",
|
||
" [1 0 0 0]\n",
|
||
" [0 0 1 0]]\n"
|
||
]
|
||
}
|
||
],
|
||
"source": [
|
||
"import numpy as np\n",
|
||
"A = np.array([[0, 0, 1, 0],\n",
|
||
" [0, 0, 1, 1],\n",
|
||
" [1, 0, 0, 0],\n",
|
||
" [0, 0, 1, 0]])\n",
|
||
"print(A)"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"id": "92d6fac0",
|
||
"metadata": {},
|
||
"source": [
|
||
"Исходный алгоритм Уоршелла проще, поскольку он находит только транзитивное замыкание графа и не использует никакой информации о весах ребер. Алгоритм Флойда в основном является этим алгоритмом с дополнительными соображениями о таких весах. Алгоритм Флойда-Уоршалла решает проблему кратчайшего пути для всех пар. Соответственно, на вход алгоритма Флойда-Уоршалла нужно подавать взвешенноую матрицу бинарного отношения, в которой ненулевой элемент обозначает не только наличие отношения между i и j элементами, но и силу этой связи (выраженную положительным числом).\n"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 21,
|
||
"id": "f071103e",
|
||
"metadata": {},
|
||
"outputs": [],
|
||
"source": [
|
||
"def warshall(G):\n",
|
||
" W = G\n",
|
||
" n = len(G)\n",
|
||
" for k in range(n):\n",
|
||
" for i in range(n):\n",
|
||
" for j in range(n):\n",
|
||
" G[i, j] = G[i, j] or (G[i, k] and G[k, j])\n",
|
||
" return W"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 22,
|
||
"id": "2c977eb9",
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"data": {
|
||
"text/plain": [
|
||
"array([[1, 0, 1, 0],\n",
|
||
" [1, 0, 1, 1],\n",
|
||
" [1, 0, 1, 0],\n",
|
||
" [1, 0, 1, 0]])"
|
||
]
|
||
},
|
||
"execution_count": 22,
|
||
"metadata": {},
|
||
"output_type": "execute_result"
|
||
}
|
||
],
|
||
"source": [
|
||
"warshall(A)"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"id": "87b5bb3e",
|
||
"metadata": {},
|
||
"source": [
|
||
"Так как транзитивное замыкание показывает, что если есть путь из i-ой вершины в k-ую и из k-ой вершины в j-ую, то есть путь и из i-ой вершины в j-ую. Соответственно сама матрица отношения это пути дляны 1, если мы строим композицию RR, то в итоге получаем наличие пути, длины 2, а если выполняем обычное возведение в степень, то за счет сложения будем видеть количество путей, длина которых соответствует степени.\n"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 23,
|
||
"id": "3a6c20c0",
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"data": {
|
||
"text/plain": [
|
||
"array([[2, 0, 3, 0],\n",
|
||
" [4, 0, 5, 1],\n",
|
||
" [3, 0, 2, 0],\n",
|
||
" [2, 0, 3, 0]])"
|
||
]
|
||
},
|
||
"execution_count": 23,
|
||
"metadata": {},
|
||
"output_type": "execute_result"
|
||
}
|
||
],
|
||
"source": [
|
||
"array_1 = ([[0, 0, 1, 0], [0, 0, 1, 1], [1, 0, 0, 0], [0, 0, 1, 0]])\n",
|
||
"np.linalg.matrix_power(array_1, 1) + np.linalg.matrix_power(array_1, 2) + np.linalg.matrix_power(\n",
|
||
" array_1, 3)+np.linalg.matrix_power(array_1, 4)+np.linalg.matrix_power(array_1, 5)"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"id": "a52bca04",
|
||
"metadata": {},
|
||
"source": [
|
||
"Поэтому встает закономерный вопрос, какой путь из предложенных будет иметь наименьшую длину?\n",
|
||
"Ответ можно найти с помощью алгоритма Флойда-Уоршалла. Только зададим веса. Обратите внимание на нули, которые обозначают отсутствующие пути.\n"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 43,
|
||
"id": "dc53474a",
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"data": {
|
||
"text/plain": [
|
||
"array([[0, 3, 0, 7],\n",
|
||
" [8, 0, 2, 0],\n",
|
||
" [5, 0, 0, 1],\n",
|
||
" [2, 0, 0, 0]])"
|
||
]
|
||
},
|
||
"execution_count": 43,
|
||
"metadata": {},
|
||
"output_type": "execute_result"
|
||
}
|
||
],
|
||
"source": [
|
||
"# ваша матрица\n",
|
||
"graph = np.array([\n",
|
||
" [0, 3, 0, 7],\n",
|
||
" [8, 0, 2, 0],\n",
|
||
" [5, 0, 0, 1],\n",
|
||
" [2, 0, 0, 0]\n",
|
||
"])\n",
|
||
"\n",
|
||
"graph"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 44,
|
||
"id": "db277779",
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"data": {
|
||
"text/plain": [
|
||
"array([[0., 3., 5., 6.],\n",
|
||
" [5., 0., 2., 3.],\n",
|
||
" [3., 6., 0., 1.],\n",
|
||
" [2., 5., 7., 0.]])"
|
||
]
|
||
},
|
||
"execution_count": 44,
|
||
"metadata": {},
|
||
"output_type": "execute_result"
|
||
}
|
||
],
|
||
"source": [
|
||
"# ваш код\n",
|
||
"def floyd_warshall(graph: np.ndarray) -> np.ndarray:\n",
|
||
" num_vertices = len(graph)\n",
|
||
" dist = np.array([[0 if i == j else graph[i][j] if graph[i][j] != 0 else np.inf for j in range(num_vertices)] for i in range(num_vertices)])\n",
|
||
"\n",
|
||
" for k in range(num_vertices):\n",
|
||
" for i in range(num_vertices):\n",
|
||
" for j in range(num_vertices):\n",
|
||
" if dist[i][k] != np.inf and dist[k][j] != np.inf:\n",
|
||
" dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])\n",
|
||
"\n",
|
||
" return dist\n",
|
||
"\n",
|
||
"\n",
|
||
"floyd_warshall(graph)"
|
||
]
|
||
}
|
||
],
|
||
"metadata": {
|
||
"kernelspec": {
|
||
"display_name": "Python 3 (ipykernel)",
|
||
"language": "python",
|
||
"name": "python3"
|
||
},
|
||
"language_info": {
|
||
"codemirror_mode": {
|
||
"name": "ipython",
|
||
"version": 3
|
||
},
|
||
"file_extension": ".py",
|
||
"mimetype": "text/x-python",
|
||
"name": "python",
|
||
"nbconvert_exporter": "python",
|
||
"pygments_lexer": "ipython3",
|
||
"version": "3.11.0"
|
||
}
|
||
},
|
||
"nbformat": 4,
|
||
"nbformat_minor": 5
|
||
}
|