Quantcast

Optimization problem

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Optimization problem

Avinoam
Hi,

Given a real matrix, size N X N, I want to find set of n<N indices
1 < i_1 < i_2 < ... < i_n < N

such that M(1, i_1) + M(i_1, i_2) + ... + N(i_n, N) is maximal.

How do I do it in Octave?

Thanks,

Avinoam
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Optimization problem

Oliver Heimlich
Am 21. April 2017 06:45:09 MESZ schrieb Avinoam <[hidden email]>:

>Hi,
>
>Given a real matrix, size N X N, I want to find set of n<N indices
>1 < i_1 < i_2 < ... < i_n < N
>
>such that M(1, i_1) + M(i_1, i_2) + ... + N(i_n, N) is maximal.
>
>How do I do it in Octave?
>
>Thanks,
>
>Avinoam
>
>
>
>
>--
>View this message in context:
>http://octave.1599824.n4.nabble.com/Optimization-problem-tp4682950.html
>Sent from the Octave - General mailing list archive at Nabble.com.
>
>_______________________________________________
>Help-octave mailing list
>[hidden email]
>https://lists.gnu.org/mailman/listinfo/help-octave

Hi Avinoam,

in Octave you'd solve it like in any other programming language. First, you need an algorithm. I guess you can use something similar to the Dijkstra algorithm, since you are looking for an optimal path through the entries of the matrix. That is, you iterate k=1...N and compute for all entries A(:, k) and A(k, :) what their optimal sum of weight and path is. Finally the optimal path can be found for entry A(N, N). I don't want to spoil the complete lesson, so you may find out the details yourself ;-)

Oliver

_______________________________________________
Help-octave mailing list
[hidden email]
https://lists.gnu.org/mailman/listinfo/help-octave
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Optimization problem

Avinoam
Oliver Heimlich wrote
Am 21. April 2017 06:45:09 MESZ schrieb Avinoam <[hidden email]>:
>Hi,
>
>Given a real matrix, size N X N, I want to find set of n<N indices
>1 < i_1 < i_2 < ... < i_n < N
>
>such that M(1, i_1) + M(i_1, i_2) + ... + N(i_n, N) is maximal.
>
>How do I do it in Octave?
>
>Thanks,
>
>Avinoam
>
>
>
>
>--
>View this message in context:
>http://octave.1599824.n4.nabble.com/Optimization-problem-tp4682950.html
>Sent from the Octave - General mailing list archive at Nabble.com.
>
>_______________________________________________
>Help-octave mailing list
>[hidden email]
>https://lists.gnu.org/mailman/listinfo/help-octave

Hi Avinoam,

in Octave you'd solve it like in any other programming language. First, you need an algorithm. I guess you can use something similar to the Dijkstra algorithm, since you are looking for an optimal path through the entries of the matrix. That is, you iterate k=1...N and compute for all entries A(:, k) and A(k, :) what their optimal sum of weight and path is. Finally the optimal path can be found for entry A(N, N). I don't want to spoil the complete lesson, so you may find out the details yourself ;-)

Oliver

_______________________________________________
Help-octave mailing list
[hidden email]
https://lists.gnu.org/mailman/listinfo/help-octave
Hi Oliver,

Thanks for the explanation,

Avinoam
Loading...