Almost TSP!! : Travelling Salesman Problem Solution through PL/SQL
Hi!!!!
/* PROBLEM STATEMENT
Here, the salesman is given the distance chart by his/her manager based on which
(s)he has to cover all the cities in the distance chart but ensure that (s)he
covers the MINIMUM DISTANCE. For better text, read http://en.wikipedia.org/wiki/Travelling_salesman_problem.
*/
/
drop table salesmans_scrambled_dist_chart;
create table salesmans_scrambled_dist_chart
(
source varchar2(5),
destination varchar2(5),
distance number(5,0)
);
truncate table salesmans_scrambled_dist_chart;
insert into salesmans_scrambled_dist_chart values ('-AGR-','-DEL-',250);
insert into salesmans_scrambled_dist_chart values ('-AGR-','-PTN-',700);
insert into salesmans_scrambled_dist_chart values ('-AGR-','-GYA-',800);
insert into salesmans_scrambled_dist_chart values ('-AGR-','-ALD-',300);
insert into salesmans_scrambled_dist_chart values ('-GYA-','-ALD-',500);
insert into salesmans_scrambled_dist_chart values ('-ALD-','-PTN-',333);
insert into salesmans_scrambled_dist_chart values ('-ALD-','-DEL-',601);
insert into salesmans_scrambled_dist_chart values ('-GYA-','-PTN-',100);
insert into salesmans_scrambled_dist_chart values ('-PTN-','-DEL-',1050);
insert into salesmans_scrambled_dist_chart values ('-DEL-','-GYA-',1100);
commit;
create or replace view v_distance_chart as
select distinct
source,
destination,
distance
FROM
(
SELECT
source,
destination,
distance
FROM
salesmans_scrambled_dist_chart
UNION ALL
SELECT
destination AS source,
source AS destination,
distance
FROM
salesmans_scrambled_dist_chart);
/
create or replace view v_all_cities as
select
city,
rownum as sno
from
(select distinct
source as city
from
v_distance_chart);
/
drop table all_cities;
create table all_cities
(
sno number(2,0),
city varchar2(5)
);
truncate table all_cities;
insert into all_cities(sno, city) select sno, city from v_all_cities;
commit;
/
create or replace package pkg_salesman_scramble is
procedure scramble_cities;
function get_sql_city_sequence return varchar2;
end pkg_salesman_scramble;
/
create or replace package body pkg_salesman_scramble is
procedure scramble_cities is
v_retval number(2,0);
begin
dbms_output.put_line('uninplemented!!!');
end scramble_cities;
function get_sql_city_sequence return varchar2 is
v_sql_stmt varchar2(4000);
v_sql_col1 varchar2(1000);
v_sql_col2 varchar2(1000);
v_sql_tbl varchar2(500);
v_sql_where varchar2(1500);
v_no_of_elements number(2,0);
v_index number(2,0);
v_inner_index number(2,0);
v_bool number(1,0);
v_pipe varchar2(4);
v_add varchar2(4);
v_comma varchar2(3);
v_and varchar2(5);
begin
v_bool := 0;
select count(*) into v_no_of_elements from all_cities;
v_pipe := '';
v_add := '';
v_comma := '';
v_and := '';
for v_index in 1..v_no_of_elements
loop
--if v_index = v_no_of_elements
--then
-- v_index_X := 1;
--else
-- v_index_X := v_index + 1;
--end if;
v_sql_col1 := v_sql_col1 || v_pipe || 'nvl(t' || v_index || '.CITY,'''')';
if v_index > 1 then
v_sql_col2 := v_sql_col2 || v_add || 'distance_between_cities(t' || v_index || '.city, t' || to_char(v_index - 1) || '.city)';
else
v_sql_col2 := 0;
end if;
v_sql_tbl := v_sql_tbl || v_comma || 'all_cities t' || v_index;
v_inner_index := v_index + 1;
for v_inner_index in v_index + 1 .. v_no_of_elements
loop
if v_bool = 1 then
v_pipe := ' || ';
v_add := ' + ';
v_comma := ' , ';
v_and := ' AND ';
end if;
v_sql_where := v_sql_where || v_and || ' t'|| v_index ||'.SNO != t'|| v_inner_index ||'.SNO ';
v_bool := 1;
end loop;
end loop;
--v_sql_stmt := 'select CITY as combinations from scrambler_2011 where sno != 0 union all ';
v_sql_stmt := v_sql_stmt ||' select ' || v_sql_col1 ||' as route, ' || v_sql_col2 ||' as distance_to_be_covered FROM ' || v_sql_tbl || ' WHERE ' || v_sql_where || ' order by distance_to_be_covered';
return(v_sql_stmt);
end get_sql_city_sequence;
end pkg_salesman_scramble;
/
create or replace function distance_between_cities( v_city1 varchar, v_city2 varchar) return number is
v_retval number(5,0);
begin
select
distance into v_retval
from v_distance_chart
where
source = v_city1
and destination = v_city2;
return v_retval;
end distance_between_cities;
/
-- select pkg_salesman_scramble.get_sql_city_sequence() from dual; -- pick the output and execute the dynamic sql, say str_dyn_sql so generated.
-- execute str_dyn_sql

Comments
-
Please login first in order for you to submit comments