Improvement of the Greedy Algorithm

Question

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!

Wasting

Could this maybe be done using an adaptation of Dijkstras algorithm? The numbers are nodes of the graph, the value of each node will be the weight of each edge pointing to it, and instead of comparing against shorter paths, we could compare against longer paths. – Caspar

Apparently that intuition is false for the general case, since the longest path problem is NP-hard in general graphs (see for example #10463236). However (!), your problem would be equivalent to find the longest path in a directed acyclic(!) graph, both the longest and the shortest path can be calculated by finding the longest/shortest path in the topological order of the nodes. – Caspar

Is this a duplicate of #14667335 ? – Mutz

Answer 1

I saw your previous question on the same topic, and I start to work on it.
As you doesn't want the direct solution, I can provide you my reflexion about your problem, I guess it could help you.

Some basic property :
1. The number of movement is alway egal to the length of the list m = length A
2. The number of starting point is egal to the length of the head of the list n = length (head A)
3. The current position could never be negative, then :
- if the current position is egal to 0 you can either go down or right
- else you can go to left, down or right

Which lead us to this pseudo code

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

This things should look like something as this

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

In fact keeping all of this in mind and adding the (!!) operator, we shouldn't be so far of the solution. To convince you play with A + list comprehension + !!, as

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

Or play with another version :

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

In fact you have two recursion the main one working on the parameter n = length (head A), you repeat the same action from 0 to (n-1) at (n-1) retrieve the result, this recursion embedded another one which work on m, repeat the same action from 0 to (m-1).

Hope it help. Good luck.

Labial

Answer 2

Keep a list of the paths to each column in the row just reached with the highest score to that cell.

You'd start (in your example), with the list

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

Then, when checking the next row, for each column, you pick the path with the highest score in the previous row that can reach that column, here, for the second row, in column 1 and 2, you'd pick the path ending in column 1 on the row above, and in column 3, you'd pick the path ending in column 2 in the row above, in column 4, the path ending in colum 3 in the previous row, so that would give you

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

for the third row, [0,1,2,0], you'd again pick the path ending in column 1 for the first two columns, the path ending in column 2 for the third, and the path ending in column 3 for the fourth,

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

for the fourth row, [2,3,4,20], you'd pick the path ending in column 2 for the first three columns, and the path ending in column 3 for the last,

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

Then, when you've reached the last row, you pick the path with the highest total.

Why it works:

Let the highest-scoring path end in column c. The part above the last column must be the highest scoring path ending in one of the columns c-1, c, c+1 on the penultimate row, since column c in the last row can only be reached from those.

Mattah

Answer 3

The best solution is not a greedy algorithm from the top down, but rather an approach that starts with the last row and works up:

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)

It is easy to solve if there is one row. So this converts each row into a list of Result with a simple [#] solution path.

Given the rest for the puzzel below a new row then adding the new row is a matter of finding the best solution from rest (by checking down, down left, down right) and combining with the new row.

This makes foldr, or here foldr1 the natural structure.

Ardin

Answer 4

I chose a different path, no pun intended. I listed the allowed index combinations and mapped the board to them. Perhaps someone can find a way to generalize it to a board of any size.

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)

Hades

Nice, but the index_combinations are very inefficient. For instance, when a = 0, and b = 2, it will try all combinations of c and d, even though it is the constraint between a and b that fails. Wouldn't it be better (although more verbose) to customize the allowable range at each level [[a,b,c,d] | a <- [0..3], b <- [max 0 (a-1)..min 3 (a+1)], c <- [max 0 (b-1)..min 3 (b+1)], d <- [max 0 (c-1)..min 3 (c+1)]] – Mutz

That looks like it could be a useful tweak for heavier computations with this model -- thanks for the suggestion, I learned something new! It would be interesting to see a benchmark test for the algorithms. – Knowle