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

Question

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

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

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

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

Answer 1

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

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

основанный на a²+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: поместить членов отсортированного списка в сетку

Сортировка зависит только от того, как вы более точно определяете свои правила. "Самый быстрый и самый дорогой первый" не работает. Что будет раньше моего "Роллс-Ройса" за 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. Рассчитать текущую погрешность метрики М
   2. Перечислите все пары автомобилей в сетке и рассчитайте метрику неправильного порядка M', которую вы получите, если поменяете местами автомобили.
   3. Поменяйте местами пары машин, которые больше всего уменьшают показатель, если такая пара была найдена
   4. Если вы поменяли две машины, повторите с шага 1
   5. Конец

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

Answer 4

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

Пример:

с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);

Редактировать:

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

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

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

Спасибо

Answer 5

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

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

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

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

Answer 6

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

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

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

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

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

Answer 7

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

Пример:

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

Answer 8

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

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

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

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

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