roboforum.ru
Технический форум по робототехнике.
Задачка
Re: Задачка
Улучшит - вполне возможно. Но в общем случае такие операции не гарантируют нахождение оптимального решения. Оптимальное может быть найдено только если перед тем как применять эти операции матрица B будет содержать ровно столько единиц, сколько их в оптимальном решении.
Re: Задачка
А разве число единиц в матрице B не всегдаа будет равно n?
Грубо коворя, располагаем единицы в B по второй диагонали (для четного n)
и перставляем...
Только вот в общем случае сложность все равно дикая, а оптимальность... не уверен.
Грубо коворя, располагаем единицы в B по второй диагонали (для четного n)
и перставляем...
Только вот в общем случае сложность все равно дикая, а оптимальность... не уверен.
Re: Задачка
blindman писал(а):Улучшит - вполне возможно. Но в общем случае такие операции не гарантируют нахождение оптимального решения. Оптимальное может быть найдено только если перед тем как применять эти операции матрица B будет содержать ровно столько единиц, сколько их в оптимальном решении.
Ну я писал про исходную задачу.
Добавлено спустя 58 секунд:
Переставляем - это решение "в лоб", сложность n!
Его можно так же "в лоб" оптимизировать, сделав оценку сначала жадным алгоритмом и потом применив метод ветвей и границ.
Добавлено спустя 1 минуту 56 секунд:
Но сложность всё равно останется NP
Re: Задачка
Типа, находим пару, у которой a(x1y1)+a(x2y2)-a(x1y2)-a(x2y1) минимально
и переставляем, проверив условие про главную диагональ.
поиск пропорционален n2... Скорость схождения не могу оценить.
Или нет?
и переставляем, проверив условие про главную диагональ.
поиск пропорционален n2... Скорость схождения не могу оценить.
Или нет?
Последний раз редактировалось Michael_K 25 дек 2009, 15:01, всего редактировалось 1 раз.
Re: Задачка
Michael_K писал(а):А разве число единиц в матрице B не всегдаа будет равно n?
Нет, не всегда. Я уточнил условие - не "ровно 1 единичный элемент в каждой строке/столбце", а "как минимум 1"
Re: Задачка
2Michael_K: Да, именно это. Скорость схождения пока тоже не берусь оценивать, но всё равно Андрей уже поменял уже условия задачи 
Добавлено спустя 5 минут 30 секунд:
Я думаю можно в текущей формулировке попробовать дин-прог применить и чуть обобщив задачу.
Убрать только надо моим методом условие про главную диагональ (поставив в неё в матрице А числа равные сумме 1 и всех положительных значений исходной матрицы А).
И попытаться перейти от матрицы A'[n, i] к матрице A''[n,i+1], где i от 1 до n-1.
Добавлено спустя 20 секунд:
Считая что А' уже решено, а A'' ща построим.
Добавлено спустя 5 минут 30 секунд:
Я думаю можно в текущей формулировке попробовать дин-прог применить и чуть обобщив задачу.
Убрать только надо моим методом условие про главную диагональ (поставив в неё в матрице А числа равные сумме 1 и всех положительных значений исходной матрицы А).
И попытаться перейти от матрицы A'[n, i] к матрице A''[n,i+1], где i от 1 до n-1.
Добавлено спустя 20 секунд:
Считая что А' уже решено, а A'' ща построим.
Re: Задачка
Может так: расставляем единицы так, чтобы было по одной в каждой строке и колонке. Потом меняем матрицу с помощью 3 операций:
1. берем единичный элемент, и рассматриваем возможность его "деления" - вместо него единица будет в той же строке, но в другой колонке, другая единица в той же колонке, но в другой строке
2. берем единичный элемент, и рассматриваем возможность его слияния с другим - вместо двух будет один на пересечении их строки и колонки (2 варианта)
3. берем единичный элемент, и рассматриваем возможность его перемещения по строке или колонке
Разумеется, операция может быть выполнена только если в ее результате не нарушатся условия задачи, и операция улучшит решение. Итерации прекращаем, когда нет возможности выполнить ни одну из 3 операций
1. берем единичный элемент, и рассматриваем возможность его "деления" - вместо него единица будет в той же строке, но в другой колонке, другая единица в той же колонке, но в другой строке
2. берем единичный элемент, и рассматриваем возможность его слияния с другим - вместо двух будет один на пересечении их строки и колонки (2 варианта)
3. берем единичный элемент, и рассматриваем возможность его перемещения по строке или колонке
Разумеется, операция может быть выполнена только если в ее результате не нарушатся условия задачи, и операция улучшит решение. Итерации прекращаем, когда нет возможности выполнить ни одну из 3 операций
Re: Задачка
Что-то мне кажется сильно сложнее... не считал - просто Ащущенье
Добавлено спустя 1 минуту 4 секунды:
Как это вы сможете двигать одну единицу, не двигая другие...
Это ж дерево сильно разрастающееся!
Добавлено спустя 3 минуты 14 секунд:
Ой, блин, все забываю, вы ж условия поменяли)
Добавлено спустя 1 минуту 4 секунды:
Как это вы сможете двигать одну единицу, не двигая другие...
Это ж дерево сильно разрастающееся!
Добавлено спустя 3 минуты 14 секунд:
Ой, блин, все забываю, вы ж условия поменяли
)Re: Задачка
После "деления" это будет возможно
Re: Задачка
Еще мысль. Преобразуем матрицу А в направленный граф с n узлами. Элемент (i,j) матрицы преобразуется в ребро с весом А(i,j) и направлением от i к j. Применяем алгоритм поиска кратчайших путей, например [[ru:Алгоритм Флойда — Уоршелла]]. Для всех ребер, входящих в найденные пути, пишем 1 в матрицу решения.
Re: Задачка
Что-то я не понял, как будут соблюдаться условия задачи...
и какой
и какой
Re: Задачка
мб таки ГА ? делаем хромосому и n-1 * n генов и вперед ) критерий проверять перемножением или суммой...
Re: Задачка
Андрей, погоди, что-то я сразу не вкурил. То что ты сначала рассказал - это же почти классическая переведенная в матрицы задача коммивояжера на ориентированном графе? 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 цикл, а у тебя разрешено несколько, лишь бы все города были охвачены
Сумма 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 цикл, а у тебя разрешено несколько, лишь бы все города были охвачены
Re: Задачка
не только несколько, но и пути с пересечениями...
Re: Задачка
В исходной задаче где по 1 единице в каждом столбце или строке - какие еще пересечения?