Групувати найбільш подібні елементи разом - java, алгоритм

У мене є двовимірний масив ints, наприклад:

int [][] board=
{
{23,17,3,29,12,10},
{17,4,11,12,10,19},
{32,33,25,25,28,35},
{27,29,24,25,23,37},
{29,40,34,26,24,39},
{23,37,29,36,31,3}
}

Я не хочу змінювати стовпці цього масивузовсім; однак я хотів би поміняти рядки так, щоб найбільш схожі рядки були згруповані разом. Подібне в даному випадку означає більшість рівних елементів.

Редагувати: Подібні рядки означають, якщо один ряд має 1,2,3,4,5,6, а інший 1,2,3,4,9,10 Вони мають 4 подібності.

Що це найкращий спосіб зробити?

Примітка: найбільша кількість рядків у моєму масиві становить близько 100, а найбільше елементів у кожному рядку буде 10, тому складність має значення як зазначено!

Відповіді:

Це питання зводиться до мандрівного продавцяпроблема. Якщо ви вважаєте, що кожен рядок є містом, а потім визначте деяку функцію відстані, яка обчислює відстань між двома рядками. Питання в тому, як замовити ряди так, щоб відстань було мінімізоване. Ця проблема є NP-Complete і не може бути вирішена в розумний проміжок часу за 100 рядів. Для цього грубого рішення знадобиться обчислення O (N!). Існують евристичні алгоритми (алгоритми, що наближаються до найкращої відповіді), які вирішать це за розумний час.

Проблема продавця подорожей (Вікіпедія)

Один із прикладів - використання жадібного алгоритму. Виберіть навпаки один рядок, це рядок 1. Потім виберіть найближчий рядок до рядка 1 як рядок 2. Потім виберіть найближчий рядок до рядка 2 як рядок 3. Запустіть, поки не будуть обрані всі рядки. Це не дуже оптимальне рішення.

Я "не фахівець з доведення алгоритмів, але буду"зробіть постріл на допомогу. Крім того, я не перевіряв це рішення або не давав йому більше 15 хвилин думки, але, думаю, воно спрацює або принаймні наблизить вас. Пам’ятайте, евристичні алгоритми не на 100% вірні :) Я ризикую бути нижче 3K:

Сортуйте кожен рядок, щоб таблиця, яку ви вставили після сортування, виглядала так:

3,  10, 12, 17, 23, 29
4,  9,  10, 11, 12, 17
25, 25, 28, 32, 33, 35
23, 24, 25, 27, 29, 37
24, 26, 29, 34, 39, 40
3,  23, 29, 31, 36, 37

Тепер сортуйте кожен рядок за значеннями в першому стовпці кожного ряду, тому результат виглядає так:

3,  10, 12, 17, 23, 29
3,  23, 29, 31, 36, 37
4,  9,  10, 11, 12, 17
23, 24, 25, 27, 29, 37
24, 26, 29, 34, 39, 40
25, 25, 28, 32, 33, 35