import java.io.*;
import java.util.*;

public class tsp {

	static int numberOfCities;
	static int[][] city;
	static PrintWriter w;
	static int numberOfPopulation=10;
	static permutation[] list;
	static int Mutation=1;

	public static void main(String[] args){

		String output_name="out.txt";
		String filename="in2.txt";

		StringTokenizer st;
		RandomAccessFile in = null;
		try {
			in = new RandomAccessFile(filename, "r");
		} catch(FileNotFoundException e) {
			System.err.println("Unable to open input file");
			System.exit(1);
		}
		try {
			String line;
			line = in.readLine();
			numberOfCities=Integer.parseInt(line);
			System.out.println(numberOfCities);

			city=new int[numberOfCities+1][numberOfCities+1];
			for(int i=0;i<numberOfCities;i++){
				line = in.readLine();
				System.out.println(line);
				String[] temp=line.split(" ");
				for(int j=0;j<numberOfCities;j++){
					city[i][j]=Integer.parseInt(temp[j]);
				}
			}
			in.close();
		} catch(IOException e) {
			System.err.println("Error reading from input file");
		}

		try{
			//RandomAccessFile out = new RandomAccessFile("output.txt", "rw");
			w =new PrintWriter(new BufferedWriter (new FileWriter(output_name)));
			try{
				//out.writeChars("Yes\n go");
				w.println("Yes");
				w.println();
				w.println("TSP algorithm");
				w.flush();
				w.close();
			}catch (Exception ex){
				System.err.println("error");
			}
		}catch (IOException e){
				System.err.println("error in file inout.txt ");
		}

		list=initialization(numberOfPopulation);
		life(50);
	}

///////////////////////////////////////////////////////////////////////////////////////////////////

	public static permutation[] initialization(int number){

		permutation[] sample=new permutation[number];
		for(int i=0;i<number;i++){
			sample[i]=new permutation(numberOfCities);
			sample[i].GenerateRandomPermutation(city);
		}
		return sample;
	}

	public static void life(int numberOfGenerations){

		for(int i=0;i<numberOfGenerations;i++){
			permutation[] Children= new permutation[numberOfPopulation];
			for(int f=0;f<numberOfPopulation;f++)
				Children[f]=new permutation(numberOfCities);

			System.out.println("round==========>"+i);

			/////////cross over/////////

			crossover(80,Children);

			/////////mutation///////////
			for(int j=0;j<numberOfPopulation;j++){
				int rand2=(int)Math.random();
				if(rand2*100<Mutation){
					int rand3=(int)(numberOfCities*Math.random());
					int rand4=(int)(numberOfCities*Math.random());
					rand4=rand4+1;
					for(int t=0;t<numberOfCities;t++)
						if(rand4==Children[j].perm[t])
							Children[j].perm[t]=Children[j].perm[rand3];

					Children[j].perm[rand3]=rand4;
				}
			}

			System.out.println();
			System.out.println("-------------------");

			//////////////////fitness///////////////////////////
			for(int j=0;j<numberOfPopulation;j++)
				Computation(Children,j,city,list);

			System.out.println();
			System.out.println(" List After Mutation");
			for(int g=0;g<numberOfPopulation;g++){
				for(int j=0;j<numberOfCities;j++)
					System.out.print(Children[g].perm[j]);
				System.out.println( "          fitness------>"+Children[g].cost );
			}


			//////////////select the best 20%//////////////////

			Replacement(Children,list);
			System.out.println();
			System.out.println("-------------------");
			System.out.println("New List After Replacement");

			for(int g=0;g<numberOfPopulation;g++){
				for(int j=0;j<numberOfCities;j++)
					System.out.print(list[g].perm[j]);
				System.out.println( "          fitness------>"+list[g].cost );
			}

		}

	}



		public static void Replacement(permutation[] ChildrenList,permutation[] EvaluatedList){

			Arrays.sort(ChildrenList,new Comp());
			Arrays.sort(EvaluatedList,new Comp());

			int Replace=(int)(0.25*numberOfPopulation);
			//EvaluatedList[0].fitness=ChildrenList[(ChildrenList.length)-1].fitness;
			//EvaluatedList[0].perm=ChildrenList[(ChildrenList.length)-1].perm;
			System.out.println("tool"+Replace);
			for(int i=0;i<Replace;i++){
				EvaluatedList[i]=ChildrenList[(ChildrenList.length-i)-1];
				//EvaluatedList[i].fitness=ChildrenList[(ChildrenList.length-i)-1].fitness;
				//EvaluatedList[i].perm=ChildrenList[(ChildrenList.length-i)-1].perm;
			}

		}
		public static void Computation( permutation[] p,int j,int [][] city,permutation[]EvaluatedList){

			p[j].cost=0;
		 	for(int i=0;i<(p[j].perm.length)-1;i++)
		 		p[j].cost=p[j].cost+(city[p[j].perm[i]][p[j].perm[i+1]]);
		 	p[j].cost=p[j].cost+city[p[j].perm[p[j].perm.length-1]][p[j].perm[0]];
	 }


/////////////////////////////////////////////////////////////////////////////////////

	public static int evaluation(permutation cycle){
		return cycle.cost;
	}
/////////////////////////////////////////////////////////////////////////////////////

	public static void alternation(){

	}
/////////////////////////////////////////////////////////////////////////////////////

	public static void fitness(){

	}
/////////////////////////////////////////////////////////////////////////////////////
	public static void crossover(int cp,permutation[] Children){

		System.out.println("CrossOver:");

		for(int w=0;w<(int)numberOfPopulation;w=w+2){

				int c1=(int)((numberOfPopulation)*Math.random());
				int c2=(int)((numberOfPopulation)*Math.random());
				permutation p1=new permutation(numberOfCities);
				permutation p2=new permutation(numberOfCities);
				p1.cost=0;
				p2.cost=0;
				p1.cost=list[c1].cost;
				p2.cost=list[c2].cost;

				for(int f=0;f<numberOfCities;f++){
					p1.perm[f]=list[c1].perm[f];
					p2.perm[f]=list[c2].perm[f];
				}

				int rand1=(int)Math.random();
				if(rand1*100<cp){

					//PMX//
					int point1=(int)((numberOfCities)*Math.random());
					int point2=(int)((numberOfCities)*Math.random());
					System.out.println();
					for(int h=0;h<numberOfCities;h++)
						System.out.print(p1.perm[h]);
					System.out.println();
					System.out.println("****");
					for(int h=0;h<numberOfCities;h++)
						System.out.print(p2.perm[h]);

					System.out.println();
					System.out.println("point1----> "+point1+"  point2-----> "+point2);
					if(point1>point2){
						int t=point1;
						point1=point2;
						point2=t;
					}
					CrossOver CrossOverList[]= new CrossOver[(point2-point1)+1];
					if(point1==point2){

						int t1=p1.perm[point1];
						int t2=p2.perm[point1];

						CrossOver x=new CrossOver(t1,t2);
						CrossOverList[0]=x;
						p1.perm[point1]=t2;
						p2.perm[point1]=t1;

						for(int s=0;s<point1;s++){
							cross(CrossOverList,p1,s,point2,point1);
							cross(CrossOverList,p2,s,point2,point1);


						}
						for(int s=point2+1;s<numberOfCities;s++){
							cross(CrossOverList,p1,s,point2,point1);
							cross(CrossOverList,p2,s,point2,point1);

						}

					}else{
						for(int j=point1;j<=point2;j++){
							int t1=p1.perm[j];
							int t2=p2.perm[j];
							CrossOver x=new CrossOver(t1,t2);
							CrossOverList[j-point1]=x;
							p1.perm[j]=t2;
							p2.perm[j]=t1;
						}
						for(int s=0;s<point1;s++){
							cross(CrossOverList,p1,s,point2,point1);
							cross(CrossOverList,p2,s,point2,point1);

						}

						for(int s=point2+1;s<numberOfCities;s++){
							cross(CrossOverList,p1,s,point2,point1);
							cross(CrossOverList,p2,s,point2,point1);

						}

					}

					Children[w].cost=p1.cost;
					for(int f=0;f<numberOfCities;f++)
						Children[w].perm[f]=p1.perm[f];
					Children[w+1].cost=p2.cost;
					for(int f=0;f<numberOfCities;f++)
						Children[w+1].perm[f]=p2.perm[f];


				}else{
					Children[w].cost=p1.cost;
					for(int f=0;f<numberOfCities;f++)
						Children[w].perm[f]=p1.perm[f];
					Children[w+1].cost=p2.cost;
					for(int f=0;f<numberOfCities;f++)
						Children[w+1].perm[f]=p2.perm[f];

				}
				System.out.println();
				for(int h=0;h<numberOfCities;h++)
					System.out.print(p1.perm[h]);
				System.out.println();
				System.out.println("****");
				for(int h=0;h<numberOfCities;h++)
					System.out.print(p2.perm[h]);
				System.out.println();

			}

}


	public static void cross(CrossOver[] CrossOverList,permutation p,int x,int point2,int point1){

		int j=-1;
		int m=0;
		while(m<(point2-point1)+1){
			for(int i=0;i<(point2-point1)+1&&i!=j;i++){
				if(((CrossOver)(CrossOverList[i])).used==false){
					if(CrossOverList[i].p1==p.perm[x]){
						p.perm[x]=CrossOverList[i].p2;
						CrossOverList[i].used=true;
						j=i;
					}
					else if(CrossOverList[i].p2==p.perm[x]){
						p.perm[x]=CrossOverList[i].p1;
						CrossOverList[i].used=true;
						j=i;

					}
				}

			}
			m++;
		}
		for(int i=0;i<point2-point1+1;i++){
			CrossOverList[i].used=false;
		}

	}
/////////////////////////////////////////////////////////////////////////////////////
	public static void mutation(int mp ,permutation[] population){

	}
////////////////////////////////////////////////////////////////////////////////////
	/*public static permutation[] selection(){

	}
*/
}

class permutation{

	int[] perm;
	int cost;
	boolean added;

	public permutation(int NumberOfCities ){
		 this.perm=new int[NumberOfCities];
		 this.cost=0;
		 this.added=false;
	}

	public void randomize(){


	}
	public void GenerateRandomPermutation (int[][] matrice){

		 	for(int k=0;k<perm.length;k++)
		 		perm[k]=-1;
		 	int i=0;
		 	while(i<perm.length){
		 		int rand=(int)((perm.length)*Math.random());
		 		rand=rand+1;
		 		boolean flag=false;
		 		for(int j=0;j<=i;j++)
		 			if(rand==perm[j]||rand==0)
		 				flag=true;

		 		if(!flag){
		 			perm[i]=rand;
		 			i++;
		 		}
		 	}
		 	////////****
			System.out.println("*1:"+perm.length);

		 	for(int j=0;j<perm.length;j++)
		 		System.out.print(perm[j]+"  ");
			System.out.println();
		 	costComputation(matrice);

		 	System.out.println(": Cost    fitness---->  "+cost);
	}

	public void costComputation(int[][] matrice){
			//this.cost=0;
			System.out.println("*2 :"+perm.length);
		 	for(int i=0;i<perm.length-1;i++)
		 		cost=cost+(matrice[perm[i]][perm[i+1]]);
		 		cost=cost+(matrice[perm[perm.length-1]][perm[0]]);
	 }
}
class CrossOver {

	int p1;
	int p2;
	boolean used;

	public CrossOver(int p1,int p2){
		this.p1=p1;
		this.p2=p2;
		this.used=false;
	}

}


class Comp implements Comparator {
	  public int compare(Object o1, Object o2) {
	    int j1 = ((permutation)o1).cost;
	    int j2 = ((permutation)o2).cost;
	    return (j1 > j2 ? -1 : (j1 == j2 ? 0 : 1));
	  }
  }