Как вы оцениваете эффективность алгоритма, если проблемное пространство не указано?

Question

Недавно здесь был пост, в котором был задан следующий вопрос:

У вас есть двумерная плоскость (X, Y) координат. Куча случайных точек выбраны. Вам необходимо выбрать максимально возможный набор выбранных точек, чтобы две точки не разделяли координату X, а две точки не разделяли координату Y.

Это все предоставленная информация.

Было представлено два возможных решения.

Один из них предложил использовать алгоритм максимального потока, чтобы каждая выбранная точка отображалась на связывание пути ( источник → X → Y → сток ). Это выполняется за время O (V ³ ), где V - количество выбранных вершин.

Другой (мой) предложил использовать венгерский алгоритм. Создайте матрицу n × n, равную 1 с, затем установите каждую выбранную координату (x, y) на 0. Венгерский алгоритм даст вам самую низкую стоимость для этой матрицы, а ответом будет число выбранных координат, равное 0. Это выполняется за время O (n ³ ), где n - большее из числа строк или столбцов.

Я рассуждаю так: в подавляющем большинстве случаев венгерский алгоритм будет работать быстрее; V равно n в случае, когда есть одна выбранная точка для каждой строки или столбца, и существенно больше для любого случая, где есть нечто большее: учитывая матрицу 50 × 50 с половина выбранных координат V равна 1250, а n равна 50.

Контраргумент состоит в том, что есть некоторые случаи, например, матрица 10 ⁹ × 10 ⁹ с выбранными только двумя точками, где V равно 2 и n - 1 000 000 000. В этом случае венгерскому алгоритму требуется смехотворно много времени для запуска, в то время как алгоритм максимального потока работает быстро.

Вот вопрос: Учитывая, что проблема не дает никакой информации относительно размера матрицы или вероятности того, что данная точка выбрана (поэтому вы не можете точно знать), как Вы решаете, какой алгоритм, вообще, является лучшим выбором для проблемы?

Answer 1

Нельзя, это невесомо.

Вы можете определить, что лучше "в целом", определив, какие входные данные вы увидите "в целом". Так, например, вы можете создать вероятностную модель входных данных, чтобы ожидаемое значение V было функцией n, и выбрать значение с наилучшим ожидаемым временем выполнения для этой модели. Но при построении вашей модели могут быть сделаны произвольные выборы, поэтому разные модели дают разные ответы. Одна модель может выбирать координаты случайным образом, другая модель может смотреть на фактический вариант использования какой-либо программы, о которой вы собираетесь писать, и смотреть на распределение входных данных, с которыми она столкнется.

В качестве альтернативы вы можете поговорить о том, какой из них имеет наилучший наихудший случай (среди всех возможных входных данных с заданными ограничениями), который обладает простотой определения и недостатком в том, что вам не гарантировано ничего о производительности актуальная программа. Так, например, HeapSort быстрее, чем QuickSort в худшем случае, но медленнее в среднем случае. Что быстрее? Зависит от того, заботитесь ли вы о среднем или худшем случае. Если вам все равно, в каком случае вы не можете заботиться о том, что «быстрее».

Это аналогично попытке ответить на вопрос «какова вероятность того, что следующий человек, которого вы увидите, будет иметь среднее (среднее) количество ног?».

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

Или мы можем предположить, что ваша следующая встреча с другим человеком выбирается случайным образом с равномерным распределением из набора всех встреч между двумя людьми, и в этом случае ответ по-прежнему «чуть меньше одного», но я считаю, что не точное та же ценность, что и у первых - люди с одноногими ногами вполне могут собираться с «себе подобными», немного больше, чем можно предположить по их частоте среди населения. Или, возможно, они собираются меньше, я действительно не знаю, я просто не понимаю, почему это должно быть точно так же, как только вы принимаете во внимание Ассоциации ветеранов и так далее.

Или мы могли бы использовать знания о вас - если вы живете с одноногим человеком, тогда ответ может быть «немного выше 0».

Какой из трех ответов является «правильным», зависит именно от контекста, о котором вы запрещаете нам говорить. Поэтому мы не можем говорить о том, что является правильным.

Answer 2

Это правильный вопрос, но нет «правильного» ответа - они несопоставимы, поэтому нет понятия «лучше».

Если ваш интерес практичен, тогда вам нужно проанализировать видывходные данные, которые могут возникнуть на практике, а также практическое время работы (включая константы) двух алгоритмов.

Если ваш интерес теоретический, где анализ наихудшего случая часто является нормой, то вВ терминах размера ввода алгоритм O (V ³ ) лучше: вы знаете, что V ≤ n ² , но вы не можете полиномиально связать n в терминах V, как вы показалисам.Конечно, теоретически лучшим алгоритмом является гибридный алгоритм, который запускает оба и останавливается, когда один из них заканчивается первым, таким образом, его время выполнения будет O (мин (V ³ , n ³⁾)).

Answer 3

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

Многие алгоритмы требуют огромных объемов памяти сверх физического максимума машины, и в этих случаях выбирается алгоритмически более неэффективный во времени, но эффективный в пространстве алгоритм.

Учитывая, чтораспределенные параллельные вычисления, я говорю, что вы просто позволяете обеим лошадям бежать и результаты говорят сами за себя.

Answer 4

Учитывая, что вы не знаете, что делает каждая таблетка, принимаете ли вы красную таблетку или голубую таблетку?

Если на самом деле недостаточно информации для принятия решения, недостаточно информации для принятия решения.Любое предположение так же хорошо, как и любое другое.

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

Answer 5

Теоретически, они оба одинаковы, потому что вы фактически сравниваете, как увеличивается количество операций, когда размер задачи увеличивается до бесконечности.

Способ определения вашей проблемы, он имеет 2 размера - n и количество точек, поэтому на этот вопрос нет ответа.