Simple AI Problem Solving for Shortest Path   Leave a comment

#ifndef __AI_BASED_PROBLEM_SOLVING_h__
#define __AI_BASED_PROBLEM_SOLVING_h__

#pragma warning(disable: 4786)
#include <tchar.h>

#include <set>
#include <map>
#include <list>

#include <functional>
#include <string>

#include <stack>

#include <algorithm>

#include <iostream>

#include <iomanip>

using namespace std;
#ifdef _UNICODE
	typedef basic_string	__tstring;
#else
	typedef basic_string		__tstring;
#endif

typedef struct __tagCITY_CONNECTIONS
{
	__tstring connection;
	__tstring from;
	__tstring to;
	double distance;
	__tagCITY_CONNECTIONS()
	{
		distance = 0;
	}

	//used for searches.
	__tagCITY_CONNECTIONS(__tstring __from, __tstring __to) : 
					from(__from), 
					to(__to)
					{
						connection =  __from;
						connection += _T(".");
						connection += __to;
					}

	__tagCITY_CONNECTIONS(__tstring __from, __tstring __to, double __dist) : 
					from(__from), 
					to(__to), 
					distance(__dist)
					{
						connection =  __from;
						connection += _T(".");
						connection += __to;
					}
	__tagCITY_CONNECTIONS(const __tagCITY_CONNECTIONS& city_conn)
	{
		connection	= city_conn.connection;
		from		= city_conn.from;
		to			= city_conn.to;
		distance	= city_conn.distance;
	}
	__tagCITY_CONNECTIONS& operator=(const __tagCITY_CONNECTIONS& city_conn){
		if(this!=&city_conn)
		{
			connection	= city_conn.connection;
			from		= city_conn.from;
			to			= city_conn.to;
			distance	= city_conn.distance;
		}
		return *this;
	}

} CITY_CONNECTIONS, *LPCITY_CONNECTIONS;

bool operator<(const __tagCITY_CONNECTIONS& cty1, const __tagCITY_CONNECTIONS& cty2){
	return (_tcscmp(cty1.connection.c_str(), cty2.connection.c_str()) (const __tagCITY_CONNECTIONS& cty1, const __tagCITY_CONNECTIONS& cty2){
	return (_tcscmp(cty1.connection.c_str(), cty2.connection.c_str()) > 0);
}

bool operator==(const __tagCITY_CONNECTIONS& cty1, const __tagCITY_CONNECTIONS& cty2){
	return (_tcscmp(cty1.connection.c_str(), cty2.connection.c_str()) == 0);
}

bool operator!=(const __tagCITY_CONNECTIONS& cty1, const __tagCITY_CONNECTIONS& cty2){
	return !(cty1==cty2);
}

typedef struct __tagFLIGHT_INFO
{
	stack nav_path;
} FLIGHT_INFO, *LPFLIGHT_INFO;

typedef struct __tagROUTE_NODE
{
	CITY_CONNECTIONS city_conn;
	__tstring city;
	__tagROUTE_NODE(){}
	__tagROUTE_NODE(const __tagROUTE_NODE& node)
	{
		city_conn = node.city_conn;
		city	  = node.city;
		targetRoutes.clear();
		copy(node.targetRoutes.begin(), node.targetRoutes.end(), 
			inserter(targetRoutes, targetRoutes.begin()));
	}
	__tagROUTE_NODE& operator=(const __tagROUTE_NODE& node)
	{
		if(this!=&node){
			city_conn = node.city_conn;
			city	  = node.city;
			targetRoutes.clear();
			copy(node.targetRoutes.begin(), node.targetRoutes.end(), 
				inserter(targetRoutes, targetRoutes.begin()));
		}
		return *this;
	}

	set targetRoutes;
}ROUTE_NODE, *LPROUTE_NODE;

bool operator<(const __tagROUTE_NODE& n1, const __tagROUTE_NODE& n2){
	return n1.city_conn.distance (const __tagROUTE_NODE& n1, const __tagROUTE_NODE& n2){
	return n1.city_conn.distance > n2.city_conn.distance;
}

bool operator==(const __tagROUTE_NODE& n1, const __tagROUTE_NODE& n2){
	return n1.city_conn.distance == n2.city_conn.distance;
}

bool operator!=(const __tagROUTE_NODE& n1, const __tagROUTE_NODE& n2){
	return n1.city_conn.distance != n2.city_conn.distance;
}

class SearchEngine;

class FlightDatabase
{
	FlightDatabase(const FlightDatabase&);
	FlightDatabase& operator=(const FlightDatabase&);
public:
	FlightDatabase(){}
	~FlightDatabase(){}
	void Add(__tstring from, __tstring to, double dist_in_miles){
		pair<set::iterator, bool> flight_inserted = 
												city_flights.insert(CITY_CONNECTIONS(from, to, dist_in_miles));
		 if(!flight_inserted.second){
			cout << _T("duplicated!") << endl;
		 }
	}
	void ShowList(){
		for_each(city_flights.begin(), city_flights.end(), DisplayFlight);
	}
	static void DisplayFlight(const CITY_CONNECTIONS& cc){
		cout << cc.from << _T(" to ") << cc.to << endl;
	}
private:
	friend class SearchEngine;
	set city_flights;
};

class SearchEngine
{
	SearchEngine(const SearchEngine&);
	SearchEngine& operator=(const SearchEngine&);
public:
	SearchEngine(const FlightDatabase& fdb){
		bNewRouteFound = false;
		m_pFlightDB = const_cast(&fdb);
	}
	~SearchEngine()
	{
		PurgeChildNodes(root);
	}
public:
	void ShowCompleteRoute(LPFLIGHT_INFO pfi)
	{
		if(pfi)
		{			
			double total_dist = 0;
			while(!pfi->nav_path.empty())
			{
				CITY_CONNECTIONS &cc = pfi->nav_path.top();
				cout << _T("from ") << cc.from
					 << _T(" to ") << cc.to <nav_path.pop();
			}
			cout.precision(2);
			cout << _T("total distance between cities :") << fixed << total_dist << _T(" miles.") << endl;
		}
	}

	bool Match(__tstring __from, __tstring __to, CITY_CONNECTIONS& cc){
		set::iterator flight = m_pFlightDB->city_flights.find(CITY_CONNECTIONS(__from, __to));
		if(flight!=m_pFlightDB->city_flights.end())
		{
			cc = *flight;
			return true;
		}
		return false;
	}

	bool FindFlightSource(__tstring __from, CITY_CONNECTIONS& cc)
	{
		set::iterator flight_source = m_pFlightDB->city_flights.begin();
		while(flight_source != m_pFlightDB->city_flights.end()){
			if(__from==flight_source->from){
				cc = *flight_source;
				return true;
			}
			flight_source++;
		}
		return false;
	}

	bool FindRoute(__tstring __from, __tstring __to, LPFLIGHT_INFO* pfi)
	{
		if(!pfi) return false;

		*pfi = NULL;
		CITY_CONNECTIONS cc;
		if(Match(__from, __to, cc)){
			search_path.push(cc);	
			bNewRouteFound = true;
		}

		if(bNewRouteFound){
			*pfi = new FLIGHT_INFO;
			while(!search_path.empty()){
				(*pfi)->nav_path.push(search_path.top());
				search_path.pop();
			}
			bNewRouteFound = false;
			//register known route before return...
			return true;
		}

		//get a flight with at least the source from
		if(FindFlightSource(__from, cc)){
			search_path.push(CITY_CONNECTIONS(cc));
			return FindRoute(cc.to, __to, pfi);
		}
		return false;
	}

	void FindRoutes(__tstring __from, __tstring __to)
	{		
		root.city = __from;
		PurgeChildNodes(root);
		if(BuildRoutesTree(__from, root)){
			//display the tree of nodes...
			DisplayNodes(root, 1);
		}
	}

	void DisplayNodes(ROUTE_NODE& node, int level){
		int l = level;
		do{
			cout <0);
		cout.precision(2);
		cout << _T("city: ") << node.city << _T(" ") << fixed << node.city_conn.distance << _T(" miles.") << endl;
		level++;
		set::iterator it = node.targetRoutes.begin();
		while(it != node.targetRoutes.end()){			
			LPROUTE_NODE pnode = *it++;
			DisplayNodes(*pnode, level);
		}
		cout <city_flights.size()==0)
			return false;				
		AddCityNodes(__from, target);
		set::iterator it = target.targetRoutes.begin();
		while(it != target.targetRoutes.end()){
			LPROUTE_NODE pnode = *it++;
			BuildRoutesTree(pnode->city_conn.to, *pnode);
		}
		return true;
	}
private:
	void AddCityNodes(__tstring __from, ROUTE_NODE& addto)
	{
		set::iterator flight_source = m_pFlightDB->city_flights.begin();
		while(flight_source != m_pFlightDB->city_flights.end()){
			if(__from==flight_source->from)
			{
				while(flight_source != m_pFlightDB->city_flights.end() && flight_source->from==__from){
					LPROUTE_NODE targetRoute = new ROUTE_NODE;
					targetRoute->city_conn	= *flight_source;
					targetRoute->city		= flight_source->to;
					//add as nodes for parent...
					addto.targetRoutes.insert(targetRoute);				
					flight_source++;
				}
				break;
			}
			flight_source++;
		}
	}
	void PurgeChildNodes(ROUTE_NODE& target){
		set::iterator it = target.targetRoutes.begin();
		while(it != target.targetRoutes.end()){
			LPROUTE_NODE pnode = *it++;
			PurgeChildNodes(*pnode);
			delete pnode;
		}
		target.targetRoutes.clear();
	}
	void PurgeChildNodes()
	{
		PurgeChildNodes(root);
	}
private:
	FlightDatabase* m_pFlightDB;
	stack search_path;
	bool bNewRouteFound;	
	ROUTE_NODE root;
}; 

#endif  //__AI_BASED_PROBLEM_SOLVING_h__
Advertisements

Posted February 2, 2013 by hmarzan

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: