当前位置 博文首页 > 丁劲犇技术发布空间：论坛：二维数组中找最大特征数组
来自论坛
有一个二维数组a[5000][5000];
a[0]={0,0,0,1,0,0,0,0,1,1,*******0,1,1,0};
a[1]={0,0,1,1,0,1,0,0,0,0,*******1,0,1,0};
a[4998]={1,0,0,1,0,1,0,1,0,0,*******0,0,0,0};
a[4999]={0,1,1,1,0,1,0,0,0,0,******0,0,1,1};
元素的排列是随机的，a[]中1的个数，位置也是随机的；
需要找到一个b[8],使得按照列号b[0]…b[7]抽取出的8列数据中，全1行数最多。
这一题第一眼看比较简单，但仔细思考还是不容易的。因为如果暴力做 C(5000,8),是个天文数字。
如果以1最多的8列作为答案呢？貌似有道理，但仔细想一想不靠谱。从一个稀疏矩阵开始，很容易就能够举出反例。
我们可以考虑遗传算法，找到次优解再说。
#include <iostream>
#include <random>
#include <cassert>
#include <vector>
#include <list>
#include <algorithm>
#include <array>
#include <set>
#include <memory.h>
using namespace std;
//行列、测试列（本例子取8）
template<int R, int C, int T>
class tag_item {
public:
tag_item(){
for (int i=0;i<T;++i)
coords[i] = 0;
}
tag_item(const tag_item & t){
memcpy(coords,t.coords,sizeof(coords));
good = t.good;
}
int coords[T];
int good = 0;
public:
inline bool operator == (const tag_item & t) const
{
for (int i=0;i<T;++i)
if (t.coords[i]!=coords[i])
return false;
return true;
}
inline tag_item & operator = (const tag_item & t)
{
for (int i=0;i<T;++i)
coords[i] = t.coords[i];
good = t.good;
return *this;
}
inline int cal_good(const char (* data)[C]) const
{
int res = 0;
for (int i = 0; i < R; ++i)
{
bool failed = false;
for (int j = 0; j < T && !failed; ++j)
{
if (!data[i][coords[j]])
failed = true;
}
if (!failed)
++res;
}
return res;
}
inline void output() const
{
using std::cout;
cout << "Weight=" << good <<" Cols: ";
for (int i = 0; i < T; ++i)
cout << " " << coords[i];
cout << "\n";
}
inline void sort()
{
std::sort(coords,coords+T,std::less<int>());
}
};
template<int R, int C, int T>
inline bool operator < (const tag_item <R,C,T>& t1, const tag_item <R,C,T>& t2) {
for (int i = 0; i < T; ++i)
{
if (t1.coords[i] < t2.coords[i])
return true;
else if (t1.coords[i] > t2.coords[i])
return false;
}
return false;
}
int main(int /*argc*/, char* /*argv*/[])
{
using namespace std;
default_random_engine e;
const int R = 5000, C = 5000, T=8;
typedef tag_item<R,C,T> citem;
char(*data)[C] = new char[R][C];
assert(data);
for (int i = 0; i < R; ++i)
for (int j = 0; j < C; ++j)
data[i][j] = e() % 2;
int best[8] = {12,445,17,2314,3033,1273,2289,4987};
//Best rows,重量一致，但是排齐
for (int i = 0; i <R/2 ; ++i)
for (int j = 0; j < 8; ++j)
{
data[i][best[j]] = 1;
data[i][best[j]+R/2] = 0;
}
//种群1024
const int S = 1024;
vector<citem> group;
std::set<citem> group_set;
//产生初始集合
for (int i = 0; i < S; ++i)
{
citem tmp;
for (int j = 0; j < T; ++j)
{
bool failed = false;
do {
tmp.coords[j] = e() % C;
failed = false;
if (j)
{
for (int k = 0; k < j && !failed; ++k)
if (tmp.coords[k] == tmp.coords[j])
failed = true;
}
} while (failed);
}
tmp.sort();
tmp.good = tmp.cal_good(data);
if (group_set.find(tmp)== group_set.end())
{
group_set.insert(tmp);
group.push_back(tmp);
}
else
--i;
}
//开始遗传优化K次
const int K = 1<<20;
for (int g = 0; g < K; ++g)
{
vector<citem> new_group;
//交叉
#pragma omp parallel for
for (int i = 0; i < S; ++i)
{
set<int> cols;
vector<int> cols_v;
for
