How to find best path in a nx2 matrix?

Hi everyone,

I have a problem about museum rooms.

• I want to block(close) k number of rooms without blocking the path and allowing the best rooms for visitors in a museum which has nx2 rooms.
• The visitors can only move between doors and only the shared walls have doors. (enterance and exit of the museum are the top 2 cells or bottom 2 cells).
• The rooms also have number of sculptures and they are positive integers. I want to allow maximum number of items to exhibit visitors.

The question is to create a function that gets nx2 matrix(rooms with points) and k(number of blocked rooms) and returns the value of total points of unblocked rooms.

Museum rooms, Allowable walk path for visitors(doors), An example of blocked path(The visitors can not move vertically to exit the museum) are below respectively.

Simple Example and desired output:

If I want to close 2 rooms in below museum,

0 and 5 closed, total point will be 90 but the path is blocked for visitors.

0 and 14 closed, total point will be 81 but the path is blocked for visitors.

0 and 16 closed, total point will be 79 and path is OK for visitors.

desired ouput: 79

Here is sample code I have started, at first I thought if I choose the minimums of rooms, that could be OK. But I really don't know what kind of approach I should use.

If some rooms have same numbers and they are the minimum 2 or 3 of the rooms, how to choose the best?

I also realized that if k increases, the number of combinations decrease. In above sample k can not be more than 3, if it is 3 I can only look at first or second column total and choose the minimum of them.

function totalSum = roomSelection(museumArray,k)
[row, column] = find(museumArray == min(museumArray));
values_of_mins = museumArray(find(museumArray == min(museumArray)));
for i  = 1:size(museumArray,1)
    for j = 1:size(museumArray,2)      
        % I wanted to check if the path is blocked or not but don't know where to start.
    end
end
% museumArray1 = [36,5;0 14;16,24];
% k = 2
% out = roomSelection(museumArray,k) -> 79
% museumArray2 = [36,5;0,14;22,12;44,35;20,49;3,26;1,31;40,33;11,28;10,24]
end

I really appreciate if any approach or any help on this problem. Thank you so much!

Luna.

Answer 1

[Matt J]

You can solve this as binary linear program, either with intlinprog or using the problem-based solver. Let X be a binary nx2 decision matrix with X(i,j)=1 in the rooms you choose to block and zero otherwise. Then you wish to choose X to minimize the linear function,

museumArray(:).' * X(:)

subject to the linear constraints,

     sum(X(:))=k  %k rooms blocked
     
     X(i,1)+X(i,2)<=1   %No blocked paths
     X(i,1)+X(i+1,2)<=1
     X(i,1)+X(i-1,2)<=1

for all i.

[Luna]

Thank you Matt, I will try this as soon as possible.