Я считаю, что Санни прав в том, что поиск методом грубой силы имеет временную сложность O(4^(m*n)), где n и m — это количество строк и столбцов в матрице, связанной с данным массивом. Я хотел бы предложить алгоритм O(n*m) и код Ruby, который его реализует.
В таких задачах, как эта, существует тенденция рассматривать переход от каждого элемента в матрице ко всем соседним элементам с большим значением (до 4), а затем от каждого из этих элементов ко всем их соседним элементам с большим значением, и и так далее (отсюда O(4^m*n)). Однако, поскольку пути должны увеличиваться, мы можем посмотреть на проблему по-другому, что позволит нам разработать высокоэффективный алгоритм оптимизации.
Предположим, мы сгруппировали все местоположения по значению. Для примера, приведенного в вопросе, это может быть выражено:
value_to_locs
#=> { 9=>[[0, 0], [0, 1]], 4=>[[0, 2]], 6=>[[1, 0], [1, 1]], 8=>[[1, 2]],
# 2=>[[2, 0]], 1=>[[2, 1], [2, 2]]}
Далее рассмотрим значения хеша в порядке убывания:
to_process = value_to_locs.keys.sort.reverse
#=> [9, 8, 6, 4, 2, 1]
Сначала мы обрабатываем два местоположения со значением 9. Длина растущего пути из любого из этих мест явно равна 1 (пути [[0, 0]] и [[1, 0]]), так как идти некуда. Мы сохраняем эту информацию в ранее пустой хэш processed, который теперь выглядит следующим образом:
processed = { [0, 0]=>{ len: 1, next: nil }, [1, 1]=>{ len: 1, next: nil } }
Далее рассмотрим одно местоположение со значением 8 (второй элемент to_process), [1, 2]. Если возрастающий путь из этого местоположения имеет длину больше 1, он должен перейти к одному из элементов processed. [1, 2] не является смежным ни с [0, 0], ни с [1, 1], поэтому мы добавляем пару ключ-значение:
[1, 2]=>{ len: 1, next: nil }
до processed, получив
processed
#=> { [0, 0]=>{ len: 1, next: nil }, [1, 1]=>{ len: 1, next: nil },
# [1, 2]=>{ len: 1, next: nil } }
Следующее значение (в to_process) для проверки — 6, которое встречается в двух местах: [1, 0] и [1, 1]. Первый находится рядом с одним местом в processed ([0, 0]), поэтому мы добавляем к processed пару ключ-значение
[1, 0]=>{ len: 1 + processed[[0, 0]][:len], next: [0, 0] }
#=>{ len: 2, next: [0, 0] }
Другой элемент со значением 6, [1, 1] имеет два соседних элемента в processed, [0, 1] и [1, 2], поэтому добавьте
[1, 1]=>{ len: 1 + processed[[0, 1]][:len], next: [0, 1] }
#=>{ len: 2, next: [0, 1] }
or
[1, 1]=>{ len: 1 + processed[[1, 2]][:len], next: [1, 2] }
#=>{ len: 2, next: [1, 2] }
до processed, а именно тот, для которого значение :len наибольшее. (Здесь ничья, так что можно выбрать любой.)
Продолжаем так до тех пор, пока все элементы исходного массива не станут ключами в processed. Затем мы выбираем в качестве начальной точки самого длинного возрастающего пути местоположение loc, для которого processed[loc][:len] является максимальным, и реконструируем связанный путь.
Обратите внимание, что ключ :next необходим только для восстановления самого длинного пути. Если нужна только длина самого длинного пути, этот ключ не нужен.
Код
def longest_increasing_path(arr)
row_indices, col_indices = 0..arr.size-1, 0..arr.first.size-1
value_to_locs = row_indices.each_with_object(Hash.new { |h,k| h[k] = [] }) { |r,h|
col_indices.each { |c| h[arr[r][c]] << [r,c] } }
processed = {}
value_to_locs.keys.sort.reverse.each do |x|
value_to_locs[x].each do |loc|
next_on_path = greater_neighbors(loc, arr, row_indices, col_indices).
max_by { |nloc| processed[nloc][:len] }
processed[loc] = next_on_path ?
{ len: 1+processed[next_on_path][:len], next: next_on_path } :
{ len: 1, next: nil }
end
end
extract_path(processed)
end
def longest_increasing_path(arr)
row_indices, col_indices = 0..arr.size-1, 0..arr.first.size-1
value_to_locs = row_indices.each_with_object(Hash.new { |h,k| h[k] = [] }) { |r,h|
col_indices.each { |c| h[arr[r][c]] << [r,c] } }
processed = {}
low, high = value_to_locs.keys.minmax
high.downto(low) do |x|
next unless value_to_locs.key?(x)
value_to_locs[x].each do |loc|
next_on_path = greater_neighbors(loc, arr, row_indices, col_indices).
max_by { |nloc| processed[nloc][:len] }
processed[loc] = next_on_path ?
{ len: 1+processed[next_on_path][:len], next: next_on_path } :
{ len: 1, next: nil }
end
end
extract_path(processed)
end
def greater_neighbors((r,c), arr, row_indices, col_indices)
curr_val = arr[r][c]
[[-1,0], [1,0], [0,-1], [0, 1]].each_with_object([]) do |(rdelta, cdelta), a|
ra = r + rdelta
ca = c + cdelta
a << [ra, ca] if row_indices.cover?(ra) && col_indices.cover?(ca) &&
curr_val < arr[ra][ca]
end
end
def extract_path(processed)
loc, g = processed.max_by { |loc,g| g[:len] }
len = g[:len]
path = [loc]
loop do
break if g[:next].nil?
loc = g[:next]
path << loc
g = processed[loc]
end
[len, path]
end
Examples
№1
arr = [
[9,9,4],
[6,6,8],
[2,1,1]
]
longest_increasing_path(arr)
#=> [4, [[2, 1], [2, 0], [1, 0], [0, 0]]]
№2
rows = 10
cols = 10
a = (1..9).to_a
arr = Array.new(rows) { Array.new(cols) { a.sample } }
#=> [[4, 7, 5, 3, 5, 4, 2, 2, 9, 3],
# [8, 3, 3, 5, 4, 2, 8, 1, 8, 3],
# [7, 1, 9, 4, 2, 7, 1, 4, 4, 6],
# [3, 7, 5, 5, 2, 3, 9, 1, 9, 7],
# [2, 6, 7, 1, 5, 9, 3, 5, 2, 9],
# [4, 4, 6, 7, 8, 4, 9, 7, 6, 1],
# [9, 7, 5, 4, 6, 8, 8, 4, 4, 8],
# [3, 1, 9, 9, 5, 7, 9, 6, 7, 2],
# [5, 6, 4, 8, 2, 3, 4, 3, 3, 9],
# [7, 9, 6, 9, 5, 2, 9, 7, 6, 3]]
require 'time'
t = Time.now
longest_increasing_path(arr)
#=> [5, [[6, 3], [6, 2], [5, 2], [5, 3], [5, 4]]]
Time.now - t
#=> 0.003606 seconds
Таким образом, самый длинный путь имеет длину 5 и содержит элементы 4, [6, 3], затем слева до 5, до 6, справа до 7, справа до 8.
#3
rows = 100
cols = 200
a = (1..20).to_a
arr = Array.new(rows) { Array.new(cols) { a.sample } }
t = Time.now
len, path = longest_increasing_path(arr)
#=> [12, [[86, 121], [86, 120], [86, 119], [87, 119], [87, 118], [86, 118],
# [85, 118], [85, 117], [86, 117], [87, 117], [88, 117], [89, 117]]]
Time.now - t
#=> 0.153562 seconds
path.map { |r,c| arr[r][c] }
#=> [1, 2, 3, 5, 7, 8, 9, 10, 11, 13, 19, 20]
Пояснение
Сначала рассмотрим вспомогательный метод greater_neighbors для примера №1. Для arr, как показано,
row_indices = 0..arr.size-1
#=> 0..2
col_indices = 0..arr.first.size-1
#=> 0..2
Затем (думая о arr как о матрице) мы группируем местоположения с одинаковым значением:
value_to_locs = row_indices.each_with_object(Hash.new { |h,k| h[k] = [] }) { |r,h|
col_indices.each { |c| h[arr[r][c]] << [r,c] } }
#=> {9=>[[0, 0], [0, 1]], 4=>[[0, 2]], 6=>[[1, 0], [1, 1]],
# 8=>[[1, 2]], 2=>[[2, 0]], 1=>[[2, 1], [2, 2]]}
processed = {}
Этот хэш будет содержать проверенные местоположения.
low, high = value_to_locs.keys.minmax
#=> [1, 9]
Это обеспечивает порядок, в котором обрабатываются местоположения с заданными значениями, от high до low.
enum0 = high.downto(low)
#=> #<Enumerator: 9:downto(1)>
Генерируется первый элемент enum0 и передается в блок:
x = enum0.next
#=> 9
а также
value_to_locs.key?(x)
#=> true
выполняется, поэтому мы не выполняем next.
Теперь мы рассматриваем все местоположения со значением 9, затем со значением 8 и так далее.
После того, как 9 сгенерировано и передано в блок, а next не выполнено, выполняется следующий расчет:
b = value_to_locs[x]
#=> [[0, 0], [0, 1]]
enum1 = b.each
#=> #<Enumerator: [[0, 0], [0, 1]]:each>
loc = enum1.next
#=> [0, 0]
c = greater_neighbors(loc, arr, row_indices, col_indices)
#=> []
Метод greater_neighbors просто создает массив всех местоположений, смежных с loc, значения которых больше, чем значение в loc.
next_on_path = c.max_by { |nloc| processed[nloc][:len] }
#=> nil
processed[loc] = next_on_path ?
{ len: 1+processed[next_on_path][:len], next: next_on_path } :
{ len: 1, next: nil }
#=> {:len=>1, :next=>nil}
processed
#=> {[0, 0]=>{:len=>1, :next=>nil}}
Теперь мы генерируем следующий и последний элемент enum1 и передаем его в блок:
loc = enum1.next
#=> [0, 1]
Расчеты для этого местоположения аналогичны расчетам для [0, 0], в результате чего:
processed
#=> {[0, 0]=>{:len=>1, :next=>nil}, [0, 1]=>{:len=>1, :next=>nil}}
Мы достигли последнего элемента enum1, поэтому выполняем следующее:
x = enum0.next
#=> 8
value_to_locs.key?(x)
#=> true # so next is not executed
b = value_to_locs[x]
#=> [[1, 2]]
enum1 = b.each
#=> #<Enumerator: [[1, 2]]:each>
loc = enum1.next
#=> [1, 2]
c = greater_neighbors(loc, arr, row_indices, col_indices)
#=> []
Опять же, деваться из этой локации некуда, поэтому получаем:
processed
#=> {[0, 0]=>{:len=>1, :next=>nil}, [0, 1]=>{:len=>1, :next=>nil},
# [1, 2]=>{:len=>1, :next=>nil}}
Продолжая,
x = enum0.next
#=> 7
value_to_locs.key?(x)
#=> false # so next is executed
x = enum0.next
#=> 6
value_to_locs.key?(x)
#=> true # so next is executed
b = value_to_locs[x]
#=> [[1, 0], [1, 1]]
enum1 = b.each
#=> #<Enumerator: [[1, 0], [1, 1]]:each>
loc = enum1.next
#=> [1, 0]
c = greater_neighbors(loc, arr, row_indices, col_indices)
#=> [[0, 0]]
next_on_path = c.max_by { |nloc| processed[nloc][:len] }
#=> [0, 0]
processed[loc] = next_on_path ?
{ len: 1+processed[next_on_path][:len], next: next_on_path } :
{ len: 1, next: nil }
#=> {:len=>2, :next=>[0, 0]}
processed
#=> {[0, 0]=>{:len=>1, :next=>nil}, [0, 1]=>{:len=>1, :next=>nil},
# [1, 2]=>{:len=>1, :next=>nil}, [1, 0]=>{:len=>2, :next=>[0, 0]}}
Наконец, мы подошли к локации ([1, 0]), которая находится рядом с локацией с более высоким значением ([0, 0]).
Вычисления продолжаются таким образом, пока не получим:
processed
#=> {[0, 0]=>{:len=>1, :next=>nil}, [0, 1]=>{:len=>1, :next=>nil},
# [1, 2]=>{:len=>1, :next=>nil}, [1, 0]=>{:len=>2, :next=>[0, 0]},
# [1, 1]=>{:len=>2, :next=>[0, 1]}, [0, 2]=>{:len=>2, :next=>[1, 2]},
# [2, 0]=>{:len=>3, :next=>[1, 0]}, [2, 1]=>{:len=>4, :next=>[2, 0]},
# [2, 2]=>{:len=>2, :next=>[1, 2]}}
Остается только найти пару ключ-значение k=>v, для которой v[:len] является максимальным, а затем извлечь самый длинный путь. Это делает помощник extract, который, как и greater_neighbors, прост.
person
Cary Swoveland
schedule
27.02.2017
