Нужно перебрать все возможные решения многомерной задачи, сохраняя лучшие N вариантов решения. Лучшие - согласно определенной функции оценки. Предпологается, что если растояние между двумя телами в данном многомерном пространсве достаточно близко, то только одно из них будет сохранено. Моя стратегия:
<PSEUDOCODE>
variant=problem.nextSolution();
while (variant.isValid()){
bool insert=true;
for (list<Variant>::iterator i=bestList.begin();i!=bestList.end();++list){
if (distance(variant, *i) < threshold){
insert=false;
break;
}
if (insert){
variant.calculateScoringFunction();//(много времени)
//пройтись по листу
//и вставить вариант в нужном месте
//если вставлено как минимум N
//вариантов, убрать последний
}
variant=problem.nextSolution();
}
</PSEUDOCODE>
Есть ли стратегии лучше?
Стоит ли, для хранения лучших результатов, использовать std::map (или какой-то другой sorted conainer) вместо std::list?
Пару пояснений и оговорок:
0. язык - С++
1. вычесление "функции оценки" забирает раза в 4-5 больше времени, чем вычесление растояния между телами в пространсве поэтому вычеслять её до того, как уверены, что вариант интересен - не имеет смысла.
2. очень и очень не хочется иметь дело с динамичеким выделением (и освобождением) памяти
3. Может вопрос и OT, так как к линуксу прямого отнашения не имеет (разве, что пишется на оном), но опыт показывает, что на этом форуме довольно высокое отношение сигнала к шуму ("signal to noise ratio") благодоря тому, что его посещают специалисты во многих облостях.
Ответ на:
комментарий
от BottleHunter
Ответ на:
комментарий
от anonymous
Ответ на:
комментарий
от AIv
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.