Искусственный разум. Параллельная специализированная гибридная машина. Метод точного мгновенного решения NP задачи - страница 7
Таблица 6. Определённый и полученный упорядоченныйвектор грузов для М = 2 и N>уг = 4.
Из таблицы 6 определим локальное оптимальное решения задачи о ранце:
W = W2 + W4 = 4 + 8 = 12
P = P2 + P4 = 6 + 7 = 13
Согласно метода, определим локальное оптимальное решения задачи о ранце для значений М = 1 и N>уг = 5 согласно таблицы 7.
Таблица 7. Определённый вектор грузов для
М = 1 и N>уг = 5
Из таблицы 7 определим локальное оптимальное решения задачи о ранце для М = 1 и N>уг = 5 :
W = W4 = 8
P = P4 = 7
Исходя из вышеизложенного выбираем локальный оптимальный результат данного примера задачи о ранце:
W = W2 + W4 = 4 +8 = 12
P = P2 + P4 = 6 + 7 = 13.
Таким образом, без перебора вариантов решения задачи о ранце, находим данным методом локальный оптимальный результат и глобальный оптимального результат для данного примера задачи о ранце с помощью моего метода. Определение лучшего результата требует выполнение дополнительных условий. Необходимо определить, что для нас является более важным, число грузов или их ценность.
Что и требовалось доказать.
Задача о назначениях
Введение
Задача о назначениях – одна из фундаментальных задач комбинаторной оптимизации. Задача состоит в поиске минимальной суммы дуг во взвешенном двудольном графе.
В наиболее общей форме задача формулируется следующим образом:
Имеется некоторое число работ и некоторое число исполнителей. Любой исполнитель может быть назначен на выполнение любой одной работы, но с неодинаковыми затратами. Нужно распределить работы так чтобы выполнить работы с минимальными затратами.
В настоящее время неизвестен эффективный точный метод решения задачи о назначениях.
Постановка задачи
Для задачи о назначениях даны два множества А и Т одного размера и задана функция стоимости
С: А × Т → R
Необходимо найти биекцию ƒ: А → Т такую, что целевая функция
Метод решения задачи о назначениях
Определяется в качестве числа угадывания (N>уг) определённое числа исполнителей и подмножеств исполнителей различной мощностью.
Первоначально осуществляется объединение исполнителей по два и упорядочение по затратам подмножеств исполнителей. В дальнейшем проводиться поэтапное объединение исполнителей в конечные подмножества исполнителей, с увеличением мощности подмножества с упорядочением этих подмножеств по возрастанию затрат, до получения подмножества исполнителей мощностью