Algorithm: Min cost in a 2D array
- From: rogerhillster@xxxxxxxxx
- Date: Fri, 05 Oct 2007 18:17:19 -0000
I have the following problem:
a. There is a 2D array with the following mapping:
Node 1 Node 2 Node 3
------------- Node N
Entry1 Cost1,1 Cost1,2 Cost1,3
----------- Cost 1,N
Entry2 Cost2,1 Cost2,2 Cost2,3
------------ Cost 2,N
---------
---------------------------------------------------------------------------------------------------
Entry N CostN,1 CostN,2 CostN,
3------------ CostN,N
b. I need to pick a mapping from EntryK to NodeJ all the way from
Entry1 to EntryN, such that the total cost is the minimum.
c. If we pick up a cost from one column that column needs to be
ignored for other entries.
d. I had thought of generating all the subsets in the set {1,2,.....N}
and then saving those subsets to pick the minimum cost as in {1,3,2,4}
in the subset means Cost1,1 + Cost2,3 + Cost 3,2 + Cost 4,4.
I have the array ready, so I also thought of Dynamic programming in
that I need to save the optimum path. But somehow I am not able to
nail it down.
Could someone let me know any ideas about this?
Thanks,
Roger.
.
- Prev by Date: Re: Exploiting limitations of Turing machines in Turing tests?
- Next by Date: Survey Help - Grad Student Independent Study
- Previous by thread: Re: maximum common subgraph
- Next by thread: Survey Help - Grad Student Independent Study
- Index(es):
Relevant Pages
|
