3
내 학사 학위 논문에서 스토리지 관리를위한 전략 할당의 효과를 입증하기 위해 분기 및 바운드 알고리즘을 구현해야합니다. 저는 프로그래머가 아닙니다. 저는 C로 된 약간의 노하우를 가지고 있습니다.하지만이 알고리즘은 인공 지능과 의사 결정을 필요로하기 때문에 바로 작성할 수는 없습니다.분기 및 바운드 알고리즘 구현
이 문제에 접근하는 방법을 알고 싶습니다.
나는 각 노드에 필요한 모든 것을 계산할 수 있도록 반복 코드 1을 가지고 있지만, 레벨 1의 노드를 나타내는 구조의 간단한 배열에 데이터를 저장하고있다. 문제는 지금 x 레벨 노드의 수입니다, 나는 x-1, x-2, x-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);
}
첫 번째 반복에 대한 내용을 게시하여 작업중인 것을 볼 수 있습니다. –
@HunterMcMillen이 코드를 게시했습니다. 일종의 엉망이지만, 내가 말했듯이 C++에 대한 나의 첫 경험이다. 나는 모든 사이클이 0 대신 인덱스 1에서 시작한다는 것을 알고 있습니다. 바로 지금 고칠 것입니다. – MarcoBi