Реализация алгоритма ветвления и ограничения - PullRequest
Новая
       0

Реализация алгоритма ветвления и ограничения

3 голосов
/ 21 февраля 2012

Мне нужно было бы реализовать алгоритм ветвления и привязки, чтобы доказать эффективность стратегии распределения для управления хранилищем в моей дипломной работе. Я не программист, у меня есть немного ноу-хау в C, но я могу понять, что этот алгоритм не может быть написан сразу, потому что это своего рода искусственный интеллект и должен принимать решения.

Я хотел бы знать, как решить эту проблему.

У меня есть рабочий код для итерации 1, так что он вычисляет все, что мне нужно для каждого узла, но я храню данные в простом массиве структур, представляющих узлы уровня 1. Проблема в том, что теперь, если х количество узлов уровня, я должен создать х-1, х-2, х-3, .... новые узлы, соответственно начиная с узлов 1,2,3, ...

Поэтому я спрашиваю, не будет ли кто-нибудь так любезно поставить меня на правильный путь решения проблемы.

вот код, который у меня есть, работающий для первой итерации, извините, но комментарии на итальянском: 

//
//  main.cpp
//  prova1
//
//  Created by Marco Braglia on 13/02/12.
//  Copyright (c) 2012 __MyCompanyName__. All rights reserved.
//

#include <fstream>
#include <iostream>
#include <vector>

using namespace std;

// definizione nuova struttura per i nodi dell'albero decisionale
struct nodo{
  int last_prod;
  int last_slot;
  float Z_L;
  float Z_U;
  float g;
  bool fathomed;
 };

// dichiarazione variabili
float distanze[361];
int   slot[112];
int slot_cum[112];
float COIp[112];
int domanda[112];
struct nodo n_0;
struct nodo n_1[112];
struct nodo n_2[111][111];
float Zb;

float LowerBound(struct nodo n);
float UpperBound(struct nodo n);

int main()
{



// lettura dati input
// distanze slot

ifstream dist_file ( "/Users/MarcoBi/Desktop/TESI di LAUREA/Xcode/dati/distanze.txt" );


if ( !dist_file.is_open() ) {
    // il file non può essere aperto
}
else {
    // leggi i dati nell'array distanze[]
    for(int i=1; !dist_file.eof(); i++){
        dist_file >> distanze[i];
    }

   // visualizza l'array per controllo
   //for(int i=0; i<360; i++){
     //cout << distanze[i] << "\n ";
    //}
}

//slot necessari per prodotto

ifstream slot_file ( "/Users/MarcoBi/Desktop/TESI di LAUREA/Xcode/dati/slot.txt" );

if ( !slot_file.is_open() ) {
    // il file non può essere aperto
}
else {
    // leggi i dati nell'array slot[]
    for(int i=1; !slot_file.eof(); i++){
        slot_file >> slot[i];
    }

    for(int i=0; i<112; i++){
        slot_cum[i]=0;
    }

    for(int i=1; i<112; i++){
        slot_cum[i]=slot_cum[i-1]+slot[i];
    }
    // visualizza l'array per controllo
  //  for(int i=0; i<111; i++){
  //  cout << slot[i] << "\n ";
  // }
 //   cin.get();
}

// COIp

ifstream coi_file ( "/Users/MarcoBi/Desktop/TESI di LAUREA/Xcode/dati/COIp.txt" );

if ( !coi_file.is_open() ) {
    // il file non può essere aperto
}
else {
    // leggi i dati nell'array COIp[]
    for(int i=1; !coi_file.eof(); i++){
        coi_file >> COIp[i];
    }

    // visualizza l'array per controllo
    //for(int i=0; i<111; i++){
    //    cout << COIp[i] << "\n ";
  //  }
}

ifstream d_file ( "/Users/MarcoBi/Desktop/TESI di LAUREA/Xcode/dati/domanda.txt" );

if ( !d_file.is_open() ) {
    // il file non può essere aperto
}
else {
    // leggi i dati nell'array COIp[]
    for(int i=1; !d_file.eof(); i++){
        d_file >> domanda[i];
    }
}


//inizializzazione nodi
n_0.last_prod=0;
n_0.last_slot=0;
n_0.Z_L = 0;
n_0.Z_U = 0;
n_0.g = 0;
n_0.fathomed = false;
    for (int j=0; j<112; j++){

            n_1[j].last_prod = 0;
            n_1[j].last_slot = 0;
            n_1[j].Z_L = 0;
            n_1[j].Z_U = 0;
            n_1[j].g = 0;
            n_1[j].fathomed = false;
        }


//inizializzazione soluzione obiettivo ad infinito
Zb=999999999999;

//calcolo bounds per nodi al livello 1
for(int i=1;i<112;i++){
        n_1[i].last_prod=i;
        n_1[i].last_slot=slot_cum[i];
        n_1[i].Z_L=LowerBound(n_1[i]);
        n_1[i].Z_U=UpperBound(n_1[i]);

    //calcolo g_c
    float dm;
    int D;
    for(int i=1;i<112;i++){
        dm=0;
        for(int j=1;j<=slot_cum[i];j++){
            dm=dm+distanze[j];
        }
        dm=dm/slot_cum[i];
        D=0;
        for(int k=1;k<=n_1[i].last_prod;k++){
            D=D+domanda[k];
        }            
        n_1[i].g=2*dm*D;
    }
    if (i==111) (n_1[i].fathomed=true);                         //fathoming Rule 1 (ultimo prodotto)
    if (n_1[i].Z_L>n_1[i].Z_U) (n_1[i].fathomed=true);          //fathoming Rule 3 (LB > UB)
    if (n_1[i].Z_U<Zb) (Zb=n_1[i].Z_U);                         //aggiorna UB migliore

}

ofstream livello1 ( "/Users/MarcoBi/Desktop/TESI di LAUREA/Xcode/risultati/livello1.txt" );

for(int i=1; i<112; i++){
   if (n_1[i].fathomed==false)
        (livello1 <<"("<< i <<","<<n_1[i].last_slot<<")"<< " LB=" << n_1[i].Z_L << " UB=" << n_1[i].Z_U << " g=" << n_1[i].g <<'\n');
}

}

float LowerBound(struct nodo n){
 int S[112];
 float d[112];
 float dmin[112];
 int q[112];
 float D;
 float LB;

 for(int i=1; i<112; i++){
    q[i]=q[i-1]+slot[i];
 }

//Calcolo S_pigreco
for(int i=0;i<112;i++){
    S[i]=0;
}

for(int i=n.last_prod +2;i<112;i++){
    for(int j=n.last_prod +1;j<=i;j++){
        S[j]=S[j-1]+slot[j];
    }
}
S[110]=S[109] + slot[110];
S[111]=S[110] + slot[111];

//calcolo somma distanze da slot j+1 a q
for(int i=0;i<112;i++){
    d[i]=0;
}

for(int j=n.last_prod + 1;j<112;j++){
    for(int i=n.last_slot + 1; i<n.last_slot + 1 + S[j]; i++){
        d[j]=d[j]+distanze[i];
    }
}

//calcolo dmin_pigreco
for(int i=n.last_prod +1; i<112; i++){
    dmin[i]= d[i]/S[i];
}

D=0;
for(int i=n.last_prod +1; i<112; i++){
    D=D+dmin[i]*domanda[i];
}
LB=(2*D);
    return LB;
}

float UpperBound(struct nodo n){
 float Ud;
 float Ur;
 int S[112];
 float d[112];
 float dm;
 int D;

for(int i=0;i<112;i++){
    S[i]=0;
}
for(int i=n.last_prod +2;i<112;i++){
    for(int j=n.last_prod +1;j<=i;j++){
        S[j]=S[j-1]+slot[j];
    }
}

//calcolo Ud
for(int i=0;i<112;i++){
    d[i]=0;
}

int t=n.last_slot;

for(int i=n.last_prod +1;i<112;i++){
    for(int j=t + 1; j<=t + slot[i]; j++){
        d[i]=d[i]+distanze[j];
    }
    t=t+slot[i];
    d[i]=d[i]/slot[i];
}
Ud=0;
Ur=0;

for(int i=n.last_prod +1;i<112;i++){
    Ud=Ud + 2*(d[i]*domanda[i]);
}

//calcolo Ur
dm=0;
for(int i=n.last_slot +1; i<361; i++){
    dm=dm+distanze[i];
}

dm=dm/(360-n.last_slot);

D=0;

for(int i=n.last_prod +1; i<112; i++){
    D=D+domanda[i];
}

Ur=2*dm*D;

return min(Ur,Ud);
}

1 Ответ

1 голос
/ 21 февраля 2012

Похоже, вам нужно динамически распределять массивы ваших структур и затем связывать их с узлами в ваших структурах. Для этого вы должны добавить указатель на тип структуры в самой структуре , а затем выделить новый массив структур и назначить результирующий адрес указателю в вашей исходной структуре, Затем вы можете перемещаться от узла к узлу при необходимости при прохождении через пространство поиска.

Ваш пример немного сложнее, чем примеры связанного списка выше, потому что он станет деревом, когда вы будете работать с пространством поиска, но вы можете использовать его, чтобы получить основы динамических структур данных в C, тогда вам следует в состоянии адаптировать его к вашей ситуации.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.

Нет похожих вопросов

...