Euclidean TSP

Introduction

This problem asks you to minimize a function.

Solutions

Binary Search

Idea

Lots of words...function has a minimum, maybe you can differentiate....but eh...just binary search!

• double value of C until slope is going upwards (be sure to choose a tiny tiny delta), or else the error will be too big
• binary search on the slope with the previously calculated max until you find the minimum

Runtime

• logarithmic

Ternary Search

Idea

Might not know whether delta is small enough to generate error. Instead come up with the max value, and run ternary search until bounds are within required epislon.

Runtime

• Logarithmic

Code

Solution - Java

import java.util.*;
public class e {
	Scanner in=new Scanner(System.in);
	public static void main(String[] args) {
		new e().go();
	}
	private void go() {
		int n=in.nextInt();
		double p=in.nextDouble(),s=in.nextDouble(),v=in.nextDouble();
		double c=0;
		double diff=1;
		while(slope(n,p,s,v,c+diff)<0)diff*=2;
		while(diff>Math.pow(10, -20)){
			if(slope(n,p,s,v,c+diff)<0)c+=diff;
			diff/=2;
		}
		System.out.printf("%f %f",compute(n,p,s,v,c),c);
	}
	double compute(int n,double p,double s,double v,double c){
		return n*Math.pow(Math.log(n)/Math.log(2),c*Math.sqrt(2))/p/Math.pow(10, 9) + s*(1 + 1/c)/v;
	}
	double slope(int n,double p,double s,double v,double c){
		return compute(n,p,s,v,c+Math.pow(10, -9))-compute(n,p,s,v,c);
	}

}