5

I've been working on an abstract chess algorithm using Haskell (trying to expand my understanding of different paradigms), and I've hit a challenge that I've been pondering about for weeks.

Here's the problem:

Given a board (represented by a list of lists of integers; each integer represents a subsequent point value), with dimensions n x n, determine the path that provides the most points. If there is a tie for best path, return either of them.

Here are the specifics:

A = [[5,4,3,1],[10,2,1,0],[0,1,2,0],[2,3,4,20]]

which renders as: 

R1: 5  4  3  1, R2: 10 2 1 0, R3: 0 1 2 0, R4: 2 3 4 20.

The rules are:

  1. You may start anywhere on the top row

  2. You may move one square at a time, either straight down, down-left (diagonal) , or down-right (diagonal).

  3. The output must be a tuple of integers.

First element is a list representing the columns vs. row, and the second element is the total number of points. Eg. for the above board, the best solution is to travel from top-left (5) and go diagonally for the remaining steps (until the 20 point square). This would result in the tuple ([1,2,3,4], 29).

Remember, this is all in Haskell so it is a functional-paradigm recursive problem. At first, I was thinking about using the greedy algorithm, that is, choosing the highest value in r1, and recursing through comparing the next 3 possibilities; choosing the highest of the 3. However, the downfall is that the greedy algorithm doesn't have the ability to see potential ahead of the next row.

How would I go about this? I'm not looking for code per se, since I enjoy solving things on my own. However, pseudocode or some algorithmic guidance would be much appreciated!

4

4 に答える 4

3

同じトピックに関するあなたの前の質問を見ました、そして私はそれに取り組み始めます。
あなたが直接的な解決策を望まないので、私はあなたにあなたの問題についての私の反省を提供することができます、私はそれがあなたを助けることができると思います。

いくつかの基本的な特性：
1。移動の数は常にリストの長さに比例しますm=長さA2
.開始点の数はリストのヘッドの長さに等しくなりますn=長さ（ヘッドA）
3。現在の位置が負になることはありません。現在の位置が
0に等しい場合は、下または右に
移動できます。それ以外の場合は、左、下、または右に移動できます。

これがこの擬似コードにつながります 

generate_path :: [[Int]] -> [[Int]]
generate_path [] = [[]] 
generate_path A =  ... -- You have to put something here
        where 
              m = length A
              n = length (head A)

このことはこのように見えるはずです 

move pos0 count0
    | count0 == 0 =   
        | pos0 == 0 = move (down count) ++ move (right count)  
        | otherwise = move (left count) ++ move (down count) ++ move (right count)  
            where 
                count = count0 - 1
                down  = position0 
                left  = position0 - 1
                right = position0 + 1

実際、これらすべてを念頭に置き、（!!）演算子を追加することで、これまでのところ解決策を見つけるべきではありません。A+リスト内包表記+で遊ぶことを納得させるために!! 、 なので 

[A !! x !! y | x <- [1..2], y <- [0..2]] -- I take random range

または別のバージョンで遊ぶ： 

[[A !! x !! y | x <- [1..2]] | y <- [0..2]]] -- I take random range

実際、2つの再帰があります。主な再帰はパラメータn =長さ（ヘッドA）で動作し、（n-1）で0から（n-1）まで同じアクションを繰り返して結果を取得します。この再帰には、別の再帰が埋め込まれています。 mで作業し、0から（m-1）まで同じアクションを繰り返します。

お役に立てば幸いです。幸運を。

于 2013-02-05T16:05:31.867 に答える
3

そのセルへの最高スコアで到達したばかりの行の各列へのパスのリストを保持します。

あなたは（あなたの例では）リストから始めます

[([1],5), ([2],4), ([3],3), ([4],1)]

次に、次の行をチェックするとき、各列について、その列に到達できる前の行の最高スコアを持つパスを選択します。ここでは、2 行目の列 1 と 2 で、パスの終わりを選択します。上の行の列 1、列 3 では、上の行の列 2 で終わるパスを選択し、列 4 では、前の行の列 3 で終わるパスを選択します。

[([1,1],15), ([1,2],7), ([2,3],5), ([3,4],3)]

3 行目では[0,1,2,0]、最初の 2 列には列 1 で終わるパスを、3 列目は列 2 で終わるパスを、4 列目は列 3 で終わるパスを再び選択します。

[([1,1,1],15), ([1,1,2],16), ([1,2,3],9), ([2,3,4],5)]

4 行目では[2,3,4,20]、最初の 3 列には列 2 で終わるパスを選択し、最後の列には列 3 で終わるパスを選択します。

[([1,1,2,1],18), ([1,1,2,2],19), ([1,1,2,3],20), ([1,2,3,4],29)]

次に、最後の行に到達したら、合計が最も高いパスを選択します。

機能する理由:

最高スコアのパスを列で終了させますc。c-1, c, c+1最後の列の上の部分は、最後から 2 番目の行の列の 1 つで終わる最高スコアのパスでなければなりませんc。

于 2013-02-05T16:01:10.033 に答える
3

最善の解決策は、トップダウンの貪欲なアルゴリズムではなく、最後の行から開始して機能するアプローチです。

import Data.Function
import Data.List

-- All elements of Board are lists of equal lengths
-- valid b = 1 == length (group (map length b))
type Value = Int
type Board = [[Value]]
type Index = Int
type Result = ([Index], Value)

p :: Board
p = [[5,4,3,1],[10,2,1,0],[0,1,2,0],[2,3,4,20]] 

best_from :: Board -> Result
best_from [] = undefined
best_from xs | any null xs = undefined
best_from b = best_of . best_list $ b

best_list :: Board -> [Result]
best_list b = foldr1 layer (map label b)
  where label = zipWith (\index value -> ([index],value)) [1..]
        layer new rest =  zipWith (\(i1,v1) (i2,v2) -> (i1++i2, v1+v2)) new best
          where temp = head rest : map best_pair (zip rest (tail rest))
                best = map best_pair (zip temp (tail rest)) ++ [last temp]

best_pair :: (Result,Result) -> Result
best_pair (a@(_,a1), b@(_,b1)) | a1 >=b1 = a
                               | otherwise = b

best_of :: [Result] -> Result
best_of = maximumBy (compare `on` snd)

main = do
  print (best_from p)

1行あれば解決しやすいです。したがって、これは各行を単純な [#] ソリューション パスを持つ Result のリストに変換します。

行restの下のパズルの場合、new行を追加するには、 (下、左下、右下にチェックを入れて)から解決策newを見つけ、その行と組み合わせます。bestrestnew

これによりfoldr、またはここでfoldr1は自然な構造になります。

于 2013-02-05T23:46:20.220 に答える
0

私は別の道を選びました。しゃれは意図していません。許可されているインデックスの組み合わせをリストし、ボードをそれらにマッピングしました。おそらく誰かがそれを任意のサイズのボードに一般化する方法を見つけることができます。

import Data.List
import Data.Ord
import Data.Maybe

a = [[5,4,3,1],[10,2,1,0],[0,1,2,0],[2,3,4,20]]
r1 = a !! 0
r2 = a !! 1
r3 = a !! 2
r4 = a !! 3

i = [0,1,2,3]
index_combinations = [[a,b,c,d] | a <- i, b <- i, c <- i, d <- i, 
                      abs (b-a) < 2, abs (c-b) < 2, abs (d-c) < 2]

mapR xs = [r1 !! (xs !! 0), r2 !! (xs !! 1), 
           r3 !! (xs !! 2), r4 !! (xs !! 3)]

r_combinations = map mapR index_combinations
r_combinations_summed = zip r_combinations $ map (foldr (+) 0) r_combinations

result = maximumBy (comparing snd) r_combinations_summed
path = index_combinations !! fromJust (elemIndex result r_combinations_summed)
于 2013-02-06T04:16:31.940 に答える