分支定界算法实现

我需要实现一个分支定界算法来证明我的学士论文中存储管理的分配策略的有效性。我不是程序员，我在C中有一些小技巧，但是我可以认识到这个算法不能马上写出来，因为它是一种人工智能，需要做出决定。分支定界算法实现

我想知道如何解决这个问题。

我有迭代1的工作代码，以便它计算每个节点需要的所有东西，但我将数据存储在表示1级节点的简单数组结构中。现在的问题是，如果x是级别节点的数量，我必须分别从节点1,2,3创建x-1，x-2，x-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); 
}

来源

2012-02-21 MarcoBi

发布您的第一次迭代，所以我们可以看到我们正在处理。 – 2012-02-21 00:15:33

@HunterMcMillen发布了代码。是一种混乱，但正如我所说的是我在C++中的第一次经历。我知道所有的循环都是从索引1开始的，而不是从0开始，现在我会解决它。 – MarcoBi 2012-02-21 10:07:31

这听起来像你需要动态分配你的结构的阵列，然后将它们链接到节点你的结构。为此，you would add a pointer to the struct type in the struct itself，然后分配一个新的结构数组和assign the resulting address to the pointer in your original struct。那么当您浏览您的搜索空间时，您可以navigate from node to node as necessary。

您的示例比上面的链接列表示例稍微复杂一些，因为它将在您搜索空间时变为树状，但您可以使用它来获取C中的动态数据结构的基础知识，然后您应该能够适应你的情况。

来源

2012-02-21 00:38:10 Bill

我认为我的节点需要是单个项目，而不是数组。从根节点开始，我需要创建新的节点，直到出现特定条件，然后重新创建每个新创建的节点。在同一迭代中创建的节点需要引用同一个节点（父亲）。我怎样才能做到这一点？ – MarcoBi 2012-02-21 19:34:35

添加一个指向父指针的指针，你很好走，有一些rosetta代码中的doubley链表的例子，它们在概念上是相似的。另外，没有数组也可以更容易，那么指针只能指向单个节点，并且只需为其中一个结构分配足够的内存。如果这对你来说真的很新，你会将sizeof运算符应用于其中一个结构体，以知道要分配多少内存。 – Bill 2012-02-21 21:05:54

只是。我实现了一个双链“树”。每个节点都有一个指向导航顺序中的下一个指针的父指针。 thx顺便说一句 – MarcoBi 2012-02-21 22:03:03

分支定界算法实现

回答

相关问题