import java.util.PriorityQueue;
import java.util.HashSet;
import java.util.Set;
import java.util.List;
import java.util.Comparator;
import java.util.ArrayList;
import java.util.Collections;
public class finalAstar{
String kodenode1A,namanode1A,kodenode1B,namanode1B;
double jarak1A,jarak1B;
int jd=0;
String[]arKode;
double[]arLati;
double[]arLongi;
double[]arJarakA;
double[]arJarakB;
String[]arNama;
String myLati="-9.50245";//GPS Myself
String myLongi="119.22644";
String myPosisi="GPS";
String myLati2="-9.59344";//Wisata
String myLongi2="118.99406";
String myPosisi2="Tujuan Objek Wisata";
public static void main(String[] args){
finalAstar x=new finalAstar();
x.init();
x.cekAwal();
x.mulai();
}
void cekJarak(){
finalAstar x=new finalAstar();
x.cekJarak("A","B");
x.cekJarak("B","C");
x.cekJarak("C","D");
x.cekJarak("B","D");
x.cekJarak("D","E");
x.cekJarak("E","F");
x.cekJarak("F","G");
x.cekJarak("F","I");
x.cekJarak("I","J");
x.cekJarak("G","H");
x.cekJarak("H","J");
x.cekJarak("H","K");
x.cekJarak("K","L");
x.cekJarak("J","K");
x.cekJarak("I","M");
x.cekJarak("J","M");
x.cekJarak("M","N");
x.cekJarak("N","O");
x.cekJarak("O","P");
x.cekJarak("O","Q");
x.cekJarak("Q","R");
x.cekJarak("N","R");
x.cekJarak("R","S");
x.cekJarak("S","T");
x.cekJarak("T","U");
x.cekJarak("U","V");
x.cekJarak("S","V");
x.cekJarak("V","A");
}
void cekAwal(){
double mlati=Double.parseDouble(myLati);
double mlongi=Double.parseDouble(myLongi);
double mlati2=Double.parseDouble(myLati2);
double mlongi2=Double.parseDouble(myLongi2);
double jmaxA=1000000000;
int indexA=0;
for(int i=0;i<jd;i++){
double r=0;
try{
r=getJarak(mlati,mlongi,arLati[i],arLongi[i]);
arJarakA[i]=r;
if(r<jmaxA){
jmaxA=r;
indexA=i;
}
}
catch(Exception ee){}
}
double jmaxB=1000000000;
int indexB=0;
for(int i=0;i<jd;i++){
double r=0;
try{
r=getJarak(mlati2,mlongi2,arLati[i],arLongi[i]);
arJarakB[i]=r;
if(r<jmaxB){
jmaxB=r;
indexB=i;
}
}
catch(Exception ee){}
}
kodenode1A=arKode[indexA];
namanode1A=arNama[indexA];
jarak1A=arJarakA[indexA];
kodenode1B=arKode[indexB];
namanode1B=arNama[indexB];
jarak1B=arJarakB[indexB];
cetak("Posisi SRC="+namanode1A);
cetak("Posisi DST="+namanode1B);
}
void mulai(){
mNode n1 = new mNode("A",0);
mNode n2 = new mNode("B",0);
mNode n3 = new mNode("C",0);
mNode n4 = new mNode("D",0);
mNode n5 = new mNode("E",0);
mNode n6 = new mNode("F",0);
mNode n7 = new mNode("G",0);
mNode n8 = new mNode("H",0);
mNode n9 = new mNode("I",0);
mNode n10 = new mNode("J",0);
mNode n11 = new mNode("K",0);
mNode n12 = new mNode("L",0);
mNode n13 = new mNode("M",0);
mNode n14 = new mNode("N",0);
mNode n15 = new mNode("O",0);
mNode n16 = new mNode("P",0);
mNode n17 = new mNode("Q",0);
mNode n18 = new mNode("R",0);
mNode n19 = new mNode("S",0);
mNode n20 = new mNode("T",0);
mNode n21 = new mNode("U",0);
mNode n22 = new mNode("V",0);
n1.adjacencies = new mEdge[]{//A
new mEdge(n2,3),
new mEdge(n22,7)
};
n2.adjacencies = new mEdge[]{//B
new mEdge(n3,6),
new mEdge(n4,7),
new mEdge(n1,3)
};
n3.adjacencies = new mEdge[]{//C
new mEdge(n4,5),
new mEdge(n2,6)
};
n4.adjacencies = new mEdge[]{//D
new mEdge(n5,11),
new mEdge(n3,5),
new mEdge(n2,7)
};
n5.adjacencies = new mEdge[]{//E
new mEdge(n6,3),
new mEdge(n4,11)
};
n6.adjacencies = new mEdge[]{//F
new mEdge(n7,4),
new mEdge(n9,3),
new mEdge(n5,3)
};
n7.adjacencies = new mEdge[]{//G
new mEdge(n8,4),
new mEdge(n6,4)
};
n8.adjacencies = new mEdge[]{//H
new mEdge(n10,3),
new mEdge(n11,3),
new mEdge(n7,4)
};
n9.adjacencies = new mEdge[]{//I
new mEdge(n10,2),
new mEdge(n13,1),
new mEdge(n6,3)
};
n10.adjacencies = new mEdge[]{//J
new mEdge(n11,2),
new mEdge(n13,1),
new mEdge(n8,3),
new mEdge(n9,2)
};
n11.adjacencies = new mEdge[]{//K
new mEdge(n12,1),
new mEdge(n8,3),
new mEdge(n10,2)
};
n12.adjacencies = new mEdge[]{//L
new mEdge(n11,1),
};
n13.adjacencies = new mEdge[]{//M
new mEdge(n14,6),
new mEdge(n10,1),
new mEdge(n9,1)
};
n14.adjacencies = new mEdge[]{//N
new mEdge(n15,14),
new mEdge(n18,10),
new mEdge(n13,6)
};
n15.adjacencies = new mEdge[]{//O
new mEdge(n16,2),
new mEdge(n17,6),
new mEdge(n14,14)
};
n16.adjacencies = new mEdge[]{//P
new mEdge(n15,2)
};
n17.adjacencies = new mEdge[]{//Q
new mEdge(n15,6),
new mEdge(n18,9),
};
n18.adjacencies = new mEdge[]{//R
new mEdge(n17,9),
new mEdge(n19,12),
new mEdge(n14,10)
};
n19.adjacencies = new mEdge[]{//S
new mEdge(n20,6),
new mEdge(n22,6),
new mEdge(n18,12)
};
n20.adjacencies = new mEdge[]{//T
new mEdge(n21,5),
new mEdge(n19,6)
};
n21.adjacencies = new mEdge[]{//U
new mEdge(n22,5),
new mEdge(n20,5)
};
n22.adjacencies = new mEdge[]{//V
new mEdge(n1,7),
new mEdge(n19,6),
new mEdge(n21,5)
};
//mNode SRC=n12;
//mNode DST=n4;
mNode SRC=n4;
if(kodenode1A.equals("A")){SRC=n12;}
else if(kodenode1A.equals("B")){SRC=n2;}
else if(kodenode1A.equals("C")){SRC=n3;}
else if(kodenode1A.equals("D")){SRC=n4;}
else if(kodenode1A.equals("E")){SRC=n5;}
else if(kodenode1A.equals("F")){SRC=n6;}
else if(kodenode1A.equals("G")){SRC=n7;}
else if(kodenode1A.equals("H")){SRC=n8;}
else if(kodenode1A.equals("I")){SRC=n9;}
else if(kodenode1A.equals("J")){SRC=n10;}
else if(kodenode1A.equals("K")){SRC=n11;}
else if(kodenode1A.equals("L")){SRC=n12;}
else if(kodenode1A.equals("M")){SRC=n13;}
else if(kodenode1A.equals("N")){SRC=n14;}
else if(kodenode1A.equals("O")){SRC=n15;}
else if(kodenode1A.equals("P")){SRC=n16;}
else if(kodenode1A.equals("Q")){SRC=n17;}
else if(kodenode1A.equals("R")){SRC=n18;}
else if(kodenode1A.equals("S")){SRC=n19;}
else if(kodenode1A.equals("T")){SRC=n20;}
else if(kodenode1A.equals("U")){SRC=n21;}
else if(kodenode1A.equals("V")){SRC=n22;}
mNode DST=n4;
if(kodenode1B.equals("A")){DST=n1;}
else if(kodenode1B.equals("B")){DST=n2;}
else if(kodenode1B.equals("C")){DST=n3;}
else if(kodenode1B.equals("D")){DST=n4;}
else if(kodenode1B.equals("E")){DST=n5;}
else if(kodenode1B.equals("F")){DST=n6;}
else if(kodenode1B.equals("G")){DST=n7;}
else if(kodenode1B.equals("H")){DST=n8;}
else if(kodenode1B.equals("I")){DST=n9;}
else if(kodenode1B.equals("J")){DST=n10;}
else if(kodenode1B.equals("K")){DST=n11;}
else if(kodenode1B.equals("L")){DST=n12;}
else if(kodenode1B.equals("M")){DST=n13;}
else if(kodenode1B.equals("N")){DST=n14;}
else if(kodenode1B.equals("O")){DST=n15;}
else if(kodenode1B.equals("P")){DST=n16;}
else if(kodenode1B.equals("Q")){DST=n17;}
else if(kodenode1B.equals("R")){DST=n18;}
else if(kodenode1B.equals("S")){DST=n19;}
else if(kodenode1B.equals("T")){DST=n20;}
else if(kodenode1B.equals("U")){DST=n21;}
else if(kodenode1B.equals("V")){DST=n22;}
//==========================================
AstarSearch(SRC,DST);
List<mNode> path = printPath(DST);
cetak("path="+path);
String hasil=String.valueOf(path);
hasil=hasil.replaceAll(", ", "");
hasil=hasil.substring(1,hasil.length()-1);
cetak("hasil="+hasil);
//===================================LKJFID
String[]AR=hasil.split("");
int p=AR.length;
String gabRute=myPosisi+"->";
String gabKode="GPS->";
double totalKM=0;
String mrute="https://www.google.co.id/maps/dir/"+myLati+","+myLongi;
for(int i=0;i<p;i++){
String KODE=AR[i];
for(int ii=0;ii<jd;ii++){
if(KODE.equalsIgnoreCase(arKode[ii])){
mrute+="/"+String.valueOf(arLati[ii])+","+String.valueOf(arLongi[ii]);
gabRute+=arNama[ii]+"->";
gabKode+=arKode[ii]+"->";
break;
}
}
if(i>0 && i<p-1){
String aw=AR[i-1];
String ah=AR[i];
int index1=getIndex(aw);
int index2=getIndex(ah);
double lat1=arLati[index1];
double lon1=arLongi[index1];
double lat2=arLati[index2];
double lon2=arLongi[index2];
double jrk=getJarak(lat1,lon1,lat2,lon2);
totalKM=totalKM+jrk;
String gablocal=aw+"-"+ah+"="+String.valueOf(jrk)+" m";
cetak("LOCAL="+gablocal);
}
}//i
gabKode+="DST";
gabRute+=myPosisi2;
cetak("MRUTE:"+hasil);;
cetak("MRUTE:"+gabKode);
cetak("MRUTE:"+gabRute);
cetak("MRUTE:"+mrute);
cetak("MKM:"+String.valueOf(totalKM));
}
public static List<mNode> printPath(mNode target){
List<mNode> path = new ArrayList<mNode>();
for(mNode node = target; node!=null; node = node.parent){
path.add(node);
}
Collections.reverse(path);
return path;
}
public static void AstarSearch(mNode source, mNode goal){
Set<mNode> explored = new HashSet<mNode>();
PriorityQueue<mNode> queue = new PriorityQueue<mNode>(50,new Comparator<mNode>(){//20
public int compare(mNode i, mNode j){
if(i.f_scores > j.f_scores){
return 1;
}
else if (i.f_scores < j.f_scores){
return -1;
}
else{return 0;}
}
}
);
source.g_scores = 0;
queue.add(source);
boolean found = false;
while((!queue.isEmpty())&&(!found)){
mNode current = queue.poll();
explored.add(current);
if(current.value.equals(goal.value)){
found = true;
}
for(mEdge e : current.adjacencies){
mNode child = e.target;
double cost = e.cost;
double temp_g_scores = current.g_scores + cost;
double temp_f_scores = temp_g_scores + child.h_scores;
if((explored.contains(child)) &&
(temp_f_scores >= child.f_scores)){
continue;
}
else if((!queue.contains(child)) ||
(temp_f_scores < child.f_scores)){
child.parent = current;
child.g_scores = temp_g_scores;
child.f_scores = temp_f_scores;
if(queue.contains(child)){
queue.remove(child);
}
queue.add(child);
}
}
}
}
void cetak(String path){
System.out.println("Path: " + path);
}
void cekJarak(String aw,String ah){
int index1=getIndex(aw);
int index2=getIndex(ah);
double lat1=arLati[index1];
double lon1=arLongi[index1];
double lat2=arLati[index2];
double lon2=arLongi[index2];
double jrk=getJarak(lat1,lon1,lat2,lon2);
String gab=aw+"-"+ah+"="+String.valueOf(jrk)+" KM";
cetak(gab);
}
int getIndex(String ch){
int index=0;
for(int i=0;i<arKode.length;i++){
if(ch.equals(arKode[i])){index=i;break;}
}
return index;
}
void init(){
jd=22;
arKode = new String[jd];
arNama = new String[jd];
arLati = new double[jd];
arLongi = new double[jd];
arJarakA = new double[jd];
arJarakB = new double[jd];
arKode[2]="A";
arNama[2]="Bondo Kodi";
arLati[2]=-9.59394;
arLongi[2]=118.99406;
arKode[1]="B";
arNama[1]="Kodi";
arLati[1]=-9.56528;
arLongi[1]=119.00009;
arKode[8]="C";
arNama[8]="waikasaha";
arLati[8]=-9.51043;
arLongi[8]=118.98258;
arKode[0]="D";
arNama[0]="Kodi Utara";
arLati[0]=-9.50669;
arLongi[0]=119.03495;
arKode[9]="E";
arNama[9]="Marapati";
arLati[9]=-9.44531;
arLongi[9]=119.11860;
arKode[10]="F";
arNama[10]="Kodim";
arLati[10]=-9.43406;
arLongi[10]=119.17894;
arKode[11]="G";
arNama[11]="Kantor daerah";
arLati[11]=-9.39273;
arLongi[11]=119.18276;
arKode[12]="H";
arNama[12]="Waikelo";
arLati[12]=-9.40577;
arLongi[12]=119.22439;
arKode[15]="I";
arNama[15]="Weelonda";
arLati[15]=-9.43802;
arLongi[15]=119.21474;
arKode[13]="J";
arNama[13]="Sapurata";
arLati[13]=-9.42961;
arLongi[13]=119.23881;
arKode[14]="K";
arNama[14]="Loura";
arLati[14]=-9.41872;
arLongi[14]=119.25647;
arKode[17]="L";
arNama[17]="Weepangali";
arLati[17]=-9.41484;
arLongi[17]=119.26739;
arKode[16]="M";
arNama[16]="Weetabula";
arLati[16]=-9.44253;
arLongi[16]=119.23177;
arKode[18]="N";
arNama[18]="Waimangura";
arLati[18]=-9.50245;
arLongi[18]=119.22644;
arKode[20]="O";
arNama[20]="Wewewa";
arLati[20]=-9.58223;
arLongi[20]=119.32829;
arKode[21]="P";
arNama[21]="Tematana";
arLati[21]=-9.59226;
arLongi[21]=119.35111;
arKode[19]="Q";
arNama[19]="Padaewata";
arLati[19]=-9.62618;
arLongi[19]=119.29358;
arKode[7]="R";
arNama[7]="Rita";
arLati[7]=-9.59764;
arLongi[7]=119.21028;
arKode[5]="S";
arNama[5]="Pahala";
arLati[5]=-9.63841;
arLongi[5]=119.10660;
arKode[6]="T";
arNama[6]="Kahale";
arLati[6]=-9.69377;
arLongi[6]=119.10356;
arKode[4]="U";
arNama[4]="Weekambala";
arLati[4]=-9.67859;
arLongi[4]=119.06037;
arKode[3]="V";
arNama[3]="Waiha";
arLati[3]=-9.63437;
arLongi[3]=119.04483;
}
public static double getJarak(double lat1, double lng1, double lat2, double lng2) {
double earthRadius = 3958.75;
double dLat = Math.toRadians(lat2-lat1);
double dLng = Math.toRadians(lng2-lng1);
double a = Math.sin(dLat/2) * Math.sin(dLat/2) +
Math.cos(Math.toRadians(lat1)) * Math.cos(Math.toRadians(lat2)) *
Math.sin(dLng/2) * Math.sin(dLng/2);
double c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a));
double dist = earthRadius * c;
int meterConversion = 1609;
double myjr=dist * meterConversion;
return Math.floor(myjr/1000);
}
}
class mNode{
public final String value;
public double g_scores;
public final double h_scores;
public double f_scores = 0;
public mEdge[] adjacencies;
public mNode parent;
public mNode(String val, double hVal){
value = val;
h_scores = hVal;
}
public String toString(){
return value;
}
}
class mEdge{
public final double cost;
public final mNode target;
public mEdge(mNode targetmNode, double costVal){
target = targetmNode;
cost = costVal;
}
}
Tidak ada komentar:
Posting Komentar