Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: -1
Последний выпуск: 19.06.2015

Алгоритм нахождения комбинации с максимальной суммой

13K
01 апреля 2010 года
Jawello
11 / / 11.04.2008
возник вопрос.
на входе имеем следующее : массив (вернее его половина до главной диагонали) , в каждом поле, которого записано число. число представляет собой связь между "индексами" массива.
нужно:составить 10ть максимальных комбинаций. каждая комбинация -последовательность величиной размерности массива и содержит в себе все, не повторяющиеся индексы.
пояснение:
__0 1 2 3 4
0|_|_|_|_|_|
1|3|_|_|_|_|
2|5|4|_|_|_|
3|6|7|8|_|_|
4|3|9|2|1|_|

к примеру у нас есть матрица размерностью 5*5. необходимо найти десять максимальных комбинаций. комбинация имеет следующий вид: 0,1,2,3,4 (или 4,3,0,1), т.е. все комбинации различаются только порядком следованием цифр. к примеру сумма связи 0,1,2,3,4 =3+4+8+1=16. связь 0-1 расположена по [1][0] и равна 3, 1-2 [2][1]=4 и т.д.
размерность массива зависит от пользователя. вторую половину при необходимости можно заполнить теме же цифрами.

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

пытался получать комбинацию с помощью рекурсии, но комбинация получается поэтапно и ее нужно все время записывать в массив, и запись происходить до проверки не меньше ли новая комбинация уже находящихся в массиве, а создавать массив 5* (5!) для этой матрицы не хотелось бы. ведь для матриц больших размерностей получим еще более огромные массивы.

за ранее спасибо.
43K
02 апреля 2010 года
loki231
76 / / 27.09.2009
Метод полного перебора можно реализовать с минимальными затратами памяти.

Зачем хранить все сгенерированные пути? А речь, как я понял, идёт о полных путях в графе с максимальным весом. Хранить нужно только 10 лучших путей. Сгенерировал цепочку, сравнил её вес с весом минимального элемента в результирующем множестве цепочек. Если вес новой цепочки больше - заменяем минимальный элемент новой цепочкой и все дела.
13K
06 апреля 2010 года
Jawello
11 / / 11.04.2008
спасибо, за ответ.
я согласен. я так же решил поступить, только не просто смотреть по последнему элементу, а находить сразу место среди этих 10ти вариантов, которое соотвествует новой цепочке (варианты цепочек расположенны в массиве в порядке возрастания) и вставлять его туда, а последний элемент (минимальный) "вытеснять" из массива.

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

тема закрыта.
43K
07 апреля 2010 года
loki231
76 / / 27.09.2009
Ну если очень прижмёт, то можно сократить множество просматриваемых цепочек следующем способом -- Для каждой из вершин, ещё не включенных в конструируемую цепочку, выбрать инцидентное ребро с максимальным весом. Полученные веса сложить с весом уже построенной чести цепочки. Это будет верхняя граница возможного веса полной цепочки, т.е. максимально возможный вес всех цепочек с началом, совпадающем с уже сформированной цепочкой. Если полученное значение веса не попадает в 10-ку лучших, то всё это множество цепочек можно отбросить.

Знаете кого-то, кто может ответить? Поделитесь с ним ссылкой.

Ваш ответ

Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог