Дискретная математика и нейронки

Продолжаем решать мои контрольные работы по дискретной математике с помощью GigaChat и Qwen 3.6 Plus.

Вот и Shedevrum считает, что использование нейронок - сродни магии

В качестве промпта закибываем скриншот задания. Не забываем, это контрольная работа и времени на качественные промпты нет.

Задача 1

Будем решать это задачу не только на минимум, но и на максимум

Решить задачу о назначениях требуется, используя алгоритм из лекций.

Текст алгоритма из лекций. Я понимаю, что существует целое семейство алгоритмов, называемых венгерскими. Но мы как на тренировке отрабатываем один. И оценивается, насколько усвоен именно этот алгоритм! Потому за использование других подходов - снижение оценки. Но нейросеть об этом не знает. Если только сразу в промпт не закинуть текст алгоритма.

Шаг 1. В каждой строке матрицы задачи найти минимальный элемент и вычесть его из всех остальных элементов строки.

Шаг 2. В каждом столбце полученной матрицы найти минимальный элемент и вычесть его из всех элементов столбца.

Шаг 3. Найти строку с одним нулем. Перевести этот нуль в список помеченных. В столбце, где находится помеченный нуль, зачеркнуть все остальные нули. В дальнейшем зачеркнутые нули не рассматриваются. Этот шаг продолжать до тех пор, пока возможно.

Шаг 4. Найти столбец с одним нулем и пометить этот нуль. В строке, где находится отмеченный нуль, все остальные нули зачеркиваются. Продолжить выполнение этого шага до тех пор, пока это возможно.

Шаг 5. Если после выполнения шагов 3 и 4 еще есть неотмеченные нули, отметить любой из них, а в строке и столбце, где находится этот отмеченный нуль, зачеркнуть все остальные нули.

Шаг 6. Если каждая строка и каждый столбец матрицы содержат ровно один отмеченный нуль, то получено оптимальное решение. Каждый из отмеченных нулей указывает прикрепление поставщика к потребителю. В противном случае провести минимальное число пересекающихся горизонтальных и вертикальных прямых через все нули. Среди не зачеркнутых этими прямыми чисел найти минимум. Этот минимум вычесть из всех незачеркнутых чисел и прибавить ко всем числам, находящимся на пересечении прямых. К полученной матрице применить алгоритм, начиная с шага 3.

Случай максимизации целевой функции сводится к задаче минимизации для матрицы, полученной из исходной матрицы умножением каж-дого элемента на –1.

Итак, проверяем в контексте данного материала.

Решение задачи на максимум мы рассмотрели на занятии:

Решение задачи на минимум предлагаю найти при помощи автоматического решателя, который использует венгерский алгоритм, как раз такой, как приведен в этом посте.

Введем условие и, нажав кнопку, получим подробное решение и ответ 15. Остается только переписать все нужное на листочек и отличная оценка за решение задачи у тебя в кармане. Но почему-то этому проверенному способы некоторые все же предпочитают генеративный ИИ, видимо, даже матрицу ручками ввести проблематично...

Решение от GigaChat

Орфография и пунктуация сохранены...

Шаг 1: Понимание задачи (ага, на лекции ко мне гигачат не ходил)

Задача о назначениях заключается в поиске оптимального соответствия между элементами двух множеств таким образом, чтобы минимизировать общую стоимость назначения. В нашем случае дана матрица стоимости размером 6×6, и нам нужно найти минимальное назначение.

Исходная матрица: аккуратно переписывается исходная матрица

Шаг 2: Применение Венгерского алгоритма

Этап 1: Вычитание минимума строки

Вычтем минимальный элемент каждой строки из всех элементов этой строки:

Ну ок, вычел... Вроде, даже правильно, если не считать, что 12-4=8... И ещё нескольких нюансов..

И тут первая ошибка - минимумы по столбцам нейросеть забывает вычесть.

Этап 2: Покрытие нулей минимальным числом линий

Покроем нули минимальным числом горизонтальных и вертикальных линий:Минимальное число линий = 4 (меньше размера матрицы)

А вот тут внимание!!! В приведенном тексте алгоритма было так? Нейросет приводит результат выполнения сего магического ритуала? Нет!

Этап 3: Нахождение наименьшего непокрытого элемента

Наименьший непокрытый элемент = 1

Тут все правильно. Только непокрытые элементы нейросеть почему-то не показывает. Колдует.

Этап 4: Модификация матрицы

Вычтем этот элемент из всех непокрытых элементов

Добавим его ко всем элементам на пересечении покрывающих линий

Текст верный, а вот результат...

От нас сокрыт сакральный процесс получения данной матрицы. Но одно точно - она неправильная!

​​Этап 5: Повторение этапа покрытия нулей. Теперь мы можем покрыть все нули четырьмя линиями, что равно размеру матрицы.

Шаг 3: Определение оптимального назначения

И после этого...

Мы нашли оптимальное решение, теперь найдем конкретные назначения:

Назначение (1,5) (строка 1, столбец 5) с весом 0

Назначение (2,3) (строка 2, столбец 3) с весом 0

Назначение (3,1) (строка 3, столбец 1) с весом 0

Назначение (4,6) (строка 4, столбец 6) с весом 0

Назначение (5,3) (строка 5, столбец 3) с весом 0

Назначение (6,4) (строка 6, столбец 4) с весом 0

Обратите внимание, что существует альтернативное оптимальное решение:

Назначение (1,5)

Назначение (2,3)

Назначение (3,1)

Назначение (4,3)

Назначение (5,6)

Назначение (6,4)

Итоговое решение

Оптимальное назначение найдено. Общая минимальная стоимость составляет 0+0+0+0+0+0=0. ГЕНИАЛЬНО! Однако, поскольку наша исходная матрица была уменьшена путем вычитания минимальных элементов, фактическая минимальная стоимость равна сумме всех вычтенных минимальных элементов:

Общая сумма: 1+2+1+0+1+4=9

Таким образом, минимальное значение целевой функции составляет 9​.

Только почему детерминированный алгоритм получает решение =15?

Назначения: (1,5), (2,2), (3,1), (4,6), (5,3), (6,4). Их нейросеть нашла "почти" верно. Но откуда 9?

Решим теперь задачу на максимум

И тут GigaChat начинает вот с такого действия: Максимальное значение в матрице: 12. Создаем новую матрицу, вычитая каждый элемент исходной матрицы из максимального значения. Ох, не зря я предложила исходную матрицу умножать на (-1) в ручном решении...

А далее... "И так сойдет"...

Применяя Венгерский алгоритм к матрице, получаем следующее оптимальное назначение:

Первая строка → пятый столбец

Вторая строка → третий столбец

Третья строка → первый столбец

Четвертая строка → шестой столбец

Пятая строка → второй столбец

Шестая строка → четвертый столбец

Расчет максимальной суммы

Суммируем полученные значения: Smax⁡=1+2+1+1+11+4=20.

Задание для размышления: сравните с правильным решением самостоятельно и сделайте для себя правильные выводы.

Qwen 3.6 Plus

Закинем тот же промпт в китайскую LLM. Думает она дольше...

Решение

Шаг 1: Вычитание минимума из каждой строки

Вычитаем минимальный элемент каждой строки из всех элементов этой строки:

• Строка 1: min = 1 → [1, 5, 3, 6, 0, 1]
• Строка 2: min = 2 → [6, 5, 0, 2, 1, 3]
• Строка 3: min = 1 → [0, 4, 2, 3, 2, 2]
• Строка 4: min = 0 → [8, 7, 1, 2, 0, 1]
• Строка 5: min = 1 → [8, 10, 0, 2, 2, 5]
• Строка 6: min = 4 → [8, 5, 5, 0, 1, 3]

После этого у всех работ, где минимум в строке/столбце выписан отдельно от матрицы, оценки пошли вниз!

Шаг 2: Вычитание минимума из каждого столбца

Вычитаем минимальный элемент каждого столбца:

Проверьте, а Qwen считать умеет?

Шаг 3: Поиск оптимального назначения

После нескольких итераций улучшения матрицы (вычитание минимальных непокрытых элементов), получаем оптимальное назначение:

Э... стой! А итерации ты куда зажал???

Оптимальное назначение:

• Строка 1 → Столбец 5 (элемент a₁₅ = 1)
• Строка 2 → Столбец 3 (элемент a₂₃ = 2)
• Строка 3 → Столбец 1 (элемент a₃₁ = 1)
• Строка 4 → Столбец 6 (элемент a₄₆ = 1)
• Строка 5 → Столбец 4 (элемент a₅₄ = 3)
• Строка 6 → Столбец 2 (элемент a₆₂ = 9)

Ответ:

Минимальная сумма: 1 + 2 + 1 + 1 + 3 + 9 = 17

Ну... честно говоря, прошлую контрольную Qwen решал лучше...

А теперь посмотрим, что делает эта LLM с задачей на максимум.

И тут снова: Для решения задачи на максимум преобразую её в задачу на минимум. Вычту каждый элемент из максимального значения матрицы (12). Ну ясно теперь, чем пользовались любители вычитать из максимального.

Поиск максимального назначения после обработки минимумов по строкам и столбцам также сводится к черно-белой нейронной магии. И получается ответ:

Оптимальное назначение на максимум:

• Работник 1 → Задача 4 (a₁₄ = 7)
• Работник 2 → Задача 1 (a₂₁ = 8)
• Работник 3 → Задача 2 (a₃₂ = 5)
• Работник 4 → Задача 6 (a₄₆ = 1)
• Работник 5 → Задача 5 (a₅₅ = 3)
• Работник 6 → Задача 3 (a₆₃ = 9)

Максимальная сумма: 7 + 8 + 5 + 1 + 3 + 9 = 33

Предлагаю сравнить с правильным ответом и сделать выводы.

Задача 2

Здесь предлагается словесная постановка.

Решить задачу с помощью алгоритма поиска максимального паросочетания. Привести двудольный граф, процесс добавления ребер в паросочетание. Хотя бы одно добавление должно быть осуществлено посредством чередующейся цепи. Привести результирующее паросочетание. В качестве ответа запишите мощность паросочетания.

Шесть друзей собираются нарядиться в разные новогодние костюмы на корпоративе. Маше нравится костюм кошки, Ивану – костюмы клоуна и эльфа, Юле – кошки и Фионы, Денис хотел бы нарядиться клоуном, богатырем или эльфом, Инна предпочитает костюмы Фионы, кошки или морячки, Яков – костюм богатыря или кошки. Используя алгоритм чередующихся цепей, определить, есть ли у компании возможность отправиться на корпоратив в разных костюмах и какие костюмы наденет каждый из друзей?

Прекрасно! Нейронкам не надо ничего распознавать, только поработать с текстом! Прям готовый промпт!

Qwen 3.6 Plus

1. Построение двудольного графа

Определим две доли графа:

• Доля U (Друзья): U={Маша,Иван,Юля,Денис,Инна,Яков}U={Маша,Иван,Юля,Денис,Инна,Яков}
• Доля V (Костюмы): V={Кошка,Клоун,Эльф,Фиона,Богатырь,Морячка}V={Кошка,Клоун,Эльф,Фиона,Богатырь,Морячка}

Ребра графа (предпочтения):

• M→{Кошка}
• I→{Клоун,Эльф}
• Y→{Кошка,Фиона}
• D→{Клоун,Богатырь,Эльф}
• In→{Фиона,Кошка,Морячка}
• Ya→{Богатырь,Кошка}

2. Процесс построения паросочетания

Будем последовательно добавлять ребра в паросочетание M, начиная с пустого множества M=∅.

Шаг 1: Обработка Маши

• Маша хочет костюм Кошки. Костюм свободен.
• Добавляем ребро (Маша,Кошка).
• M={(Маша,Кошка)}

Шаг 2: Обработка Ивана

• Иван хочет Клоуна. Костюм свободен.
• Добавляем ребро (Иван,Клоун).
• M={(Маша,Кошка),(Иван,Клоун)}

Шаг 3: Обработка Юли

• Юля хочет Кошку (занято Машей).
• Юля хочет Фиону. Костюм свободен.
• Добавляем ребро (Юля,Фиона).
• M={(Маша,Кошка),(Иван,Клоун),(Юля,Фиона)}

Шаг 4: Обработка Дениса

• Денис хочет Клоуна (занято Иваном).
• Денис хочет Богатыря. Костюм свободен.
• Добавляем ребро (Денис,Богатырь).
• M={(Маша,Кошка),(Иван,Клоун),(Юля,Фиона),(Денис,Богатырь)}

Шаг 5: Обработка Инны

• Инна хочет Фиону (занято Юлей).
• Инна хочет Кошку (занято Машей).
• Инна хочет Морячку. Костюм свободен.
• Добавляем ребро (Инна,Морячка).
• M={(Маша,Кошка),(Иван,Клоун),(Юля,Фиона),(Денис,Богатырь),(Инна,Морячка)}

Шаг 6: Обработка Якова (использование чередующейся цепи)

• Яков хочет Богатыря (занято Денисом) или Кошку (занято Машей).
• Прямое добавление невозможно. Ищем чередующуюся цепь , начинающуюся в Якове и заканчивающуюся в свободной вершине.Путь: Яков→Богатырь. Ребро (Яков,Богатырь) не в M.
• Вершина Богатырь соединена с Денисом ребром из M (Денис,Богатырь).
• Переходим к Денису. У Дениса есть другие предпочтения: Клоун (занято) и ЭльфЭльф (свободно!).
• Путь продолжается: ...→Денис→Эльф. Ребро (Денис,Эльф) не в M.
• Вершина Эльф свободна. Цепь найдена!
• Чередующаяся цепь: Яков—Богатырь—Денис—Эльф
• Операция симметрической разности:
• Мы удаляем из паросочетания ребро (Денис,Богатырь) и добавляем ребра (Яков,Богатырь) и (Денис,Эльф).
• Новое паросочетание:
• M′={(Маша,Кошка),(Иван,Клоун),(Юля,Фиона),(Инна,Морячка),(Яков,Богатырь),(Денис,Эльф)}M′={(Маша,Кошка),(Иван,Клоун),(Юля,Фиона),(Инна,Морячка),(Яков,Богатырь),(Денис,Эльф)}

Тут, надо признать, решение получено правильное. Единственное, в нем много лишних слов, которые нормальный человек писать бы не стал. Плюс не мешает свести к терминологии, используемой на занятиях. Но у некоторых авторов работ следы Квена явно просматриваются.

GigaChat

Как ни странно, но на этот раз и он справился! Правда, ввел много новых обозначений и даже попытался нарисовать двудольный граф. Я знаю, что LLM - личности творческие.

Красотища-то какая!

Начнем с пустого паросочетания M=∅.

Шаг 2: Первое увеличение паросочетания

Попытаемся найти свободный узел слева (все узлы свободны). Возьмем вершину M (Маша). Она связана только с K (Кошка). Это простой увеличивающий путь: M−K.Обновляем паросочетание: M={M−K}.

Шаг 3: Второе увеличение паросочетания

Ищем новый увеличивающий путь. Рассмотрим вершину I (Иван). У него два свободных соседа: C и E. Простой увеличивающий путь: I−C.Обновляем паросочетание: M={M−K,I−C}.

Шаг 4: Третье увеличение паросочетания

Рассмотрим вершину Y (Юлия). Ее соседи: F и K. Узел K занят, а F свободен. Простой увеличивающий путь: Y−F.Обновляем паросочетание: M={M−K,I−C,Y−F}.

Шаг 5: Четвертое увеличение паросочетания

Рассмотрим вершину D (Денис). Его свободные соседи: B и E. Простой увеличивающий путь: D−B.Обновляем паросочетание: M={M−K,I−C,Y−F,D−B}.

Шаг 6: Пятое увеличение паросочетания

Рассмотрим вершину N (Инна). Ее свободные соседи: M. Простой увеличивающий путь: N−M.Обновляем паросочетание: M={M−K,I−C,Y−F,D−B,N−M}.

Шаг 7: Шестое увеличение паросочетания

Рассмотрим последнюю вершину J (Яков). Его соседи: B и K. Оба заняты, но можно построить чередующуюся цепь: J−B−D−E−I−C

Эта цепь является увеличивающей, потому что: Начинается в свободной вершине J, Чередуются ребра вне паросочетания и ребра паросочетания, Завершается в свободной вершине C.

Хотя... я студентов еще учила отмечать, какое ребро откуда взято...

Выполняем перестановку вдоль цепи: Удаляем пары D−B и I−C

Добавляем пары J−B, D−E, I−C

Обновляем паросочетание: M={M−K,I−C,Y−F,J−B,N−M,D−E}

Результирующее паросочетание

После завершения процесса построения имеем полное паросочетание мощности 6:

Маша (M) наряжается в костюм Кошки (K)

Иван (I) выбирает костюм Клоуна (C)

Юлия (Y) надевает костюм Фионы (F)

Денис (D) становится Эльфом (E)

Инна (N) выберет костюм Морячки (M)

Яков (J) станет Богатырём (B)

Запись, хоть и правильная, но требует некоторой стилистической обработки. Интересно было бы прогнать все задачи из контрольной. Обходится ли какая-то из них без построения чередующейся цепи? А то много недочетов на этот счет.

Задача 3

Простой и понятный алгоритм Дейкстры вызывает немало боли у студентов. Посмотрим, что творят нейронные сети. Требования к оценке жесткие. Нужно построить таблицу с расстановкой пометок и привести полностью (вместе с транзитными вершинами) пути до всех остальных вершин из v1. При проверке выяснилось, что некоторые вопросы задачи оказались не замечены студентами (или используемыми ими нейросетями). Давайте посмотрим...

GigaChat

Давайте просто посмотрим в чат

LLM досконально идет по шагам алгоритма Дейкстры и выставляет пометки. Причем, делает это качественно и с правильными пометками. Остается только транспонировать полученные столбцы и записывать их строками в табличку. Ну и не забывать, что после получения постоянной пометки, в следующих строчках мы значение постоянной пометки не переписываем. А те, кто переписывают, получают минусы в оценку.

Но нейронка довольно быстро сбивается с правильного пути. Обратите внимание на кратчайший путь до вершины v4, например.

В результате получен также неверный ответ в пути к вершине с максимальным индексом. 19 вместо 22.

Но GigaChat знает, какой вопрос задан, и оформляет ответ.

Найдите ошибки. Ну и транзитные вершины придется восстанавливать из таблицы самостоятельно.

Qwen 3.6 Plus

Китайская нейросеть, видимо, не знакома с нашим российским стилем изложения техники меток имени Дейкстры. Поэтому записывается явный поток сознания.

Но, надо отметить, что задача при этом решена верно. Осталось только извлечь нужную информацию, сформировать таблицу и записать тот ответ, который ждет преподаватель. А такой поток мыслей на контрольной работе не оценивался. Нужна таблица!

А Qwen тем временем в качестве ответа записывает полный путь от v1 до v7 и напрочь забывает, что в задаче требовалось привести и остальные пути от вершины v1.

Вывод

Думаю, очевиден. Нейронные сети могут справиться с этой контрольной работой. Кроме задачи о назначениях. Для которой все же более эффективным является использование решателя. Я, вообще, не понимаю, зачем скармливать нейронкам задачи, которые имеют решение при помощи детерминированного алгоритма. Почему не проще найти уже готовый скрипт (или самому написать его). Видимо, лень. Легче выдумать, чем использовать алгоритм. Нейронки при решении использовать можно. Но для получения качественной работы требуется много времени и четкого понимания того, что нужно получить. Потому на контрольной работе выгоднее решить самим, чем попросить LLM.