Что такое обозначение big-O для этого алгоритма?

В настоящее время я пытаюсь понять динамическое программирование, и у меня возникла интересная проблема: «Учитывая шахматную доску из квадратов nxn и начальную позицию (xs, ys), найдите кратчайший (как и в случае движений) путь a рыцарь может перейти в конечное положение (xe, ye) ». Это как мое решение будет звучать как:Что такое обозначение big-O для этого алгоритма?

Initialize the matrix representing the chess board (except the "square" xs,ys) with infinity. 
The first value in a queue is the square xs,ys. 
while(the queue is not empty){ 
     all the squares available from the first square of the queue (respecting the rules of chess) get "refreshed" 
     if (i modified the distance value for a "square") 
        add the recently modified square to the queue 
}

Может кто-то пожалуйста, помогите мне узнать, что значение вычисления времени O для этой функции? Я (вроде) понимаю big-O, но я просто не могу поместить значение для этой конкретной функции.

источник

2012-02-17 Patrunjel

Я не вижу, как это работает. «все квадраты, доступные с первого квадрата», применимы только к первой итерации. Что вы делаете на второй итерации - произвольно выбираете 1 квадрат из своей очереди, из которого следует пересчитывать расстояния, или использовать структуру ветвящихся данных для раздельного разветвления и измерения расстояний от каждого квадрата в очереди? – mbeckish

Прошу прощения, я не очень хорошо себя проявил, я имел в виду первый квадрат очереди (как в обычной очереди). – Patrunjel

Вам не хватает логики о не «освежающих» квадратах с более низким значением, чем текущее значение? – mbeckish

Поскольку вы используете очередь, порядок обработки квадратов будет в порядке минимального расстояния. Это означает, что вы только когда-либо измените значение расстояния для квадрата один раз, и поэтому время будет O (n^2), так как существует n^2 квадратов.

источник

2012-02-17 21:27:39

Я думал, что я буду изменять квадрат только один раз (сначала мне хотелось просто проверить, содержит ли очередь n^2 сущности, в статической выделенной очереди это действительно эффективна по времени), но затем я сделал несколько примеров на бумаге и выяснил, что вы не получаете общее оптимальное значение, потому что времена, когда мелкомасштабное «оптимальное» значение не является оптимальным, поэтому, когда вы их добавляете, вы также не получаете общее оптимальное значение. – Patrunjel

Первым пунктом в вашей очереди будет начальная позиция с нулевым расстоянием. Затем вы добавите все позиции на расстоянии одного. Вы обработаете каждый из них, и в конце вы добавите все позиции с расстоянием до двух и т. Д. –

Звучит несколько как алгоритм кратчайшего пути Дейкстры. В этом случае это O (N^2), вы находите «расстояние» для всех возможных путей от источника к месту назначения, чтобы определить самый низкий.

источник

2012-02-17 21:30:15 akhisp

Это можно представить как Дейкстра, но это имеет O (n^2), поэтому мой интерес к сложность алгоритма (хотя невозможно быть меньше n^2 ...). – Patrunjel

Ваш алгоритм сформулирован плохо

Вы не определяете содержимое вашей «очереди»

вы не определяют «обновилась»

вы всегда застрял на первой площади , вы не отслеживаете текущий квадрат.

~~также, алгоритм Google Djkistra~~ Нет, не выполняйте алгоритм dijkstra. у вас нет взвешенного графика.

Если вы хотите использовать динамический алгоритм программирования для перебора своего пути к ответу, я бы начал с (xe, ye), и вы должны получить O (n^2) в сетке nxn

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

источник

2012-02-17 21:30:50

В списке содержится информация о квадратах (координаты x, y), средство обновления выбирает минимальное значение из двух параметров, которые у меня есть. Я знаком с алгоритмом Дейкстры, но эта проблема находится в главе «Динамическое программирование» в книге проблем. А также, честно говоря, Дейкстра будет проще, но я считаю, что хорошей практикой является не превращать действие решения проблем в алгоритм. Это помогает вам не укорениться в определенном мышлении. – Patrunjel

Прежде всего, динамическое программирование не означает, что вы перенаправляете свой ответ. 2^n - грубая сила, n^2 - легкий ветер. Во-вторых, D.P. подразумевает, что вы вычисляете локальное оптимальное решение и используете его дальше, пока не получите общее оптимальное решение. Поэтому мне пришлось бы пройти через все квадраты, так что вы буквально не сможете получить решение (используя DP) более эффективно, чем O (n^2). И если бы я использовал графики, я мог бы просто составить график, в котором смежность узла с другим означает, что вы можете перейти на этот квадрат, и я мог бы просто BF от начала до конца и выводить стоимость. – Patrunjel

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

эта по моему мнению, является первым поиском. Понятно, что вы добавляете квадрат не более одного раза в очередь, а обработка записи в очереди - O (1), поэтому общая сложность ограничена O (N^2). Однако, если вы можете доказать теорему, в которой указано количество ходов, которые нужно получить от позиции A до B на шахматной доске NxN, меньше, чем N (и это, по-видимому, разумно, если N равно или больше 8), тогда ваш алгоритм будет НА).

источник

2012-02-17 22:21:29 Bogdan

Не могли бы вы подробно рассказать, как доказать, что вы сказали, опустить мой O() на n? – Patrunjel

Ну, я ошибался, даже если такая теорема может быть доказана, ваш исходный алгоритм имеет худшую сложность O (N^2). Может быть ситуация, когда конечная позиция является последней, которая добавляется в очередь, поэтому вы должны проверить в конце все квадраты таблицы. – Bogdan

Лучшее, что я могу представить в этот момент, - это жадная эвристика, в которой вы выбираете следующий шаг, чтобы быть ближайшим (с использованием Манхэттенского расстояния) до целевого положения, пока расстояние не станет ниже 3. Затем вы запустите локальный поиск, чтобы добраться до целевое положение. Это не гарантирует, что вы дадите кратчайший путь, но это будет O (N) время и длина. – Bogdan

Что такое обозначение big-O для этого алгоритма?

ответ

Смежные вопросы