fatal_error a écrit:en tout cas, par rapport à la matrice binaire et qu'on veut faire des packs de 1, ca correspond au terme seriation.
en particulier, on peut par exemple regarder un algo spectral pour seriation:
http://www.sandia.gov/~bahendr/papers/seriation.ps
(c'est assez bien expliqué et illustré)
Après je sais pas ce que ca donne au niveau des résultats, il faut que j'implémente pour voir...
fatal_error a écrit:la matrice étudiée dans le document est carrée symétrique et binaire (binaire étant facultatif):)
fatal_error a écrit:bon... ca marche pas avec la seriation à priori parce que en cherchant le fieldvector, on tombe sur le vecteur propre de composantes toutes égales (car il y a le même nombre de 1 par ligne et colonne dans A), et du coup on récurse à l'infini dans la seconde branche de l'algorithme.
si on enlève cette première valeur propre, on est pas mal assujettis aux erreurs numériques et quand bien même (à 1e-4 près) la plus longue séquence de valeurs égales pour une instance (5,10) c'est pas 6 mais 3 ...
#include
#include
#include
#include
#include
#include
#include
#include
#include
class Timer {
private:
unsigned long begTime;
public:
void start() {
begTime = clock();
}
unsigned long elapsedTime() {
return ((unsigned long) clock() - begTime) / CLOCKS_PER_SEC;
}
bool isTimeout(unsigned long seconds) {
return seconds >= elapsedTime();
}
};
struct Params{
size_t k;
size_t p;
size_t n;
std::string toString()const{
std::stringstream oss;
oss Container;
Comb(){}
Comb(size_t n):_n(n), _v(n,0){}
std::string stringify() const{
std::stringstream oss;
for(size_t i=0; i= max){
return false;
}
}
}
return true;
}
void insert(size_t i){
_v[i] = 1;
}
protected:
Container _v;
size_t _n;
};
struct Edge{
const Comb* _c1;
const Comb* _c2;
Edge(const Comb* c1, const Comb* c2):_c1(c1), _c2(c2){}
const Comb* beg()const{return _c1;}
const Comb* end()const{return _c2;}
};
class Graph{
public:
void addEdge(const Edge& e){
_s.push_back(e);
}
void store(const Comb* c){
size_t size = _m.size()+1;
_m[c] = size;
}
void writeDimac(const std::string& fName)const{
std::ofstream out(fName.c_str());
std::stringstream oss;
for(auto it = _s.begin(); it!=_s.end(); ++it){
oss beg())->second end())->second second first->stringify() MyMap;
MyMap _m;
std::deque _s;
};
Params handleInput(int argc, char* argv[]){
if(argc combinatorial(size_t k, size_t n){
std::vector v(n);
std::vector ol(C(k,n));
std::fill(v.begin() + n - k, v.end(), true);
size_t z = 0;
do {
Comb combination(n);
for (size_t i = 0; i &combs){
Graph g;
Timer t;
std::coutcompatible(*it2, k)){
g.addEdge(Edge(&*it, &*it2));
}
}
}
std::cout<<"elapsed "<<t.elapsedTime()<<std::endl;
return g;
}
int main(int argc, char* argv[]){
try{
const auto ¶ms = handleInput(argc, argv);
const auto &combs = combinatorial(params.p, params.n);
std::cout<<"combis : "<<combs.size()<<std::endl;
Graph g = buildGraph(params.k, combs);
std::cout<<"built"<<std::endl;
g.writeDimac("./output.txt");
g.writeCombis("./graph.txt");
}catch(const std::string &e){
std::cout<<e<<std::endl;
std::cout<<"expects ./exe k p n \n";
std::cout<<"where \n";
std::cout<<"\t k : maximum size of intersecting set of two random combination (excluded) \n";
std::cout<<"\t p : size of combination taken from elements \n";
std::cout<<"\t n : number of elements"<<std::endl;
}
return 0;
}
#!/home/gogol/soft/io.js/bin/bin/node
var exec = require('child_process').exec;
var fs = require('fs');
function Buf(size, onComplete){
this.size = size;
this.onComplete = onComplete;
this.s = '';
}
Buf.prototype.fill = function(data){
this.s += data;
if(this.s.length == this.size){
this.onComplete();
}
}
Buf.prototype.empty = function(){
this.s = '';
}
function printComb(line, graph){
var arr = line.split('').map(function(digit, idx){
if(digit=='0'){
return ;
}
idx = line.length - 1 - idx; //bit vector output by aco-dls-clique is read from right to left
return (idx+1)+':'+graph[idx+1];
}).filter(function(x){
return x && x.length
})
console.log('Solution : '+line+'\n'+'length : '+arr.length);
console.log(arr.join('\n')+'\n');
}
exec('./exe 3 5 15', function(err, stdout, stderr){
var combiMap = {}
console.log('reading graph');
fs.readFile('./graph.txt', function(err, data){
combiMap = JSON.parse(data.toString());
var cmd = ['cd somePath/aco-dls-clique/src/cpp'];
cmd.push('./local-go somePath/cliques/output.txt 1 100000 5');
var buf = new Buf(Object.keys(combiMap).length, function(){
printComb(buf.s, combiMap);
buf.empty();
});
console.log('running '+cmd)
var child = exec(cmd.join(' && '));
child.stdout.on('data', function(data){
data.split('\n').filter(function(line){
return line.match(/^[01]+$/);
}).forEach(function(dataQuantum){
buf.fill(dataQuantum);
});
});
});
});
2992:8,9,12,13,14
2894:6,7,9,10,12
2888:6,7,8,11,13
2727:4,8,10,11,12
2609:4,5,9,10,14
2567:4,5,6,12,13
2400:3,5,9,11,12
2388:3,5,8,10,13
2338:3,5,6,7,14
2330:3,4,11,13,14
2276:3,4,7,8,9
2198:2,9,10,11,13
2150:2,7,8,10,14
2139:2,6,11,12,14
2009:2,5,6,8,9
1893:2,4,5,7,11
1844:2,3,7,12,13
1729:2,3,4,6,10
1642:1,6,10,13,14
1567:1,5,8,11,14
1544:1,5,7,9,13
1470:1,4,7,12,14
1437:1,4,6,9,11
1342:1,3,7,10,11
1313:1,3,6,8,12
1129:1,2,5,10,12
1085:1,2,4,8,13
1046:1,2,3,9,14
953:0,7,9,11,14
823:0,5,7,8,12
810:0,5,6,10,11
749:0,4,7,10,13
720:0,4,6,8,14
666:0,3,10,12,14
604:0,3,6,9,13
422:0,2,5,13,14
374:0,2,4,9,12
323:0,2,3,8,11
283:0,1,11,12,13
252:0,1,8,9,10
2:0,1,2,6,7
1:0,1,3,4,5
fatal_error a écrit:hello,
moi non plus, j'ai pas pris la peine de lire, l'algo est pas de moi
c'est pris de githug aco-dls (dynamic local search)
le papier peut etre trouvé là : http://arxiv.org/pdf/1109.5717.pdf
pour 18 j'ai trouvé 69 en une heure et 68 en dix minutes
fatal_error a écrit:j'ai pas pris la peine de noter le 69 et le 3 5 25 me fait planter (...) la bécane :marteau:
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include "local.hpp"
#include
#define MAX_THREADS 8
class Timer {
private:
unsigned long begTime;
std::string _s;
public:
void start(const std::string& s) {
std::cout= elapsedTime();
}
};
struct Params{
size_t k;
size_t p;
size_t n;
Params():spd(1),steps(100000),cons(5){}
size_t spd;
size_t steps;
size_t cons;
std::string toString()const{
std::stringstream oss;
oss Container;
Comb(){}
Comb(size_t n, size_t idx):_n(n), _v(n,0), _idx(idx){}
std::string stringify() const{
std::stringstream oss;
for(size_t i=0; i= max){
return false;
}
}
}
return true;
}
size_t idx()const{return _idx;}
void insert(size_t i){
_v[i] = 1;
}
protected:
Container _v;
size_t _n;
size_t _idx;
};
struct Edge{
const Comb* _c1;
const Comb* _c2;
Edge(const Comb* c1, const Comb* c2):_c1(c1), _c2(c2){}
const Comb* beg()const{return _c1;}
const Comb* end()const{return _c2;}
};
class Graph{
typedef std::vector Container;
public:
Graph(const Container* c):_m(c){}
void addEdge(const Edge& e){
_s.push_back(e);
}
void writeDimac(const std::string& fName)const{
std::ofstream out(fName.c_str());
std::stringstream oss;
Timer t;
t.start("foor loop");
for(auto it = _s.begin(); it!=_s.end(); ++it){
oss beg()->idx();
oss end()->idx() size()size(), _s.size());
for(auto it = _s.begin(); it!=_s.end(); ++it){
g->add_edge(it->beg()->idx()-1, it->end()->idx()-1);
}
return g;
}
void writeCombis(const std::string& fName)const{
std::ofstream out(fName.c_str());
std::stringstream oss;
for(auto it = _m->begin(); it!=_m->end(); ++it){
oss idx() stringify() _s;
};
Params handleInput(int argc, char* argv[]){
if(argc combinatorial(size_t k, size_t n){
std::vector v(n);
std::vector ol(C(k,n));
std::fill(v.begin() + n - k, v.end(), true);
size_t z = 0;
do {
Comb* combination = new Comb(n, z+1);
for (size_t i = 0; i insert(i);
}
}
ol[z] = combination;
z++;
} while (std::next_permutation(v.begin(), v.end()));
return ol;
}
Graph buildGraph(size_t k, const std::vector &combs){
Graph g(&combs);
Timer t;
t.start("building graph");
auto p_comb = combs[0];
std::vector candidates;
candidates.reserve(combs.size());
for(auto it2 = combs.begin()+1; it2!=combs.end(); ++it2){
if(p_comb->compatible(**it2, k)){
g.addEdge(Edge(p_comb, *it2));
candidates.push_back(*it2);
}
}
for(auto it = candidates.begin(); it!=candidates.end(); ++it){
for(auto it2 = it+1; it2!=candidates.end(); ++it2){
if((*it)->compatible(**it2, k)){
g.addEdge(Edge(*it, *it2));
}
}
}
t.stop();
return g;
}
void go(const Graph& graph, const Params &p){
graph_t *g = graph.getGraph_t();
boost::thread threads[MAX_THREADS];
DLS *dls = new DLS[MAX_THREADS];
double start = (double)clock()/CLOCKS_PER_SEC;
std::cout n, dls);
}
std::cout " " << bests.size() << std::endl;
std::cout << "Primer mejor en " << bestFirst - start << std::endl;
delete g;
}
int main(int argc, char* argv[]){
try{
const auto ¶ms = handleInput(argc, argv);
const auto &combs = combinatorial(params.p, params.n);
std::cout<<"combis : "<<combs.size()<<std::endl;
Graph g = buildGraph(params.k, combs);
std::cout<<"built"<<std::endl;
Timer t;
t.start("write combis");
g.writeCombis("./graph.txt");
t.stop();
std::cout<<"combi ready"<<std::endl;
go(g, params);
for(auto comb: combs){
delete comb;
}
}catch(const std::string &e){
std::cout<<e<<std::endl;
std::cout<<"expects ./exe k p n \n";
std::cout<<"where \n";
std::cout<<"\t k : maximum size of intersecting set of two random combination (excluded) \n";
std::cout<<"\t p : size of combination taken from elements \n";
std::cout<<"\t n : number of elements"<<std::endl;
}
return 0;
}
Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 7 invités
Tu pars déja ?
Identification
Pas encore inscrit ?
Ou identifiez-vous :