Задачка

blindman

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

Michael_K

А разве число единиц в матрице B не всегдаа будет равно n?
Грубо коворя, располагаем единицы в B по второй диагонали (для четного n)
и перставляем...
Только вот в общем случае сложность все равно дикая, а оптимальность... не уверен.

=DeaD=

blindman писал(а):

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

Ну я писал про исходную задачу.

Добавлено спустя 58 секунд:
Переставляем - это решение "в лоб", сложность n!

Его можно так же "в лоб" оптимизировать, сделав оценку сначала жадным алгоритмом и потом применив метод ветвей и границ.

Добавлено спустя 1 минуту 56 секунд:
Но сложность всё равно останется NP

Michael_K

Типа, находим пару, у которой a(x1y1)+a(x2y2)-a(x1y2)-a(x2y1) минимально
и переставляем, проверив условие про главную диагональ.
поиск пропорционален n²... Скорость схождения не могу оценить.
Или нет?

blindman

Michael_K писал(а):

А разве число единиц в матрице B не всегдаа будет равно n?

Нет, не всегда. Я уточнил условие - не "ровно 1 единичный элемент в каждой строке/столбце", а "как минимум 1"

=DeaD=

2Michael_K: Да, именно это. Скорость схождения пока тоже не берусь оценивать, но всё равно Андрей уже поменял уже условия задачи

Добавлено спустя 5 минут 30 секунд:
Я думаю можно в текущей формулировке попробовать дин-прог применить и чуть обобщив задачу.

Убрать только надо моим методом условие про главную диагональ (поставив в неё в матрице А числа равные сумме 1 и всех положительных значений исходной матрицы А).

И попытаться перейти от матрицы A'[n, i] к матрице A''[n,i+1], где i от 1 до n-1.

Добавлено спустя 20 секунд:
Считая что А' уже решено, а A'' ща построим.

blindman

Может так: расставляем единицы так, чтобы было по одной в каждой строке и колонке. Потом меняем матрицу с помощью 3 операций:

1. берем единичный элемент, и рассматриваем возможность его "деления" - вместо него единица будет в той же строке, но в другой колонке, другая единица в той же колонке, но в другой строке
2. берем единичный элемент, и рассматриваем возможность его слияния с другим - вместо двух будет один на пересечении их строки и колонки (2 варианта)
3. берем единичный элемент, и рассматриваем возможность его перемещения по строке или колонке

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

Michael_K

Что-то мне кажется сильно сложнее... не считал - просто Ащущенье

Добавлено спустя 1 минуту 4 секунды:
Как это вы сможете двигать одну единицу, не двигая другие...
Это ж дерево сильно разрастающееся!

Добавлено спустя 3 минуты 14 секунд:
Ой, блин, все забываю, вы ж условия поменяли

)

blindman

После "деления" это будет возможно

blindman

Еще мысль. Преобразуем матрицу А в направленный граф с n узлами. Элемент (i,j) матрицы преобразуется в ребро с весом А(i,j) и направлением от i к j. Применяем алгоритм поиска кратчайших путей, например [[ru:Алгоритм Флойда — Уоршелла]]. Для всех ребер, входящих в найденные пути, пишем 1 в матрицу решения.

Michael_K

Что-то я не понял, как будут соблюдаться условия задачи...
и какой :wink:

Duhas

мб таки ГА ? делаем хромосому и n-1 * n генов и вперед ) критерий проверять перемножением или суммой...

=DeaD=

Андрей, погоди, что-то я сразу не вкурил. То что ты сначала рассказал - это же почти классическая переведенная в матрицы задача коммивояжера на ориентированном графе? A[i,j] - время в пути из i в j. B[i,j] - используем это ребро в выбранном кольцевом пути по всем городам или нет. Как раз получается B[i,j] или 0 или 1.

Сумма B[i,j] по j от 0 до n-1 при любом i равна 1, сумма B[i,j] по i от 0 до n-1 при любом j равна 1 - это типа в каждый город должны ровно 1 раз войти и ровно 1 раз выйти.

Тут же понятно, почему B[i,i]=0 при любом i

нечего из i в i ходить

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

Michael_K

не только несколько, но и пути с пересечениями...

=DeaD=

В исходной задаче где по 1 единице в каждом столбце или строке - какие еще пересечения?

roboforum.ru

Задачка

Кто сейчас на конференции