Как можно отсортировать сетку 10 x 10 из 100 изображений автомобилей в двух измерениях по цене и скорости?

Question

Вот сценарий.

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

Какой алгоритм сортировки мне нужно использовать для этого, и есть ли у вас какие-либо советы?

РЕДАКТИРОВАТЬ: результаты не должны быть точными - на самом деле я имею в видус гораздо большей сеткой, поэтому было бы достаточно, если бы автомобили были сгруппированы примерно в нужном месте.

Answer 1

Просто идея, вдохновленная Мистером Кантором :

• рассчитать макс (скорость) и макс (цена)
• нормализует все данные о скорости и цене в диапазоне 0..1
• для каждого автомобиля, рассчитать «расстояние» до возможного максимума

на основе ² + b² = c², расстояние может быть что-то вроде

sqrt( (speed(car[i])/maxspeed)^2 + (price(car[i])/maxprice)^2 )

применять взвешивание по мере необходимости (визуально)

• сортировка авто по расстоянию
• поместите «лучший» автомобиль в «лучший» квадрат (справа вверху в вашем случае)
• пройтись по сетке зигзагом и заполнить следующий автомобиль в отсортированном списке

Результат (зеркальный, верхний левый - лучший):

1 - 2   6 - 7
  /   /   /
3   5   8
| /
4

Answer 2

Рассматривайте это как две проблемы:

1: создать отсортированный список 2: Поместить членов отсортированного списка в сетку

Сортировка зависит только от того, как вы более точно определяете свои правила. «Самый быстрый и самый дорогой первый» не работает. Который стоит первым, мой Rolls Royce за 100 000 фунтов стерлингов, максимальная скорость 120 или мой мини-автомобиль стоимостью 50 000 фунтов стерлингов, максимальная скорость 180?

Получив свой список, как вы будете его заполнять? Первое и последнее легко, но куда идет номер два? Вдоль вершины или вниз? Тогда где дальше, вдоль рядов, вдоль колонн, зигзагообразно? Вы должны решить. После этого кодирование должно быть легким.

Answer 3

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

Я бы попробовал следующий подход. Предположим, у вас есть N машин, и вы хотите поместить их в сетку X * Y. Предположим, N == X * Y.

1. Поместите все N машин в сетку в случайных местах.
2. Определить метрику, которая вычисляет общее искажение в сетке; например, подсчитать количество пар автомобилей C1 = (x, y) и C2 = (x ', y'), чтобы C1.speed> C2.speed, но y C2.price, но x
3. Запустите следующий алгоритм:
   1. Рассчитать текущую метрику неупорядоченности M
   2. Перечислите по всем парам автомобилей в сетке и рассчитайте метрику неправильного порядка M ', которую вы получите, если поменяете местами автомобили
   3. Поменяйте местами пары автомобилей, которые больше всего уменьшают показатель, если такая пара была найдена
   4. Если вы поменяли две машины, повторите с шага 1
   5. Конец

Это стандартный подход локального поиска к задаче оптимизации. То, что у вас здесь есть, в основном простая комбинаторная задача оптимизации. Другим подходом, который можно попробовать, может быть использование самоорганизующейся карты (SOM) с заданным градиентом скорости и стоимости в матрице.

Answer 4

Требуется ли ограничение 10х10? Если это так, у вас должно быть десять скоростей и десять цен, иначе диаграмма не будет иметь особого смысла. Например, что произойдет, если самый быстрый автомобиль не самый дорогой?

Я бы рекомендовал вам сделать размер сетки равным

  (number of distinct speeds) x (number of distinct prices), 

тогда это будет (довольно) простой случай упорядочения по двум осям.

Answer 5

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

Пример:

с1 (20,1000) с2 (30,5000) с3 (20, 500) с4 (10, 3000) с5 (35, 1000)

Предположим, что Car (скорость, цена) является показателем в приведенном выше списке, а основным является скорость.

1 Получить машину с минимальной скоростью

2 Тогда получите все машины с одинаковым значением скорости

3 Упорядочить эти значения в порядке возрастания цены автомобиля

4 Получите следующий автомобиль со следующим минимальным значением скорости и повторите описанный выше процесс

с4 (10, 3000)
с3 (20, 500)
с1 (20, 1000)
с2 (30, 5000)
с5 (35, 1000)

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

cars.OrderBy(x => x.Speed).ThenBy(p => p.Price);

Edit:

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

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

Таким образом, в каждом ряду машины будут иметь одинаковую скорость, показанную в сетке.

Спасибо

Answer 6

Хммм ... вид пузырьковой сортировки может быть простым алгоритмом.

1. Создайте случайный массив 10х10.
2. Найдите двух соседей (горизонтальных или вертикальных), которые находятся в «неправильном порядке», и обменяйте их.
3. Повторяйте (2), пока таких соседей не будет найдено.

Два соседних элемента находятся в «неправильном порядке», когда: а) они горизонтальные соседи и левый медленнее правого, б) они вертикальные соседи, а верхний дешевле нижнего.

Но на самом деле я не уверен, останавливается ли этот алгоритм для всех данных. Я почти уверен, что это очень медленно :-). Это должно быть легко реализовать, и после некоторого конечного числа итераций частичный результат может быть достаточно хорошим для ваших целей. Вы также можете начать с создания массива, используя один из других методов, упомянутых здесь. Также он будет поддерживать ваше состояние в форме массива.

Редактировать: Здесь уже слишком поздно что-либо доказывать, но я провел несколько экспериментов на python. Похоже, что случайный массив 100x100 может быть отсортирован таким образом за несколько секунд, и мне всегда удавалось получить полный 2-й порядок (то есть: в конце я получил неправильно упорядоченных соседей). Предполагая, что ОП может предварительно рассчитать этот массив, он может поместить любое разумное количество автомобилей в массив и получить разумные результаты. Экспериментальный код: http://pastebin.com/f2bae9a79 (вам нужен matplotlib, и я тоже рекомендую ipython). iterchange это метод сортировки там.

Answer 7

Другой вариант - применить оценку 0 .. 200% к каждой машине и отсортировать по этой оценке.

Пример:

score_i = speed_percent(min_speed, max_speed, speed_i) + price_percent(min_price, max_price, price_i)

Answer 8

Если данные происходят из базы данных, вы должны упорядочить их при извлечении из базы данных. Это должно означать только добавление ORDER BY speed, price в конце вашего запроса, но перед частью LIMIT (где «скорость» и «цена» - это имена соответствующих полей).

Как уже говорили другие, «самый быстрый и самый дорогой» - это трудная вещь, вам нужно просто выбрать одну для сортировки первой. Однако было бы возможно сделать приближение, используя этот алгоритм:

1. Найдите самую высокую цену и самую быструю скорость.
2. Нормализовать все цены и скорости, например. дробь из 1. Вы делаете это путем деления цены на самую высокую цену, найденную на шаге 1.
3. Умножьте нормализованную цену и скорость вместе, чтобы создать одно число "цена и скорость".
4. Сортировать по этому номеру.

Это гарантирует, что автомобиль A быстрее и дороже, чем автомобиль B, и он будет включен в список. Автомобили, где одно значение выше, а другое ниже, грубо сортируются. Я бы порекомендовал хранить эти значения в базе данных и сортировать по вашему выбору.

Поместить их в сетку 10х10 легко. Начните выводить элементы, а когда вы наберете кратное 10, начните новую строку.