Выбрать диагональные элементы квадратной матрицы, так чтобы их сумма была наименьшей

@Надежда Баутина · Регистрация: 29.04.2017

Студворк — интернет-сервис помощи студентам

Выбрать $https://www.cyberforum.ru/cgi-bin/latex.cgi?n$ элементов квадратной матрицы (размером $https://www.cyberforum.ru/cgi-bin/latex.cgi?n$ (строк) × $https://www.cyberforum.ru/cgi-bin/latex.cgi?n$ (столбцов), где $https://www.cyberforum.ru/cgi-bin/latex.cgi?2\leq n\leq 6$ ) так, чтобы :

1) нужно выбрать по одному элементу из каждой строки и каждого столбца матрицы.
Аналогично выбираются элементы для составления одного слагаемого определителя матрицы. Данные элементы соединены на рисунке линиями, которые в данном случае соединяют только три элемента.

Выбрать диагональные элементы квадратной матрицы, так чтобы их сумма была наименьшей

2) Сумма выбранных элементов должна быть наименьшей.

Как это сделать? Есть какая-нибудь теория по этой теме из математики или программирования?

Пока что вижу только один вариант решения: нужно подсчитать все суммы для всевозможных выбранных элементов. И выбрать наименьшую из них. Значит элементы, которые составляют наименьшую сумму, и являются искомыми. Но считаю его совсем не оптимальным. Так как, если $https://www.cyberforum.ru/cgi-bin/latex.cgi?n$ =6 , то появляется очень много вариантов выбора элементов, которые нужно прописывать в алгоритме.

@salam · 02.11.2017, 19:11

есть теория, эта задача называется "задача о назначениях".

ну вообще у вас же не зря ограничение на n задано. скорее всего более-менее разумно написанный перебор будет работать в пределах секунды.

@Shamil1 · 02.11.2017, 20:30

Можно добавить кэширование и отсечение.

Если использовать рекурсивный алгоритм:
Значение для матрицы равно минимуму из (элемент первого столбца + значение для матрицы, полученной вычёркиванием строки и столбца с этим элементом).

На каждом шаге перед рекурсивным вызовом проверяем:
1. Если мы уже считали значение для данной подматрицы, то берём его из кэша.
2. Если оценка снизу значения для данной подматрицы + выбранный элемент в сумме больше текущего лучшего значения, то проверять эту ветку не имеет смысла. Оценку снизу можно получить, например, сложив минимальный элемент из каждой строки.

Добавлено через 1 минуту
Ещё можно добавить приоритет перебора:
Элементы первого столбца перебираем в порядке возрастания. Тогда выше вероятность, что мы раньше получим хорошее значение и будем отсекать больше веток.

@Надежда Баутина · 02.11.2017, 20:49 **[ТС]**

Сообщение от Shamil1

Если использовать рекурсивный алгоритм:
Значение для матрицы равно минимуму из (элемент первого столбца + значение для матрицы, полученной вычёркиванием строки и столбца с этим элементом).

Поясните пожалуйста поподробней идею. Пока что не совсем поняла как это реализовать.

@Shamil1 · 02.11.2017, 21:08

Помните, как вычисляется определитель матрицы через миноры? То же самое, только вместо умножения - сумма, а вместо суммы - минимум.

Новые блоги и статьи Все статьи Все блоги /
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .	Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .	PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .

@Надежда Баутина 0 / 0 / 0 Регистрация: 29.04.2017 Сообщений: 9

	Выбрать диагональные элементы квадратной матрицы, так чтобы их сумма была наименьшей 02.11.2017, 18:20. Показов 1196. Ответов 4 Метки матрица (Все метки) Выбрать $https://www.cyberforum.ru/cgi-bin/latex.cgi?n$ элементов квадратной матрицы (размером $https://www.cyberforum.ru/cgi-bin/latex.cgi?n$ (строк) × $https://www.cyberforum.ru/cgi-bin/latex.cgi?n$ (столбцов), где $https://www.cyberforum.ru/cgi-bin/latex.cgi?2\leq n\leq 6$ ) так, чтобы : 1) нужно выбрать по одному элементу из каждой строки и каждого столбца матрицы. Аналогично выбираются элементы для составления одного слагаемого определителя матрицы. Данные элементы соединены на рисунке линиями, которые в данном случае соединяют только три элемента. 2) Сумма выбранных элементов должна быть наименьшей. Как это сделать? Есть какая-нибудь теория по этой теме из математики или программирования? Пока что вижу только один вариант решения: нужно подсчитать все суммы для всевозможных выбранных элементов. И выбрать наименьшую из них. Значит элементы, которые составляют наименьшую сумму, и являются искомыми. Но считаю его совсем не оптимальным. Так как, если $https://www.cyberforum.ru/cgi-bin/latex.cgi?n$ =6 , то появляется очень много вариантов выбора элементов, которые нужно прописывать в алгоритме. 0

@salam 194 / 174 / 30 Регистрация: 10.07.2012 Сообщений: 800
	02.11.2017, 19:11
	есть теория, эта задача называется "задача о назначениях". ну вообще у вас же не зря ограничение на n задано. скорее всего более-менее разумно написанный перебор будет работать в пределах секунды. 1

@Shamil1 Модератор 3133 / 2280 / 469 Регистрация: 26.03.2015 Сообщений: 8,874
	02.11.2017, 20:30
	Можно добавить кэширование и отсечение. Если использовать рекурсивный алгоритм: Значение для матрицы равно минимуму из (элемент первого столбца + значение для матрицы, полученной вычёркиванием строки и столбца с этим элементом). На каждом шаге перед рекурсивным вызовом проверяем: 1. Если мы уже считали значение для данной подматрицы, то берём его из кэша. 2. Если оценка снизу значения для данной подматрицы + выбранный элемент в сумме больше текущего лучшего значения, то проверять эту ветку не имеет смысла. Оценку снизу можно получить, например, сложив минимальный элемент из каждой строки. Добавлено через 1 минуту Ещё можно добавить приоритет перебора: Элементы первого столбца перебираем в порядке возрастания. Тогда выше вероятность, что мы раньше получим хорошее значение и будем отсекать больше веток. 1

@Shamil1 Модератор 3133 / 2280 / 469 Регистрация: 26.03.2015 Сообщений: 8,874
	02.11.2017, 21:08
	Помните, как вычисляется определитель матрицы через миноры? То же самое, только вместо умножения - сумма, а вместо суммы - минимум. 0