最短ハミルトン路の高速解法

[実現したいこと]
最短ハミルトン路の高速解法（N=50）

巡回セールスマン問題（TSP）と似た問題で、最も遠い地点同士を結ばないパターン（最短ハミルトン路）の高速解法を調査しています。
50地点を5秒位を目安に解く方法を調査しています。

NP完全問題みたいとのことで、任意の点数の厳密解の高速解法は存在しないと思われますが、
TSPのように近似解法は存在するのでしょうか？

1.厳密解は技術的に無理
2.近似解法なら存在する

もしご存知の方がいればご教示のほど、宜しくおねがいします。

[試したこと]
①TSPの2-opt法を元に距離が一番長い組み合わせを除外
→検索で最初に選択する組み合わせによっては、見た目が近似解にならない

②bitdp
このサイトをもとに試してみました。
→N=20ぐらいまでは大丈夫ですが、N=50では正常に実行できません。

c++
1#include <iostream>  
2#include <vector> 
3#include <cmath> 
4
5using namespace std;
6
7
8const int INF = 1e9; 
9vector<vector <double> > dist; 
10
11const int M = 20;
12double best[1<<M][M];
13int previ[1<<M][M];
14int num;
15
16void buildPath(int S, int i, vector<int> &path) {
17  if (!S) return;
18  buildPath(S^(1<<i), previ[S][i], path);
19  path.push_back(i);
20}
21
22double shortestHamiltonPath(const vector<vector <double> > &w, int s, vector<int> &path) 
23{
24  
25  int N = 1 << num;
26  for (int S=0;S<N;S++){  
27    for (int i=0;i<num;i++){ 
28        best[S][i] = INF;
29    }
30  }
31
32  best[1<<s][s] = 0;
33    for (int S=0;S<N;S++){  
34        for (int i=0;i<num;i++){
35            if (S&(1<<i)){ 
36                for (int j=0;j<num;j++){
37                    if (best[S|(1<<j)][j] > best[S][i] + w[i][j]){
38                        best[S|(1<<j)][j] = best[S][i] + w[i][j];
39                        previ[S|(1<<j)][j] = i;
40                    }
41                }
42            }
43        }
44    }
45
46  int t = min_element(best[N-1], best[N-1]+num) - best[N-1];
47  path.clear(); buildPath(N-1, t, path);
48  return best[N-1][t];
49}
50
51
52int main(int argc, char* argv[]) 
53{
54    vector<int> path;
55    int max_i,max_j;
56    double max;
57
58    cin >> num; 
59
60    vector<double> x(num),y(num);
61
62    dist = vector<vector< double> >(num, vector<double>(num, INF)); 
63    
64    for (int i = 0; i < num; ++i) {
65        cin >> x[i] >> y[i];
66    }
67
68    max=0;
69    for (int i = 0; i < num; i++){ 
70        for (int j = 0; j < num; j++){ 
71            dist[i][j] = sqrt(pow((x[i] - x[j]),2) + pow((y[i] - y[j]),2)); 
72            if(max < dist[i][j]){
73                max = dist[i][j];
74                max_i=i;
75                max_j=j;
76            }
77        }
78    }
79
80    
81    double ans = shortestHamiltonPath(dist, max_i, path); 
82    cout << "長さ:" << (ans == INF ? -1 : ans) << endl;
83    for(unsigned i=0 ; i < path.size() ; i++){
84        cout << "地点番号：" << path[i] << endl;
85    }
86
87    return 0; 
88}
89

[データ]
入力件数
x座標0 y座標0
x座標1 y座標1
x座標2 y座標2
.
.
.

(入力例)
20
396 162
96 38
221 336
121 380
416 85
98 296
377 78
44 400
84 61
319 380
117 278
22 103
162 381
244 417
317 120
260 256
280 202
223 61
124 119
182 263

（出力例）

長さ:1544.61
地点番号：4
地点番号：6
地点番号：0
地点番号：14
地点番号：17
地点番号：1
地点番号：8
地点番号：11
地点番号：18
地点番号：16
地点番号：15
地点番号：19
地点番号：10
地点番号：5
地点番号：7
地点番号：3
地点番号：12
地点番号：2
地点番号：13
地点番号：9
（地点番号は逆順でも良いです）