Почему этот код TSP потерпел неудачу в упомянутом случае, но работал где-то еще? - PullRequest
Новая
       25

Почему этот код TSP потерпел неудачу в упомянутом случае, но работал где-то еще?

0 голосов
/ 27 марта 2019

Я реализую задачу коммивояжера с динамическим подходом.Я добавил свою попытку ниже.Код скомпилирован и дал правильный вывод для большинства случаев.Однако это не удалось, когда у меня было матричное представление: [[0,10,1], [1,0,10], [10,1,0]].Я ожидаю, что результат будет 3, но он показывает мне 30 в качестве результата.

Я сделал рекурсивные вызовы, и карта dict хранит ключи для запоминания. 

#include<bits/stdc++.h>
using namespace std;

int v;
int G[10][10];
int parent[10];
map<pair<int,set<int> >, int > dict;
void solve(int,set<int>);
int tsp(int,set<int>);

int main(){
    set<int> s,s_o;
    set<int>::iterator it;
    cout<<"Give number of vertices"<<endl;
    cin>>v;
    for(int i=0;i<v;i++)
        s.insert(i);
    //cout<<"Give number of edges"<<endl;
    //cin>>e;
    s_o=s;
    cout<<"Give edges"<<endl;
    for(int i=0;i<v;i++){
        for(int j=0;j<v;j++){
            cin>>G[i][j];
        }
    }
    solve(0,s);
    return 0;
}

void solve(int i,set<int> s){
    parent[i]=-1;
    set<int>::iterator it;
    it=s.find(i);
    s.erase(it);
    // for(it=s.begin();it!=s.end();++it)
    //   cout<<*it<<" ";
    int ans=tsp(0,s);
    cout<<ans<<endl;
    for(int i=0;i<v;i++)
        cout<<parent[i]<<" ";
    cout<<endl;
}

int tsp(int a,set<int>s){
    set<int>::iterator it;
    int min_cost=1000000;
    int k,min_k;
    if(s.empty()){
        return G[a][0];
    }
    for(it=s.begin();it!=s.end();++it){
        k=*it;
        s.erase(it);
        if(dict.find(pair<int, set<int> >(k,s))!=dict.end()){
            //cout<<"here"<<endl;
            return G[a][k]+ dict.at(pair<int, set<int> >(k,s));
        }
        else{
            if(tsp(k,s)<min_cost){
                min_cost=tsp(k,s);
                min_k=k;
            }
            pair<int,set<int> > x(k,s);
            dict.insert(pair<pair<int, set<int> >,int >(x,min_cost));
            parent[a]=min_k; //i must admit that this is accidental, but 
            //it worked xD
            return G[a][k]+min_cost;
        }
    }
}

Также родительский массив, который я ожидаю, будет содержать родителя вершины и -1 для источника (0 в случае),Что-то не так в функции tsp ()?Если нет, то почему он дал ответ как 30?Кроме того, что не так в использовании родительского массива?

Спасибо за вашу помощь!:)

...