Java Reference
In-Depth Information
}
return
select ;
}
// Update the incidence matrix
void
Update(
int
sel)
int
i,j;
for
(i=0;i
<
nbsubsets ; i++)
{
if
(i!=sel)
for
(j=0;j
<
nbelements ; j++)
if
(incidenceMatrix [ sel ][ j ]) incidenceMatrix [ i ][ j]=
false
;
}
for
(j=0;j
<
nbelements ; j++)
incidenceMatrix [ sel ][ j]=
false
;
}
An initial set cover problem is created by building a new object of type
SetCover
,
as follows:
Program 9.12
Creating an instance of a set cover problem
int
[] [] subsets =
{{
0,1,3
}
,
{
2,3,4
}
,
{
0,2,5
}
,
{
1,2,4
}
,
{
3,4,5
}
,
{
0,2
}}
;
SetCover setcover=
new
SetCover (6 ,6) ;
setcover . SetSubsets( subsets ) ;
System . out . println (
"Set cover problem:"
);
setcover . Display() ;
Finally, The greedy set cover algorithm is concisely written as follows:
Program 9.13
Greedy algorithm for solving SCPs
static boolean
[ ] GreedySCP( SetCover problem )
boolean
[] result=
new boolean
[ problem . nbsubsets ];
int
cover=0;
int
select ;
for
(
int
i=0;i
<
problem . nbsubsets ; i++)
result [ i]=
false
;
while
( cover!=problem . nbelements)
// Choose largest not-yet covered subset
select=problem . LargestSubset () ;
result [ select]=
true
;
// Update covered matrix
cover+=problem.Cover(select);
Search WWH ::
Custom Search