Backtracking is the n! solution. It does not require too much space. However it is much slower than the O ( 2^n . n ) solution. This difference is easily evident even if you try to solve for say n = 15.
15 ! = 1307674368000 operations
15 . 2^15 = 491520 operations
I still believe that the dynamic programming solution is the best even though it requires a lot of space. For large 'n' the space would surely increase exponentially , but then for those larger numbers it would be much much time consuming to get the n! solution.
Here is a problem which I had solved : http://online-judge.uva.es/p/v109/10944.html
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <cassert>
using namespace std;
int dist[20][20];
char arr[50][50];
int ord[20],no;
int memo[20][1<<17];
int go(int c,int st)
{
int &ret=memo[c][st];
if (ret>=0)
return ret;
if (st==1)
return ret=dist[c][0];
ret=1<<30;
for(int i=1;i<=no;i++)
if ((st&(1<<i)))
ret <?= dist[c][i]+go(i,st&~(1<<i));
return ret;
}
int main(void)
{
int x,y,i,j;
while (scanf("%d %d\n",&x,&y)==2){
memset(dist,0x7f,sizeof(dist));
int c=1;
for(i=0;i<x;i++){
fgets(arr[i],sizeof(arr[i]),stdin);
for(j=0;j<y;j++)
if (arr[i][j]=='#')
arr[i][j]=c++;
else if (arr[i][j]=='L')
arr[i][j]=0;
}
for(i=0;i<x;i++)
for(j=0;j<y;j++){
if (arr[i][j]=='.')
continue;
int k,m;
for(k=i;k<x;k++)
for(m=0;m<y;m++){
if (arr[k][m]=='.')
continue;
int t = min(abs(i-k),abs(j-m));
dist[arr[i][j]][arr[k][m]] = t+abs(i-k)-t+abs(j-m)-t;
dist[arr[k][m]][arr[i][j]] = t+abs(i-k)-t+abs(j-m)-t;
}
}
c--;
if (c==0)
printf("0\n");
else{
int min=1<<30;
memset(memo,0xff,sizeof(memo));
int cst = (1<<c+1)-1;
no=c;
for(i=1;i<=c;i++)
min <?= dist[0][i]+go(i,cst & ~(1<<i));
printf("%d\n",min);
}
}
return 0;
}
-Dhyanesh
On 12/22/05, sudhakar-aluri <[EMAIL PROTECTED]> wrote:
what if we use "backtracking" to find the hamiltonian cycles and
finding the min of that. It reduces the space required.since we need to
store only one cycle at one shot. am i missing the stack space required
of recursion of backtrack.??
Dhyanesh, what about time. does it reduces the time as well??
here we go...
{
mincost <- 0;
answercycle < - null;
while( (h <- GetNextHamiltoncycle()) != NULL){.
C <- getcose(h);
if( mincost == 0)
mincost = C; //init.
else if( C < mincost)
{
mincost <- C;
answercycle <- h;
}
}
}
