Jump to content
joao.palma

Caminho mais curto com paragem em varias cidades

Recommended Posts

joao.palma

Boas, estou à procura do melhor algoritmo para encontrar o melhor caminho, começando na cidade A, para a cidade B e passando por outras cidades.

Exemplo ir do porto a lisboa mas parar em espinho, aveiro, coimbra, figueira da foz e santarem.

Alguém sabe de algum algoritmo?

O Dijkstra obtem todos os melhores caminho do ponto A para os outros pontos.

Grafo:

CREATE TABLE CITIES
(
ID_CITY INTEGER PRIMARY KEY,
DESIGNATION VARCHAR(50)
);
CREATE TABLE LINK
(
ID_LINK INTEGER PRIMARY KEY,
CITY_1 INTEGER,
FOREIGN KEY (CITY_1) REFERENCES CITIES(ID_CITY),
CITY_2 INTEGER,
FOREIGN KEY (CITY_2) REFERENCES CITIES(ID_CITY),
DISTANCE FLOAT
);

Edited by brunoais

Share this post


Link to post
Share on other sites
KTachyon

Existe o A*. Só precisas de uma boa heurística.

EDIT: Se tiveres dificuldade em encontrar, pesquisa por "A star".

Edited by KTachyon

“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.”

-- Tony Hoare

Share this post


Link to post
Share on other sites
joao.palma

Existe o A*. Só precisas de uma boa heurística.

EDIT: Se tiveres dificuldade em encontrar, pesquisa por "A star".

O A* não dá porque só encontra o caminho da Cidade A para a cidade B... e eu quero que vá da cidade A para a cidade B passando por C, F e G.

Pelo que encontrei até agora só o TSP (http://en.wikipedia.org/wiki/Travelling_salesman_problem) é que se encaixa mais.. o principal problema deste é que começa e acaba no mesmo ponto...

Outro problema que estou a ter é na implementação deste algoritmo é arranjar um que funcione em PL/SQL ou arranjar um noutra linguagem para adaptar depois!

Edited by joao.palma

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.