2016-09-24 19 views
2

私はあなたがアップダウン右左斜め、どの方向に行くことができthis->最長のサブシーケンスが

1 6 2 
8 3 7 
4 9 5 

のような行列があり、最長のサブシーケンスを見つける必要があり、あなたが選択することができますその絶対差が3より大きいような順序で次の番号を割り当てる。

上記の場合と同様に、最長サブシーケンスは1->6->2->7->3->8->4->9->5である。

私は最初の番号や2番目の番号などの最長シーケンスを見つけるような最長のシーケンスを見つけるためのブルートフォースコードを書くことができます。そして、最大のカウントを持つものを返します。

私はDPを初めて使用しています。 DPを使ってこれを解決する他の方法はありますか?私はDPを使って解決策を理解することができません。

+0

この問題は[NP-hardと思われる](https://en.wikipedia.org/wiki/Longest_path_problem)です。 –

答えて

3

Nを行数とし、Mを列数とします。

あなたが状態で、動的プログラミングアプローチを試すことができます。 dp(int row_idx, int col_idx, int visited_msk)visited_msk(すなわちmatrix[i][j]ためvisited_mskでIDがあなたのDPインサイドi*M + j

になり、今まで訪問した細胞を表す整数であり、あなたは意志隣接する8つのセル(境界内にある場合)を繰り返し、絶対差が3より大きく、次のようにセルが訪問されない場合にのみ現在のセルからDPを呼び出します。

マスクはnew_idx = new_row_idx * M + new_col_idxです内部ループで、次いで条件はこのようなものであろう:

if(abs(matrix[row_idx][col_idx] - matrix[new_row_idx][new_col_idx]) > 3 && !((visited_msk >> new_idx) & 1)) { 
    result = max(result, dp(new_row_idx, new_col_idx, visited_msk | (1<<new_idx)) + 1); 
} 

このアプローチの順序は、(2 ^(N * M)* N * M * 8)Oであり、それは微細になりN * M(グリッドサイズ)が< = 15の場合

+0

答えを少し詳しく教えてもらえますか?私はあなたを得ることができませんでした –

+0

visited_mskは整数になります。特定の反復のために訪問したアイテムを追跡するためにvisited_mskのリストを保持する必要がありますか?特定の要素に対して可能なすべてのパスを訪れたら、最大値を見つけて、その要素のvisited_mskをリストから削除して次の要素と続けます。 –

+1

'visited_msk'は普通の整数ですが、それをbool配列として扱います。 プログラミング言語で 'signed int'は32ビット(符号用に1ビット)で構成されています。例:5は101として表されます。 したがって、intを配列として扱った場合、5は要素0と2が1(訪問済み)に設定され、他のビットは設定されていない配列です。インデックスでビットを設定する場合3対1では '(0101 | 1000)= 1101'とする必要があります。 (1 <<3)' -> 'msk |(1 << idx)' '(msk >> idx)&1)'は、ビットが1または0に設定されているかどうかをチェックします。ビットマスクの詳細については、 http://stackoverflow.com/questions/を参照してください。 10493411/what-is-bit-masking – khairy

関連する問題