<!--uyt = setTimeout("Initialize_SA()", 4000)SPARSITY = new Array(0,0,5,10,20,30,40,50,60,70,80,90,100)RANGE = new Array([1,10],[1,10],[10,20],[20,30],[30,40],[40,50])NEGATIVE = new Array(0,0,5,10,20,30,40,50,60,70,80,90,100)Status_SA = "Idle"BB = "                                                   "function Initialize_SA(){//uytr = window.frames[0].location="sa_up.html"n = 10n_sa = 10Cycle = falsesign = 0range = 1sparsity  = 0ur = 10lr = 1form_SA = window.document.forms.module_1Fill_SA(form_SA)}function Help_SA(form){WIN1_Help = open('WIN1_Help.html','WIN1_Help',"width=500,height=300,title='Help'")oioi = setTimeout("WIN1_Help.focus()",1000) }function Clear_SA(form){if(Status_SA != "Idle"){return}for(i=1;i<=n_sa;i++){ eval('form.f_' + i  + '.value =" ?"')eval('form.IP_' + i  + '.value =" ?"')eval('form.NUD_' + i  + '.value =" ?"')for(j=1;j<=n_sa;j++){eval('form.d_' + i + '_' + j + '.value =" *"')				}				}form.status.value="Idle ..."Status_SA = "Idle"}function Gen_SA(form){if(Status_SA != "Idle"){return}Clear_SA(form)//n = 4 + top.up.document.forms[0].n.selectedIndex//formup = top.up.document.forms[0]//formup.n.selectedIndex = 0var c = form.cycle.selectedIndexif ( c == 0){Cycle =  false} else {Cycle = true}sign = NEGATIVE[form.sign.selectedIndex]sparsity = form.sparsity.selectedIndexc = form.range.selectedIndexc = RANGE[c]lr = c[0]ur = c[1]//Create(n)Fill_SA(form)}function Create(n){Font = '<font face="verdana,arial">'var t = '<html><body bgcolor="white" text="black"><form name="SA_Module">'t += '<table align="center" cellpadding=0 cellspacing=0 border=0 width="9">'t += '<tr><td align="center">'t += '<table align="center" border=1 width="*" cellpading=3 cellspacing=0><tr align="center"><td bgcolor="red"> <input type="button" value="Solve:" onClick="top.Solve()"></td><td nowrap><font face="verdana,arial" color="red"> &nbsp; f(j) = min {D(x,j) + f(x): x in P(j)} , j=1,2,...,' + n + ' ; <font color="black">&nbsp; [ f(1) = 0] </font></td><td bgcolor="darkblue"><input type="button" name="Print" value=" Print " onClick="top.Print()"></td></tr>'t += '<tr align="center"><td><font face="verdana,arial">Status: </font></td><td><input type="text" size = 60 onfocus="this.blur()" name="status" value="Idle ... " style="font-family:verdana,arial;font-size:10pt"></td><td><input type="reset" name="Clear" value=" Clear "></td></tr></table>'t += '</td></tr><tr><td align="center">'t += '<table align="center" border=1 cellspacing=0>'t += '<tr bgcolor="gold" align="center"><td bgcolor="red"><font color="white" face="verdana,arial">f(j)</font></td>'for (j=1;j<=n-1;j++){t += '<td><input type="text" size=4 name="f_' +  + j +  '"  value=" ? " onfocus="this.blur()"></td>'} t += '<td bgcolor="red"><input type="text" size=4 name="f_' +  + n +  '"  value=" ? " onfocus="this.blur()"></td></tr>'t += '<tr align="center" bgcolor="lightgrey"><td bgcolor="black"><font face="verdana,arial" color="white">D(i,j)</font></td>'for(j=1;j<=n;j++){t += '<td>&nbsp;' + Font + j + '&nbsp;</font></td>' }t += '</tr>' for(i=1;i<=n;i++){t += '<tr align="center"><td bgcolor="lightgrey">&nbsp;' + Font + i+ '</font>&nbsp;</td>'for(j=1;j<=n;j++){IJcolor="white"IJtype="text"BB = ""if((j == i) || (j==1)){IJcolor="beige"; IJtype="hidden"; BB = "&nbsp;"} t += '<td bgcolor="'+ IJcolor+ '" >' + BB + '<input type="' + IJtype + '" size=4 name="d_' + i + '_' + j +  '"  value=" * "></td>'} 	}t +='<tr></table></td><tr></table>'t += '<center><font color="darkblue" face="verdana,arial">* = Infinity ; UB = Unbounded (below)</font></center></form>'t += '</body></html>'window.down.document.clear()window.down.document.open()window.down.document.write(t)window.down.document.close()}function Fill_SA(form){ for(i=1;i<=n_sa;i++){ for(j=1;j<=n_sa;j++){eval('form.d_' + i + '_' + j + '.value =" *"')				}				}var dr = ur - lrvar s = SPARSITY[sparsity]/100for(i=1;i<=n_sa;i++){ var jj = 1if(!Cycle) {jj = i}for(j=jj+1;j<=n_sa;j++){var r = Math.random()if( r < s) {continue}var sss = 1if(Math.random() < (sign/100) ) {sss = -1}if((i == j) || (j == 1)){continue}var dd = Math.floor(lr + Math.random()*dr + 0.5)eval('form.d_' + i + '_' + j + '.value ="' + (sss*dd) + '"')	}	}form.status.value="Generated new problem. Now, idle ..."Status_SA = "Idle"}function Solve_SA(form){if(Status_SA != "Idle"){return} Status_SA = "Solve"form.status.value="Preprocessing  ...."Read_SA(form)Initialize_DP_SA(form)DP_SA(form)}function Read_SA(form){var n = n_saD = new Array()for(i=1;i<=n;i++){	D[i] = new Array()	for(j=1;j<=n;j++){		dd = eval('form.d_' + i + '_' + j + '.value')		if(isNaN(dd)){D[i][j] = Infinity} 			else {D[i][j] = Number(dd)}if(dd == BB.substring(0,dd.length-1)) {D[i][j] = Infinity} if(D[i][j] == Infinity){eval('form.d_' + i + '_' + j + '.value = " *"')} 				}			}S = new Array()P = new Array()for(j=1;j<=n;j++){	S[j] = new Array()	P[j] = new Array()	for(k=1;k<=n;k++){	if(D[j][k] < Infinity){S[j][S[j].length] = k} 	if(D[k][j] < Infinity){P[j][P[j].length] = k}				}			}		}function Initialize_DP_SA(form){form_SA = formvar n = n_saF = new Array()OIP = new Array()NUD = new Array()NAD = new Array()KNN = new Array()Flag = new Array()for(j=1;j<=n;j++){	F[j] = Infinity	OIP[j] = "*"	NUD[j] = 0	NAD[j] = 0	Flag[j] = false	eval('form.f_' + j + '.value = " * "')	eval('form.IP_' + j + '.value = " ? "')	eval('form.NUD_' + j + '.value = " ? "')	}F[1] = 0ITER = 0form.f_1.value = 0}function DP_SA(form){var n = n_saITER += 1form.status.value = "Iteration No. " + ITER + " of the SA procedure ..."var FLAG = falsevar Flag = new Array()	for(j=1;j<=n;j++){		for(x=0;x<P[j].length;x++){			NAD[j] += 1			var k = P[j][x]			var dd = F[k] + D[k][j]			if(dd  < F[j] ){			F[j] = dd			OIP[j] = k			NUD[j] += 1			FLAG = true					} 								}				}Update_F_SA(form_SA)if(!FLAG){End_SA(form_SA); return}if(ITER == n){		Flag_SA = new Array()		for(j=1;j<=n;j++){Flag_SA[j] = false}		Neg_DP_Cycles()		return		}tre = setTimeout('DP_SA(form_SA)',0)}function Neg_DP_Cycles(){ITER += 1var n = n_saform_SA.status.value = "Iteration No. " + ITER + " of the SA procedure ..."for(j=1;j<=n;j++){	for(x=0;x<P[j].length;x++){	NAD[j] += 1	var k = P[j][x]	var dd = F[k] + D[k][j]	if(dd  < F[j] ){		F[j] = dd		OIP[j] = k		NUD[j] + 1		Flag_SA[j]  = true				} 							}			}Update_F_SA(form_SA)if(ITER > (2*n_sa)){Unbounded_SA(form_SA);return}tre = setTimeout('Neg_DP_Cycles()',0)}function Initialize_f_SA(form){form_SA = formvar n = n_saF = new Array()OIP = new Array()NUD = new Array()KNN = new Array()Flag = new Array()for(j=1;j<=n;j++){	F[j] = Infinity	OIP[j] = "*"	NUD[j] = 0	Flag[j] = false	eval('form.f_' + j + '.value = " * "')	eval('form.IP_' + j + '.value = " ? "')	eval('form.NUD_' + j + '.value = " ? "')	}F[1] = 0ITER = 0form.f_1.value = 0}function Suc_app_SA(form){var n = n_saITER += 1form.status.value = "Iteration No. " + ITER + " of the SA procedure ..."var FLAG = falsevar Flag = new Array()for(var m=1;m<=n;m++){Flag[m] = false}	for(j=1;j<=n;j++){		for(x=0;x<S[j].length;x++){			var k = S[j][x]			var dd = F[j] + D[j][k]			if(dd  < F[k] ){			F[k] = dd			OIP[k] = j			NUD[k] += 1			Flag[k]  = true			FLAG = true					} 								}				}Update_F_SA(form_SA)if(!FLAG){End_SA(form_SA); return}if(ITER > n){		Flag_SA = new Array()		for(j=1;j<=n;j++){Flag_SA[j] = false}		Neg_Cycles()		return		}tre = setTimeout('Suc_app_SA(form_SA)',0)}function Update_F_SA(form){var n = n_safor(j=1;j<=n;j++){var dd = Math.min(Infinity,F[j])if(KNN[j] > n){dd = "UB"; F[j] = -Infinity} if(dd == Infinity){dd = " *"} eval('form.f_' + j + '.value = "' + dd + '"')eval('form.IP_' + j + '.value = "' + OIP[j] + '"')eval('form.NUD_' + j + '.value = "' + NUD[j] + "/" + NAD[j] + '"')	}}function Unbounded_SA(form){var n = n_safor(j=1;j<=n;j++){	dd = F[j]	if(F[j] == Infinity){dd = " *"}	if(Flag_SA[j]){ dd = "UB"; F[j] = -Infinity}  	eval('form.f_' + j + '.value = "' + dd + '"')	eval('form.IP_' + j + '.value = "' + OIP[j] + '"')	}End_SA(form)}function End_SA(form){Status_SA = "Idle"form.status.value ="Solved in " + ITER + " iterations. Now idle ..."}function Neg_Cycles(){ITER += 1var n = n_saform_SA.status.value = "Iteration No. " + ITER + " of the SA procedure ..."for(j=1;j<=n;j++){	for(x=0;x<S[j].length;x++){	var k = S[j][x]	var dd = F[j] + D[j][k]	if(dd  < F[k] ){		F[k] = dd		OIP[k] = j		Flag_SA[k]  = true				} 							}			}Update_F_SA(form_SA)if(ITER > (2*n_sa)){Unbounded_SA(form_SA);return}tre = setTimeout('Neg_Cycles()',0)}// -->