Алгоритм динамического программирования

Question

Приведена матрица размера NxM из 0 и 1. Если мышь присутствует на [i:j], тогда это будет 1, в противном случае это будет 0. Мы должны начать с [0:0] и достигнуть [n-1:m-1]. Мы можем идти вниз или вправо. Мышь в позиции [i:j] нас пугает, если мы пройдем через позицию [x:y], такую, что |i-x|+|j-y|<=1.

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

Этот вопрос задан в интервью. Я попытался решить эту проблему по идее, используемой в общей проблеме DP, где мы можем двигаться вниз и вправо и находить минимальный путь, но во всех этих проблемах мы можем взять минимум [i-1:j] и [i:j-1], чтобы найти текущий минимальный индекс и сократить все строки слева направо.

Но я не могу использовать эту идею здесь, так как здесь мышь воздействует на 4 ячейки.

Может кто-нибудь дать идею, как это можно решить?

Answer 1

Я думаю, что самый простой (недостаточно эффективный способ) для решения этой проблемы - решить кратчайший путь на графике вершин NxM со следующей функцией стоимости края (i и j - это узлы графа, которые относятся к ячейкам (i ' , J «) и (I»», J„“) в основной матрице):

c(i,j) = 1 if [(i',j') and (i'',j'') are sideByside] && [(i'',j'') is scaring] , 
     0 otherwise 

Answer 2

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

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

   Иллюстрация: (C является текущей ячейкой, L находится слева, S является источником для L)

   0S1 <- this mouse already scared us 
   0LC 
   

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

   Иллюстрация: (C является текущей ячейкой, T является верхней, S является источником для T)

   0ST 
   01C 
   ^- this mouse already scared us 
   

3. При рассмотрении клетки в верхней части, если эта клетка имеет мышь, мы знаем, это уже испугало нас.

   Иллюстрация: (C является текущей ячейкой)

   01 <- this mouse already scared us 
   0C 
   

4. При рассмотрении клетки слева, если клетка имеет мышь, мы знаем, что это уже напугали нас.

   Иллюстрация: (C является текущая ячейка)

   01C 
   ^- this mouse already scared us 
   

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

   Иллюстрация: (1 является текущей ячейкой, L находится слева, T находится на вершину)

   0T 
   L1 <- this mouse already scared us 
   

Выведение алгоритма здесь не должна быть слишком трудно.

Answer 3

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

Сложность создается тем требованием, что если мы пройдем через одну из 5 ячеек в пределах диапазона мыши, тогда нам нужно увеличить шаткий путь, но только один раз.

Этого можно достичь с помощью битового поля шириной N, где N - количество мышей, а i-й бит указывает, запутан ли путь к i-й мыши. Затем DP может использовать побитовое ИЛИ с одним вектором (0,0, ..., 0,1,0, .., 0,0), где 1 находится в i-й позиции для i-й мыши.

Но тогда у вас возникнет проблема с поиском наилучшего частичного пути, потому что нет строгого порядка битных полей с равным весом. В какой-то простой эвристической логике вы узнаете, что вам нужно только разграничить не более чем на 9 ячеек, окружающих мышь. Таким образом, вы можете просто отслеживать набор наилучших частичных путей рядом с ним. Решения, находящиеся рядом с мышью i, являются лучшими решениями, когда вы не боитесь мыши i, и тех, где вы боитесь мыши i. После того, как близость оставлена, различия между ними уже не актуальны.

Answer 4

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

Мы назначаем грузы по краям. Во-первых, все ребра имеют вес 0. Затем рассмотрим мышь в вершине A. Вершина A имеет 4 смежных ребра b, c, d, e, которые соединяют A с вершинами B, C, D, E (случай, когда A имеет только 2 или 3 смежных края аналогичны). Итак, теперь мы увеличиваем вес на 1 для каждого ребра, смежного с вершинами B, C, D, E, кроме ребер b, c, d, e. Теперь вершина A добавляет вес 2 к каждому MINIMAL весовому пути, «испуганному вершиной A». Особое внимание необходимо уделить любому из возможных 4-х угловых мышей, где мы можем увеличить вес ребер на 2.

Теперь у нас есть простейшая проблема DP поиска пути минимального веса в целочисленной решетке с ходом вниз/вправо. Моя забота о мышах, которые разделены только 1 или 2 шагами. Я быстро проверил, и это, похоже, работает, но у меня нет полного доказательства.