Алгоритм нахождения комбинации с максимальной суммой
возник вопрос.
на входе имеем следующее : массив (вернее его половина до главной диагонали) , в каждом поле, которого записано число. число представляет собой связь между "индексами" массива.
нужно:составить 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!) для этой матрицы не хотелось бы. ведь для матриц больших размерностей получим еще более огромные массивы.
за ранее спасибо.
на входе имеем следующее : массив (вернее его половина до главной диагонали) , в каждом поле, которого записано число. число представляет собой связь между "индексами" массива.
нужно:составить 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!) для этой матрицы не хотелось бы. ведь для матриц больших размерностей получим еще более огромные массивы.
за ранее спасибо.
Метод полного перебора можно реализовать с минимальными затратами памяти.
Зачем хранить все сгенерированные пути? А речь, как я понял, идёт о полных путях в графе с максимальным весом. Хранить нужно только 10 лучших путей. Сгенерировал цепочку, сравнил её вес с весом минимального элемента в результирующем множестве цепочек. Если вес новой цепочки больше - заменяем минимальный элемент новой цепочкой и все дела.
Зачем хранить все сгенерированные пути? А речь, как я понял, идёт о полных путях в графе с максимальным весом. Хранить нужно только 10 лучших путей. Сгенерировал цепочку, сравнил её вес с весом минимального элемента в результирующем множестве цепочек. Если вес новой цепочки больше - заменяем минимальный элемент новой цепочкой и все дела.
спасибо, за ответ.
я согласен. я так же решил поступить, только не просто смотреть по последнему элементу, а находить сразу место среди этих 10ти вариантов, которое соотвествует новой цепочке (варианты цепочек расположенны в массиве в порядке возрастания) и вставлять его туда, а последний элемент (минимальный) "вытеснять" из массива.
ну собственно, сейчас я и реализвал все с помощью метода полного перебора, минуя вышеупомянутую матрицу. просто получаю новую комбинацию, считаю ее вес и при необходимости добавляю в массив содержащий в себе лучшие комбинации. меня, просто интересовало, нет ли другого метода, не метода полного перебора, с помощью которого, можно получить не только максимальную комбинацию, но следующие по старшенству за ней. все таки так называемые жадные методы, и методы поиска в ширину гораздо быстрее полного перебора. но в конкретном случае, метод поиска в ширину не подойдет, а жадный метод не факт,что найдет комбинацию с максимальным весом. да и к тому же оба этих метода обеспечивают нахождение только 1ой максимальной комбинации. видимо тут можно применить только полный перебор)
тема закрыта.
я согласен. я так же решил поступить, только не просто смотреть по последнему элементу, а находить сразу место среди этих 10ти вариантов, которое соотвествует новой цепочке (варианты цепочек расположенны в массиве в порядке возрастания) и вставлять его туда, а последний элемент (минимальный) "вытеснять" из массива.
ну собственно, сейчас я и реализвал все с помощью метода полного перебора, минуя вышеупомянутую матрицу. просто получаю новую комбинацию, считаю ее вес и при необходимости добавляю в массив содержащий в себе лучшие комбинации. меня, просто интересовало, нет ли другого метода, не метода полного перебора, с помощью которого, можно получить не только максимальную комбинацию, но следующие по старшенству за ней. все таки так называемые жадные методы, и методы поиска в ширину гораздо быстрее полного перебора. но в конкретном случае, метод поиска в ширину не подойдет, а жадный метод не факт,что найдет комбинацию с максимальным весом. да и к тому же оба этих метода обеспечивают нахождение только 1ой максимальной комбинации. видимо тут можно применить только полный перебор)
тема закрыта.
Ну если очень прижмёт, то можно сократить множество просматриваемых цепочек следующем способом -- Для каждой из вершин, ещё не включенных в конструируемую цепочку, выбрать инцидентное ребро с максимальным весом. Полученные веса сложить с весом уже построенной чести цепочки. Это будет верхняя граница возможного веса полной цепочки, т.е. максимально возможный вес всех цепочек с началом, совпадающем с уже сформированной цепочкой. Если полученное значение веса не попадает в 10-ку лучших, то всё это множество цепочек можно отбросить.