2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Boolean backtrack
Сообщение29.11.2012, 20:08 
Есть следующая задача.

Есть 6 файлов, их нужно разослать по 4м каналам, как можно быстрее ( интенсивней )

Вот пример алгоритма.

Изображение


Проблема в том, что в моей реализации, он ходит на 1 уровне в значение 1, а потом не возвращается опять на 1ый уровень в ветку со значением 0. Помогите пофиксить

Вот реализация:

Код:
//
//  main.cpp
//  Additive
//
//  Created by MacBook Pro on 23.11.12.
//  Copyright (c) 2012 Vyacheslav Tsurka. All rights reserved.
//
// TODO: Add checkLevel function

#include <iostream>
#include <vector>
using namespace std;

struct info {
    std::vector<float> input;
    float constrains;
};

std::vector<float> next(info params, std::vector<float> candiates);
std::vector<float> first(info params, std::vector<float> candiates);
bool reject(info params, std::vector<float> set);
bool accept(info params, std::vector<float> set);
float getPathSummary(info params, std::vector<float> set);
int backtrack(info params, std::vector<float> set);

int main(int argc, const char * argv[])
{
    info data;
    memset(&data, 0, sizeof(info));
    data.input = {0, 4, 0.5,0.7};
    data.constrains = 2;
    //std::cout << data.constrains << endl;
    std::vector<float> root = {1};
   
    backtrack(data, root);
    return 0;
}

int backtrack(info params, std::vector<float> set)
{
    if (reject(params, set)) {
        return 0;
    }
   
    if (accept(params, set)) {
        std::cout << "Accepted" << getPathSummary(params, set) << endl;
    }
   
    set = first(params,set);
    while(set.size() != 0) {
        backtrack(params, set);
        set = next(params,set);
    }
   
    return 1;
}
/**
* Проходит ли кандидат условия
*/
bool reject(info params, std::vector<float> set)
{
    float sizes = 0;
    for (int i = 0; i < set.size(); i++) {
        sizes += params.input[i] * set[i];
    }
    bool isRejected = ((sizes > params.constrains) || (params.input.size() < set.size())) ? true : false;
    std::cout << "Reject check:" << isRejected << endl;
    return isRejected;
    }

bool accept(info params, std::vector<float> set)
{
    return true;
}

/**
* Получить значение по пути
*/
float getPathSummary(info params, std::vector<float> set)
{
    float summary = 0;
    for (int i =0; i < set.size(); i++) {
        summary += params.input[i] * set[i];
    }
   
    return summary;
}

/**
* Значение первого кандидата
*/
std::vector<float> first(info params, std::vector<float> candiates)
{
    int l = (int) candiates.size();
    if (l > params.input.size()) {
        std::vector<float> tmp;
        std::cout << "First return empty vector" << endl;
        memset(&tmp,0,sizeof(float));
        return tmp;
    } else {
        std::cout << "First path inc" << endl;
        candiates.push_back(1);
        return candiates;
    }
}

std::vector<float> next(info params, std::vector<float> candiates)
{
    int l = (int) candiates.size();
    if (l > params.input.size()) {
        std::vector<float> tmp;
        memset(&tmp,0,sizeof(float));
        return tmp;
    } else {
        std::cout << "Next path inc" << endl;
        candiates.push_back(0);
        return candiates;
    }
}

 
 
 [ 1 сообщение ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group