Вопрос по algorithm, graph, nodes – Какой тип алгоритма я должен использовать?

7

Допустим, у меня есть четыре группы

A [ 0, 4, 9]

B [ 2, 6, 11]

C [ 3, 8, 13]

D [ 7, 12 ]

Теперь мне нужно одно число из каждой группы (т. Е. Новой группы) E [число A, число B, число C, число D], чтобы разница между максимальным числом в E и минимальным числом в E была возможно самое низкое. Какой тип проблемы это? Какой алгоритм графа будет лучше для решения этой проблемы? Заранее спасибо.

П.С .: Я пытаюсь решить эту проблему в Java и извините за неуказанный заголовок.

Редактировать : Наконец, я нашел то, что на самом деле ищуhttp://rcrezende.blogspot.in/2010/08/smallest-relevant-text-snippet-for.html

@RedhopIT Рассмотрим A [0, 10000] B [100, 9999] C [200, 9998] D [300, 9997]. Взятие минимума каждой группы не сработает в этом случае. irrelephant
@ База не домашняя работа, я нахожусь в середине проекта, где у меня такая ситуация. user1624525
@Pigueiras: вопросы об алгоритмах находятся в теме для переполнения стека David Robinson
Не знаю, сработает ли это, но у вас есть indexA, indexB, ... C и ... D. Сформируйте группу E со значениями в A [indexA], .... Хотя разница в группе E больше 3, увеличьте индекс, который относится к наименьшему значению. Проверьте разницу группы E на каждом этапе цикла. Edit, я думаю, это не сработает, если у групп нет уникальных значений. знак равно irrelephant
Это домашнее задание? Если это так, пожалуйста, добавьте тег. Baz

Ваш Ответ

2   ответа
4
  1. Combine contents of every group into a single array. Each element of the array should be a pair of (number, group name).
  2. Sort this array by numbers.
  3. Advance two iterators, one after another. Move first iterator when elements of not every group are between these iterators. Move second iterator when there is an element of each group between these iterators. For details see this question.
  4. Minimum distance between iterators determine optimal resulting group (you only need to drop unneeded elements when there are several representatives of the same group there).

Другой алгоритм:

  1. Sort elements of each group (if not sorted already).
  2. Put a pair (number, group name) for smallest elements of each group into priority queue (min-heap, priority=number).
  3. Remove smallest element from the queue and replace it with the next element from the same group.
  4. Repeat step 3 until no more elements are left in some group. Calculate max(queue) - min(queue) for each iteration and if it is smaller than any previous value, update the best-so-far resulting group.
Проблема действительно отображаема (группа - это аналогия разных символов в алфавите, число - это более или менее аналогия с позицией символа в тексте). +1
2

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

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

  • For each element of A: call it a, you are looking for a numbers which are close to interval (a,a)
  • Now for each group pick the closest numbers (you can do it with binary search). Now you have a new search interval, either (a,b1) or (b2,a)

Пример:

  • Pick 4 from A, searching close to (4,4)
  • A) Pick 2 from B, searching close to (2,4)
  • .... Pick 3 from C, it's in the interval. searching close to (2,4)
  • .... Pick 7 from D, interval is (2,7), distance is 5.
  • B) Pick 6 from B, searching close to (4,6)
  • ....

Похожие вопросы