Ճանապարհորդող վաճառող անձ HackerRank լուծում ալգորիթմով

Ճանապարհորդող վաճառողը դասական գրաֆիկական խնդիր է: Այստեղ բերված է i քաղաքից j քաղաք տեղափոխվելու արժեքը։ Խնդիրն է գտնել մի ուղի, որը սկսվում է 0 քաղաքից, որն առավելագույնը մեկ անգամ ընդգրկում է բոլոր այն քաղաքները, որոնց արժեքը ամենափոքրն է:

Խնդրի հայտարարություն.

Տրվում է Mչափի N մատրիցա, որտեղ M[i][j]նշանակում է iքաղաք j քաղաք տեղափոխելու արժեքը: Ձեր խնդիրն է շրջագայություն կատարել քաղաքից 0(0-ի վրա հիմնված ինդեքս) դեպի բոլոր մյուս քաղաքները, որպեսզի այցելեք յուրաքանչյուր քաղաք առավելագույնը մեկ անգամ, իսկ վերջում վերադառնաք քաղաք 0 րոպեում:

Մուտքի ձևաչափ

Մուտքի առաջին տողը պարունակում է T ամբողջ թիվ, որը նշանակում է թեստային դեպքերի թիվը: Այնուհետև հետևում են T թեստի դեպքերը: Յուրաքանչյուր փորձնական դեպք պարունակում է N ամբողջ թիվ, որը նշանակում է մատրիցայի չափը, այնուհետև հաջորդ տողում կան N*N տարածության առանձնացված արժեքներ M մատրիցից:

Սահմանափակումներ

1<=T<=15, 1<=N<=12, 1<=M[][]<10000

Ելքի ձևաչափ

Յուրաքանչյուր փորձնական դեպքի համար նոր տողով տպեք պահանջվող արդյունքը, որը նշանակում է շրջագայության նվազագույն արժեքը:

Նմուշի մուտքագրում

2
2
0 111
112 0
3
0 1000 5000
5000 0 1000
1000 5000 0

Նմուշի արդյունք

223
3000

Նվազագույն արժեքով ուղին ցուցադրված է թավերով:

Ալգորիթմ

• Վերցրեք գրաֆիկի մուտքագրումը 2D մատրիցայի մեջ:
• Նախաձեռնեք n չափերի այցելված զանգվածը 0-ով:
• Սահմանել visited[0]_ից 1:
• Զանգի անցում arr-ով, cur node (0), այցելած հանգույցների քանակը (cnt = 1), ընդհանուր արժեքը (0), Քանի որ արդեն 0th հանգույցում, ուստի 0th հանգույցից 0th հանգույց անցնելու արժեքը 0 է:
• Ստուգեք if cnt == n. Եթե ​​ճիշտ է, ապա մենք այցելել ենք բոլոր հանգույցները: Ներդրեք ans-ի նվազագույն չափը և (ընդհանուր + արժեքը ընթացիկ հանգույցից հանգույց 0 անցնելու համար) ans: Հետո վերադարձիր։
• Կրկնել բոլոր հանգույցների միջով:
• Եթե ​​ith հանգույցը չի այցելվում, և այն վավեր հանգույց է, ապա դարձրեք visited[cur]=1: Զանգի անցում կատարելով այն հանգույցը հավասարեցնելով cur, cnt+1-ին և ընդհանուր+արժեքը՝ cur-ից մինչև ith հանգույց (arr[cur][i]):

C++ ներդրում

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

int ans = INT_MAX, n;

bool valid(int i) {
  return i >= 0 && i < n;
}

void traverse(vector<vector<int> >& arr, int cur, vector<int> visited, int cnt, int total) {
  // all nodes are visited
  if(cnt == n) {
    ans = min(ans, total + arr[cur][0]); // add the distance from last node to the 0th node
    return;
  }
  
  // explore all the paths that are not yet visited
  for(int i = 0; i < n; i++) {
    if(!visited[i] && valid(i)) {
      visited[i] = 1;
      traverse(arr, i, visited, cnt+1, total+arr[cur][i]);
      visited[i] = 0; // so that this node can be used in another sequence to check if min cost can be obtained
    }
  }
}

int main() {
  int t;
  cin>>t;
  
  while(t--) {
    cin>>n;
    vector<vector<int> > arr(n, vector<int>(n));
    vector<int> visited(n, 0);
    ans = INT_MAX;
    
    // take the graph input
    for(int i = 0; i < n; i++) {
      for(int j = 0; j < n; j++) {
        cin>>arr[i][j];
      }
    }
    visited[0] = 1;
    // check all possible path to find the min cost path
    traverse(arr, 0, visited, 1, 0); 
    
    cout<<ans<<endl;
  }
  return 0;
}

Խնդիրի հղումը՝ https://www.hackerrank.com/contests/target-samsung-13-nov19/challenges/travelling-salesman-4

Շնորհակալություն այս հոդվածը կարդալու համար: Հարցերի դեպքում թողեք մեկնաբանություն ստորև: Դուք կարող եք կապվել ինձ հետ LinkedIn,Twitter-ում: Արի, ասա բարև